基于受限制候选表的反应蚁群算法求解TSP问题

Solution of TSP problem by using algorithm of reactive ant colony with restricted candidate list

针对蚁群算法求解大规模旅行商问题(TSP)时会出现计算时间长等问题,将反应贪婪随机适应搜索机制引入蚁群算法中,提出了一种基于受限制候选表(RCL)的反应蚁群算法,其中的候选表大小可以随机选取.将蚂蚁要选择的下一点的范围控制在RCL中,避开了许多局部极小点,克服了最近邻居候选表的不足,提高了搜索效率.对大规模TSP问题进行仿真实验的结果表明该算法具有良好的性能.

Aimed at the time-consuming problem that would happened with the solution of massive traveling salesman problem （TSP） by using algorithm of reactive ant colony, a kind of reactive ant colony algorithm based on restricted candidate list （RCL） was proposed by means of introducing a mechanism of greed stochastic adaptive searching into ant colony algorithm. In the algorithm proposed, the dimension of candidate list could be selected stochastically. When the next point that the ant would select was controlled to be within the scope of RCL, a lot of local minimum points could be avoided, the insufficiency of most nearest neighbor candidate list would be overcomed, and the searching efficiency would be improved. It was shown by a simulation test on massive TSP that this algorithm proposed possessed fine performance.