改进的演化近似算法求解TSP问题  

Improved Evolutionary Approximation Algorithms for TSP

作　　者：杨利英[1] 覃征[1] 贺升平[1] 黄茹[1] 

机构地区：[1]西安交通大学电子与信息工程学院计算机科学技术系,西安710049

出　　处：《微电子学与计算机》2004年第6期126-128,共3页Microelectronics & Computer

基　　金：国防十五预研项目(102010302)

摘　　要：TSP是典型的具有NPC复杂性的组合优化问题。在演化算法的基础上,提出了一种有效求解TSP问题的近似算法IEAA。IEAA采用单性生殖方式,通过保留一组较优个体加速了算法的收敛。详细介绍了的算法的设计和实现,并用于求解CTSP问题,实验结果表明,该算法能有效的解决CTSP问题,且算法性能优于基本演化算法SEA。Traveling Salesman Problem (TSP) is a typical combinatorial optimization problem. It has been proved that TSP is of NPC complexity. Therefore, it has significant meaning to solve this problem. We present a kind of approximation algorithm for TSP based on evolutionary algorithms which is defined as IEAA(Improved Evolutionary Approximation Algorithms).In the evolutionary process, IEAA conserves a group of better individuals instead of the best one in every cycle. Meanwhile, it uses only mutation operator meaning an asexual reproduction and only individuals with better performance have the chance to reproduce. All these characteristics speed up algorithms convergence. We use IEAA to resolve Chinese-TSP and get the encouraging result comparing with simple evolutionary algorithms.

关 键 词：TSP 近似算法 演化算法 CTSP 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]