蚁群算法在求解TSP问题中的改进研究

王宝生，屈宝存

（辽宁石油化工大学 辽 宁 抚 顺 1 13001）

旅行商问题(Traveling Salesman Problem,TSP)是一个易于描述却难以处理的NP-HARD问题。近年来，它引起了许多学者的广泛关注。旅行商问题不仅具有很重要的理论价值，而且还具有广泛的实际应用价值，如机器人路径规划、电路板设计、城市管道铺设优化、交通运输以及物流配送等领域都可视为TSP问题的具体应用。对于旅行商问题，目前常用的方法有模拟退火算法、遗传算法、神经网络法等。

蚁群优化算法是模拟自然界中真实蚁群的觅食行为而形成的一种模拟进化算法。它是一种新兴的仿生学优化算法，属于元启发算法的一种。它具有采用分布式并行计算机制、易于与其他方法结合、具有较强的鲁棒性等优点，但其搜索时间长、易陷于局部最优解是其最突出的缺点。因此，既要使得蚁群算法的搜素空间尽可能的大，以寻找那些可能存在最优解的解空间，同时，又要充分利用蚂蚁体内当前所有的有效信息，使得蚁群算法搜索的侧重点放在那些可能具有较高适应值的个体所在的区间内，以较大的概率收敛到全局最优解。因此，在“探索”和“利用”之间建立一个平衡点是蚁群算法研究的关键问题之一。

为了克服蚁群算法的这些缺陷，使它的性能更好,研究者们探索了信息素残留因子(1-ρ)、信息启发式因子、期望启发式因子、信息素强度、蚂蚁数目等蚁群算法的影响因素，并进行了改进[1-3]。高尚提出了混沌蚁群算法，采用混沌初始化改善个体质量和利用混沌扰动避免搜素过程陷入局部极值，实验表明该算法提高了计算效率[4]。……