基于动态熵进化的异构蚁群优化

Heterogeneous Ant Optimization Based on Dynamic Entropy Evolution

针对蚁群算法在求解旅行商问题(Traveling Salesman Problem,TSP)时收敛速度慢、求解精度低等问题,文中提出了一种基于动态熵进化的异构蚁群优化算法。该算法中,由蚁群系统(Ant Colony System,ACS)和最大最小蚂蚁系统(Max-Min Ant System,MMAS)构成异构双种群,实现种群间优势互补。文中提出动态熵进化策略,通过信息熵来动态控制种群间的交流频率,并将两个种群各自最优解的公共路径的信息素进行融合,以调节低熵种群最优路径上的信息素分布,进而有效保留两个种群的历史搜索信息以及加快算法收敛。将低熵种群最优解的非公共路径进行伪初始化,以扩大其在较优解附近的搜索范围,提高解的精度,从而实现两个种群的协同进化。仿真实验结果表明,所提算法在求解大规模旅行商问题时能有效平衡算法多样性与收敛性之间的关系。

In view of the overcome the problem of the slow convergence speed and low precision of ant colony algorithm in solving TSP(Traveling Salesman Problem),a heterogeneous ant optimization based on dynamic entropy evolution is proposed.In this algorithm,a heterogeneous double population is comprised of ACS(Ant Colony System)and MMAS(Max-Min Ant System),which is helpful to promote the complementary advantages between the populations.And the dynamic entropy evolution strategy is introduced to dynamically control the communication frequency between the populations by information entropy.The pheromones of the two populations'optimal common paths are fused to adjust the distribution of pheromones on the optimal paths of the low entropy populations,thereby effectively preserving the historical search information of the two populations and accelerating the convergence of the algorithm.The non-common path of the optimal solution of low entropy population is pseudo-initialized to expand its search range near the optimal solution and improve the accuracy of the solution,so as to realize the co-evolution of two populations.Simulation results show that the proposed algorithm can effectively balance the relationship between algorithm diversity and convergence when solving large-scale traveling salesman problems.