[1]苏劲松 周昌乐 蒋旻隽.一种基于逆转算子的求解TSP问题的改进演化算法[J].计算机技术与发展,2007,(07):94-97.
　SU Jin-song,ZHOU Chang-le,JIANG Min-jun.An Improved Evolutionary Algorithm for Traveling Salesman Problem Based on Inver- Over Operator[J].,2007,(07):94-97.
点击复制

一种基于逆转算子的求解TSP问题的改进演化算法()

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:
期数:
2007年07期
页码:
94-97
栏目:
智能、算法、系统工程
出版日期:
1900-01-01

文章信息/Info

Title:
An Improved Evolutionary Algorithm for Traveling Salesman Problem Based on Inver- Over Operator
文章编号:
1673-629X（2007）07-0094-04
作者:
苏劲松1; 2 周昌乐2 蒋旻隽1; 2
[1]厦门大学软件学院[2]厦门大学人工智能研究所
Author(s):
SU Jin-song;  ZHOU Chang-le;  JIANG Min-jun
[1]Software School of Xiamen University[2] Institute of Artificial Intelligence of Xiamen University
关键词:
旅行商问题; 演化算法; 逆转算子
Keywords:
traveling salesman problem;  evolutionary algorithm;  inver- over operator
分类号:
TP301.6
文献标志码:
A
摘要:
使用逆转算子求解TSP的演化算法具有很强全局搜索能力，在求解TSP问题中显示了巨大的优势。但是，该算法同样存在执行效率低、最终得到的最优个体整体质量不高等缺陷。在对算法和TSP问题进行分析的基础上，对算法进行三方面的改进：就近选择；动态变异概率；基于较优个体的贪婪搜索。实验结果表明：经过改进的算法提高了执行效率，能够改善算法得到的最优个体的整体质量
Abstract:
The evolutionary algorithm using inver - over operator for the traveling salesman problem （TSP） has great ascendancy, because its ability in global searching for optimal individual is powerful. However, it has the some limitations： low executive efficiency and the dissatisfactory average individuals obtained by algorithm. To avoid these limitations, improves the algorithm mentioned above in three aspects： close - by visit method, dynamic mutation probability and greedy search based on preferable individuals. A desirable result is obtained. It is showed by the experiment that the algorithm can be executed with high efficiency and the average quality of the optimal individual of the algorithm is improved

相似文献/References:

[1]段凤玲 李龙澍 曹文婷.具有多态特征和聚类处理的蚁群算法[J].计算机技术与发展,2009,(12):77.
　DUAN Feng-ling,LI Long-shu,CAO Wen-ting.Ant Colony Algorithm with Polymorphism and Clustering Processing[J].,2009,(07):77.
[2]谭伟 李向.微粒群优化算法的研究[J].计算机技术与发展,2009,(03):87.
　TAN Wei,LI Xiang.Research Status and Development of Particle Swarm Optimization[J].,2009,(07):87.
[3]杨益 方潜生 高翠云.求解TSP问题的遗传算法硬件实现[J].计算机技术与发展,2009,(04):54.
　YANG Yi,FANG Qian-sheng,GAO Cui-yun.Implementation of Hardware Based on Genetic Algorithm for Solving TSP Problem[J].,2009,(07):54.
[4]王娟 王建.一种求解TSP问题的改进蚁群算法[J].计算机技术与发展,2008,(12):50.
　WANG Juan,WANG Jian.An Improved Ant Colony Algorithm for Solving TSP Problem[J].,2008,(07):50.
[5]陈文兰 戴树贵.求解旅行商问题的混合蚂蚁算法[J].计算机技术与发展,2007,(07):110.
　CHEN Wen-lan,DAI Shu-gui.A Hybrid Ant Colony Algorithm for Solving Traveling Salesman Problem[J].,2007,(07):110.
[6]孙宪丽 王敏 李颖.求解TSP问题的一种启发式算法[J].计算机技术与发展,2010,(10):70.
　SUN Xian-li,WANG Min,LI Ying.A Heuristic Algorithm to Solve Travelling Salesman Problem[J].,2010,(07):70.
[7]赵玉章 郭文强 冯昊[].基于二点组合算法的旅行商问题应用性能分析[J].计算机技术与发展,2011,(10):137.
　ZHAO Yu-zhang,GUO Wen-qiang,FENG Hao.Performance Analysis of Two Vertices Combination Algorithm in TSP[J].,2011,(07):137.
[8]赵越,徐鑫,赵焱,等.自适应记忆遗传算法研究[J].计算机技术与发展,2014,24(02):63.
　ZHAO Yue[],XU Xin[],ZHAO Yan[],et al.Research on Adaptive Memory Genetic Algorithm[J].,2014,24(07):63.
[9]宗德才[],王康康[]. 旅行商问题中巡回路径的数据结构[J].计算机技术与发展,2014,24(12):72.
　ZONG De-cai[],WANG Kang-kang[]. Data Structure of Tour for Traveling Salesman Problem[J].,2014,24(07):72.
[10]易正俊[],李勇霞[],易校石[].自适应蚁群算法求解最短路径和TSP问题[J].计算机技术与发展,2016,26(12):1.
　YI Zheng-jun[],LI Yong-xia[],YI Xiao-shi[]. Solving of Shortest Path Problem and TSP with Adaptive Ant Colony Algorithm[J].,2016,26(07):1.

备注/Memo

备注/Memo:
苏劲松（1982-），男，福建泉州人，硕士研究生，研究方向为人工智能；周昌乐，教授，博士生导师，CCF会员，主要从事人工智能领域的教学和研究工作
更新日期/Last Update: 1900-01-01