混合编码差分进化算法求解含邻域Dubins旅行商问题(英文)  

Hybrid encoding based differential evolution algorithms for Dubins traveling salesman problem with neighborhood

作　　者：辛斌[1,2] 陈杰[1,2] 徐冬玲[3] 陈玉旺[3] 

机构地区：[1]北京理工大学自动化学院,北京100081 [2]复杂系统智能控制与决策国家重点实验室,北京100081 [3]曼彻斯特大学商学院认知与决策科学研究中心

出　　处：《控制理论与应用》2014年第7期941-954,共14页Control Theory & Applications

基　　金：supported by the National Natural Science Foundation of China(No.61304215);the Projects of Major International(Regional)Joint Research Program of NSFC(No.61120106010);the Foundation for Innovative Research Groups of the National Natural Science Foundation of China(No.61321002);the Beijing Outstanding Ph.D.Program Mentor(No.20131000704)

摘　　要：含邻域Dubins旅行商问题(DTSPN)是一个具有挑战性的混合变量优化问题,它源于Dubins车的运动规划,例如轨迹受曲率约束的高速飞行器.本文在对DTSPN的相关研究进行综述的基础上,提出两种混合编码差分进化算法来有效求解DTSPN,这两种算法分别采用完整编码方案和部分编码方案.完整编码差分进化算法在整个解空间中搜索最优的Dubins路径,有利于充分探索搜索空间.通过对Dubins车在相邻两点间移动时的终端朝向进行松弛,本文提出一种部分编码差分进化算法,在解的质量和计算时间方面实现了较好的权衡.比较性计算实验包含两种差分进化算法以及现有文献中的两种先进DTSPN算法,实验结果表明基于终端朝向松弛和部分编码的差分进化算法能够以较小的计算代价得到DTSPN的高质量解,明显优于其他算法.The Dubins traveling salesman problem with neighborhood （DTSPN） is a challenging mixed-variable optimization problem,stemming from the motion planning of a Dubins vehicle,e.g.an aircraft moving at a high speed,whose trajectory is restricted by curvature constraints.In this paper,a survey result of DTSPN is firstly provided; then,in order to solve DTSPN efficiently,we propose two hybrid encoding-based differential evolution （DE） algorithms,which adopt complete encoding scheme and partial encoding scheme,respectively.The DE algorithm with complete encoding searches for optimal Dubins tours in the entire solution space,in favor of a sufficient exploration of the search space.By relaxing the terminal heading of a Dubins vehicle when it moves from one point to another,a novel DE with partial encoding is proposed to achieve a better tradeoff between solution quality and computational time.Comparative experiments,involving the two DE algorithms and two state-of-the-art DTSPN algorithms identified in literature,show that the DE based on terminal heading relaxation and partial encoding can find high-quality solutions to DTSPN with lower computation cost,and has remarkable advantages over the other algorithms.

关 键 词：Dubins车 路径规划 曲率约束 含邻域Dubins旅行商问题 差分进化 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] O221[自动化与计算机技术—控制科学与工程]