随机摄动蚁群算法的收敛性及其数值特性分析

从随机优化技术出发,针对基本蚁群算法,提出了一种随机摄动蚁群优化算法。并从理论上对该算法的收敛性及一些相关特性进行了探索性分析,指出该算法在有限迭代次数下以概率e-1(e 是一个很小的正数)找到全局或局部最优解(至少一次);而且如果迭代时间足够长,将以概率1收敛于全局或局部最优解。最后,以TSP问题为例,对该算法中若干参数的选取进行了仿真分析,提出了具有普遍意义的参数选取方法,并制定出各参数的最佳取值范围。

The Numerical Characteristics Analysis and Convergence Proof for Ant Colony Optimization Algorithm with Random Perturbation Behavior

A novel ant colony optimization algorithm with random perturbation behavior(RPACO) based on combination of general ant colony optimization and stochastic mechanism is developed in this paper. Some convergence properties for the proposed method are exploringly studied. In particular, we prove that for any small constant0>e, the approach will converge to an optimal solution at least once with probability e-1 during the finite iterations and the probability tends to 1 for the enough large number of iterations. Furthermore, the empirical method of finding optimal parameter settings based on the TSP problem via simulating a large number of trials is used in this paper, and finally the optimal numeric area of parameters can be obtained. The effectiveness of the proposed method has been demonstrated on the corresponding numerical results.