蟻群算法及其在路徑規(guī)劃中的應(yīng)用.ppt

1、蟻群算法及其在路徑規(guī)劃中的應(yīng)用,Q. Song 2011. 4. 6,Swarm Intelligence,Dumb parts, properly connected into a swarm, yield smart results. Kevin Kelly,Algorithms inspired from insects,Ant Colony Optimization (ACO) Particle Swarm Optimization (PSO) Fish Swarm (FS),Two bridges experiment,from nest to food constrained to

2、 move in two asymmetric paths,Principles,蟻群算法的基本原理源于昆蟲學(xué)家們的觀察和發(fā)現(xiàn),生物界中的螞蟻在搜索食物源時(shí),能夠在其走過的路徑上釋放一種螞蟻特有的分泌物(pheromone)信息激素,使得一定范圍內(nèi)的其它螞蟻能夠覺察并影響其行為。當(dāng)某些路徑上走過的螞蟻越來越多時(shí),留下的這種信息激素也越多,以致后來螞蟻選擇該路徑的概率也越高,從而增加了該路徑的吸引強(qiáng)度,螞蟻群體就是靠著這種內(nèi)部的生物協(xié)同機(jī)制形成了一條它們自己并未意識(shí)到的最短路線。,Behaviors of ant,each ant moves at random, pheromone is de

3、posited on path,ants detect lead ants path, inclined to follow,more pheromone on path increases probability of path being followed,作為與遺傳算法同屬一類的通用型隨機(jī)優(yōu)化方法，蟻群算法不需要任何先驗(yàn)知識(shí)，最初只是隨機(jī)地選擇搜索路徑，隨著對(duì)解空間的“了解”，搜索變得有規(guī)律，并逐漸逼近直至最終達(dá)到全局最優(yōu)解。蟻群算法對(duì)搜索空間的“了解”機(jī)制主要包括三個(gè)方面： (1)螞蟻的記憶。一只螞蟻搜索過的路徑在下次搜索時(shí)就不會(huì)再被選擇，由此在蟻群算法中建立tabu(禁忌)列表來進(jìn)行

4、模擬； (2)螞蟻利用信息素進(jìn)行相互通信。螞蟻在所選擇的路徑上會(huì)釋放一種叫做信息素的物質(zhì)，當(dāng)同伴進(jìn)行路徑選擇時(shí)，會(huì)根據(jù)路徑上的信息素進(jìn)行選擇，這樣信息素就成為螞蟻之間進(jìn)行通訊的媒介。,(3)螞蟻的集群活動(dòng)。通過一只螞蟻的運(yùn)動(dòng)很難到達(dá)食物源，但整個(gè)蟻群進(jìn)行搜索就完全不同。當(dāng)某些路徑上通過的螞蟻越來越多時(shí)，在路徑上留下的信息素?cái)?shù)量也越來越多，導(dǎo)致信息素強(qiáng)度增大，螞蟻選擇該路徑的概率隨之增加，從而進(jìn)一步增加該路徑的信息素強(qiáng)度，而某些路徑上通過的螞蟻較少時(shí)，路徑上的信息素就會(huì)隨時(shí)間的推移而蒸發(fā)。因此，模擬這種現(xiàn)象即可利用群體智能建立路徑選擇機(jī)制，使蟻群算法的搜索向最優(yōu)解推進(jìn)。,The Algorith

5、m,Used to solve TSP Transition from city i to j depends on: - Tabu list: list of cities having visited - Visibility = 1/dij; represents local information, heuristic desirability to visit city j when in city i. - Pheromone trail for each edge, represents the learned desirability to visit city j when

6、in city i.,s,i,t,j,j,j,The Algorithm,Transition Rule Probability of ant k going from city i to j: Alpha and beta are adjustable parameters that control the relative importance of trail versus visibility; allowedk= N tabuk ,The Algorithm,Pheromone update :,: a coefficient such that represents the eva

7、poration of trail between time t and t+n,: the quantity per unit of length of trail substance laid on edge (i,j) by ant k between time t and t+n,The Algorithm,Three types of * ant-cycle system: Q: a constant Lk: the tour length of the kth ant,The Algorithm,Three types of * ant-quantity system:,The A

8、lgorithm,Three types of * ant-density system:,The Algorithm,Difference between three models: * ant-cycle system uses global information * ant-quantity system and ant-density system uses local information * ant-cycle system used to solve TSP,TSP Example,A,E,D,C,B,dAB =100; dBC = 60; dDE =150,TSP Exam

9、ple,A,E,D,C,B,TSP Example,Iteration 1,A,E,D,C,B,TSP Example,TSP Example,A,E,D,C,B,Iteration 2,TSP Example,A,E,D,C,B,Iteration 3,A,E,D,C,B,TSP Example,Iteration 4,A,E,D,C,B,TSP Example,Iteration 5,L1 =300,L2 =450,L3 =260,L4 =280,L5 =420,TSP Example,End of First Run,All ants die,New ants are born,Save

10、 Best Tour (Sequence and length),TSP Example,t = 0; NC = 0; ij(t)=c for ij=0 Place the m ants on the n nodes,Update tabuk(s),Compute the length Lk of every ant Update the shortest tour found =,For every edge (i,j) Compute For k:=1 to m do,Initialize,Choose the city j to move to. Use probability,Tabu

11、 list management,Move k-th ant to town j. Insert town j in tabuk(s),Set t = t + n; NC=NC+1; ij=0,NCNCmax & not stagn.,Yes,End,No,Yes,VRPTW Example,N customers are to be visited by K vehicles Given * Depots (number, location) * Vehicles (capacity, costs, time to leave, time on road.) * Customers (dem

12、ands, time windows, priority, .) * Route Information (maximum route time or distance, cost on the route),VRPTW Example,Objective Functions to Minimize * Total travel distance * Total travel time * Number of vehicles Subject to: * Vehicles ( # ,Capacity,time on road,trip length) * Depots (Numbers) *

13、Customers (Demands,time windows),VRPTW Example,Relation with TSP?!,VRPTW Example,Simple Algorithm - Place ants on depots (Depots # = Vehicle #). - Probabilistic choice (1/distance, di, Q) amount of pheromone - If all unvisited customer lead to a unfeasible solution: Select depot as your next custome

14、r. - Improve by local search. - Only best ants update pheromone trial.,Advantages,Positive Feedback accounts for rapid discovery of good solutions. Distributed computation avoids premature convergence. The greedy heuristic helps find acceptable solution in the early solution in the early stages of the search process. The collective interaction of a population of agents