版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
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
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 網(wǎng)路工程外文翻譯--蟻群系統(tǒng)一個(gè)合作學(xué)習(xí)模式解決旅行商問題的方法
- 網(wǎng)路工程外文翻譯--蟻群系統(tǒng)一個(gè)合作學(xué)習(xí)模式解決旅行商問題的方法(英文).pdf
- 網(wǎng)路工程外文翻譯--蟻群系統(tǒng)一個(gè)合作學(xué)習(xí)模式解決旅行商問題的方法
- 網(wǎng)路工程外文翻譯--蟻群系統(tǒng)一個(gè)合作學(xué)習(xí)模式解決旅行商問題的方法(英文).pdf
- 網(wǎng)路工程外文翻譯--蟻群系統(tǒng)一個(gè)合作學(xué)習(xí)模式解決旅行商問題的方法(譯文)
- 網(wǎng)路工程外文翻譯--蟻群系統(tǒng)一個(gè)合作學(xué)習(xí)模式解決旅行商問題的方法(譯文).doc
- 網(wǎng)路工程外文翻譯--蟻群系統(tǒng)一個(gè)合作學(xué)習(xí)模式解決旅行商問題的方法(譯文).doc
- 旅行商問題-畢業(yè)設(shè)計(jì)外文翻譯
- 基于蟻群算法的旅行商問題研究
- 一種改進(jìn)的蟻群算法求解旅行商問題.pdf
- 應(yīng)用智能螞蟻算法解決旅行商問題.pdf
- 旅行商問題畢業(yè)論文
- 求解旅行商問題的新方法研究.pdf
- 樹算法求解旅行商問題.pdf
- 混合遺傳算法解決旅行商問題的研究.pdf
- 蟻群算法及其在廣義旅行商問題求解中的應(yīng)用.pdf
- 求解旅行商問題的進(jìn)化算法.pdf
- 基于流水算法的旅行商問題求解
- 旅行商問題的兩種算法.pdf
- 蟻群算法及其應(yīng)用研究——基于旅行商問題和圖像分類.pdf
評論
0/150
提交評論