论文部分内容阅读
含邻域Dubins旅行商问题(DTSPN)是一个具有挑战性的混合变量优化问题,它源于Dubins车的运动规划,例如轨迹受曲率约束的高速飞行器.本文在对DTSPN的相关研究进行综述的基础上,提出两种混合编码差分进化算法来有效求解DTSPN,这两种算法分别采用完整编码方案和部分编码方案.完整编码差分进化算法在整个解空间中搜索最优的Dubins路径,有利于充分探索搜索空间.通过对Dubins车在相邻两点间移动时的终端朝向进行松弛,本文提出一种部分编码差分进化算法,在解的质量和计算时间方面实现了较好的权衡.比较性计算实验包含两种差分进化算法以及现有文献中的两种先进DTSPN算法,实验结果表明基于终端朝向松弛和部分编码的差分进化算法能够以较小的计算代价得到DTSPN的高质量解,明显优于其他算法.
The Dubins Traveling Salesman Problem with Neighborhood (DTSPN) is a challenging hybrid variable optimization problem that comes from the motion planning of Dubins vehicles, such as high-speed aircraft with trajectory constrained by curvature.This article is based on a review of related studies on DTSPN , Two hybrid encoding differential evolution algorithms are proposed to solve DTSPN effectively, and the two algorithms adopt full encoding scheme and partial encoding scheme, respectively.The complete encoding differential evolution algorithm searches for the optimal Dubins path in the entire solution space, which is beneficial to full exploration Search space.By relaxation of the terminal orientation of the Dubins car moving between two adjacent points, a partial differential coding algorithm is proposed in this paper to achieve a better trade-off between the quality of the solution and the computing time.Comparison experiments Including two kinds of differential evolution algorithms and two kinds of advanced DTSPN algorithms in the existing literature. The experimental results show that the differential evolution algorithm based on terminal-oriented relaxation and partial coding can obtain the high-quality solution of DTSPN with a little computational cost, which is obviously better than the other algorithm.