一种求解TSP的混合遗传蚁群算法  

Hybrid genetic ant colony algorithm for traveling salesman problem

作　　者：徐金荣[1] 李允[1] 刘海涛[1] 刘攀[2] 

机构地区：[1]西南交通大学信息科学与技术学院,成都610031 [2]西南交通大学CAD中心,成都610031

出　　处：《计算机应用》2008年第8期2084-2087,2112,共5页journal of Computer Applications

基　　金：国家863计划项目(2005AA1Z2060)

摘　　要：结合遗传算法和蚁群算法,提出了一种求解TSP的基于启发式遗传信息的蚁群遗传算法。该算法由蚁群遗传算法和基于启发式遗传信息的蚁群算法两部分组成。蚁群遗传算法将蚁群算法和遗传算法结合起来,提高了遗传算法的种群的多样性;基于启发式遗传信息的蚁群算法是将启发式遗传信息加入到蚁群算法中,防止蚁群算法对信息素过分依赖,缩小最优解的搜索空间。HGI-ACGA算法是将启发式遗传信息加入到蚁群遗传算法中,可以提高蚁群算法的收敛速度和寻优能力。实验结果表明,HGI-ACGA算法在收敛速度和收敛精度上均优于ACGA和ACA算法。A new Heuristic Genetic Information based Ant Colony Genetic Algorithm （HGI-ACGA） to solve Traveling Salesman Problems（TSP） was proposed. HGI-ACGA＇ s two sub-algorithms are Ant Colony Genetic Algorithm（ACGA） and Heuristic Genetic Information based Ant Colony Algorithm（HGI-ACA）. ACGA enhances genetic algorithm＇ s population diversity and reduces the search domain, while HGI-ACA eliminates the creation of invalid tours and also avoids depending on pheromone excessively. A combination of genetic information and pheromone leads to a significant improvement in performance. The strategy of HGI-ACGA algorithm can improve convergence rate and capacity of searching optimal solution. Experimental results show that the proposed algorithm generally exhibits a better solution and a higher rate of convergence for TSP than ACGA and ACA.

关 键 词：遗传算法 蚁群算法 信息素 启发式遗传信息 旅行商问题 

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