摘要
旅行商问题(Travelling Salesman Problem,TSP)是一个著名的组合优化问题。提出用进化算法求解该问题。算法采用自然编码方式表示个体,设计了一种利用种群的边产生后代个体的新交叉策略。采用随机DoubleBridge变异策略,最后设计了结合2-交换和特殊3-交换的局部搜索算子改善解(个体)的质量。数值模拟实验表明,该算法是有效的。
Travelling Salesman Problem is a famous problem in combinatorial optimization. A novel evolutionary algorithm is proposed to solve TSP in this paper. First, nature coding is used to express an individual; then, a new crossover strategy is designed to generate off spring based on using the edge information in the current population;furthermore, the random doublebridge move mutation is used as the mutation strategy;finally, an effective local search method incorporating 2 -exchange and a special 3 - exchange operator is designed to improve the quality of the solution. The simulation experiment shows that the proposed algorithm is effective.
出处
《现代电子技术》
2007年第22期77-79,81,共4页
Modern Electronics Technique
基金
国家自然科学基金(60374063)
陕西省自然科学基础研究计划项目(2006A12)
关键词
旅行商问题
组合优化
进化算法
局部搜索
travelling salesman problem
combinatorial optimization
evolutionary algorithm
local search
