Some Issues of ACO Algorithm Convergence
Lorenzo Carvelli, Giovanni Sebastiani · InTech eBooks · 2011
The study of the convergence of ACO algorithms, or more in general of stochastic algorithms for solving combinatorial optimization problems is very important. In fact, it can provide information that can be useful in practice when applying such algorithms. This information can be of different kinds. The most basic question of interest is about algorithm capability of solving the problem of interest. Given the stochastic nature of the kind of algorithms considered, this question can be properly formulated in terms of the “failure” probability, i.e. the probability that after the current iteration the algorithm has not yet found the solution. We are of course interested in ACO algorithms whose failure probability converges to zero. Another kind of convergence, that is stronger than simply having the failure probability to converge to zero, is when the whole ACO colony approaches, as time goes to infinity, a set of individuals all corresponding to one of the problem solutions. In addition to algorithm’s effectiveness, other natural questions arise. In fact, the user is interested in the quantification of the time used by the algorithm to solve the problem. Since this time is random, the quantification will involve its expected value, its variance and ideally its distribution. Let us now go back to the failure probability. There are often situations where, by applying ACO algorithms, or more in general stochastic algorithms, to solve combinatorial optimization problems, the failure probability goes to zero too slowly. In those situations, one could ask the question if, instead of running the ACO algorithm for a certain time, it would be more convenient to stop it after another time T, smaller than the former, and to start it again from the beginning, and so on, until the original time is reached. In the case of a positive answer to this question, one could also study the problem of finding an optimal value for the time T. In this chapter, we will illustrate some relevant known theoretical results on the former issues. Furthermore, we will provide some results on a our ingoing research on the last issue. Beside this, some numerical simulation results will also be introduced and discussed.