引入基因簇求解TSP的遗传算法

计算机科学 ›› 2009, Vol. 36 ›› Issue (6): 248-250.

引入基因簇求解TSP的遗传算法

出版日期:2018-11-16 发布日期:2018-11-16
基金资助:
本文受国家863目标导向项目（2006AA022347）资助.

Online:2018-11-16 Published:2018-11-16

摘要/Abstract

摘要： 在用遗传算法求解TSP时，极易破坏已经发现的较短线路片段，从而使遗传算法的收敛变慢。为了保护较短的线路片段，遗传操作以基因和基因簇为单位进行，优良基因簇可完整地遗传到下一代。在获得第一个近似最优解后，粉碎已发现的基因簇并继续寻优，以期能够获得全局最优解。使用CHN144及TSPLIB中的数据进行试验，找到了CHN144问题的当前最优路径。通过对TSP225的实验获得了最短路径3859，优于目前已经公布的最短路径3916。实验表明，基于基因簇的算法具备3000个城市左右的寻优能力。

关键词: 旅行商问题基因簇遗传算法

Abstract: When a genetic algorithm is used to solve the TSP （Traveling Salesman Problem）, shorter paths found before are accessible to be destroyed, and thus the convergence of the genetic algorithm slows down. To prevent the shorter paths from being destroyed, the

Key words: Traveling salesman problem,Gene cluster,Genetic algorithm

. 引入基因簇求解TSP的遗传算法[J]. 计算机科学, 2009, 36(6): 248-250. https://doi.org/

参考文献

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed