蚁群算法及其在路径规划中的应用

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,蚁群算法及其在路径规划中的应用,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 move in two asymmetric paths,Principles,蚁群算法的基本原理源于昆虫学家们的观察和发现,生物界中的蚂蚁在搜索食物源时,能够在其走过的路径上释放一种蚂蚁特有的分泌物,(pheromone),信息激素,使得一定范围内的其它蚂蚁能够觉察并影响其行为。当某些路径上走过的蚂蚁越来越多时,留下的这种信息激素也越多,以致后来蚂蚁选择该路径的概率也越高,从而增加了该路径的吸引强度,蚂蚁群体就是靠着这种内部的生物协同机制形成了一条它们自己并未意识到的最短路线。,Behaviors of ant,each ant moves at random,pheromone is deposited on path,ants detect lead ants path,inclined to follow,more pheromone on path,increases probability,of path being followed,作为与遗传算法同属一类的通用型随机优化方法，蚁群算法,不需要任何先验知识,，最初只是随机地选择搜索路径，随着对解空间的“了解”，搜索变得有规律，并逐渐逼近直至最终达到全局最优解。蚁群算法对搜索空间的“了解”机制主要包括三个方面：,(1)蚂蚁的记忆。一只蚂蚁搜索过的路径在下次搜索时就不会再被选择，由此在蚁群算法中建立tabu(禁忌)列表来进行模拟；,(2)蚂蚁利用信息素进行相互通信。蚂蚁在所选择的路径上会释放一种叫做信息素的物质，当同伴进行路径选择时，会根据路径上的信息素进行选择，这样信息素就成为蚂蚁之间进行通讯的媒介。,(3)蚂蚁的集群活动。通过一只蚂蚁的运动很难到达食物源，但整个蚁群进行搜索就完全不同。当某些路径上通过的蚂蚁越来越多时，在路径上留下的信息素数量也越来越多，导致信息素强度增大，蚂蚁选择该路径的概率随之增加，从而进一步增加该路径的信息素强度，,而某些路径上通过的蚂蚁较少时，路径上的信息素就会随时间的推移而蒸发,。因此，模拟这种现象即可利用群体智能建立路径选择机制，使蚁群算法的搜索向最优解推进。,The Algorithm,Used to solve TSP,Transition from city i to j depends on:,-,Tabu list: list of cities having visited,-,Visibility = 1/d,ij,; 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 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; allowed,k,= N tabu,k,The Algorithm,Pheromone update :,: a coefficient such that represents the evaporation 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,L,k,: the tour length of the,k,th ant,The Algorithm,Three types of,* ant-quantity system:,The Algorithm,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,1,4,3,2,5,d,AB,=100; d,BC,= 60; d,DE,=150,TSP Example,A,E,D,C,B,1,A,5,E,3,C,2,B,4,D,TSP Example,Iteration 1,A,E,D,C,B,1,A,1,A,1,A,1,A,1,A,D,TSP Example,TSP Example,A,E,D,C,B,3,C,B,5,E,A,1,A,D,2,B,C,4,D,E,Iteration 2,TSP Example,A,E,D,C,B,4,D,E,A,5,E,A,B,3,C,B,E,2,B,C,D,1,A,D,C,Iteration 3,A,E,D,C,B,4,D,E,A,B,2,B,C,D,A,5,E,A,B,C,1,A,DCE,3,C,B,E,D,TSP Example,Iteration 4,A,E,D,C,B,1,A,D,C,E,B,3,C,B,E,D,A,4,D,E,A,B,C,2,B,C,D,A,E,5,E,A,B,C,D,TSP Example,Iteration 5,1,A,D,C,E,B,5,E,A,B,C,D,L,1,=300,L,2,=450,L,3,=260,L,4,=280,L,5,=420,2,B,C,D,A,E,3,C,B,E,D,A,4,D,E,A,B,C,TSP Example,End of First Run,All ants die,New ants are born,Save 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 tabu,k,(s),Compute the length L,k,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 list management,Move k-th ant to town j. Insert town j in tabu,k,(s),Set t = t + n; NC=NC+1; ,ij,=0,NCNC,max,&,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 (demands, 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),*,Customers (Demands,time windows),VRPTW Example,Relation with TSP?!,Depot,Depots,8:00-12:30,8:15-9:30,10:00-11:45,8:00-9:00,10:00-11:15,11:00-11:30,8:30-10:30,10:15-11:45,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 customer.,-,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.,Disadvantages,Slower convergence than other Heuristics,Performed poorly for TSP problems larger than 75 cities.,No centralized processor to guide the AS towards good solutions,Improvements,Elitist strategy,AS,rank,ACS,MMAS,