一种基于蚁群算法的TSP问题分段求解算法  

An Ant Colony Algorithm Based Partition Algorithm for TSP

作　　者：吴斌[1] 史忠植[1] 

机构地区：[1]中国科学院计算技术研究所智能信息处理开放实验室,北京100080

出　　处：《计算机学报》2001年第12期1328-1333,共6页Chinese Journal of Computers

摘　　要：群居性昆虫行为的研究为计算机科学家提供了设计分布式控制和优化算法的有力方法 .对以蚁群算法为代表的群集智能的研究已经逐渐成为一个研究热点 .该文首先在蚁群算法的基础上提出了相遇算法 ,提高了蚁群算法蚂蚁一次周游的质量 ,然后将相遇算法与采用并行策略的分段算法相结合 ,提出一种基于蚁群算法的 TSP问题分段求解算法 .实验结果表明该算法有较好的有效性 .Optimization algorithms inspired by models of co-operative food retrieval in ants have been unexpectedly successful and become known in recent years as Ant Colony Optimization (ACO).As a novel computational approach, swarm intelligence systems such as ant system have become a hot research domain. This paper proposes a meeting algorithm and a partition algorithm for TSP based on typical ant algorithms. The meeting algorithm improves the ant touring quality, it provides good initial touring results for local optimization on the condition of low iteration times. Combining with a simple parallelization strategy--the partition algorithm, this paper gets some good experiment results on Traveling Salesman Problems.The main idea of meeting algorithm is that there are two ants in a touring instead of one ant in typical ant algorithms. The two ants start a touring from a same city, and choose cities from different directions. By sharing a same tabu list, they meet at the middle of a touring. Experiment results show the two-ant touring is slightly shorter than the one-ant touring. Based on the shorter touring by two ants on the condition of low iteration times, a parallelization strategy is developed. It is the partition algorithm. The whole path is partitioned into several segments, then adapted meeting algorithm is again applied on the segments. Three TSP instances are used in this paper. They are ST70(70 cities), KroB150 (from TSPLIB) and CHC144(Chinese 144 cities). Comparing the best results available, 678.59( from the best path provided by TSPLIB), 26130 (from TSPLIB) and 30354.3 (by GA), some experiment results on the synthesized algorithm of meeting algorithm and partition algorithm are rather better. They are 677.1096, 26127.35 and 30354.3.

关 键 词：蚁群算法 组合优化 旅行商问题 并行策略 群集智能 计算机 

分 类 号：O22[理学—运筹学与控制论] TP301.6[理学—数学]