Computer Engineering and Applications ›› 2010, Vol. 46 ›› Issue (10): 44-47.DOI: 10.3778/j.issn.1002-8331.2010.10.015

• 研究、探讨 • Previous Articles     Next Articles

Premium-penalty ant colony optimization

ZHANG Fei-jun1,GAO Wei2,WANG Lei2   

  1. 1.Department of Post-graduate,Wuhan Polytechnic University,Wuhan 430023,China
    2.Department of Civil Engineering,Wuhan Polytechnic University,Wuhan 430023,China
  • Received:2008-10-06 Revised:2008-12-22 Online:2010-04-01 Published:2010-04-01
  • Contact: ZHANG Fei-jun

奖惩蚁群算法

张飞君1,高 玮2,汪 磊2   

  1. 1.武汉工业学院 研究生院,武汉 430023
    2.武汉工业学院 土木系,武汉 430023
  • 通讯作者: 张飞君

Abstract: Due to the random probabilistic search strategy,the slow convergence is the main problem of the traditional Ant Colony Optimization(ACO).In order to improve the convergence of the algorithm,the Premium-Penalty Ant Colony Optimization(PPACO) is proposed.In this new algorithm,the better solutions found by the ants are awarded while the ordinary ones are punished.In order to counteract the polarization of pheromone values on all roads,the pheromone trails are limited to an interval [τmin,τmax] and the evaporation rate is set to a higher value.The results of the simulation experiments on several traveling salesman problems show that the PPACO is ranked among the best ACO for tackling the complicated combination optimization problems.

Key words: ant colony optimization, rank, premium, penalty

摘要: 由于传统蚁群算法所采用的是随机概率搜索策略,收敛速度慢是其主要问题。为了提高算法的收敛速度,这里提出一种带奖惩策略的蚁群算法(PPACO)。新算法中,每次循环中发现的较优解都被挑选出来加以奖励,而普通解则被惩罚,这样就加快了较优路径和普通路径上信息素的差异;另外,为了不使这种差异对算法产生过多的影响,所有路径上的信息素都被限制在一定的范围[τmin,τmax]内,同时,信息素的挥发系数被设为相对较高值。通过典型模拟实验证明,新算法对解决复杂组合优化问题非常有效。

关键词: 蚁群算法, 排序, 奖励, 惩罚

CLC Number: