提出一种多阶段,多偏好的改进蚁群算法(MP2AS),包括4种蚁型,对信息素、能见度与节约值有不同的重视程度.常态时,所有蚂蚁遵循同一转移规则,同时更新公共和私有信息素;一旦陷入局部最优,4种蚁型将根据各自确定的偏好类型,运用随机的偏好权重,计算转移概率,并只更新其私有信息素.偏好类型的互异性使蚁群得以沿不同方向独立进化;而偏好权重的随机性进一步提高了改善当前最优解的概率.为避免某种蚁型因长期孤立进化而积累病态,定期用全局最优解更新公共及私有信息素,增强蚁型间的交流,指导蚁群的进化方向.车辆路径问题标准算例的数值实验结果说明该算法具有很强的全局搜索和局部开发能力.%This paper proposes an improved ant system with multiple phases and preferences (Mr AS). The ant colony is composed of four ant groups, which attaches different significance to pheromone, visibility and savings. Normally all ants conduct state transitions with the same rule and simultaneously update the public/private pheromones. Once trapped in local optima, each ant group will calculate the transition probability according to its own preference type and stochastic weights, and update its own private pheromone. The discrepancy of preference type realizes the concurrent search along different directions, while the random preference weights increase the probability of finding superior solutions. The global optimal solution is periodically utilized to update the public and private pheromones to enhance the communication among ant groups and provide guidance for the evolution of the whole ant colony. Numeric experiments are performed on various vehicle routing benchmark problems and computational results indicate that the proposed algorithm is with strong capability of global exploration as well as local exploitation.
展开▼
