旅行商问题(TSP)的伪并行遗传算法  

Solving traveling salesman problem(TSP) with pseudo-parallel genetic algorithms

作　　者：刘军[1] 王介生[1] 

机构地区：[1]鞍山科技大学 电子信息与工程学院,辽宁鞍山114044

出　　处：《控制理论与应用》2007年第2期279-282,共4页Control Theory & Applications

基　　金：国家自然科学基金(59977009)

摘　　要：旅行商问题(TSP)是典型的NP完全组合优化问题．本文基于遗传算法求解TSP问题时的独特性,提出一种采用无性繁殖的改进伪并行遗传算法,避免了交叉算子对良好基因模式的破坏;初始种群通过贪婪算法得到并进行预处理,提高算法的收敛速度;伪并行遗传算法中子群体之间的信息交换采用孤岛模型．这些改进措施对降低算法的复杂程度、提高算法的收敛速度和全局搜索能力有重要意义．仿真研究结果表明,该算法的寻优效率较高,有效地克服了标准遗传算法的早熟收敛问题．Traveling salesman problem （TSP） is a typical NP complete combinatorial optimum problem.An improved pseudo-parallel genetic algorithms （IPPGA） is proposed with an asexual reproduction for avoiding crossover operators＇ breach to nice gene patterns. The initial population is produced by greedy algorithm in order to enhance convergence ve- locity. Information exchange between subgroups employs island model in IPPGA. These measures are of great significance on reducing complexities and enhancing convergence velocity, as well as increasing global searching ability of the algorithm. Finally, simulation study of IPPGA demonstrates its capability of strong global search and superiority to SGA and high immunity against premature convergence.

关 键 词：旅行商问题 无性繁殖 伪并行遗传算法 贪婪算法 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]