《蚁群算法及其在路径规划中的应用》由会员分享，可在线阅读，更多相关《蚁群算法及其在路径规划中的应用（33页珍藏版）》请在金锄头文库上搜索。
1、蚁群算法及其在路径规划中的应用 Q. Song 2011. 4. 6 Swarm Intelligence oDumb parts, properly connected into a swarm, yield smart results. Kevin Kelly Algorithms inspired from insects oAnt Colony Optimization (ACO) oParticle Swarm Optimization (PSO) oFish Swarm (FS) Two bridges experiment ofrom nest to food constrain
2、ed to move in two asymmetric paths Principles o蚁群算法的基本原理源于昆虫学家们的观察和发现,生物界中的蚂 蚁在搜索食物源时,能够在其走过的路径上释放一种蚂蚁特有的分 泌物(pheromone)信息激素,使得一定范围内的其它蚂蚁能够觉 察并影响其行为。当某些路径上走过的蚂蚁越来越多时,留下的这 种信息激素也越多,以致后来蚂蚁选择该路径的概率也越高,从而 增加了该路径的吸引强度,蚂蚁群体就是靠着这种内部的生物协同 机制形成了一条它们自己并未意识到的最短路线。 Behaviors of ant each ant moves at random, phe
3、romone is deposited on path ants detect lead ants path, inclined to follow more pheromone on path increases probability of path being followed o作为与遗传算法同属一类的通用型随机优化方法，蚁群算法不需 要任何先验知识，最初只是随机地选择搜索路径，随着对解空间 的“了解”，搜索变得有规律，并逐渐逼近直至最终达到全局最优解 。蚁群算法对搜索空间的“了解”机制主要包括三个方面： o(1)蚂蚁的记忆。一只蚂蚁搜索过的路径在下次搜索时就不会再被 选择，由此在蚁群
4、算法中建立tabu(禁忌)列表来进行模拟； o(2)蚂蚁利用信息素进行相互通信。蚂蚁在所选择的路径上会释放 一种叫做信息素的物质，当同伴进行路径选择时，会根据路径上 的信息素进行选择，这样信息素就成为蚂蚁之间进行通讯的媒介 。 o(3)蚂蚁的集群活动。通过一只蚂蚁的运动很难到达食物源，但整 个蚁群进行搜索就完全不同。当某些路径上通过的蚂蚁越来越多 时，在路径上留下的信息素数量也越来越多，导致信息素强度增 大，蚂蚁选择该路径的概率随之增加，从而进一步增加该路径的 信息素强度，而某些路径上通过的蚂蚁较少时，路径上的信息素 就会随时间的推移而蒸发。因此，模拟这种现象即可利用群体智 能建立路径选择机制
5、，使蚁群算法的搜索向最优解推进。 The Algorithm 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 desir
6、ability 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; allowedk= N tabuk The Algorithm Pheromone update : : a coefficient
7、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 oThree types of * ant-cycle system: Q: a constant Lk: the tour length of the kth ant The Algorithm oThree types o
8、f * ant-quantity system: The Algorithm oThree types of * ant-density system: The Algorithm oDifference 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
9、 2 5 dAB =100; dBC = 60; dDE =150 A E D C B 1 A 5 E 3 C 2 B 4 D Iteration 1 A E D C B 1 A 1 A 1 A 1 A 1 A,D A E D C B 3 C,B 5 E,A 1 A,D 2 B,C 4 D,E Iteration 2 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 Iteration 4 A E D C
10、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 Iteration 5 1 A,D,C,E,B 5 E,A,B,C,D L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 2 B,C,D,A,E 3 C,B,E,D,A 4 D,E,A,B,C End of First Run All ants die New ants are born Save Best Tour (Sequence and length) t = 0; NC = 0; ij(t)=c for ij=0 Place the
11、 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 list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=
12、NC+1; ij=0 NCNCmax & not stagn. Yes End No Yes VRPTW Example oN customers are to be visited by K vehicles oGiven * Depots (number, location) * Vehicles (capacity, costs, time to leave, time on road.) * Customers (demands, time windows, priority, .) * Route Information (maximum route time or distance
13、, cost on the route) VRPTW Example oObjective Functions to Minimize * Total travel distance * Total travel time * Number of vehicles oSubject to: * Vehicles ( # ,Capacity,time on road,trip length) * Depots (Numbers) * Customers (Demands,time windows) VRPTW Example oRelation with TSP?! DepotDepots 8:
14、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 oSimple 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 depo
15、t as your next customer. - Improve by local search. - Only best ants update pheromone trial. Advantages oPositive Feedback accounts for rapid discovery of good solutions. oDistributed computation avoids premature convergence. oThe greedy heuristic helps find acceptable solution in the early solution in the early stages of the search process. oThe collective interaction of a population of agents. Disadvantages oSlower convergence than other Heuristics oPerformed poorly for TSP problems larger than 75 cities. oNo c
