优化设计-蚁群算法

蚁群算法算法起源一蚁群优化算法概念二蚁群算法与TSP问题四蚁群算法本质三一算法起源01蚁群算法(antcolonyoptimization,ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。02它由MarcoDorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。一算法起源MacroDorigo03蚁群算法提出者一算法起源巢穴食物巢穴巢穴食物食物图1现实中的蚂蚁寻找食物二蚁群优化算法相关概念01蚁群算法提出者蚁群算法原理蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为外激素(pheromone)的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。二蚁群优化算法相关概念02蚁群算法提出者蚂蚁觅食过程在蚁群寻找食物时，它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素。当它们碰到一个还没有走过的路口时．就随机地挑选一条路径前行。与此同时释放出与路径长度有关的信息素。路径越长，释放的激索浓度越低.当后来的蚂蚁再次碰到这个路口的时候．选择激素浓度较高路径概率就会相对较大。这样形成一个正反馈。最优路径上的激索浓度越来越大．而其它的路径上激素浓度却会随着时间的流逝而消减。最终整个蚁群会找出最优路径。二蚁群优化算法相关概念03蚁群算法提出者蚂蚁觅食简化过程蚂蚁从A点出发，速度相同，食物在D点，可能随机选择路线ABD或ACD。假设初始时每条分配路线一只蚂蚁，每个时间单位行走一步，本图为经过9个时间单位时的情形：走ABD的蚂蚁到达终点，而走ACD的蚂蚁刚好走到C点，为一半路程。蚁群算法提出者本图为从开始算起，经过18个时间单位时的情形：走ABD的蚂蚁到达终点后得到食物又返回了起点A，而走ACD的蚂蚁刚好走到D点。蚁群优化算法相关概念蚁群算法提出者假设蚂蚁每经过一处所留下的信息素为一个单位，则经过36个时间单位后，所有开始一起出发的蚂蚁都经过不同路径从D点取得了食物，此时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路线。这是正反馈效应。蚁群优化算法相关概念蚁群算法提出者信息素的更新方式有2种：挥发：也就是所有路径上的信息素以一定的比率进行减少，模拟自然蚁群的信息素随时间挥发的过程；增强：给评价值“好”(有蚂蚁走过)的边增加信息素。蚁群算法提出者多样性：蚂蚁在觅食的时候路线不一，随机性的向着某个方向行走，打破常规，进行创新。正反馈：优化的路线不断被保存并加大自身概率，保证了相对优良的信息能够被保存下来。多样性保证了系统的创新能力，正反馈保证了优良特性能够得到强化，两者要恰到好处的结合。蚂蚁简单规则的两个方面：二蚁群优化算法相关概念04蚁群算法提出者蚁群的基本信息范围：蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径（一般是3），那么它能观察到的范围就是3*3个方格世界，并且能移动的距离也在这个范围之内。环境：蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有别的蚂蚁，还有信息素，信息素有两种，一种是找到食物的蚂蚁洒下的食物信息素，一种是找到窝的蚂蚁洒下的窝的信息素。每个蚂蚁都仅仅能感知它范围内的环境信息。环境以一定的速率让信息素消失。蚁优化算法相关概念蚁群算法提出者觅食规则：在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直接过去。否则看是否有信息素，并且比较在能感知的范围内哪一点的信息素最多，这样，它就朝信息素多的地方走，并且每只蚂蚁都会以小概率犯错误，从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样，只不过它对窝的信息素做出反应，而对食物信息素没反应。移动规则：每只蚂蚁都朝向信息素最多的方向移，并且，当周围没有信息素指引的时候，蚂蚁会按照自己原来运动的方向惯性的运动下去，并且，在运动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈，它会记住最近刚走过了哪些点，如果发现要走的下一点已经在最近走过了，它就会尽量避开。播撒信息素规则：每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多，并随着它走远的距离，播撒的信息素越来越少。蚁优化算法相关概念蚁群算法提出者根据这几条规则，蚂蚁之间并没有直接的关系，但是每只蚂蚁都和环境发生交互，而通过信息素这个纽带，实际上把各个蚂蚁之间关联起来了。比如，当一只蚂蚁找到了食物，它并没有直接告诉其它蚂蚁这儿有食物，而是向环境播撒信息素，当其它的蚂蚁经过它附近的时候，就会感觉到信息素的存在，进而根据信息素的指引找到了食物。为什么蚂蚁可以找到食物05蚂蚁正常行进，突然环境变化，增加了障碍物蚂蚁以同等概率选择各条路径，紧接着，随着时间的增加较短路径信息浓度高，选择该路径的蚂蚁逐渐增多。蚂蚁最终绕过障碍物找到最优路径三蚁群算法本质蚁群算法提出者选择机制：信息素越多的路径，被选择的概率越大；更新机制：路径上的信息素会随蚂蚁的经过次数增加而增长，而且同时也会随时间的推移逐渐挥发消失；协调机制：蚂蚁之间实际上是通过信息素来相互通信、协同工作的。蚁群算法本质蚁群算法提出者作为一种应用于组合优化问题的算法，基本蚁群算法的逻辑结构（如下图所示）可以表述为：先将具体的优化组合问题表述成规范的格式，然后利用蚁群算法在“探索”和“利用”之间根据信息素这一反馈载体确定决策点，同时按照相应的信息素更新规则对每只蚂蚁个体的信息素进行增量构建，随后从整体角度规划出蚁群活动的行为方向，周而复始，即可求出组合优化问题的最优解。基本蚁群算法的逻辑结构01蚁群算法提出者TSP问题四蚁群算法与TSP问题TSP问题又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路经的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。02蚁群算法提出者模型建立四蚁群算法与TSP问题现实蚂蚁在觅食过程中主要按照所处环境的信息素量来决定前进方向，在算法构造过程中，信息素被抽象为图的边上的轨迹，蚂蚁到达每一节点处根据边上的信息素浓度选择下一节点。蚂蚁从初始节点（巢穴）按照一定转移概率选择下一节点，最终选择行走到目标节点（食物源），这样便得到了TSP问题的一个可行解。给出一个n个城市组成的集合，TSP问题可以被描述为访问每个城市一次找到最短路程的封闭式旅行问题。bi(t)(i=1,...,n)表示t时刻在城市i中的蚂蚁数量，m=是蚂蚁的总数。tij(t)为t时刻从城市i到城市j路径上的信息量，tij(0)可以设置为任意数值（在实验中是每条路径上的一个很小的数值）。城市i和城市j之间的距离定义为dij（dij=[(xi-xj)2+(yi-yj)2]1/2）。为了约束蚂蚁访问所有的城市而不重复访问（即确定一个n城市的循环），我们为每个蚂蚁定义一个数据结构用于记录蚂蚁k访问过的城市，称为禁忌表tabuk。在蚂蚁行动过程中tabuk动态调整，当一次循环结束后清空禁忌表，蚂蚁重新选择路径，重新填充禁忌表。四蚁群算法与TSP问题四蚁群算法与TSP问题在行进过程中，蚂蚁根据每条路径上的信息素量及路径的启发信息来计算转移概率pij。启发函数hij等于1/dij，表示蚂蚁从城市i转移到城市j的期望程度。城市i到城市j的转移概率定义为kallowedsisisijijtt][*)]([][*)]([pij(4-1)其中，allowedk={C-tabuk}表示蚂蚁k下一步允许选择的城市。a和b分别是表示允许用户控制轨迹和能见度的相对重要性的参数，a反映了蚂蚁在运动过程中所积累的信息在运动时所起的作用，b反映了蚂蚁在运动过程中启发信息在选择路径时的受重视程度。四蚁群算法与TSP问题(4-2)tij(t+n)=(1-ρ)*tij(t)+Dtij(t)Dtij(t)=(t)Δτijkm1k(4-3)ρ—表示信息素挥发系数1-ρ—表示信息素残留因子Dtijk(t)—表示第k只蚂蚁在本次循环中留在路径(i,j)上的信息素量四蚁群算法与TSP问题按的不同取法，可形成三种类型的蚂蚁算法模型：（1）Ant-CircleSystem模型，有式中，Q为常量，为第k只蚂蚁在本次循环中所走路径的长度。（2）Ant-QuantitySystem模型ijkij,kij0kkQL若第只蚂蚁在本次循环中经过，否则ijij,ktt+1ijd0kQ若第只蚂蚁在时刻和之间经过，否则kL（4-4）（4-5）四蚁群算法与TSP问题（3）Ant-DensitySystem模型很明显在后两种模型中，利用的都是局部信息，而第一种模型利用的是整体信息。这三种模型在求解不同问题时各有优势。ij,ktt+1ij0kQ若第只蚂蚁在时刻和之间经过，否则（4-6）四蚁群算法与TSP问题03算法运行步骤1.参数初始化：令t=0设置最大循环次数NcMax，循环次数Nc=0将m只蚂蚁置于n个节点上，在每个节点i放置bi(t)只蚂蚁初始化每条边(i,j)上的信息素量tij(0)=c为一个常量，初始时刻Dtijk(0)=0初始化禁忌表tabuk及路线表routek2.设置索引号s=1，对k=1~m将蚂蚁k的起始城市放入禁忌表中，并重复以下步骤直至禁忌表填充完整：对k=1~m，利用式(4.1)计算转移概率pij，根据伪随机比例规则选择下一城市，将蚂蚁k移动到下一城市j并将其填入禁忌表，同时记录蚂蚁k的路线s++四蚁群算法与TSP问题3.对k=1~m，根据routek的记录计算蚂蚁k所走循环路径的总长度，找到最佳路线4.按式(4-2)计算每只蚂蚁的信息素增量Dtijk(t)5.更新每条路径上的信息素量tij(t+n)6.清空禁忌表及路线表7.Nc++，若NcNcMax，返回步骤2，否则，循环结束，输出结果蚁群算法提出者五蚁群算法与TSP问题基于JSP问题的蚁群算法流程开始初始化索引号s=1k=k+1蚂蚁k=1利用式(4.1)计算转移概率pij，选择下一节点j修改禁忌表，记录路线s=s+1根据记录计算长度，记录最短路径按式(4-3)(4-4)更新每条路径上的信息素量k≥蚂蚁总数mNYs≥nNY清空禁忌表及路线表NcNcMaxNc++输出结果，结束YN蚁群算法提出者五蚁群算法与TSP问题蚁群算法所研究问题谢谢！！！