第5章蚁群算法课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,5,蚁群算法,Ant Colony Optimization,5 蚁群算法 Ant Colony Optimizatio,2,2,3,目录,1,、蚁群算法起源,2,、蚁群算法模型,3,、实例仿真,4,、蚁群算法特点,5,、总结,3 目录1,第5章蚁群算法课件,双桥实验,双桥实验,蚁群优化（ant colony optimization,ACO）是20世纪90年代初由意大利学者M.Dorigo等通过模拟蚂蚁的行为而提出的一种,随机优化技术,（,寻找优化路径的机率型算法,）。,研究主要是以蚂蚁寻找食物之后能选择一条最短路径来连接蚁穴和食物源。,1991,年，M.Dorigo在法国巴黎第一届欧洲人工生命会议上最早提出了蚁群算法的基本模型，,1992,年又在其博士论文中进一步阐述了蚁群算法的核心思想。,Macro Dorigo,1.,蚁群算法起源,蚁群优化（ant colony optimization,A,蚂蚁觅食过程,在蚁群寻找食物时，能够在它所经过的路径上留下一种称之为,信息素,(pheromone),的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息,正反馈现象,：,某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。,最优路径上的信息素浓度越来越大，而其它的路径上激素浓度却会随着时间的流逝而消减。最终整个蚁群会找出最优路径。,蚂蚁觅食过程在蚁群寻找食物时，能够在它所经过的路径上留下一种,A,点为蚁穴，食物在,D,点，可能随机选择路线,ABD,或,ACD,。假设初始时每条路线有一只蚂蚁，每个时间单位行走一步，本图为经过,9,个时间单位时的情形：走,ABD,的蚂蚁到达食物，而走,ACD,的蚂蚁刚好走到,C,点，为一半路程。,简化的蚂蚁寻食过程,A点为蚁穴，食物在D点，可能随机选择路线ABD或ACD。假设,本图为从开始算起，经过,18,个时间单位时的情形：走,ABD,的蚂蚁到达,D,点后得到食物又返回了起点,A,，而走,ACD,的蚂蚁刚好走到,D,点。,本图为从开始算起，经过18个时间单位时的情,假设蚂蚁每经过一处所留下的信息素为一个单位，则经过,36,个时间单位后，,ABD,的路线往返了,2,趟，每一处的信息素为,4,个单位，而,ACD,的路线往返了一趟，每一处的信息素为,2,个单位，其比值为,2,：,1,。,按信息素的指导，,ABD,路线增加一只蚂蚁（共,2,只），,ACD,路线仍为一只蚂蚁。再经过,36,个时间单位后，两条线路上的信息素为,12,和,4,，比值为,3,：,1,。,于是，,ABD,路线增加一只蚂蚁（共,3,只），,ACD,路线仍为一只蚂蚁。再经过,36,个时间单位后，两条线路上的信息素为,24,和,6,，比值为,4,：,1,。,若继续进行，则按信息素的指导，最终所有的蚂蚁会放弃,ACD,路线，而都选择,ABD,路线。,假设蚂蚁每经过一处所留下的信息素为一个单位,蚁群算法通常用于求解复杂的,组合优化问题,。所谓组合优化,是指在离散的、有限的数学结构上,寻找一个满足给定条件,并使其目标函数值达到最大或最小的解,.,理论假设,1,、蚁群之间通过信息素和环境进行通信。,2,、蚂蚁对环境的反应由其内部模式决定。,3,、个体水平上，每个蚂蚁相对独立；群体水平 上，每只蚂蚁的行为是随机的。,2.,蚁群算法模型,蚁群算法通常用于求解复杂的组合优化问题。所谓组合优化,是指在,算法规则,12,1.,范围,蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径（一般是,3,），那么它能观察到的范围就是,3*3,个方格世界，并且能移动的距离也在这个范围之内。,算法规则121.范围蚂蚁观察到的范围是一个方格世界，蚂蚁有,13,2.,环境,蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有别的蚂蚁，还有信息素，信息素有两种，一种是找到食物的蚂蚁洒下的食物信息素，一种是找到窝的蚂蚁洒下的窝的信息素。每个蚂蚁都仅仅能感知它范围内环境信息。环境以一定的速率让信息素消失 。,132.环境 蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，,14,3.,觅食规则,在每只蚂蚁能感知的范围内寻找是否有食 物，如果有就直接过去。否则看是否有信息素，并且比较在能感知的范围内哪一点的信息素最多，这样，它就朝信息素多的地方走，并且每只蚂蚁都会以小概率犯错误，从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样，只不过它对窝的信息素做出反应，而对食物信息素没反应。,143.觅食规则 在每只蚂蚁能感知的范围内寻找是否有食,15,4.,移动规则,每只蚂蚁都朝向信息素最多的方向移，并且，当周围没有信息素指引的时候，蚂蚁会按照自己原来运动的方向惯性的运动下去，并且，在运动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈，它会记住最近刚走过了哪些点，如果发现要走的下一点已经在最近走过了，它就会尽量避开。,154.移动规则每只蚂蚁都朝向信息素最多的方向移，并且，当,16,5.,避障规则,如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，并且有信息素指引的话，它会按照觅食的规则行为。,165.避障规则如果蚂蚁要移动的方向有障碍物挡住，它会随机,17,6.,播撒信息素规则,每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多，并随着它走远的距离，播撒的信息素越来越少。,176.播撒信息素规则每只蚂蚁在刚找到食物或者窝的时候撒发,现以平面上,n,个城市的旅行商问题（,Traveling Salesman Problem,，,TSP,）为例说明基本蚁群算法模型。,旅行商问题：一商人去,n,个城市销货，所有城市走一遍再回到起点，使所走路程最短。,TSP,在许多工程领域具有广泛的应用价值，例如电路板布线、,VLSI,芯片设计、机器人控制、网络路由等。随着城市数目的增多,问题空间将呈指数级增长。,现以平面上n个城市的旅行商问题（ Traveling Sal,TSP,问题的数学描述,TSP,问题表示为一个,N,个城市的有向图,G=,（,N,，,A,），其中,城市之间距离,目标函数为,其中， ，为城市,1,2,，,n,的,一个排列， 。,TSP问题的数学描述TSP问题表示为一个N个城市的有向图G=,蚁群算法求解,TSP,下面以,TSP,为例说明基本蚁群算法模型。,首先将,m,只蚂蚁随机放置在,n,个城市，通常,： ，,m,只蚂蚁同时由一个城市运动到下一个城市，逐步完成它们的搜索过程。整个算法的迭代过程以,N,为刻度， ， 为预设的最大迭代次数。每次迭代过程中以,t,为刻度， ，蚂蚁,k,根据概率转换规则选择下一个城市，由此生成一个由,n,个城市组成的行动路线，并伴随信息素的更新。,蚁群算法求解TSP下面以TSP为例说明基本蚁群算法模型。,（,2,）能见度,定义为距离的倒数，即,代表由城市,i,到城市,j,的,启发性愿望,，距离越短，能见度越大，被选择的愿望越大，由此引导蚂蚁搜索。其信息是固定的。,（,3,）虚拟信息素,当由城市,i,选择城市,j,后，将在,ij,路径上留下虚拟信息素 ，代表由城市,i,到,j,的,获知性愿望,，是动态的全局信息，在线实时更新。,蚂蚁,k,由城市,i,转到城市,j,的决定因素：,（,1,）禁忌列表,该表用于存储第,k,只蚂蚁在当前时刻已访问过的所有城市，每只蚂蚁在选择下一个城市前，先检索该表来确定下一步可能选择的城市是否已经走过，如果走过就不在选择范围内，这样可以避免重复访问同一个城市。,（2）能见度定义为距离的倒数，即代表由城市i到城市j的启,信息素更新方式体现在,信息素的增加,和,信息素的挥发,两个方面。挥发系数,信息素更新公式如下：,表示当,m,个蚂蚁都选择了下一个城市后，所有选择由,i,到,j,的蚂蚁在该路径上遗留的信息素之和,表示第,k,只蚂蚁在路径,ij,上留下的信息素,为预设参数，表示信息素的强度,表示第,k,只蚂蚁在,t,时刻选择城市,j,后经过的所有城市构成的路径长度,信息素更新方式体现在信息素的增加和信息素的挥发两个方面。挥发,其中：,表示,ij,路径上的,信息素浓度,；,是,启发信息,，,能见度,；,和,反映了信息素与启发信息的相对重要性；,表示蚂蚁,k,已经访问过的城市列表，,禁忌列表,。,（,4,）概率转换规则,位于城市,i,的第,k,只蚂蚁选择下一个城市,j,的概率为,:,注意：处在同一城市,i,的两只蚂蚁，即使都按照上述概率选择下一个城市，结果也可能是不同的。,其中：（4）概率转换规则注意：处在同一城市i的两只蚂蚁，即使,系统在上述四个因素（,禁忌列表、能见度、虚拟信息素、概率转换规则,）的控制下，实现路径选择策略和信息素更新策略。,上述信息素更新方式与真实蚂蚁觅食过程最为接近，但是在解决,TSP,问题上，效果并不是特别理想。,Dorigo,针对信息素更新策略又给出了三种模型。,系统在上述四个因素（禁忌列表、能见度、虚拟信息素、概率转换规,蚁量系统（,Ant-Quantity,）,蚁密系统（,Ant-Density,）,蚁周系统（,Ant-Cycle,）,三种模型,它们的差别在于表达式,的不同,(,即更新信息素的方式和更新量不同,),。,Ant-Quantity,和,Ant-Density,模型都是利用,局部信息,，即,m,个蚂蚁都各自选完下一城市后，就对所走路径并行进行信息素更新，两者的区别仅仅在于更新的信息素量有所不同。,Ant-Cycle,模型是,所有蚂蚁选择完所有城市,完成一次迭代后，更新所有路径上的信息素，并且每只蚂蚁经过的路径所更新的信息素是相同的。,蚁量系统（Ant-Quantity）三种模型它们的差别在于表,蚁量算法,（,Ant-Quantity,）：,蚁密算法,（,Ant-Density,）：,蚁周算法,（,Ant-Cycle,）：,蚁量算法（ Ant-Quantity ）： 蚁密,27,通过实验表明，在这三种算法中：,Ant-Cycle,算法的效果最好，这是因为它用的是全局信息；而其余两种算法用的是局部信息。这种更新方法很好地保证了残留信息不至于无限累积，非最优路径会逐渐随时间推移被忘记,。,27 通过实验表明，在这三种算法中：Ant-Cycle,TSP,算法流程图,（,Ant-Cycle,）,k,是否等于,m,t,是否等于,n,N,是否等于,N,max,根据公式更新信息素,记录当前最优路径,T,+,和最优路径长度,L,+,禁忌表清零,输出最优路径,T,+,和最优路径长度,L,+,结束,设置参数各个参数，并计算各个城市之间的距离，生成距离矩阵,D,，生成禁忌列表及存储最优路径和最优路径长度的矩阵,T,+,和,L,+,开始,将,m,个蚂蚁随机分布到,n,个城市，并将蚂蚁所在的位置存储到禁忌表中，并令,N=0,令,t=0,N=N+1,令,k=0,t=t+1,令,k=k+1,第,k,个蚂蚁根据公式选择下一个城市，并更新禁忌表,N,N,N,Y,Y,Y,TSP算法流程图（ Ant-Cycle ）k是否等于mt是否,蚁群算法的误区与对策,29,误区一：利用最大概率确定被选城市。,蚁群算法的误区与对策29误区一：利用最大概率确定被选城市。,s,4,0.31,s,2,0.49,s,1,0.14,S,3,0.06,轮盘赌法（赌轮选择法）, 在,0, 1,区间内产生一个均匀分布的随机数,r,。, 若,r,q,1,则城市,x,1,被选中。, 若,q,k,-1,r,q,k,(2,k,N,),则城市,x,k,被选中。 其中的,q,i,称为城市,x,i,(,i,=1, 2,n,),的积累概率,其计算公式为,对策一,s4s2s1S3轮盘赌法（赌轮选择法）对策一,31,误区二：,Q,值的影响不大,31误区二： Q值的影响不大,32,对策二,32对策二,33,误区三：参数组合选择,33误区三：参数组合选择,34,对策三,34对策三,3.,实例仿真,采用靳潘教授所提出的,31,个城市的,CTSP,（求一条从北京出发经过中国,31,个省会城市及直辖市最后又回到北京的最短回路。,3.实例仿真采用靳潘教授所提出的31个城市的CTSP（求一条,36,36,下图对应,31,个城市的巡回路线为：北京,-,福州,-,南昌,-,合肥,-,杭州,-,南京,-,西安,-,台北,-,太原,-,呼和浩特,-,沈阳,-,上海,-,石家庄,-,长春,-,哈尔滨,-,济南,-,天津,-,武汉,-,郑州,-,长沙,-,银川,-,兰州,-,广州,-,海口,-,南宁,-,西宁,-,成都,-,乌鲁木齐,-,昆明,-,拉萨,-,贵阳,-,北京。,从仿真结果看最优解为,:,15708km,。,目前，公认的,TSP,问题,最优结果为,15398km,，虽然，不完全相等，但是结果比较相近，这说明蚂蚁算法虽然不是,TSP,问题的最好算法，但是依据蚂蚁觅食过程提出的蚁群算法具有一定的可行性。,下图对应31个城市的巡回路线为：北京-福州-南昌-合肥-杭州,一、蚁群大小,一般情况下蚁群中蚂蚁的个数不超过,TSP,图中节点的个数。,二、终止条件,1,给定一个外循环的最大数目；,2,当前最优解连续,K,次相同而停止，其中,K,是一个给定的整数，表示算法已经收敛，不再需要继续。,蚁群的规模及停止规则,一、蚁群大小蚁群的规模及停止规则,优化问题,蚂蚁觅食问题,各个状态,要遍历的各个路径,解,蚂蚁经过的一条完整路径,最优解,最短路径,各状态的吸引度,信息素的浓度,状态更新,信息素更新,目标函数,路径长度,蚂蚁觅食行为与优化问题的对照关系,优化问题蚂蚁觅食问题各个状态要遍历的各个路径解蚂蚁经过的一条, 其原理是一种,正反馈机制,或称,增强型学习系统,;,它通过【最优路径上蚂蚁数量的增加信息素强度增加后来蚂蚁选择概率增大最优路径上蚂蚁数量更,大,增加】达到最终收敛于最优路径上,。, 它是一种,通用型随机优化方法,它吸收了蚂蚁的行为特,点,它是使用人工蚂蚁仿真来求解问题,。,但人工蚂蚁决不是对实际蚂蚁的一种简单模拟,它融进了人类的智能,。具,有一定的记忆能力，能够记忆已经访问过的节点。选择路径时不是盲目的。而是按一定规律有意识地寻找最短路径。例如，在,TSP,问题中，可以预先知道当前城市到下一个目的地的距离。,4.,蚁群算法的特点, 其原理是一种正反馈机制或称增强型学习系统; 它通过【最, 它是一种,启发式算法,计算复杂性为,其中,Nc,是迭代次数, m,是蚂蚁数目, n,是目的节点数目,。, 它是一种,本质上的并行算法。, 它是一种,全局优化的方法,不仅可用于求解单目标优化问题,而且可用于求解多目标优化问题,。, 它是一种启发式算法, 计算复杂性为 它是一种本质上的并,蚁群算法还不像其它的启发式算法那样已形成系统的分析方法和具有坚实的数学基础。,参数的选择更多的是依靠实验和经验，没有定理来确定。,而且它的计算时间偏长，国内外的有关研究仍停留在实验探索阶段，但从当前的应用效果来看，这种模仿自然生物的新型系统寻优思想无疑具有十分光明的前景。,5.,总结,蚁群算法还不像其它的启发式算法那样已形成系统的分析方法和具有,发展趋势,如今的主要研究方向就是利用ACO算法去解决更加复杂的优化问题，包括：,1、动态问题，在问题求解过程中，它的实例数据，例如目标函数值、决策参数、约束条件都在发生变化。,2、随机问题，在这类问题中，由于不确定性、噪音、近似性或其他因素，人们只能得到目标函数值、决策参数值与约束条件的概率信息；,3、多目标问题，其中使用一个多目标函数作为评估解质量的标准。,发展趋势如今的主要研究方向就是利用ACO算法去解决更加复杂的,