Quick-ACO: Accelerating Ant Decisions and Pheromone Updates in ACO

摘要

In Ant Colony Optimization (ACO) algorithms, solutions are constructed through a sequence of probabilistic decisions by artificial ants. These decisions are guided by information stored in a pheromone matrix which is repeatedly updated in two ways: Pheromone values in the matrix are increased by the ants to mark preferable decisions (probabilistic selection of items) whereas evaporation reduces each pheromone value by a certain percentage to weaken the relevance of former, potentially unfavorable, decisions. This paper introduces novel methods for expedited ant decisions and pheromone update for ACO. It is proposed to speedup decisions of ants by temporarily allowing them to select any item. If this item has already been chosen before (which would result in an inadmissible solution), the ant repeats its decision until an admissible item has been chosen. This method avoids to continuously determine the probability distributions over the yet admissible items which otherwise would require frequent expensive prefix sum calculations. The procedure of pheromone matrix updates is accelerated by entirely abandoning evaporation while re-scaling pheromone values and update increments. It should be empasized that both new methods do not change the optimization behavior compared to standard ACO. In experimental evaluations with a range of benchmark instances of the Traveling Salesman Problem, the new methods were able to save up to 90% computation time compared to a ACO algorithm which uses standard procedures for pheromone update and decision making.