计算机工程与应用 ›› 2007, Vol. 43 ›› Issue (28): 75-77.

• 学术探讨 • 上一篇    下一篇

基于单亲算子的TSP演化算法

刘宏兵1,2,熊盛武2   

  1. 1.信阳师范学院 计算机系,河南 信阳 464000
    2.武汉理工大学 计算机科学与技术学院,武汉 430070
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2007-10-01 发布日期:2007-10-01
  • 通讯作者: 刘宏兵

Evolutionary algorithms of TSP based on monomer operators

LIU Hong-bing1,2,XIONG Sheng-wu2   

  1. 1.Department of Computer Science,Xinyang Normal University,Xinyang,Henan 464000,China
    2.School of Computer,Wuhan University of Technology,Wuhan 430070,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2007-10-01 Published:2007-10-01
  • Contact: LIU Hong-bing

摘要: 在单亲初始种群上,设计了单点插入、线段插入、路径插入和变异四种算子,构造了基于单亲算子的TSP演化算法。该算法在单个个体上进行演化操作,随机选取单个个体,选择随机长度的路径并顺序地插入其余的任何两结点间形成新路径,对新路径进行变异操作以得到最终的路径。实验结果表明,和简单的TSP遗传算法相比,该算法可得更好的解,且减少了演化时间。

关键词: TSP, 简单遗传算法, 插入, 变异

Abstract: Single-point insertions,line insertion,route insertion and mutation operators designed on the monomer are used to form the evolutionary algorithms based on monomer operators.The algorithms perform the evolutionary operations on the random monomer in which the new routes are obtained by selecting the random sub-routes and then inserting the sub-routes in the remained arbitrary two points,and the final route is obtained by mutating the new route.The experimental results show that the algorithms can not only achieve the better solutions but also reduce the evolutionary time.

Key words: TSP, simple genetic algorithm, insertion, mutation