人工智能07蚁群算法及其应用（PPT51页)

第七章蚁群算法及其应用蚁群算法的背景•20世纪50年代中期创立了仿生学，人们从生物进化的机理中受到启发。提出了许多用以解决复杂优化问题的新方法，如进化规划、进化策略、遗传算法等，这些算法成功地解决了一些实际问题。•蚁群算法从蚂蚁觅食得到启发。蚁群算法的背景•仿生算法•集群智能算法•概率型算法遗传算法、进化算法粒子群算法（课程论文2）、蚁群算法用来解决众多NP-hard问题蚁群算法的背景自然蚁群的自组织行为特征•高度结构化的组织——虽然蚂蚁的个体行为极其简单，但由个体组成的蚁群却构成高度结构化的社会组织，蚂蚁社会的成员有分工，有相互的通信和信息传递。•自然优化——蚁群在觅食过程中，在没有任何提示下总能找到从蚁巢到食物源之间的最短路径；当经过的路线上出现障碍物时，还能迅速找到新的最优路径。•信息正反馈——蚂蚁在寻找食物时，在其经过的路径上释放信息素（外激素）。蚂蚁基本没有视觉，但能在小范围内察觉同类散发的信息素的轨迹，由此来决定何去何从，并倾向于朝着信息素强度高的方向移动。•自催化行为——某条路径上走过的蚂蚁越多，留下的信息素也越多（随时间蒸发一部分），后来蚂蚁选择该路径的概率也越高。蚁群算法的背景•概念原型各个蚂蚁在没有事先告诉他们食物在什么地方的前提下开始寻找食物。当一只找到食物以后，它会向环境释放一种挥发性分泌物pheromone(称为信息素,该物质随着时间的推移会逐渐挥发消失，信息素浓度的大小表征路径的远近)来实现的，吸引其他的蚂蚁过来，这样越来越多的蚂蚁会找到食物。有些蚂蚁并没有像其它蚂蚁一样总重复同样的路，他们会另辟蹊径，如果另开辟的道路比原来的其他道路更短，那么，渐渐地，更多的蚂蚁被吸引到这条较短的路上来。最后，经过一段时间运行，就可能会出现一条最短的路径被大多数蚂蚁重复着。蚁群算法的提出•算法的提出蚁群算法（AntColonyOptimization,ACO），又称蚂蚁算法——一种用来在图中寻找优化路径的机率型算法。它由MarcoDorigo于1992年在他的博士论文“Antsystem:optimizationbyacolonyofcooperatingagents”中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。最早用于解决著名的旅行商问题(TSP,travelingsalesmanproblem)。蚁群算法的提出•基本原理蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为信息素(pheromone)的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。蚁群算法的提出•简化的蚂蚁寻食正反馈过程蚂蚁从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路线。这也就是前面所提到的正反馈效应。蚁群算法的提出•人工蚁群算法基于以上蚁群寻找食物时的最优路径选择问题，可以构造人工蚁群，来解决最优化问题，如TSP问题。人工蚁群中把具有简单功能的工作单元看作蚂蚁。二者的相似之处在于都是优先选择信息素浓度大的路径。较短路径的信息素浓度高，所以能够最终被所有蚂蚁选择，也就是最终的优化结果。两者的区别在于人工蚁群有一定的记忆能力，能够记忆已经访问过的节点。同时，人工蚁群在选择下一条路径的时候是按一定算法规律有意识地寻找最短路径，而不是盲目的。例如在TSP问题中，可以预先知道当前城市到下一个目的地的距离。人工蚁群VS自然蚁群蚁群算法的特征蚁群算法采用了分布式正反馈并行计算机制,易于与其他方法结合,并具有较强的鲁棒性。•（1）其原理是一种正反馈机制或称增强型学习系统；它通过信息素的不断更新达到最终收敛于近似最优路径上；•（2）它是一种通用型随机优化方法；但人工蚂蚁决不是对实际蚂蚁的一种简单模拟，它融进了人类的智能；•（3）它是一种分布式的优化方法；不仅适合目前的串行计算机，而且适合未来的并行计算机；•（4）它是一种全局优化的方法；不仅可用于求解单目标优化问题，而且可用于求解多目标优化问题；•（5）它是一种启发式算法；计算复杂性为O(NC*m*n2)，其中NC是迭代次数，m是蚂蚁数目，n是目的节点数目。蚁群算法的特征算法优点：•（1）求解问题的快速性——由正反馈机制决定•（2）全局优化性——由分布式计算决定，避免蚁群在寻优空间中过早收敛•（3）有限时间内答案的合理性——由贪婪式搜索模式决定，使能在搜索过程的早期就找到可以接受的较好解蚁群算法的基本思想算法流程图：开始初始化迭代次数Nc=Nc+1蚂蚁k=1蚂蚁k=k+1按照状态转移概率公式选择下一个元素修改禁忌表K=蚂蚁总数m？按照公式进行信息量更新满足结束条件？输出程序计算结果结束YYNN蚁群算法的基本思想以TSP问题为例：•1、根据具体问题设置多只蚂蚁，分头并行搜索。•2、每只蚂蚁完成一次周游后，在行进的路上释放信息素，信息素量与解的质量成正比。•3、蚂蚁路径的选择根据信息素强度大小（初始信息素量设为相等），同时考虑两点之间的距离，采用随机的局部搜索策略。这使得距离较短的边，其上的信息素量较大，后来的蚂蚁选择该边的概率也较大。蚁群算法的基本思想•4、每只蚂蚁只能走合法路线（经过每个城市1次且仅1次），为此设置禁忌表来控制。•5、所有蚂蚁都搜索完一次就是迭代一次，每迭代一次就对所有的边做一次信息素更新，原来的蚂蚁死掉，新的蚂蚁进行新一轮搜索。•6、更新信息素包括原有信息素的蒸发和经过的路径上信息素的增加。•7、达到预定的迭代步数，或出现停滞现象（所有蚂蚁都选择同样的路径，解不再变化），则算法结束，以当前最优解作为问题的解输出。蚁群算法的数学模型•TSP算例分析旅行商问题（TSP）给定n个城市和两个两个城市之间的距离，要求确定一条经过所有城市仅一次的最短路径。第一步:初始化将m只蚂蚁随机放到n个城市，每只蚂蚁的禁忌表为蚂蚁当前所在城市，各边信息素初始化为c。禁忌表体现了人工蚂蚁的记忆性，使得蚂蚁不会走重复道路，提高了效率。蚁群算法的数学模型第二步:选择路径路径在t时刻，蚂蚁k从城市i转移到城市j的概率为：蚁群算法的数学模型蚁群算法的数学模型蚁群的规模和停止规则•蚁群大小:一般情况下蚁群中蚂蚁的个数不超过TSP图中节点的个数。•终止条件:1给定一个外循环的最大数目，表明已经有足够的蚂蚁工作；2当前最优解连续K次相同而停止，其中K是一个给定的整数，表示算法已经收敛，不再需要继续；3目标值控制规则，给定优化问题（目标最小化）的一个下界和一个误差值，当算法得到的目标值同下界之差小于给定的误差值时，算法终止。第四步：输出结果若未达到终止条件则转步骤二，否则，输出目前的最优解。TSP应用举例TSP应用举例TSP应用举例TSP应用举例TSP应用举例TSP应用举例改进的蚁群优化算法▲最优解保留策略蚂蚁系统（带精英策略的蚂蚁系统ASelite）▲蚁群系统（ACS）▲最大-最小蚂蚁系统（MMAS）▲基于优化排序的蚂蚁系统（ASrank）▲最优最差蚂蚁系统（BWAS）▲一种新的自适应蚁群算法（AACA）▲基于混合行为的蚁群算法（HBACA）改进的蚁群算法•一般蚁群算法的框架主要有三个组成部分：1.蚁群的活动；2.信息素的挥发；3.信息素的增强；•主要体现在转移概率公式和信息素更新公式。（一）带精英策略的蚂蚁系统eliteAS特点——在信息素更新时给予当前最优解以额外的信息素量，使最优解得到更好的利用。找到全局最优解的蚂蚁称为“精英蚂蚁”。ijijijijtnt1否则是当前最优解的一部分若边,0,ΔijLQτgbijijτΔgbL——精英蚂蚁在边上增加的信息素量；ij——精英蚂蚁个数；——当前全局最优解路径长度。特点１、状态转移规则——伪随机比率规则)1,0(0q)1,0(q0qq设为常数，为随机数，如果，则蚂蚁转移的下一座城市是使取最大值的城市；若，仍按转移概率确定。βijαijtηtτ)]([)]([0qq２、全局更新规则——只有精英蚂蚁才允许释放信息素，即只有全局最优解所属的边才增加信息素。３、局部更新规则——蚂蚁每次从城市转移到城市后，边上的信息素适当减少。ijji,0q一般，取值较大。（二）蚁群系统ACS规则１和２都是为了使搜索过程更具有指导性，即使蚂蚁的搜索主要集中在当前找出的最好解邻域内。规则３则是为了使已选的边对后来的蚂蚁具有较小的影响力，以避免蚂蚁收敛到同一路径。（三）最大最小蚂蚁系统MMASmaxmin,关于的取值，没有确定的方法，有的书例子中取为0.01，10；有的书提出一个在最大值给定的情况下计算最小值的公式。1、每次迭代后，只对最优解所属路径上的信息素更新。特点2、对每条边的信息素量限制在范围内，目的是防止某一条路径上的信息素量远大于其余路径，避免过早收敛于局部最优解。maxmin,（四）基于优化排序的蚂蚁系统rankAS特点：每次迭代完成后，蚂蚁所经路径由小到大排序，并根据路径长度赋予不同的权重，路径越短权重越大。信息素更新时对考虑权重的影响。kij特点：主要是修改了ACS中的全局更新公式，增加对最差蚂蚁路径信息素的更新，对最差解进行削弱，使信息素差异进一步增大。（五）最优最差蚂蚁系统BWAS（六）一种新的自适应蚁群算法AACA特点：将ACS中的状态转移规则改为自适应伪随机比率规则，动态调整转移概率，以避免出现停滞现象。说明：在ACS的状态转移公式中，是给定的常数；在AACA中，是随平均节点分支数ANB而变化的变量。ANB较大，意味着下一步可选的城市较多，也变大，表示选择信息素和距离最好的边的可能性增大；反之减小。0q0q0q（七）基于混合行为的蚁群算法HBACA特点：按蚂蚁的行为特征将蚂蚁分成4类，称为4个子蚁群，各子蚁群按各自的转移规则行动，搜索路径，每迭代一次，更新当前最优解，按最优路径长度更新各条边上的信息素，如此直至算法结束。蚂蚁行为——蚂蚁在前进过程中，用以决定其下一步移动到哪个状态的规则集合。1、蚂蚁以随机方式选择下一步要到达的状态。2、蚂蚁以贪婪方式选择下一步要到达的状态。3、蚂蚁按信息素强度选择下一步要到达的状态。4、蚂蚁按信息素强度和城市间距离选择下一步要到达的状态。蚂蚁行为蚁群算法与遗传、模拟退火算法的比较实验结果表明：•1、蚁群算法所找出的解的质量最高，遗传算法次之，模拟退火算法最低。•2、蚁群算法的收敛速度最快，遗传算法次之，模拟退火算法最慢。蚁群算法之所以能够快速收敛到全局最优解，是因为该算法的个体之间不断进行信息交流和传递。单个个体容易收敛于局部最优，多个个体通过合作可以很快地收敛于解空间的最优解的附近。蚁群算法的应用•应用领域蚁群算法能够被用于解决大多数