求解旅行商问题的动态邻域差异演化算法改进研究  

Travelling Salesman Problem Solving Dynamic Neighborhood Improvement of Differential Evolution Algorithm

作　　者：刘永军[1] 孔佑琳 

机构地区：[1]石家庄经济学院信息工程学院,石家庄050031 [2]石家庄市赵县人民检察院,石家庄051530

出　　处：《智能计算机与应用》2015年第6期15-17,21,共4页Intelligent Computer and Applications

基　　金：河北省科技厅科技支撑计划项目(14211810D)

摘　　要：旅行商问题(Traveling Saleman Problem,TSP)是一个典型的组合优化问题,针对该问题主要采用动态规划和智能优化等算法。为了有效求解TSP问题,设计了一种带邻域操作的差异演化算法。为了克服差异演化算法容易收敛于局部最优的弱点,通过引入簇和邻域的概念,将种群中的个体归入距离其最近的子种群,用个体的当前邻域极值替换群体的当前最佳。同时,算法在进化过程中动态调整邻域大小。通过在多个TSP问题上的仿真实验表明,该算法在求解TSP问题时鲁棒性强,求解精度高。Traveling Saleman Problem is a classical Combinatorial Optimization Problem. Dynamic design and intelligence optimization are usually used to solve it. In order to overcome the weakness that the differential evolution algorithm converges to a local optimum easily,and by introducing the concept of clusters and neighborhood,the population of individuals are classified as its nearest sub- population groups,and replace the most good with the extreme values of the current individual neighborhood. At the same time,the number of neighborhood is adjust from two to the size of population. Some experiments on classical TSP problem show that this improved DE algorithm is effective and robust to solve TSP and has higher precision.

关 键 词：旅行商问题 差异演化 动态邻域搜索 自适应 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]