| 解旅行商问题的一个新进化算法 |
| |
| 引用本文： | 覃锦华,谢作党,王宇平.解旅行商问题的一个新进化算法[J].现代电子技术,2007,30(22):77-79,81. |
| |
| 作者姓名： | 覃锦华 谢作党 王宇平 |
| |
| 作者单位： | 1. 西安电子科技大学理学院,陕西,西安,710071
2. 西安电子科技大学,计算机学院,陕西,西安,710071 |
| |
| 基金项目： | 国家自然科学基金;陕西省自然科学基金 |
| |
| 摘 要： | 旅行商问题(Travelling Salesman Problem,TSP)是一个著名的组合优化问题。提出用进化算法求解该问题。算法采用自然编码方式表示个体,设计了一种利用种群的边产生后代个体的新交叉策略。采用随机DoubleBridge变异策略,最后设计了结合2-交换和特殊3-交换的局部搜索算子改善解(个体)的质量。数值模拟实验表明,该算法是有效的。
|
| 关 键 词： | 旅行商问题 组合优化 进化算法 局部搜索 |
| 文章编号： | 1004-373X（2007）22-077-03 |
| 收稿时间： | 2007-05-23 |
| 修稿时间： | 2007-05-23 |
A Novel Evolutionary Algorithm for Travelling Salesman Problem |
| |
| QIN Jinhua,XIE Zuodang,WANG Yuping.A Novel Evolutionary Algorithm for Travelling Salesman Problem[J].Modern Electronic Technique,2007,30(22):77-79,81. |
| |
| Authors: | QIN Jinhua XIE Zuodang WANG Yuping |
| |
| Abstract: | 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. |
| |
| Keywords: | travelling salesman problem combinatorial optimization evolutionary algorithm local search |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
