用蚁群优化算法求解中国旅行商问题  

Applying Ant Colony Optimizations to Chinese Traveling Salesman Problem

作　　者：燕忠[1] 袁春伟[1] 

机构地区：[1]东南大学生物医学工程系分子与生物分子电子学教育部重点实验室,江苏南京210096

出　　处：《电路与系统学报》2004年第3期122-126,共5页Journal of Circuits and Systems

基　　金：国家自然科学基金重点资助项目(69831010)

摘　　要：中国旅行商问题是一个组合优化问题,是一个NP问题。本文提出用蚁群优化算法去解决,同时提出了两种改进的方法,其中,Ant-F能够增强系统的搜索能力,使系统避免早熟,具有正负反馈的功能,仿真简单,容易理解;而ACS+是在Ant Colony System(ACS)的基础上改进而成,它使系统在演化的后期能够通过适当增大系统区分信息素对比强度的方法,尽快找到最优的解。和其它的几种蚁群优化算法、遗传算法和模拟退火算法相比较,实验表明,ACS+是本文提及的几种算法中最优的一种,它能加快系统收敛的速度,找到问题的最优值。The Chinese Traveling Salesman Problem(CTSP)is one of combinatorial optimization problems, and is a NP. Based on Ant Colony Optimizations (ACOs), two improved versions of ACOs are proposed to solve this problem. One is Ant-F, in which systems search probability is increased to avoid premature. Such system with negative and positive feedback can be simply simulated and easily understood. The other is ACS+, which can be used to speed up systems convergence at the last stage of evolution by means of magnifying the contrast between the intensity of pheromone laid on every edge. The empirical experiments indicate that performance of ACS+ is better when compared with other ACOs, GA(Genetic Algorithm) and Simulated Annealing.

关 键 词：蚂蚁系统 蚁群优化算法 旅行商问题 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]