人工智能07蚁群算法及其应用

1、第七章 蚁群算法及其应用蚁群算法法的背景景20世纪50年代中期期创立了了仿生学学，人们们从生物物进化的的机理中中受到启启发。提提出了许许多用以以解决复复杂优化化问题的的新方法法，如进进化规划划、进化化策略、遗传算算法等，这些算算法成功功地解决决了一些些实际问问题。蚁群算法法从蚂蚁蚁觅食得得到启发发。蚁群算法法的背景景仿生算法法集群智能能算法概率型算算法遗传算法法、进化化算法粒子群算算法（课课程论文文2）、蚁群算法法用来解决决众多NP-hard问题蚁群算法法的背景景自然蚁群群的自组组织行为为特征高度结构构化的组组织虽然蚂蚁蚁的个体体行为极极其简单单，但由由个体组组成的蚁蚁群却构构成高度度结构化化

2、的社会会组织，蚂蚁社社会的成成员有分分工，有有相互的的通信和和信息传传递。自然优化化蚁群在觅觅食过程程中，在在没有任任何提示示下总能能找到从从蚁巢到到食物源源之间的的最短路路径；当当经过的的路线上上出现障障碍物时时，还能能迅速找找到新的的最优路路径。信息正反反馈蚂蚁在寻寻找食物物时，在在其经过过的路径径上释放放信息素（外激素素）。蚂蚂蚁基本本没有视视觉，但但能在小小范围内内察觉同同类散发发的信息息素的轨轨迹，由由此来决决定何去去何从，并倾向向于朝着着信息素素强度高高的方向向移动。自催化行行为某条路径径上走过过的蚂蚁蚁越多，留下的的信息素素也越多多（随时时间蒸发发一部分分），后后来蚂蚁蚁选择该该

3、路径的的概率也也越高。蚁群算法的背景概念原型型各个蚂蚁蚁在没有有事先告告诉他们们食物在在什么地地方的前前提下开开始寻找找食物。当一只找找到食物物以后，它会向向环境释释放一种种挥发性性分泌物物pheromone(称为信息素,该物质随随着时间间的推移移会逐渐渐挥发消消失，信信息素浓浓度的大大小表征征路径的的远近)来实现的的，吸引引其他的的蚂蚁过过来，这这样越来来越多的的蚂蚁会会找到食食物。有些蚂蚁蚁并没有像像其它蚂蚁一样样总重复复同样的的路，他他们会另另辟蹊径径，如果果另开辟辟的道路路比原来来的其他他道路更更短，那那么，渐渐渐地，更多的的蚂蚁被被吸引到到这条较较短的路路上来。最后，经经过一段段时间

4、运运行，就就可能会会出现一一条最短短的路径径被大多多数蚂蚁蚁重复着着。蚁群算法的的提出算法的提提出蚁群算法法（AntColony Optimization,ACO），又称称蚂蚁算算法一种用来来在图中中寻找优优化路径径的机率率型算法法。它由MarcoDorigo于1992年在他的的博士论论文“Antsystem:optimizationbyacolonyofcooperatingagents”中提出，其灵感感来源于于蚂蚁在在寻找食食物过程程中发现现路径的的行为。最早用用于解决决著名的的旅行商商问题(TSP ,traveling salesman problem)。蚁群算法的的提出基本原理理蚁群算

5、法法是对自自然界蚂蚂蚁的寻寻径方式式进行模模似而得得出的一一种仿生生算法。蚂蚁在运运动过程程中，能能够在它它所经过过的路径径上留下下一种称之为信息素(pheromone)的物质进进行信息息传递，而且蚂蚂蚁在运运动过程程中能够够感知这这种物质质，并以以此指导导自己的的运动方方向，因因此由大大量蚂蚁蚁组成的的蚁群集集体行为为便表现现出一种种信息正正反馈现现象：某一路径径上走过过的蚂蚁蚁越多，则后来来者选择择该路径径的概率率就越大大。蚁群算法的的提出简化的蚂蚂蚁寻食正反反馈过程程蚂蚁从A点出发，速度相相同，食食物在D点，可能能随机选选择路线线ABD或ACD。假设初初始时每每条路线分分配一只蚂蚁，每个

6、时时间单位位行走一一步，本本图为经经过9个时间单单位时的的情形：走ABD的蚂蚁到到达终点点，而走走ACD的蚂蚁刚刚好走到到C点，为一一半路程程。蚁群算法的的提出本图为从从开始算算起，经经过18个时间单单位时的的情形：走ABD的蚂蚁到到达终点点后得到到食物又又返回了了起点A，而走ACD的蚂蚁刚刚好走到到D点。蚁群算法的的提出假设蚂蚁蚁每经过过一处所所留下的的信息素素为一个个单位，则经过过36个时间单单位后，所有开开始一起起出发的的蚂蚁都都经过不不同路径径从D点取得了了食物，此时ABD的路线往往返了2趟，每一一处的信信息素为为4个单位，而ACD的路线往往返了一一趟，每每一处的的信息素素为2个单位，

7、其比值值为2：1。寻找食物物的过程程继续进进行，则则按信息息素的指指导，蚁蚁群在ABD路线上增增派一只只蚂蚁（共2只），而而ACD路线上仍仍然为一一只蚂蚁蚁。再经经过36个时间单单位后，两条线线路上的的信息素素单位积积累为12和4，比值为为3：1。若按以上上规则继继续，蚁蚁群在ABD路线上再再增派一一只蚂蚁蚁（共3只），而而ACD路线上仍仍然为一一只蚂蚁蚁。再经经过36个时间单单位后，两条线线路上的的信息素素单位积积累为24和6，比值为为4：1。若继续进进行，则则按信息息素的指指导，最最终所有有的蚂蚁蚁会放弃弃ACD路线，而而都选择择ABD路线。这这也就是是前面所所提到的的正反馈效效应。蚁群算

8、法的的提出人工蚁群群算法基于以上上蚁群寻寻找食物物时的最最优路径径选择问问题，可可以构造造人工蚁蚁群，来来解决最最优化问问题，如如TSP问题。人工蚁群群中把具具有简单单功能的的工作单单元看作作蚂蚁。二者的的相似之之处在于于都是优优先选择择信息素素浓度大大的路径径。较短短路径的的信息素素浓度高高，所以以能够最最终被所所有蚂蚁蚁选择，也就是是最终的的优化结结果。两者的区区别在于于人工蚁蚁群有一一定的记忆能力力，能够记记忆已经经访问过过的节点点。同时时，人工工蚁群在选择择下一条路路径的时时候是按按一定算算法规律律有意识识地寻找找最短路路径，而而不是盲目目的。例如在在TSP问题中，可以预预先知道道当前

9、城城市到下下一个目目的地的的距离。人工蚁群群VS自然蚁群群蚁群算法的的特征蚁群算法采用了分分布式正正反馈并并行计算算机制,易于与其其他方法法结合,并具有较强的鲁棒性。（1）其原理理是一种种正反馈馈机制或或称增强强型学习习系统；它通过信信息素的的不断更更新达到到最终收收敛于近似最最优路径上上；（2）它是一一种通用用型随机机优化方方法；但人工蚂蚂蚁决不不是对实实际蚂蚁蚁的一种种简单模模拟，它它融进了了人类的的智能；（3）它是一一种分布布式的优优化方法法；不仅适合合目前的的串行计计算机，而且适适合未来来的并行行计算机机；（4）它是一一种全局局优化的的方法；不仅可用用于求解解单目标标优化问问题，而而且

10、可用用于求解解多目标标优化问问题；（5）它是一一种启发发式算法法；计算复杂杂性为O(NC*m*n2)，其中NC是迭代次次数，m是蚂蚁数数目，n是目的节节点数目目。蚁群算法法的特征征算法优点点：（1）求解问题题的快速速性由正反馈馈机制决决定（2）全局优化化性由分布式式计算决决定，避避免蚁群群在寻优优空间中中过早收收敛（3）有限时间间内答案案的合理理性由贪婪式式搜索模模式决定定，使能能在搜索索过程的的早期就就找到可可以接受受的较好好解蚁群算法法的基本本思想算法流程程图：开始初始化迭代次数Nc=Nc+1蚂蚁k=1蚂蚁k=k+1按照状态转移概率公式选择下一个元素修改禁忌表K=蚂蚁总数m？按照公式进行信

11、息量更新满足结束条件？输出程序计算结果结束YYNN蚁群算法法的基本本思想以TSP问题为例例：1、根据具具体问题题设置多多只蚂蚁蚁，分头头并行搜搜索。2、每只蚂蚂蚁完成成一次周周游后，在行进进的路上上释放信信息素，信息素素量与解解的质量量成正比比。3、蚂蚁路路径的选选择根据据信息素素强度大大小（初初始信息息素量设设为相等等），同同时考虑虑两点之之间的距距离，采采用随机机的局部部搜索策策略。这这使得距距离较短短的边，其上的的信息素素量较大大，后来来的蚂蚁蚁选择该该边的概概率也较较大。蚁群算法法的基本本思想4、每只蚂蚂蚁只能能走合法法路线（经过每每个城市市1次且仅1次），为为此设置置禁忌表表来控制制

12、。5、所有蚂蚂蚁都搜搜索完一一次就是是迭代一一次，每每迭代一一次就对对所有的的边做一一次信息息素更新新，原来来的蚂蚁蚁死掉，新的蚂蚂蚁进行行新一轮轮搜索。6、更新信信息素包包括原有有信息素素的蒸发发和经过过的路径径上信息息素的增增加。7、达到预预定的迭迭代步数数，或出出现停滞现象象（所有蚂蚂蚁都选选择同样样的路径径，解不不再变化化），则则算法结结束，以以当前最最优解作作为问题题的解输输出。蚁群算法的的数学模模型TSP算例分析析旅行商问问题（TSP）给定n个城市和两两个两个个城市之之间的距距离，要要求确定定一条经过所有有城市仅仅一次的的最短路径径。第一步:初始化将m只蚂蚁随随机放到到n个城市，每

13、只蚂蚂蚁的禁禁忌表为为蚂蚁当当前所在在城市，各边信息素素初始化化为c。禁忌表体体现了人人工蚂蚁蚁的记忆忆性，使使得蚂蚁蚁不会走走重复道道路，提提高了效效率。蚁群算法的的数学模模型第二步:选择路径径路径在t时刻，蚂蚂蚁k从城市i转移到城城市j的概率为为：蚁群算法法的数学学模型蚁群算法的的数学模模型蚁群的规规模和停停止规则则蚁群大小小:一般情况况下蚁群群中蚂蚁蚁的个数数不超过过TSP图中节点点的个数数。终止条件件:1给定一个个外循环环的最大大数目，表明已已经有足足够的蚂蚂蚁工作作；2当前最优优解连续续K次相同而而停止，其中K是一个给给定的整整数，表表示算法法已经收收敛，不不再需要要继续；3目标值控

14、控制规则则，给定定优化问问题（目目标最小小化）的的一个下下界和一一个误差差值，当当算法得得到的目目标值同同下界之之差小于于给定的的误差值值时，算算法终止止。第四步：输出结结果若未达到到终止条条件则转步骤二二，否则，输出目目前的最最优解。TSP应用举例例TSP应用举例例TSP应用举例例TSP应用举例例TSP应用举例例TSP应用举例例改进的蚁蚁群优化化算法最优解保留策略蚂蚁系统（带精英策略的蚂蚁系统ASelite） 蚁群系统（ACS） 最大-最小蚂蚁系统（MMAS） 基于优化排序的蚂蚁系统（ASrank）最优最差蚂蚁系统（BWAS） 一种新的自适应蚁群算法（AACA） 基于混合行为的蚁群算法（HB

15、ACA） 改 进 的蚁群算法一般蚁群群算法的的框架主主要有三三个组成成部分：蚁群的活动；信息素的的挥发；信息素的的增强；主要体现现在转移移概率公公式和信信息素更更新公式式。（一）带精英策略的蚂蚁系统特点在信息素素更新时时给予当当前最优优解以额额外的信信息素量量，使最最优解得得到更好好的利用用。找到到全局最最优解的的蚂蚁称称为“精精英蚂蚁蚁”。精英蚂蚁在边 上增加的信息素量；精英蚂蚁个数；当前全局最优解路径长度。特点、状态转移规则伪随机比率规则 设 为常数， 为随机数，如果 ，则蚂蚁转移的下一座城市是使 取最大值的城市；若 ，仍按转移概率确定。、全局更新规则只有精英蚂蚁才允许释放 信息素，即只有

16、全局最优解所属的边才增加 信息素。 、局部更新规则蚂蚁每次从城市 转移到 城市 后，边 上的信息素适当减少。 一般， 取值较大。（二）蚁群系统规则和和都是是为了使使搜索过过程更具具有指导导性，即即使蚂蚁蚁的搜索索主要集集中在当当前找出出的最好好解邻域域内。规规则则则是为了了使已选选的边对对后来的的蚂蚁具具有较小小的影响响力，以以避免蚂蚂蚁收敛敛到同一一路径。（三）最大最小蚂蚁系统 关于 的取值，没有确定的方法，有的书例子中取为0.01，10；有的书提出一个在最大值给定的情况下计算最小值的公式。1、每次迭代后，只对最优解所属路径上的信 息素更新。特点2、对每条边的信息素量限制在范围 内，目的是防

17、止某一条路径上的信息素量远 大于其余路径，避免过早收敛于局部最优解。 （四）基于优化排序的蚂蚁系统特点：每次迭代完成后，蚂蚁所经路径由小到大排序，并根据路径长度赋予不同的权重，路径越短权重越大。信息素更新时对 考虑权重的影响。 特点：主要是修改了ACS中的全局更新公式，增加 对最差蚂蚁路径信息素的更新，对最差解进 行削弱，使信息素差异进一步增大。 （五）最优最差蚂蚁系统（六）一种新的自适应蚁群算法特点：将ACS中的状态态转移规规则改为为自适应应伪随机机比率规则则，动态态调整转转移概率率，以避避免出现现停滞现象象。说明：在ACS的状态转移公式中， 是给定的常数；在AACA中， 是随平均节点分支数

18、ANB而变化的变量。ANB较大，意味着下一步可选的城市较多， 也变大，表示选择信息素和距离最好的边的可能性增大；反之减小。（七）基于混合行为的蚁群算法特点：按蚂蚁的的行为特特征将蚂蚂蚁分成成4类，称为为4个子蚁群群，各子子蚁群按按各自的的转移规规则行动动，搜索索路径，每迭代代一次，更新当当前最优优解，按按最优路路径长度度更新各各条边上上的信息息素，如如此直至至算法结结束。蚂蚁行为为蚂蚁在前前进过程程中，用用以决定定其下一一步移动动到哪个个状态的的规则集集合。1、蚂蚁以随机方式选择下一步要到达的状态。2、蚂蚁以贪婪方式选择下一步要到达的状态。3、蚂蚁按信息素强度选择下一步要到达的状态。4、蚂蚁按

19、信息素强度和城市间距离选择下一步要到达的状态 。蚂蚁行为蚁群算法法与遗传传、模拟拟退火算算法的比比较实验结果果表明：1、蚁群算算法所找找出的解解的质量量最高，遗传算算法次之之，模拟拟退火算算法最低低。2、蚁群算算法的收收敛速度度最快，遗传算算法次之之，模拟拟退火算算法最慢慢。蚁群群算法之之所以能能够快速速收敛到到全局最最优解，是因为为该算法法的个体体之间不不断进行行信息交交流和传传递。单单个个体体容易收收敛于局局部最优优，多个个个体通通过合作作可以很很快地收收敛于解解空间的的最优解解的附近近。蚁群算法的的应用应用领域域蚁群算法法能够被用用于解决决大多数数优化问问题或者者能够转转化为优优化求解解

20、的问题题。现在其应应用领域域已扩展展到多目目标优化化、数据据分类、数据聚聚类、模模式识别别、电信信QoS管理、生生物系统统建模、流程规规划、信信号处理理、机器器人控制制、决策策支持以以及仿真真和系统统辩识等等方面，群智能能理论和和方法为为解决这这类应用用问题提提供了新新的途径径。蚁群算法的的应用蚁群算法法在电信信路由优优化中已已取得了了一定的的应用成成果。HP公司和英英国电信信公司在在90年代中后后期都开开展了这这方面的的研究，设计了了蚁群路由由算法（AntColony Routing, ACR）。每只蚂蚁蚁就像蚁蚁群优化化算法中中一样，根据它它在网络络上的经经验与性性能，动动态更新新路由表表

21、项。如如果一只只蚂蚁因因为经过过了网络络中堵塞塞的路由由而导致致了比较较大的延延迟，那那么就对对该表项项做较大大的增强强。同时时根据信信息素挥挥发机制制实现系系统的信信息更新新，从而而抛弃过过期的路路由信息息。这样样，在当当前最优优路由出出现拥堵堵现象时时，ACR算法就能能迅速的的搜寻另另一条可可替代的的最优路路径，从从而提高高网络的的均衡性性、负荷荷量和利利用率。目前这这方面的的应用研研究仍在在升温，因为通通信网络络的分布布式信息息结构、非稳定定随机动动态特性性以及网网络状态态的异步步演化与与ACO的算法本本质和特特性非常常相似。蚁群算法的的应用基于群智智能的聚聚类算法法起源于于对蚁群群蚁卵

22、的的分类研研究。Lumer和Faieta将Deneubourg提出将蚁蚁巢分类类模型应应用于数数据聚类类分析。其基本本思想是是将待聚聚类数据据随机地地散布到到一个二二维平面面内，然然后将虚虚拟蚂蚁蚁分布到到这个空空间内，并以随随机方式式移动，当一只只蚂蚁遇遇到一个个待聚类类数据时时即将之之拾起并并继续随随机运动动，若运运动路径径附近的的数据与与背负的的数据相相似性高高于设置置的标准准则将其其放置在在该位置置，然后后继续移移动，重重复上述述数据搬搬运过程程。按照照这样的的方法可可实现对对相似数数据的聚聚类。蚁群算法的的应用ACO还在许多多经典组组合优化化问题中中获得了了成功的的应用，如二次次规划问问题（QAP）、机器器人路径径规划、作业流流程规划划、图着着色（GraphColoring）等问题题。经过多年年的发展展，ACO已成为能能够有效效解决实实际二次次规划问问题的几几种重要要算法之之一。AS在作业流流程计划划（Job-shopScheduling）问题中中的应用用实例已已经出现现，这说说明了AS在此领域域的应用用潜力。利用MAX-MIN AS解决PAQ也取得了了比较理理想的效效果，并并通过实实验中的的计算数数