網(wǎng)路工程外文翻譯--蟻群系統(tǒng)一個(gè)合作學(xué)習(xí)模式解決旅行商問(wèn)題的方法（英文）

1、IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 1, NO. 1, APRIL 1997 53Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman ProblemMarco Dorigo, Senior Member, IEEE, and Luca Maria Gambardella

2、, Member, IEEEAbstract—This paper introduces the ant colony system (ACS), a distributed algorithm that is applied to the traveling salesman problem (TSP). In the ACS, a set of cooperating agents called ants cooperate to

3、find good solutions to TSP’s. Ants cooperate using an indirect form of communication mediated by a pheromone they deposit on the edges of the TSP graph while building solutions. We study the ACS by running experiments to

4、 understand its operation. The results show that the ACS outperforms other nature-inspired algorithms such as simulated annealing and evo- lutionary computation, and we conclude comparing ACS-3-opt, a version of the ACS

5、augmented with a local search procedure, to some of the best performing algorithms for symmetric and asymmetric TSP’s.Index Terms—Adaptive behavior, ant colony, emergent behav- ior, traveling salesman problem.I. INTRODUC

6、TION THE natural metaphor on which ant algorithms are based is that of ant colonies. Real ants are capable of finding the shortest path from a food source to their nest [3], [22] without using visual cues [24] by exploit

7、ing pheromone information. While walking, ants deposit pheromone on the ground and follow, in probability, pheromone previously deposited by other ants. In Fig. 1, we show a way ants exploit pheromone to find a shortest

8、path between two points. Consider Fig. 1(a): ants arrive at a decision point in which they have to decide whether to turn left or right. Since they have no clue about which is the best choice, they choose randomly. It ca

9、n be expected that, on average, half of the ants decide to turn left and the other half to turn right. This happens both to ants moving from left to right (those whose name begins with an L) and to those moving from righ

10、t to left (name begins with an R). Fig. 1(b) and (c) shows what happens in the immediately following instants, supposing that all ants walk at approximately the same speed. The number of dashed lines is roughly proportio

11、nal to the amount of pheromone that the ants have deposited on the ground. Since the lower path is shorter than the upper one, more ants will visit it on average, and therefore pheromone accumulates faster. After a short

12、 transitory period the difference in the amount of pheromone on the two paths is sufficiently large so as to influence the decision of new ants coming into the system [this is shown byManuscript received October 7, 1996;

13、 revised January 18, 1997 and February 3, 1997. This work was supported by the Swiss National Science Fund Contract 21-45 653.95. M. Dorigo is with IRIDIA, Universit` e Libre de Bruxelles, 1050 Bruxelles, Belgium (e-mail

14、: mdorigo@ulb.ac.be). L. M. Gambardella is with IDSIA, 6900 Lugano, Switzerland. Publisher Item Identifier S 1089-778X(97)03303-1.Fig. 1(d)]. From now on, new ants will prefer in probability to choose the lower path, sin

15、ce at the decision point they perceive a greater amount of pheromone on the lower path. This in turn increases, with a positive feedback effect, the number of ants choosing the lower, and shorter, path. Very soon all ant

16、s will be using the shorter path. The above behavior of real ants has inspired ant system, an algorithm in which a set of artificial ants cooperate to the solution of a problem by exchanging information via pheromone dep

17、osited on graph edges. The ant system has been applied to combinatorial optimization problems such as the traveling salesman problem (TSP) [7], [8], [10], [12] and the quadratic assignment problem [32], [42]. The ant col

18、ony system (ACS), the algorithm presented in this article, builds on the previous ant system in the direction of improving efficiency when applied to symmetric and asymmetric TSP’s. The main idea is that of having a set

19、of agents, called ants, search in parallel for good solutions to the TSP and cooperate through pheromone-mediated indirect and global communication. Informally, each ant constructs a TSP solution in an iterative way: it

20、adds new cities to a partial solution by exploiting both information gained from past experience and a greedy heuristic. Memory takes the form of pheromone deposited by ants on TSP edges, while heuristic information is s

21、imply given by the edge’s length. The main novel idea introduced by ant algorithms, which will be discussed in the remainder of the paper, is the syner- gistic use of cooperation among many relatively simple agents which

22、 communicate by distributed memory implemented as pheromone deposited on edges of a graph. This paper is organized as follows. Section II puts the ACS in context by describing ant system, the progenitor of the ACS. Secti

23、on III introduces the ACS. Section IV is dedicated to the study of some characteristics of the ACS: We study how pheromone changes at run time, estimate the optimal number of ants to be used, observe the effects of phero

24、mone-mediated cooperation, and evaluate the role that pheromone and the greedy heuristic have in ACS performance. Section V provides an overview of results on a set of standard test problems and comparisons of the ACS wi

25、th well-known general purpose algorithms like evolutionary computation and simulated annealing. In Section VI we add local optimization to the ACS, obtaining a new algorithm called ACS-3-opt. This algorithm is compared f

26、avorably with the winner of the First International Contest on Evolutionary Optimization [5] on asymmetric TSP (ATSP) problems (see Fig. 2), while it yields a slightly worse performance on TSP problems. Section VII is108

27、9–778X/97$10.00 ? 1997 IEEEDORIGO AND GAMBARDELLA: ANT COLONY SYSTEM 55Fig. 3. The ACS algorithm.probability with which ant in city chooses to move to the cityifotherwise(1)where is the pheromone, is the inverse of the d

28、istance , is the set of cities that remain to be visited by ant positioned on city (to make the solution feasible), and is a parameter which determines the relative importance of pheromone versus distance . In (1) we mul

29、tiply the pheromone on edge by the corresponding heuristic value . In this way we favor the choice of edges which are shorter and which have a greater amount of pheromone. In ant system, the global updating rule is imple

30、mented as follows. Once all ants have built their tours, pheromone is updated on all edges according to(2)whereif tour done by antotherwiseis a pheromone decay parameter, is the length of the tour performed by ant , and

31、is the number of ants. Pheromone updating is intended to allocate a greater amount of pheromone to shorter tours. In a sense, this is similar to a reinforcement learning scheme [2], [26] in which better solutions get a h

32、igher reinforcement (as happens, for exam- ple, in genetic algorithms under proportional selection). The pheromone updating formula was meant to simulate the change in the amount of pheromone due to both the addition of

33、new pheromone deposited by ants on the visited edges and to pheromone evaporation. Pheromone placed on the edges plays the role of a dis- tributed long-term memory: this memory is not stored locally within the individual

34、 ants, but is distributed on the edges of the graph. This allows an indirect form of communication called stigmergy [9], [23]. The interested reader will find a full description of ant system, of its biological motivatio

35、ns, and computational results in [12].Although ant system was useful for discovering good or optimal solutions for small TSP’s (up to 30 cities), the time required to find such results made it infeasible for larger probl

36、ems. We devised three main changes to improve its performance which led to the definition of the ACS, presented in the next section.III. ACSThe ACS differs from the previous ant system because of three main aspects: i) t

37、he state transition rule provides a direct way to balance between exploration of new edges and exploitation of a priori and accumulated knowledge about the problem, ii) the global updating rule is applied only to edges w

38、hich belong to the best ant tour, and iii) while ants construct a solution a local pheromone updating rule (local updating rule, for short) is applied. Informally, the ACS works as follows: ants are initially positioned

39、on cities chosen according to some initialization rule (e.g., randomly). Each ant builds a tour (i.e., a feasible solution to the TSP) by repeatedly applying a stochastic greedy rule (the state transition rule). While co

40、nstructing its tour, an ant also modifies the amount of pheromone on the visited edges by applying the local updating rule. Once all ants have terminated their tour, the amount of pheromone on edges is modified again (by

41、 applying the global updating rule). As was the case in ant system, ants are guided, in building their tours, by both heuristic information (they prefer to choose short edges) and by pheromone information. An edge with a

42、 high amount of pheromone is a very desirable choice. The pheromone updating rules are designed so that they tend to give more pheromone to edges which should be visited by ants. The ACS algorithm is reported in Fig. 3.

43、In the following we discuss the state transition rule, the global updating rule, and the local updating rule.A. ACS State Transition RuleIn the ACS the state transition rule is as follows: an ant positioned on node choos