MAX–MIN Ant System

Future Generation Computer Systems 16 (2000) 889–914 MAX–MIN Ant System Thomas Stützle a;�;1, Holger H. Hoos b;2 a IRIDIA, Université Libre de Bruxelles, Avenue Franklin Roosevelt 50, CP 194/6, 1050 Brussels, Belgium b Computer Science Department, University of British Columbia, 2366 Main Mall, Vancouver, BC, Canada V6T 1Z4 Abstract Ant System, the first Ant Colony Optimization algorithm, showed to be a viable method for attacking hard combinatorial optimization problems. Yet, its performance, when compared to more fine-tuned algorithms, was rather poor for large instances of traditional benchmark problems like the Traveling Salesman Problem. To show that Ant Colony Optimization algorithms could be good alternatives to existing algorithms for hard combinatorial optimization problems, recent research in this area has mainly focused on the development of algorithmic variants which achieve better performance than Ant System. In this paper, we presentMAX–MIN Ant System (MMAS), an Ant Colony Optimization algorithm derived from Ant System. MMAS differs from Ant System in several important aspects, whose usefulness we demonstrate by means of an experimental study. Additionally, we relate one of the characteristics specific to MMAS — that of using a greedier search than Ant System — to results from the search space analysis of the combinatorial optimization problems attacked in this paper. Our computational results on the Traveling Salesman Problem and the Quadratic Assignment Problem show thatMMAS is currently among the best performing algorithms for these problems. © 2000 Elsevier Science B.V. All rights reserved. Keywords: Ant Colony Optimization; Search space analysis; Traveling Salesman Problem; Quadratic Assignment Problem; Combinatorial optimization 1. Introduction Ant Colony Optimization (ACO) [8,11,13,14] is a recently developed, population-based approach which has been successfully applied to several NP-hard combinatorial optimization problems [5,7,12,19,20,27,32,41] (see [10,11] for an overview). As the name suggests, ACO has been inspired by the behavior of real ant colonies, in particular, by their foraging behavior. One of its main ideas is � Corresponding author. Tel.: C32-2-650-3167; fax: C32-2-650-2715. E-mail addresses: tstutzle@ulb.ac.be (T. Stützle), hoos@cs.ubc.ca (H.H. Hoos) 1 On leave from FG Intellektik, TU Darmstadt, Germany. 2 Tel.: C1-604-822-5109; fax: C1-604-822-5485. the indirect communication among the individuals of a colony of agents, called (artificial) ants, based on an analogy with trails of a chemical substance, called pheromone, which real ants use for commu- nication. The (artificial) pheromone trails are a kind of distributed numeric information (called stigmergic information in [9]) which is modified by the ants to reflect their experience accumulated while solv- ing a particular problem. Recently, the ACO meta- heuristic has been proposed to provide a unifying framework for most applications of ant algorithms [10,11] to combinatorial optimization problems. Al- gorithms which actually are instantiations of the ACO metaheuristic will be called ACO algorithms in the following. The first ACO algorithm, called Ant System (AS) [8,13,14], was applied to the Traveling Salesman Prob- 0167-739X/00/$ – see front matter © 2000 Elsevier Science B.V. All rights reserved. PII: S0167 - 739 X (00 )00043 -1 890 T. Stützle, H.H. Hoos / Future Generation Computer Systems 16 (2000) 889–914 lem (TSP). It gave encouraging results, yet its perfor- mance was not competitive with state-of-the-art algo- rithms for the TSP. Therefore, one important focus of research on ACO algorithms has been the introduc- tion of algorithmic improvements to achieve a much better performance. Typically, these improved algo- rithms have been tested again on the TSP [6,12,42]. While they differ mainly in specific aspects of the search control, all these ACO algorithms are based on a stronger exploitation of the search history to di- rect the ants’ search process. Recent research on the search space characteristics of some combinatorial op- timization problems has shown that for many problems there exists a correlation between the solution quality and the distance from very good or optimal solutions [3,4,23,31]. Hence, it seems reasonable to assume that the concentration of the search around the best solu- tions found during the search is the key aspect that led to the improved performance shown by the modified ACO algorithms. The MAX–MIN Ant System (MMAS) al- gorithm discussed in this paper achieves a strong exploitation of the search history by allowing only the best solutions to add pheromone during the pheromone trail update. Also, the use of a rather simple mechanism for limiting the strengths of the pheromone trails effectively avoids premature conver- gence of the search. Finally, MMAS can easily be extended by adding local search algorithms. In fact, the best performing ACO algorithms for many differ- ent combinatorial optimization problems improve the solutions generated by the ants with local search al- gorithms [5,12,19,28,41–43]. As our empirical results show, MMAS is currently one of the best perform- ing ACO algorithms for the TSP and the Quadratic Assignment Problem (QAP). The remainder of this paper is structured as fol- lows. In Section 2, we introduce ACO algorithms and discuss their application to the TSP, using AS as a starting point. Next, we review some results from the search space analysis of the TSP which show that so- lution quality and distance from a global optimum are tightly correlated and we give new results for a sim- ilar analysis of the QAP search space. In Section 4, we give details on the modifications of AS leading to MMAS and present an experimental investigation showing the effectiveness of these modifications. Sec- tion 5 gives the results of our extensive experimental analysis of MMAS with additional local search for the TSP. In Section 6, we show thatMMAS is one of the best available algorithms for the QAP. In Section 7, we briefly summarize our main results and point out directions for further research. 2. Ant Colony Optimization 2.1. ACO algorithms ACO algorithms make use of simple agents called ants which iteratively construct candidate solutions to a combinatorial optimization problem. The ants’ solu- tion construction is guided by (artificial) pheromone trails and problem-dependent heuristic information. In principle, ACO algorithms can be applied to any com- binatorial optimization problem by defining solution components which the ants use to iteratively construct candidate solutions and on which they may deposit pheromone (see [10,11] for more details). An individ- ual ant constructs candidate solutions by starting with an empty solution and then iteratively adding solu- tion components until a complete candidate solution is generated. We will call each point at which an ant has to decide which solution component to add to its current partial solution a choice point. After the solu- tion construction is completed, the ants give feedback on the solutions they have constructed by depositing pheromone on solution components which they have used in their solution. Typically, solution components which are part of better solutions or are used by many ants will receive a higher amount of pheromone, and hence, will more likely be used by the ants in future iterations of the algorithm. To avoid the search get- ting stuck, typically before the pheromone trails get reinforced, all pheromone trails are decreased by a factor �. The ants’ solutions are not guaranteed to be optimal with respect to local changes and hence may be fur- ther improved using local search methods. Based on this observation, the best performing ACO algorithms for many NP-hard static combinatorial problems 3 are in fact hybrid algorithms combining probabilistic 3 Static combinatorial problems are those in which all relevant problem data are available before the start of the algorithm and do not change during the algorithm’s run. T. Stützle, H.H. Hoos / Future Generation Computer Systems 16 (2000) 889–914 891 Fig. 1. Algorithmic skeleton for ACO algorithms applied to static combinatorial problems. solution construction by a colony of ants with local search algorithms [5,12,19,28,41–43]. In such hybrid algorithms, the ants can be seen as guiding the local search by constructing promising initial solutions, be- cause ants preferably use solution components which, earlier in the search, have been contained in good locally optimal solutions. In general, all ACO algorithms for static combina- torial problems follow a specific algorithmic scheme outlined in Fig. 1. After the initialization of the pheromone trails and some parameters, a main loop is repeated until a termination condition — which may be a certain number of solution constructions or a given CPU-time limit — is met. In the main loop, first, the ants construct feasible solutions, then the generated solutions are possibly improved by ap- plying local search, and finally the pheromone trails are updated. It should be noted that the ACO meta- heuristic [10,11] is more general than the algorithmic scheme given here. 4 2.2. Combinatorial optimization problems Almost all ACO algorithms have initially been tested on the TSP [6,8,12–14,42]. In this paper, we focus on the TSP and the QAP as application domains for MMAS . 2.2.1. Traveling Salesman Problem The TSP can be represented by a complete graph G D .N; A/ with N being the set of nodes, also called cities, and A being the set of arcs fully con- necting the nodes. Each arc .i; j/ 2 A is assigned 4 For example, the algorithmic scheme of Fig. 1 does not capture the application of ACO algorithms to network routing problems (for an example see [7]). a value dij which represents the distance between cities i and j . The TSP then is the problem of finding a shortest closed tour visiting each of the n D jN j nodes of G exactly once. For symmetric TSPs, the distances between the cities are indepen- dent of the direction of traversing the arcs, that is, dij D dji for every pair of nodes. In the asym- metric TSP (ATSP) at least for one pair of nodes i; j we have dij 6D dji . All the TSP instances used in the empirical studies presented in this paper are taken from the TSPLIB benchmark library accessible at http://www.iwr.uni-heidelberg.de/ iwr/comopt/software/TSPLIB95. These instances have been used in many other studies and partly stem from practical applications of the TSP. 2.2.2. Quadratic Assignment Problem The QAP is the problem of assigning a set of facili- ties to a set of locations with given distances between the locations and given flows between the facilities. The goal is to place the facilities on locations in such a way that the sum of the products between flows and distances is minimal. Given n facilities and n loca- tions, two n � n matrices A D [aij ] and B D [brs], where aij is the distance between locations i and j , and brs is the flow between facilities r and s, the QAP is the problem to minimize f .�/ D nX iD1 nX jD1 bij a�.i/�.j/; (1) where � is an arbitrary permutation of the set of in- tegers f1; : : : ; ng (corresponding to an assignment of facilities to locations), and �.i/ gives the location of facility i in �. Intuitively, bij a�.i/�.j/ represents the cost contribution of simultaneously assigning facility i to location �.i/ and facility j to location �.j/. The QAP is anNP-hard optimization problem [38] and it is considered to be one of the hardest optimiza- tion problems. To date, instances of size n � 20 can generally not be solved to optimality and one has to apply heuristic algorithms which find very high qual- ity solutions in a relatively short computation time. The instances on which we will testMMAS are taken from the QAPLIB benchmark library (accessible at http://serv1.imm.dtu.dk/�sk/qaplib/). 892 T. Stützle, H.H. Hoos / Future Generation Computer Systems 16 (2000) 889–914 2.3. Applying AS to the TSP When applying AS to the TSP, arcs are used as solu- tion components. A pheromone trail �ij .t/, where t is the iteration counter, is associated with each arc .i; j/; these pheromone trails are modified during the run of the algorithm through pheromone trail evaporation and pheromone trail reinforcement by the ants. When applied to symmetric TSP instances, pheromone trails are also symmetric (�ij .t/ D �ji.t/) while in applica- tions to ATSPs possibly �ij .t/ 6D �ji.t/. 2.3.1. Tour construction Initially, m ants are placed on m randomly cho- sen cities. Then, in each construction step, each ant moves, based on a probabilistic decision, to a city it has not yet visited. This probabilistic choice is biased by the pheromone trail �ij .t/ and by a locally avail- able heuristic information �ij . The latter is a function of the arc length; AS and all other ACO algorithms for the TSP use �ij D 1=dij . Ants prefer cities which are close and connected by arcs with a high pheromone trail and in AS an ant k currently located at city i chooses to go to city j with a probability: pkij .t/ D [�ij .t/]� [�ij ]�P l2N ki [�il.t/] � [�il]� if j 2 N ki ; (2) where � and � are two parameters which determine the relative importance of the pheromone trail and the heuristic information, and N ki is the feasible neigh- borhood of ant k, that is, the set of cities which ant k has not visited yet. Each ant k stores the cities visited in its current partial tour in a list, that is, each ant has a limited memory which is used to determine N ki in each construction step and thus to guarantee that only valid Hamiltonian cycles are generated. Additionally, it allows the ant to retrace its tour, once it is com- pleted, so that it can deposit pheromone on the arcs it contains. 2.3.2. Pheromone update After all ants have completed the tour construction, the pheromone trails are updated. This is done first by lowering the pheromone trails by a constant factor (evaporation) and then by allowing the ants to deposit pheromone on the arcs they have visited. In particular, the update follows this rule: �ij .t C 1/ D � �ij .t/ C mX kD1 1�kij .t/; (3) where the parameter � (with 0 � � < 1) is the trail persistence (thus, 1 − � models the evaporation) and 1�kij .t/ is the amount of pheromone ant k puts on the arcs it has used in its tour. The evaporation mech- anism helps to avoid unlimited accumulation of the pheromone trails. While an arc is not chosen by the ants, its associated pheromone trail decreases expo- nentially; this enables the algorithm to “forget” bad choices over time. In AS, 1�kij .t/ is defined as follows: 1�kij .t/ D 8< : 1=Lk.t/ if arc.i; j/ is used by ant k in iteration t; 0 otherwise: (4) where Lk.t/ is the tour length of the kth ant. By Eq. (4), the better the ant’s tour is, the more pheromone is received by the arcs belonging to this tour. In general, arcs which are used by many ants and which are con- tained in shorter tours will receive more pheromone and therefore will more likely be chosen in future it- erations of the algorithm. In this sense the amount of pheromone �ij .t/ represents the learned desirability of choosing the city j to move to when an ant is in city i. 2.4. Applying AS to the QAP The AS application to the TSP can be extended to the QAP in a straightforward way. The main differ- ence is in the definition of the solution components which for the QAP are given by the assignments of fa- cilities to locations. Hence, the pheromone trails �ij .t/ in the QAP application correspond to the desirability of assigning a facility i to a location j . For the solution construction, it can be convenient to use a preordering of the facilities (or, equivalently, the locations) and assign facilities in the given order. The decision points are related to the assignments: at each decision point an ant probabilistically decides on which location the next facility should be put. In AS for the QAP, these decisions are done according to Eq. (2) using a QAP-specific heuristic information [28]. In this case the feasible neighborhood N ki of ant k comprises those locations which are still free. The single construction steps are repeated until a complete T. Stützle, H.H. Hoos / Future Generation Computer Systems 16 (2000) 889–914 893 assignment is obtained. The pheromone update is done as in the TSP application. 2.5. Improvements over Ant System AS has been compared with other general purpose heuristics on some relatively small TSP instances with up to 75 cities. Some initial results were encourag- ing and have shown the viability of the approach; for example, AS could be shown to achieve better tour qualities than other nature-inspired algorithms, such as simulated annealing or genetic algorithms [14]. However, for larger TSP instances AS gives a very poor solution quality compared to state-of-the-art al- gorithms. A first improvement over AS, called the elitist strategy for Ant System (ASe) [8,14], gives a strong additional reinforcement to the solution com- ponents belonging to the best solution found since the start of the algorithm; this solution is denoted as sgb (global-best solution) in the following. This is realized by adding a quantity e=f .sgb/, where e is the number of elitist ants and f .sgb/ is the solution cost of sgb, to the arcs used in sgb after each iteration. Some limited results presented in [8,14] suggest that the use of the elitist strategy with an appropriate number of elitist ants allows AS to find better tours and to find them earlier in the run. Yet, if too many elitist ants are used, the search concentrates early around suboptimal solu- tions leading to a premature stagnation of the search. Search stagnation is defined in [14] as the situation where all ants follow the same path and construct the same solution over and over again, such that better solutions cannot be found anymore. Other improvements over AS include Ant Colony System (ACS) [12,18] and the rank-based version of Ant System (ASrank) [5]. In ACS and MMAS, the best solutions found during the search are exploited by allowing only one ant to update the trails after each iteration, while in ASrank a fixed number of ants of the current iteration — the better the ants are ranked in the current iteration, the more weight they are given for the trail update — and the global-best ant are allowed to update the pheromone trails. 3. Search space characteristics All improved ACO algorithms have one important feature in common: they exploit the best solutions found during the search much more than what is done by AS. Also, they use local search to improve the solu- tions constructed by the ants. The fact that additional exploitation of the best found solutions provides the key for an improved performance, is certainly related to the shape of the search space of many combinato- rial optimization problems. In this section, we report some results on the topology of search spaces of TSP and QAP instances which partly explain the observed performance differences and motivates important aspects of the algorithmic design of MMAS. 3.1. Analysis of fitness landscapes Central to the search space analysis of combinato- rial optimization problems is the notion of fitness land- scape [39,48]. Intuitively, the fitness landscape can be imagined as a mountainous region with hills, craters, and valleys. A local search algorithm can be pictured as a wanderer that performs a biased walk in this land- scape. In a minimization problem such as the TSP or the QAP, the goal is to find the lowest point in this landscape. The effectiveness of a given search strat- egy for the wanderer strongly depends on the rugged- ness of the landscape, the distribution of the valleys and craters in the landscape, and the overall number of valleys and craters. Formally, the fitness landscape is defined by 1