搜索不同TSP最佳路径的多蚁群优化算法  

A Multiple Ant Colonies Optimization Algorithm for Finding Different Optimal Tours in the TSP

作　　者：吴红[1] 王远世[1] 

机构地区：[1]中山大学数学与计算科学学院,广东广州510275

出　　处：《中山大学学报（自然科学版）》2005年第4期13-15,19,共4页Acta Scientiarum Naturalium Universitatis Sunyatseni

基　　金：教育部归国留学人员基金;广东省自然科学基金博士科研启动资助项目(04300594)

摘　　要：提出一种搜索不同TSP最佳路径的多蚁群优化算法。在该算法中,各蚁群中的蚂蚁被其所在蚁群的气味吸引的同时,亦受到其它蚁群气味的排斥。具体表现为:第1个蚁群的蚂蚁不受其它蚁群气味的影响;第2个蚁群只受第一个蚁群的排斥;第3个蚁群只受第1个蚁群和第2个蚁群的排斥,…,最后一个蚁群受其前面每一个蚁群的排斥。该算法通过引入依时间变化的气味蒸发系数,证明了若系统存在不同的最佳路径,则算法中的不同蚁群以概率为1地收敛于不同的最佳路径。A multiple ant colonies optimization algorithm for the TSP is presented. While each ant is attracted by the pheromone of its own colony, there exists repulsion in the colony-level interactions： the first colony is not affected by other colonies; the second colony is only repelled by the first colony; the third colony is only repelled by the first and the second colonies,… Inductively, the final colony is repelled by all the colonies before it. By introducing a timedependent evaporation rate into the algorithm, it is presentedcolonies is gu.amnteed with probability one to converge and findthat if there exist differenta different optimal touroptimal tours, each of the

关 键 词：蚁群优化算法 旅行商问题 网络路由 

分 类 号：O175.24[理学—数学]