摘要
针对蚁群算法易陷入局部最优与收敛速度较慢的不足,提出了动态学习机制的双种群蚁群算法。该算法重点引入奖惩模型,奖励算子提高算法的收敛速度,惩罚算子增加种群的多样性。由SA-MMAS(adaptive simulated annealing ant colony algorithm based on max-min ant system)和MMAS(max-min ant system)两个种群合作搜索路径,蚁群间根据不同城市规模动态地进行信息素交流,在种群交流后利用奖惩模型对双种群间的学习合作行为给予动态的反馈,从而平衡算法的多样性与收敛速度。通过17个经典旅行商问题(traveling salesman problem,TSP)实例进行验证,结果表明该算法能以较少的迭代次数取得最优解或接近最优解。对于中大规模的TSP问题效果更好,从而验证了算法的高效性和可行性。
Aiming at the deficiencies of ant colony algorithm that can easily fall into the local optimum and the convergence speed is slow, a dual population ant colony algorithm based on dynamic learning mechanism is proposed. This algorithm focuses on the reward penalty model. The reward operator improves the convergence speed of the algorithm, and the penalty operator improves the diversity of the algorithm. Two populations SA-MMAS (adaptive simulated annealing ant colony algorithm based on max-min ant system) and MMAS (max-min ant system) cooperatively search paths, and then the ant colonies dynamically communicate pheromone according to different city sizes. After communication between the two colonies, the incentive penalty model is used to give dynamic feedback to the learning cooperative behavior between the two colonies, thus balancing the diversity and convergence speed of the algorithm. Verified by 17 classic TSP (traveling salesman problem) instances, the results show that the algorithm can obtain the optimal solution or near optimal solution with fewer iterations. It is more effective for medium and large-scale TSP, thus verifying the efficiency and feasibility of the algorithm.
作者
袁汪凰
游晓明
刘升
YUAN Wanghuang;YOU Xiaoming;LIU Sheng(School of Electronic and Electrical Engineering,Shanghai University of Engineering Science,Shanghai 201600,China;School of Management,Shanghai University of Engineering Science,Shanghai 201600,China)
出处
《计算机科学与探索》
CSCD
北大核心
2019年第7期1239-1250,共12页
Journal of Frontiers of Computer Science and Technology
基金
国家自然科学基金Nos.61673258,61075115,61403249,61603242~~
关键词
动态学习
奖惩模型
双种群
旅行商问题
dynamic learning
reward penalty model
dual population
traveling salesman problem (TSP)
