谷文祥，李向涛，王春颖，李国媛，殷明浩

（东北师范大学计算机科学与信息技术学院，吉林 长春 130117）

一种求解TSP问题的混合算法

谷文祥，李向涛，王春颖，李国媛，殷明浩

（东北师范大学计算机科学与信息技术学院，吉林 长春 130117）

结合粒子群算法、蚁群算法、重力搜索算法提出了一种新的混合算法——TSP-GPAA.该算法将粒子群算法和重力搜索算法加入到蚁群算法中，利用粒子群算法的全局搜索能力解决了蚁群算法的初始信息素匮乏的问题，并且重力搜索算法将粒子群算法和蚁群算法参数进行优化，明显提高了蚁群算法的优化性能.实验表明新算法对于解决TSP问题是有效的.

蚁群算法；粒子群算法；重力搜索算法；旅行商问题

0 引言

TSP问题是一个重要的组合优化问题，已经被证明是NP完备的.任何能使该问题的求解得以简化的方法，都会受到高度的评价和关注.虽然目前存在一些可以精确地求解TSP问题的算法，但针对大规模的TSP问题，这些算法往往不能胜任.为了解决这一问题，研究人员提出了多种智能算法来处理TSP问题，目前被广泛使用的有遗传算法［1－3］、人工神经网络方法［4］、粒子群算法［5－7］、模拟退火算法［8］、蚁群算法［9］等.然而，这些算法大多不尽如人意，容易陷入局部极小或收敛过慢等问题.近些年，研究人员发现几种智能算法灵活的组合可以为求解TSP提供更好的启发式信息，并且这类混合算法在处理TSP问题上可以提供更有效的行为和更高的灵活性.鉴于以上……