Evolving Ant Colony Optimization

Social insects---ants, bees, termites and wasps---exhibit a collective problem-solving ability (Deneubourg and Goss, 1989; Bonabeau et al., 1997). In particular, several ant species are capable of selecting the shortest pathway, among a set of alternative pathways, from their nest to a food source (Beckers et al., 1990). Ants deploy a chemical trail (or pheromone trail) as they walk; this trail attracts other ants to take the path that has the most pheromone. This reinforcement process results in the selection of the shortest path: the first ants coming back to the nest are those that took the shortest path twice (to go from the nest to the source and to return to the nest), so that more pheromone is present on the shortest path than on longer paths immediatly after these ants have returned, stimulating nestmates to choose the shortest path. Taking advantage of this ant-based optimizing principle combined with pheromone evaporation to avoid early convergence to bad solutions, Colorni et al. (1991, 1992, 1993), Dorigo et al. (1996), Dorigo and Gambardella (1997a, 1997b; Gambardella and Dorigo, 1995) and Gambardella et al.}(1997) have proposed a remarkable optimization method, Ant Colony Optimization (ACO), which they applied to classical NP-hard combinatorial optimization problems, such as the traveling salesman problem (Lawler et al., 1985), the quadratic assignment problem (Gambardella et al., 1998) or the job-shop scheduling problem (Colorni et al., 1993), with reasonable success. More applications are described by Bonabeau et al. (1998). The parameters of the ACO algorithms developed in these papers were hand-tuned. In the present letter we demonstrate the good performance of ACO algorithms when parameters are selected using a systematic procedure. More precisely we use a genetic algorithm (Goldberg, 1989) to evolve ACO algorithms. A simple implementation of this approach, tested on the traveling salesman problem (TSP), resulted in: (1) increased convergence speed (compared to the performance of the best hand-tuned ACO algorithm) toward the optimal solution for a 30-city problem (Whitley et al., 1989), and (2) several very good floating point solutions for a 51-city problem (Eilon et al., 1969). Our results suggest that it might be possible to systematically find parameters that significantly increase the performance of ACO algorithms, and confirm that ACO is more than an exotic metaheuristic as it compares well with existing algorithms on popular benchmark problems. To appear in Advances in Complex Systems 1(2/3): 149-159.