《蚁群算法原理与应用1》由会员分享，可在线阅读，更多相关《蚁群算法原理与应用1（61页珍藏版）》请在金锄头文库上搜索。
1、自然计算与群体智能赵林亮计算机应用技术研究所 zhaollacm.org1蚁群算法赵林亮计算机应用技术研究所 zhaollacm.org2参考文献APPEARED IN PROCEEDINGS OF ECAL91-EUROPEAN CONFERENCE ON ARTIFICIAL LIFE, PARIS, FRANCE, ELSEVIER PUBLISHING,134142. Distributed Optimization by Ant Colonies Alberto Colorni, Marco Dorigo, Vittorio Maniezzo Dipartimento di Elet
2、tronica, Politecnico di Milano Piazza Leonardo da Vinci 32, 20133 Milano, ItalyIEEE Transactions on Systems, Man, And Cybernetics- Part B: Cybernetics,Vol.26, No.1, Feb 1996. 29-41 Ant System: Optimization by a Colony of Cooperating Agents Marco Dorigo, Member, IEEE, Vittorio Maniezzo, and Alberto C
3、olornihttp:/iridia.ulb.ac.be/mdorigo/HomePageDorigo/3Fig. 1. An example with real antsa) Ants follow a path between points A and E. b) An obstacle is interposed; ants can choose to go around it following one of the two different paths with equal probability. c) On the shorter path more pheromone is
4、laid down.4Fig. 2. An example with artificial antsa) The initial graph with distances. b) At time t=0 there is no trail on the graph edges; therefore, ants choose whether to turn right or left with equal probability. c) At time t=1 trail is stronger on shorter edges, which are therefore, in the aver
5、age, preferred by ants. 5双桥实验(Goss S, 1989)Naturwissenschaften 76, 579-581 (1989) Self-organized Shortcuts in the Argentine Ant S. Goss, S. Aron, J. L. Deneubourg, and J. M. Pasteels Unit of Behavioural Ecology, C.P. 231, Universit6 Libre de Bruxelles, B- 1050 Bruxelles6Fig. 1. A colony of I humilis
6、 selecting the short branches on both modules of the bridgea) one module of the bridge b) and c): photos taken 4 and 8 min after placement of the bridge7双桥实验数学模型假设条件：1、非对称桥上的信息量与过去一个时间段内经过该桥的蚂蚁数目成正比；2、某一时刻蚂蚁按照桥上残留的信息量多少来选择其中某座桥3、经过该桥的蚂蚁数目越多则桥上的残留信息量就越大设短桥为A，长桥为B，mA和mB分别表示经过桥A和桥B的蚂蚁数目mA + mB = m当所有m只
7、蚂蚁都经过两座桥之后，第m+1只蚂蚁选择桥A的概率为：而选择桥B的概率为：8 参数h 和 k用以匹配真实实验数据 第m+1只蚂蚁首先计算 然后生成一个在区间0,1上均匀分布的随机数 若 ，则选择桥A，否则选择桥B9基本蚁群算法的数学模型10P、NP、NP-C、NP-hard问题 P类问题 所有可用DTM (Deterministic one-tape Turing Machine) 在多项式时间内求解的判定问题的 集合。简记为O(p(n) 即 P=L: 存在一个多项式时间DTM程序M，是 的L=LM , 其中LM表示程序M所识别的语言。 若存在一个多项式时间DTM程序，它在编码策 略e之下求解
8、判定问题，即L, eP,则称该 判定问题属于P类问题。11P、NP、NP-C、NP-hard问题 NP类问题 (Non-deterministic Polynomial) 若存在一个多项式函数 g(x) 和一个验证算法H, 对一类判定问题A的任何一个“是”回答，满足 其输入长度d(s)不超过g(d(I), 其中d(I)为I的输 入长度，且验证算法中S为I的“是”回答的计算 时间不超过g(d(I), 则称判定问题A为非多项式 确定问题。 NP类问题是所有可用NDTM (Non- Deterministic one-tape Turing Machine)在多项 式时间内求解的判定问题的集合12P
9、、NP、NP-C、NP-hard问题 NP-C类问题 (NP-Complete) 是NP类中最困难的一类问题。 有重要实际意义和工程背景 TSP (Traveling Salesman Problem) Symmetric; Asymmetric NP-hard类问题 NP-C NP-hardNPPNP-hardNP-C13基本蚁群算法模型 基本假设 蚂蚁之间通过信息素和环境进行通信。每只蚂 蚁仅根据其周围的局部环境作出反应，也只对 周围的局部环境产生影响； 蚂蚁对环境的反应由其内部模式决定。即蚂蚁 是反应型适应性主体 在个体水平上，每只蚂蚁仅根据环境做出独立 选择；在群体水平上，单只蚂蚁的行
10、为是随机 的，但蚁群可通过自组织过程形成高度有序的 群体行为。14TSP (Traveling Salesman Problem) 有向图 有向图D的三元组为 (V, E, f)，其中V是一个非 空集合，其元素称为有向图的结点；E是一个 集合，其元素称为有向图的弧段（边）；f是从 E到VxV上的一个映射（函数）。 E中的元素总是和V中的序偶对有对应关系，可 用V中的序偶代替E中的元素。 一个有向图可简记为(V, E).15TSP (Traveling Salesman Problem) TSP 设C=c1, c2, , cn 是n个城市的集合， L=lij|ci, cj C是集合C中的元素（城
11、市）两两连接的 集合， dij(i, j=1,1,n)是lij的Euclidean距离，即G=(C, L)是一个有向图，TSP的目的是从有向图G中寻 出长度最短的Hamilton圈， 即一条对C=c1, c2, , cn中n个元素（城市）访问且 只访问一次的最短封闭曲线16TSP (Traveling Salesman Problem) TSP简单形象描述 给定n个城市，一个旅行商从某一城市出发，访问各城 市一次且仅有一次后再回到原出发城市，要求找出一 条最短的巡回路径 可分为对称TSP (Symmetric Traveling Salesman Problem) 和非对称TSP (Asymm
12、etric Traveling Salesman Problem) TSP是NP-C问题 n城市规模的TSP，存在(n-1)!/2条不同闭合路径 。17基本蚁群算法数学模型 设bi(t)表示t时刻位于元素i的蚂蚁数目，ij (t)为t 时刻路径(i, j)上的信息量，n表示TSP规模，m为 蚁群中蚂蚁总数，则是t时刻集合C中元素（城 市）两两连接lij上残留信息量的集合，在初始时刻 各条路径上的信息量相等，并设ij(0)=const, 基本 蚁群算法的寻优是通过有向图g=(C, L, )实现的 。18 蚂蚁k(k=1,2,m)在运动过程中，根据各条路径上的信息 量决定其转移方向。这里用禁忌表t
13、abuk来记录蚂蚁k当前 所走过的城市，集合随着tabuk进化过程做动态调整。在搜 索过程中，蚂蚁根据各条路径上的信息量及路径的启发信 息来计算状态转移概率。在t时刻蚂蚁k由元素（城市）i转 移到元素（城市）j的状态转移概率：19 其中allowedk=C-tabuk表示蚂蚁k下一步允许选择的城市 ；为信息启发式因子，表示轨迹的相对重要性，反映了 蚂蚁在运动过程中积累的信息在蚂蚁运动时所起的作用， 其值越大，则该蚂蚁越倾向于选择其它蚂蚁经过的路径， 蚂蚁之间的协作性越强；为期望启发式因子，表示能见 度的相对重要性，反映蚂蚁在运动过程中启发信息在蚂蚁 选择路径中的受重视程度，其值越大，则该状态状
14、态转移 概率越接近于贪心规则； ij(t)为启发函数， ij(t) =1/dij 式中dij表示相邻两个城市之间的距离。对蚂蚁k而言，dij 越小，则ij(t)越大，pijk也就越大。显然，该启发函数表示 蚂蚁从元素（城市）i转移到元素（城市）j的期望程度。20 为了避免残留信息素过多引起残留信息淹没启发信息， 在每只蚂蚁走完一步或者完成对所有n个城市的遍历(也 即一个循环结束)后，要对残留信息进行更新处理。这 种更新策略模仿了人类大脑记忆的特点，在新信息不断 存人大脑的同时，存储在大脑中的旧信息随着时间的推 移逐渐淡化，甚至忘记。由此，t+n时刻在路径(i, j)上 的信息量可按如下规则进行
15、调整 21 式中，表示信息素挥发系数，则1-表示信息素 残留因子，为了防止信息的无限积累， 的取值 范围为0，1), ij(t)表示本次循环中路径(i, j)上的 信息素增量，初始时刻ij(t) =0, ijk(t) 表示第k 只蚂蚁在本次循环中留在路径(i, j)上的信息量。 根据信息素更新策略的不同，Dorigo M提出了三 种不同的基本蚁群算法模型，分别称之为Ant- Cycle模型、Ant-Quantity模型及Ant-Density模型 ，其差别在于ijk(t)求法的不同。 22 Ant-Cycle模型 式中，Q表示信息素强度，它在一定程度上影响 算法的收敛速度；Lk表示第k只蚂蚁在
16、本次循环中 所走路径的总长度。23 Ant-Quantity模型 24 Ant-Density模型 区别： 式(5)和式(6)中利用的是局部信息，即蚂蚁完成一步后 更新路径上的信息素；而式(4)中利用的是整体信息， 即蚂蚁完成一个循环后更新所有路径上的信息素，在 求解TSP时性能较好，因此通常采用式(4)作为蚁群算 法的基本模型。25基本蚁群算法的实现 以TSP为例，基本蚁群算法的具体实现步骤 如下： (1)参数初始化。令时间t=0和循环次数Nc=0，设 置最大循环次数Ncmax, 将m个蚂蚁置于n个元素( 城市)上，令有向图上每条边(i, j)的初始化信息 量ij(t)=const, 其中const表示常数，且初始时刻 ij(0)=0(2)
