期刊文献+

一种双近邻表示的演化算法解决TSP

A 2-Adjacency Representation in Evolutionary Algorithm for Traveling Salesman Problems
下载PDF
导出
摘要 用演化算法解决旅行商问题(TSP)时,传统的路径表示方法是非常不适合演化过程处理的。提出了一种双近邻表示法。这种能够将每个路径唯一表示的新的方法提高了演化算子的继承能力。为了提高收敛速度,演化算子中还使用了一种混合的局部搜索。大量的标准测试题的实验结果可以表明该文提出的算法能够全部达到或更优于现存最优解。 When solving Traveling Salesman Problems with evolutionary algorithm, the traditional routing representations were not considerably appropriate for evolutionary processing, and would depress the global efficiency of the performance. A 2- adjacency representation was presented in this paper. The new representation which was exclusive for each routing improved the heritability of genetic operators. A hybrid local search was also applied to genetic operators in order to speed up the convergence. The experimental results showed that the proposed scheme was obviously able to compete with the existing optimal results in many standard benchmark problems, some of them were even better.
作者 黄欢 熊盛武
出处 《武汉理工大学学报》 CAS CSCD 北大核心 2006年第10期93-96,共4页 Journal of Wuhan University of Technology
基金 国家自然科学基金(60572015) 国家973重大基础研究前期研究专项(2004CCA02500)
关键词 旅行商问题 演化算法 路径 双近邻表示 traveling salesman problems evolutionary algorithm routing 2-adjacency representation
  • 相关文献

参考文献10

  • 1Bland R G,Shoallcross D F.Large Traveling Salesman Problems Arising from Experiments in X-ray Crystallography:A Preliminary Report on Computation[J].Operations Research Letters,1989,(8):125-128.
  • 2Brady R M.Optimization Strategies Gleaned from Biological Evolution[J].Nature,1985,(317):804-806.
  • 3Oliver I M,Smith D J,Holland J R C.A Study of Permutation Crossover Operators on TSP[A].Proceedings of the Second International Conference[C].Hillsdale:Lawrence Erlbaum,1987.224-230.
  • 4Wang Yuping,Li Yinghua,Dang Chuangyin.A Novel Globally Convergent Hybrid Evolutionary Algorithm for Traveling Salesman Problems[A].Proceedings of 2004 International Conference on Machine Learning and Cybernetics[C].Shanghai:IEEE,2004.2485-2489.
  • 5Grefenstette J J,Gopal R,Rosmaita B,et al.Genetic Algorithms for the TSP[A].Genetic Algorithms and Their Applications Proceeding of the First International Conference on Genetic Algorithms[C].New Jersey:Lawrence Erlbaum,1985.160-168.
  • 6Lin S,Kernighan B W.An Effective Heuristic Algorithm for the Traveling Salesman Problem[J].Operations Research,1973,(21):498-516.
  • 7Held M,Karp R M.The Traveling Salesman Problem and Minimum Spanning Trees[J].Operation Research,1970,(18):1138-1162.
  • 8Reinelt G.TSPLI--A Traveling Salesman Problem Library[J].ORSA J.Comput,1991,(3):376-384.
  • 9Interdisciplinary Center for Scientific Computing of the Ruprecht-Karls-University of Heidelberg.TSPLIB[EB/OL].http://www.iwr.uni-heidelberg.de/iwr/comopt/soft/TSPLIB95/TSPLIB.html.(1994-04-29)[2005-10-24].
  • 10萧蕴诗,李炳宇,吴启迪.求解TSP问题的模式学习并行蚁群算法[J].控制与决策,2004,19(8):885-888. 被引量:20

二级参考文献5

  • 1Dorigo M, Maniezzo V, Colorni A. The ant system: Optimization by a colony of cooperating agents[J]. IEEE Trans on Systems, Man and Cybernetics - Part B,1996,26(1):29-41.
  • 2Dorigo M, Gambardella L. Ant colony system: A cooperative learning approach to the traveling salesman problem[J]. IEEE Trans on Evolutionary Computation,1997,1(1):53-66.
  • 3Bullnheimer B, Kotsis G, Strauss C. Parallelization strategies for the ant system[R]. Vienna: University of Vienna,1997.
  • 4Thomas Stützle, Holger Hoos. MAX-MIN ant system and local search for the traveling salesman problem[A]. Proc IEEE Int Conf on Evolutionary Computation (ICEC′97)[C]. Indianapolis,1997.309-314.
  • 5康立山 谢云 尤失勇.非数值并行算法(一)[M].北京:科学出版社,1998..

共引文献19

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部