Ant Algorithms Solve Difficult Optimization Problems.pdfVIP

Ant Algorithms Solve Difficult Optimization Problems Marco Dorigo IRIDIA Universite? Libre de Bruxelles 50 Avenue F. Roosevelt B-1050 Brussels, Belgium mdorigo@ulb.ac.be Abstract. The ant algorithms research field builds on the idea that the study of the behavior of ant colonies or other social insects is interesting for computer scientists, because it provides models of distributed orga- nization that can be used as a source of inspiration for the design of op- timization and distributed control algorithms. In this paper we overview this growing research field, giving particular attention to ant colony op- timization, the currently most successful example of ant algorithms, as well as to some other promising directions such as ant algorithms inspired by labor division and brood sorting. 1 Introduction Models based on self-organization have recently been introduced by ethologists to study collective behavior in social insects [2, 3, 5, 14]. While the main mo- tivation for the development of these models was to understand how complex behavior at the colony level emerges out of interactions among individual insects, computer scientists have recently started to exploit these models as an inspira- tion for the design of useful optimization and distributed control algorithms. For example, a model of cooperative foraging in ants has been transformed into a set of optimization algorithms, now known as ant colony optimization (ACO) [22, 24], capable of tackling very hard computational problems, such as the trav- eling salesman [28, 20, 29, 26, 60], the quadratic assignment problem [47, 46, 35, 61], the sequential ordering problem [33], the shortest common supersequence problem [49], various scheduling problems [57, 12, 48], and many others (see Ta- ble 1). More recently, ACO has also been successfully applied to distributed control problems such as adaptive routing in communications networks [54, 17]. Another model, initially introduced to explain brood sorting in ants, was