基于互信息的混合蚁群算法及其在旅行商问题上的应用

Abstract

为了提高蚁群算法的求解性能,从医学图像配准算法的思想出发,提出了一种基于互信息相似度的混合蚁群算法.为了表示最优路径和待配准路径之间的互信息熵,在蚁群算法的概率算子中增加了一个新的相似度影响因子,从而可以增加原算法的全局搜索能力,同时可以加速算法在解空间的搜索速度.将该算法应用在旅行商问题上,根据旅行商问题的特定环境,对混合蚁群算法的算式进行了一定程度的化简,使得算法在解决此类问题时,相应的时间复杂度降低.通过实验与多种传统算法进行对比,结果表明该改进算法在求解性能和跳出局部最小解方面都有一定程度的提高.

To improve the performance of the ant colony algorithm, from the viewpoint of medical image registration, a hybrid ant colony algorithm is proposed based on mutual information similarity. To express the mutual entropy of the optimal path and the matching paths, a new similarity influence factor is added to the probability operator of the ant colony algorithm, which can improve the global search capability and accelerate the search speed. Besides, the proposed algorithm is applied in the traveling salesman problem, and the formulae are simplified in order to decrease time complexity. Compared with the traditional algorithms through experiments, the results demonstrate that the proposed algorithm can improve to some extent the solution performance and the capacity of jumping out of local minimum.