An efficient ant colony optimization strategy for the resolution of multi-class queries

摘要

Ant Colony Optimization is a bio-inspired computational technique for establishing optimal paths in graphs. It has been successfully adapted to solve many classical computational problems, with considerable results. Nevertheless, the attempts to apply ACO to the question of multidimensional problems and multi-class resource querying have been somewhat limited. They suffer from either severely decreased efficiency or low scalability, and are usually static, custom-made solutions with only one particular use. In this paper we employ Angry Ant Framework, a multipheromone variant of Ant Colony System that surpasses its predecessor in terms of convergence quality, to the question of multi-class resource queries. To the best of the authors knowledge it is the only algorithm capable of dynamically creating and pruning pheromone levels, which we refer to as dynamic pheromone stratification. In a series of experiments we verify that, due to this pheromone level flexibility, Angry Ant Framework, as well as our improvement of it called Entropic Angry Ant Framework, have significantly more potential for handling multi-class resource queries than their single pheromone counterpart. Most notably, the tight coupling between pheromone and resource classes enables convergence that is both better in quality and more stable, while maintaining a sublinear cost. (C) 2016 Elsevier B.V. All rights reserved.