时变挥发率条件下求解Steiner树蚁群优化算法的收敛性

A Convergence Proof for the Ant Colony Optimization Algorithms for Solving the Steiner Tree under Condition of Time Dependent Evaporation Rate

蚁群优化算法是最近提出的求解复杂组合优化问题的启发式算法.在蚁群优化算法中,信息素的更新规则直接影响着算法性能,固定挥发率条件下,虽然也能得到求解Steiner树蚁群优化算法的收敛性结果,但算法的探优能力差,易于陷入局部最优.本文在设计求解最小Steiner树蚁群优化算法时,采用了动态更新信息素挥发率的方法,并给出了时变挥发率条件下算法的收敛性证明.具体的,在时变挥发率条件下,当迭代次数充分大时,该算法能以概率1找到最优解.另外,在动态更新信息素下界的条件下,也能得到类似的收敛性结果.

Ant colony optimization algorithms is a recently proposed metaheurestic approach for solving complex combinatorial optimization problem. In ant colony optimization, pheromone trails update rule has playing an important role to the performance of the algorithms. Although convergence result has been presented for the ant colony optimization algorithms for the steiner tree with fixed evaporation rate, the algorithms do have a poor ability of exploring the search space and easily ＂trap into＂ local optimal solution.In this paper, a time dependent pheromone trails evaporation rate is first adapted when designing the ant colony optimization algorithms for the steiner tree, and a convergence proof is presented with time dependent evaporation rate. In particular, it is shown that under condition of time dependent pheromone trails evaporation rate, the probability of finding an optimal solution tends to 1 for sufficiently large number of algorithm iterations. In addition, the similar convergence result is given under the condition of time dependent lower pheromone trails bound.