On some applications of ant colony optimization metaheuristic to plane truss optimization

摘要

Ant colony optimization metaheuristic (ACO) represents a new class of algorithms particularly suited to solve real-world combinatorial optimization problems. ACO algorithms, published for the first time in 1991 by M. Dorigo [Optimization, learning and natural algorithms (in Italian). Ph.D. Thesis, Dipartimento di Elettronica, Politecnico di Milano, Milan, 1992] and his coworkers, have been applied, particularly starting from 1999 (Bonabeau et al., Swarm intelligence: from natural to artificial systems, Oxford University Press, New York, 1999; Dorigo et al., Artificial life 5(2):137–172, 1999; Dorigo and Di Caro, Ant colony optimization: a new metaheuristic, IEEE Press, Piscataway, NJ, 1999; Dorigo et al., Ant colony optimization and swarm intelligence, Springer, Berlin Heidelberg New York, 2004; Dorigo and Stutzle, Ant colony optimization, MIT Press, Cambridge, MA, 2004), to several kinds of optimization problems such as the traveling salesman problem, quadratic assignment problem, vehicle routing, sequential ordering, scheduling, graph coloring, management of communications networks, and so on. The ant colony optimization metaheuristic takes inspiration from the studies of real ant colonies’ foraging behavior. The main characteristic of such colonies is that individuals have no global knowledge of problem solving but communicate indirectly among themselves, depositing on the ground a chemical substance called pheromone, which influences probabilistically the choice of subsequent ants, which tend to follow paths where the pheromone concentration is higher. Such behavior, called stigmergy, is the basic mechanism that controls ant activity and permits them to take the shortest path connecting their nest to a food source. In this paper, it is shown how to convert natural ant behavior to algorithms able to escape from local minima and find global minimum solutions to constrained combinatorial problems. Some examples on plane trusses are also presented.