第五章电脑鼠控制策略与算法研究17122.docx

《第五章电脑鼠控制策略与算法研究17122.docx》由会员分享，可在线阅读，更多相关《第五章电脑鼠控制策略与算法研究17122.docx（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第五章 蚁群算法在迷宫电脑鼠中的应用5.1 引言许多智能问题，如下棋游戏、战略决策、机器人路径规划等都可以转化为寻找迷宫最优路径问题。传统解决迷宫最优路径问题的算法通常会随着迷宫规模的增大、复杂性的增加，算法的空间和时间复杂性呈指数增加，从而很难用于求解大规模的问题实例。从蚁群觅食过程中能够发现蚁巢与食物源之间的最短路径受到启发，并利用该过程与著名的旅行商问题(TravelingSalesman Problem, TSP)之间的相似性，意大利学者M. Dorigo等人提出了一种新型的模拟进化算法-蚁群算法1,2。对TSP问题的求解结果显示，蚁群算法具有极强的鲁棒性和发现较好解的能力，但同时也存

2、在一些缺陷，如收敛速度慢、易出现停滞现象等2。目前，蚁群算法已在组合优化、计算机网络路由、连续函数优化、机器人路径规划、数据挖掘、电网优化等领域取得了突出的成就2-5，实践证明该算法是一种解决优化问题特别是组合优化问题的有力工具。5.2 迷迷宫的基基本信息息及常用用迷宫搜搜寻策略略5.2.11 迷宫宫的基本本信息从比赛规则则中得知知，迷宫宫是由一一个个118cmm18ccm大小小的方格格组成的的，迷宫宫大小为为1616，即即行列各各有166个方格格。若将将三维迷迷宫转化化成二维维图形,迷宫可可用图55.1表表示.图 5.11 迷迷宫行列列与坐标标对应关关系5.2.22 常用用搜寻法法则和策策略

3、5.2.22.1迷宫宫搜寻法法则设定搜寻法法则和策策略是为为了电脑脑鼠可以以以最快快的方式式找到终终点，到到达目标标后随即即从所走过过的路径径中找出出一条可行路径径返回起起点，然然后再做做冲刺，直直达目的的；法则则的设定定很重要要，它可可以使电电脑鼠不不多走冤冤枉路，可可节省很很多时间间而制胜胜。每一只电脑脑鼠到达达一方格格时它最最多有三三个方向向可前进进，最少少则因为为三面都都有墙，没没有可以以前进的的方向；当遇到到二个以以上的可可选择方方向时，由由于不同同场合需需要而有有不同优优先搜寻寻的方向向顺序，常常见的法法则有以以下几种种：右手法则则：遇叉叉路时，以以右边为为优先前前进方向向，然后后

4、直线方方向，左左边方向向；左手法则则：遇叉叉路时，以以左边为为优先前前进方向向，然后后直线方方向，右右边方向向；中左法则则：与右右手法则则相似，不不过方向向选择顺顺序改为为直线优优先，然然后左边边，右边边；中右法则则：遇叉叉路时，以以直线为为优先前前进方向向，然后后右边方方向，左左边方向向；求心法则则：遇叉叉路时，以以距中心心最短的的那个方方向优先先，然后后依次选选择。乱数法则则：以电电脑鼠的随机值作为为下一前前进方向向。5.2.22.2迷宫宫搜寻策策略迷宫搜寻模模式有全全迷宫搜搜寻策略略和部分分迷宫搜搜寻策略略两种：全迷宫搜搜寻策略略：电脑脑鼠以任任一搜寻寻法则前前进到达达终点后后，电脑脑鼠

5、会反反身继续续前进，然然后以原原设定的的搜寻法法则，时时时检查查未走过过的路，直直到每一一方格都都搜寻过过后，才才回起点点。部分迷宫宫搜寻策策略：电电脑鼠以以任一搜搜寻法则则前进到到达终点点后，电电脑鼠将将沿原路路线返回回起点，不不再进行行其它搜搜寻。如果比赛规规则不计计算搜寻寻时间，可可采用全全迷宫搜搜寻策略略，待地地毯式的的搜寻过过所有方方格后，再再计算最最佳路径径，作最最后的冲冲刺，冲冲刺成绩绩一定相相当不错错。由于于新制国国际比赛赛规则加加入搜寻寻时间的的成绩计计量，因因此我们们必须考考虑部分分迷宫搜搜寻策略略，甚至至还可能能须考虑虑加入求求心法则则，截路路径功能能等更智智慧的法法则来

6、协协助；此此时找到到的路径径可能不不是最佳佳路径，但但保证花花的时间间最短。5.2.33迷宫问问题经典典算法求解迷宫问问题，经经典算法法有深度度优先搜搜索和广广度优先先搜索两两种。深度优先先搜索(DFSS)：从从入口出出发，顺顺着某一一方向向向前探索索，若能能走通，则则继续往往前走；否则沿沿原路退退回(回溯)，换一一个方向向再继续续探索直至所所有可能能的通路路都探索索到为止止。如果果恰好某某一步探探索到出出口，则则就找到到了从入入口到出出口的路路径。为为了保证证在任何何位置上上都能沿沿原路退退回，防防止死循循环，需需要使用用堆栈来来保存大大量记录录。而要要求解迷迷宫最短短路径，则则必须用用深度

7、优优先搜索索出所有有到达出出口的路路径，通通过比较较得到最最短距离离的路径径这样样也必然然要求增增加数据据空间来来保存搜搜索过程程中当前前最短路路径增增加了空空间复杂杂度。广度优先先搜索(BFSS)：从从入口出出发，离离开入口口后依次次访问与与当前位位置邻接接的单元元格(上下左左右方向向)，然后后分别从从这些相相邻单元元格出发发依次访访问它们们的邻接接格，并并使“先被访访问的单单元格的的邻接格格先于后被访访问的单单元格的的邻接格格”被访问问，直至至访问到到迷宫出出口，则则找到了了迷宫问问题的最最优解，即即迷宫最最短路径径。该算算法的显显著特点点是“层层推推进”，探索索点会随随着探索索的深入入急

8、剧增增加，相相应地，需需要大量量的空间间用来保保存探索索过程的的记录空间复复杂度大大。与此同时，上上述两种种算法都都比较抽抽象复杂杂，编程程实现容容易出现现问题调试比比较困难难，因此此在本篇篇论文中中提出了了一种新新的容易易理解和和调试的的算法，该该算法复复杂度较较低，求求解较大大规模的的迷宫问问题也有有不俗的的表现。5.3蚁群群算法在在迷宫电电脑鼠中中的应用用5.3.11 蚁群群算法的的基本知知识5.3.11.1 蚂蚁的的基本习习性 蚂蚂蚁是最最古老的的社会昆昆虫之一一，它的的个体结结构和行行为虽简简单，但但是由这这些简单单个体构构成的蚂蚂蚁群体体，却表表现出高高度结构构化的社社会组织织.蚂

9、蚁蚁王国俨俨然是一一个小小小“社会”。这里，有有专司产产卵的后后蚁;有有为数众众多的从从事觅食食打猎、兴兴建屋穴穴、抚育育后代的的工蚁;有负责责守卫门门户、对对敌作战战的兵蚁蚁;还有有专备后后蚁招婿婿纳赘的雄蚁蚁等等.蚂蚁是社会会性昆虫虫，组成成社会的的三要素素之一就就是社会会成员除除有组织织、有分分工之外外，还有有相互的的通讯和和信息传传递。研究究表明，蚁蚁群有着着奇妙的的信息系系统，其中包包括视觉觉信号、声声音通讯讯和更为为独特的的无声语语育，即即包括化化学物质质不同的的组合、触触角信号号和身体体动作在在内的多多个征集集系统，来来策动其其他个体体.蚂蚁蚁特有的的控制自自身环境境的能力力，是

10、在在高级形形式的社社会性行行为及不不断进化化过程中中获得的的。5.3.11.2蚂蚂蚁的觅觅食策略略觅食行为是是蚁群一一个重要要而有趣趣的行为为.据昆昆虫学家家的观察察和研究究，发现现蚂蚁有有能力在在没有任任何可见见提示下下找出从从蚁穴到到食物源源的最短短路径，并并且能随随环境变变化适应应性地搜搜索新的的路径，产产生新的的选择.虽然单单个蚂蚁蚁的行为为极其简简单，但但由大量量的蚂蚁蚁个体组组成蚂蚁蚁群体却却表现出出极其复复杂的行行为，能能够完成成复杂的的任务。1生物学家和和仿生学学家经过过大量的的细致观观察研究究发现，蚂蚂蚁在觅觅食走过过的路径径上释放放一种妈妈蚁特有有的分泌泌物-信息激激素(P

11、Pherromoone).蚂蚁蚁个体之之间正是是通过这这种信息息激素进进行信息息传递，从从而能相相互协作作，完成成复杂任任务.在在一定范范围内蚂蚂蚁能够够察觉到到这种信信息激素素并指导导它的行行为，当当一些路路径通过过的蚂蚁蚁越多，则则留下的的信息激激素轨迹迹(trraill )也也就越多多，招致致后来更更多的蚂蚂蚁选择择该路径径的概率率也越高高，于是是越发增增加了该该路径的的信息素素强度.这种选选择过程程称之为为蚂蚁的的自催化化过程，形形成一种种正反馈馈机制，可可理解为为增强型型学习系系统.蚂蚂蚁最终终可以发发现最短短路径.自然界中蚁蚁群的自自组织行行为引起起了昆虫虫学家的的注意.Deuuu

12、u-bouurg等等通过“双桥实实验”对蚁群群的觅食食行为进进行了研研究如图图5.22所示，对对称双桥桥(两座座桥的长长度相同同)A、B将蚁巢与食物源分开，蚂蚁从蚁巢自由地向食物源移动.实验结果显示，在初始阶段出现一段时间的震荡(由于某些随机因素，使通过某座桥上的蚂蚁数急剧增多或减少)后，蚂蚁趋向于走同一条路径.在该实验中，绝大部分蚂蚁选择A桥. 在实验初期期，A, B两两座桥上上都没有有外激素素存在，蚂蚂蚁将以以相同的的概率选选择A、BB两座桥桥，故此此时蚂蚁蚁在两座座桥上留留下的外外激素量量相等.经过一一段时间间后，由由于随机波波动致使使大部分分蚂蚁选选择A桥桥(也有有可能为为B桥)，因此

13、此更多的的外激素素将会留留在A桥桥上，致致使A桥桥对后来来的蚂蚁蚁有更大大的吸引引力.随随着时问问的推移移，A桥桥上的蚂蚂蚁数将将越来越越多,而而B桥上上正好相相反.SG.ooaaLLsy等等人给出出了上述实验验的概率模型型.首先先，假定定桥上残残留的外外激素量量与过去去一段时时间经过过该桥的的蚂蚁数数成正比比(这意意味着不不考虑外外激素蒸蒸发的情情况);其次，某某一时刻刻蚂蚁按按桥上外外激素量量的多少少来选择择某座桥桥，即蚂蚂蚁选择择某座桥桥的概率率与经过过该桥的的蚂蚁数数成正比比.当所所有m只蚂蚁蚁都经过过两座桥桥以后，设设Am, Ann分别为为经过AA桥和BB桥的蚂蚂蚁数(Am+ Ann

14、=m),则第m+ 1只蚂蚁蚁选择AA桥的概概率为:式(5.00)而选择B桥桥的概率率为:其中参数hh和k用来匹匹配真实实实验数数据.第第(m+1)只蚂蚁蚁首先按按式(55.0)计算选选择概率率PA(m)，然然后生成成一个在在区间0,11上一一致分布布的随机机数a，如果果aPA(m)，则则选择AA桥，否否则选择择B桥. 图5.2双双桥实验验除能够找到到蚁巢和和食物源源之间的的最短路路径外，蚁蚁群还有有极强的的适应环环境的能能力，如如图5.3所示示，在蚁蚁群经过过的路线线上突然然出现障障碍物时时，蚁群群能够很很快重新新找到新新的最优优路径。图5.3 蚁群的的自适应应行为(a.)蚁蚁群在蚁蚁巢和食食

15、物源之之间的路路径上移移动(b)路径径上出现现障碍物物(c)较短短路径上上的外激激素以更更快的速速度增加加(d)所有有的蚂蚁蚁都选择择较短的的路径5.1.11.3 人工蚂蚂蚁与真真实蚂蚁蚁的异同同比较相同点比比较蚁群算法是是从自然然中真实实蚂蚁觅觅食的群群体行为为得到启启发而提提出的，其其很多观观点都来来源于真真实蚁群群，因此此算法中中所定义义的人工工蚂蚁与与真实蚂蚂蚁存在在如下共共同点。都存在一一个群体体中个体体相互交交流通信信的机制制。人工工蚂蚁与与真实蚂蚂蚁都存存在一种种改变当当前所处处环境的的机制：真实蚂蚂蚁在经经过的路路径上留留下信息息素，人人工蚂蚁蚁改变在在其所经经过路径径上存储储

16、的数字字信息，该该信息就就是算法法中所定定义的信信息量，它它记录了了蚂蚁当当前解和和历史解解的性能能状态，而而且可被被其他后后继人工工蚂蚁读读写。都要完成成一个相相同的任任务。人人工蚂蚁蚁与真实实蚂蚁都都要完成成一个相相同的任任务，即即寻找一一条从源源节点（巢巢穴）到到目的节节点（食食物）的的最短路路径。利用当前前信息进进行路径径选择的的随机选选择策略略。人工工蚂蚁与与真实蚂蚂蚁从某某一个节节点到下下一个节节点的移移动是利利用概率率选择策策略实现现的，概概率选择择策略只只利用当当前的信信息去预预测未来来的情况况，而不不能利用用未来的的信息，故故选择策策略在时时间和空空间都是是局部的的。不同点比

17、比较在从真实蚁蚁群行为为获得启启发而构构造蚁群群算法的的过程中中，人工工蚂蚁还还具备了了真实蚂蚂蚁所不不具有的的一些特特性。人工蚂蚁蚁存在于于一个离离散的空空间中，他他们的移移动式从从一个状状态到另另外一个个状态的的转换。人工蚂蚁蚁具有记记忆起本本身过去去行为的的内在状状态。人工蚂蚁蚁存在于于一个与与时间无无关联的的环境之之中。人工不是是完全盲盲目的，它它还受到到问题空空间特征征的启发发。例如如有的问问题中人人工蚂蚁蚁在产生生一个解解后改变变信息量量，而有有的问题题中人工工蚂蚁每每作出一一步选择择就更改改信息量量，但无无论哪种种方法，信信息量的的更新并并不是随随机都可可以进行行的。为了改善善算

18、法的的优化效效率，人人工蚂蚁蚁可增加加一些性性能，如如预测未未来、局局部优化化、回退退等，这这些行为为在真实实蚂蚁行行为中是是不存在在的。在在很多具具体的应应用中，人人工蚂蚁蚁可在局局部优化化过程中中相互交交换信息息，还有有一些蚁蚁群算法法中的人人工蚂蚁蚁可实现现简单的的预测。5.3.11.4 蚁群群算法的的基本特特点蚁群优化算算法是从从自然界界中蚂蚁蚁的觅食食行为受受到启发发而提出出的一种种模拟进进化算法法。ACCO算法法可以看看成是一一种基于于解空间间参数化化概率分分布模型型的搜索索算法框框架，其其中解空空间参数化化概率模模型的参参数就是是信息素素，因而而这种模模型就是是信息素素模型.在基

19、于于模型的的搜索算算法框架架中，可可行解通通过在一一个解空空间参数数化概率率分布模模型上的的搜索产产生，此此模型的的参数用用以前产产生的解解来进行行更新，使使得在新新模型上上的搜索索能集中中在高质质量的解解搜索空空间内.这种方方法的有有效性建建立在高高质量的的解总是是包含好好的解构构成元素素的假设设前提下下.通过过学习这这些解构构成元素素对解的的质量的的影响有有助于找找到一种种机制，并并通过解解构成元元素的最最佳组合合来构造造出高质质量的解。蚁群优优化算法法的主要要特点概概括如下下:采用分布布式控制制，不存存在中心心控制;每个个体体只能感感知局部部的信息息，不能能直接使使用全局局信息;个体可改

20、改变环境境，并通通过环境境来进行行间接通通讯机制制;具有自组组织性，即即群体的的复杂行行为是通通过个体体的交互互过程中中突现出出来的智智能;是一类概概率型的的全局搜搜索方法法，这种种非确定定性使算算法能够够有更多多的机会会求得全全局最优优解;其优化过过程不依依赖于优优化问题题本身的的严格数数学性质质，诸如如连续性性、可导导性及目目标函数数和约束束函数的的精确数数学描述述;是一类基基于多主主体的智智能算法法，各主主体间通通过相互互协作来来更好地地适应环环境;具有潜在在的并行行性，其其搜索过过程不是是从一点点出发，而而是同时时从多个个点同时时进行.这种分分布式多多智能体体的协作作过程是是异步并并发

21、进行行的，分分布并行行模式将将大大提提高整个个算法的的运行效效率和快快速反应应能力。5.3.22 基本本蚁群算算法的原原理及算算法实现现5.3.22.1 基本蚁蚁群算法法的机制制原理模拟蚂蚁蚁群体觅觅食行为为的蚁群群算是作作为一种种新的计计算智能能模式引引入的,该算法法基于如如下基本本假设：蚂蚁之间间通过信信息素和和环境进进行通信信.每只只蚂蚁仅仅更具其其周围的的局部环环境做出出反应,也只对对其周围围的局部部环境产产生影响响。蚂蚁对环环境的反反应由其其内部模模式决定定.因为为蚂蚁是是基因生生物,蚂蚂蚁的行行为实际际上是其其基因的的适应性性表现,即蚂蚁蚁是反应应型适应应性主体。在个体水水平上,每

22、只蚂蚂蚁仅根根据环境境做出独独立选择择;在群群体水平平上,单单质蚂蚁蚁的行为为是随机机的,但但蚁群可可通过自自组织过过程形成成高度有有序的群群体行为为。由上述假设设和分析析可见,基本蚁蚁群算法法的寻优优机制包包括两个个基本段段:适应应阶段和和协作阶阶段.在在适应阶阶段,各各候选解解根据积积累的信信息不断断调整自自身结构构,路径径上经过过的蚂蚁蚁越多,信息量量越大,则该路路径越容容易被选选择;时时间越长长,信息息量会越越小;在在协作阶阶段,候候选解之之间通过过信息交交流,以以期望产产生性能能更好的的解,类类似于学学习自动动机的学学习机制制。蚁群算法实实际上是是一类智智能多主主体系统统,其自自组织

23、机机制使得得蚁群算算法不需需要对所所求问题题的每一一个方面面都有详详尽的认认识.自自组织本本质上是是蚁群算算法机制制在没有有外界作作用下使使系统熵熵增加的的动态过过程,体体现了从从无序到到有序的的动态演演化,其其逻辑结结构如图图5.44所示。信息素更新管理组合优化问题信息素,决策点问题表达个体B信息素个体A信息素蚁群活动规划图5.4 基本蚁蚁群算法法的逻辑辑结构由图5.44可见,先将具具体的组组合优化化问题表表述成规规范的格格式,然然后利用用蚁群算算法在“探索(expplorratiion)”和“利用(expploiitattionn)”之间根根据信息息素这一一反馈载载体确定定决策点点,同时时

24、按照相相应的信信息素根根新规则则对每只只蚂蚁个个体的信信息素进进行增量量构建,随后从从整体角角度规划划出蚁群群活动的的行为方方向,周周而复始始,即可可求出组组合优化化问题的的最优解解。5.3.22.2基本蚁蚁群算法法的数学学模型设bi(tt)表示示t时刻刻位于元元素i的的蚂蚁数数目,为为t时刻刻路径上上的信息息量,nn表示TTSP规规模,mm为蚁群群蚂蚁的的总数目目,则mm=;=是t时时刻各条条路径上上信息量量相等,并设=connst,基本蚁蚁群算法法的寻优优是通过过有向图图g=(C,LL,)实现现的. 蚂蚁在在运动过过程中,根据各各条路径径上的信信息量决决定其转转移方向向.这里里用禁忌忌表来

25、记记录蚂蚁蚁k当前前所走过过的城市市,集合合随着进进化过程程做动态态调整.在搜索索过程中中,蚂蚁蚁根据各各路径上上的信息息量及路路径的启启发信息息来计算算状态转转移概率率.表示示t时刻刻蚂蚁由由元素(城市)i转移到到元素(城市)j的状态态转移概概率 式(5.11)式中,表示示蚂蚁下下一步允允许选择择的城市市;为信信息启发发式因子子,表示示轨迹的的相对重重要性,反映了了蚂蚁在在运动过过程中所所积累的的信息在在蚂蚁运运动时所所起的作作用,其其值越大大,则改改蚂蚁越越倾向于于选择其其他蚂蚁蚁经过的的路径,蚂蚁之之间协作作性越强强;为期期望启发发式因子子,表示示能见度度的相对对重要性性,反映映了蚂蚁蚁

26、在运动动过程中中启发信信息在蚂蚂蚁选择择路径中中的受重重视的成成度,其其值越大大,则该该状态转转移概率率越接近近于贪心心规则;为启发发函数,其表达达式如下下式(5.22)式中,表示示相邻两两个城市市之间的的距离.对蚂蚁蚁而言,越小,则越大大,也越越大.显显然,该该启发函函数表示示蚂蚁从从元素(城市)i转移移到元素素(城市市)j的的期望程程度.为了避免免残留信信息素过过多引起起残留信信息淹没没启发信信息,在在每只蚂蚂蚁走完完了一步步或者完完成对所所有n个个城市的的遍历(也即一一个循环环结束)后,要要对残留留信息进进行更新新处理.这种更更新策略略模仿了了人类大大脑记忆忆的特点点,在新新信息不不断存

27、如如大脑的的同时,存储在在大脑中中的旧信信息随着着时间的的推移逐逐渐淡化化,甚至至忘记.由此,t+nn时刻路路径上的的信息量量可按如如下规则则进行调调整 式(55.3)式(5.44)式中,表示示信息素素挥发系系数,则则表示信信息素残残留因子子,为了了防止信信息的无无限积累累,的取取值范围围为:;表示本本次循环环中路径径(i, j)上的信信息素增增量,初初始时刻刻,)表示示第只蚂蚂蚁在本本次循环环中留在在路径(i, j)上上的信息息量.根据信息息素更新新策略的的不同，Dorrigoo M提提出了三三种不同同的基本本蚁群算算法模型型,分别别称之为为Antt-Cyyclee模型、Antt-Quuan

28、ttityy模型及及Antt-Deensiity模模型,其其差别在在于求发发不同.在Antt-Cyyclee模型中中式(5.55)式中,Q表表示信息息素强度度,它在在一定程程度上影影响了算算法的收收敛速度度;表示示第只蚂蚂蚁在本本次循环环中所走走路径的的总长度度.在Antt-Quuanttityy模型中中式(5.66)在Ant-Dennsitty模型型中式(5.77)区别:式(5.66)和式式(5.7)中中利用的的是局部部信息,即蚂蚁蚁走完一一步后更更新路径径上的信信息素;而式(5.55)中利利用的是是整体信信息,即即蚂蚁完完成了一一个循环环后更新新所有路路径上的的信息素素,在求求解TSSP时

29、性性能较好好,因此此通常采采用式(5.55)作为为蚁群算算法的基基本模型型.此外外，在DDoriigo MM等人的的论文中中还对蚁蚁群算法法提出了了一些讨讨论，其其中包括括不同的的蚁群初初始分布布对求解解的影响响等，还还提出了了所谓的的精英策策略(eelittistt sttrattegyy)，以以强化精精英蚂蚁蚁(发现现迄今最最好路径径的蚂蚁蚁)的影影响.结结果发现现，对精精英蚂蚁蚁数而言言有一个个最优的的范围:低于此范围围，增加加精英蚂蚂蚁数可可较早地地发现更更好的路路径，高高于此范围围，精英英蚂蚁会会在搜索索早期迫迫使寻优过程程始终在在次优解解附近，导导致性能能变差。5.3.22.2 基

30、基本蚁群群算法的的实现步步骤及程程序结构构流程以TSP为为例,基基本蚁群群算法的的具体实实现步骤骤如下:参数初始始化.令令时间tt=0和和循环次次数=00,设置置最大循循环次数数,将m只只蚂蚁置置于个元元素(城城市)上上,令有有向图每每条边的的初始化化信息量量,其中中表示常常数,且且初始化化时刻。循环次数数=+1.蚂蚁的禁禁忌表索索引号=1蚂蚁数目目=+1.蚂蚁个体体根据状状态转换换概率公公式计算算的概率率选择元元素(城城市)jj并前进进,.修改禁忌忌表指针针,即选选择好之之后将蚂蚂蚁移动动到新的的元素(城市),并把把该元素素(城市市)移动动到该蚂蚂蚁个体体的禁忌忌表中.若集合CC中的元元素(

31、城城市)未未遍历完完,即=0) aand(i+ddiii=00) annd(jj+djji 00。迷宫可行行解的构构造在利用蚁群群算法求求解迷宫宫最短路路径问题题时，为为了使每每只蚂蚁蚁能以尽尽可能高高的概率率生成可可行解，本本文采用用两组数数量相等等的蚁群群分别从从迷宫的的起点和和终点同同时出发发，每只只蚂蚁按按公式(2)确确定的概概率在迷迷宫中漫漫游。为为尽量避避免生成成无效路路径，为为蚂蚁分分配一张张禁忌表表。该表表记录蚂蚂蚁当前前走过的的点集，以以避免选选择已经经走过的的点。则则对任意意一只蚂蚂蚁，在在移动过过程中可可以定义义如下的的生命周周期:蚂蚁走走进死角角，除非非沿原路路返回一一

32、步或多多步，不不能再朝朝前移动动，则将将该蚂蚁蚁从系统统中删除除;蚂蚁到到达另一一组蚁群群的出发发点，此此时该蚂蚂蚁走过过的路径径为一条条可行路路径;蚂蚁碰碰到另一一组的某某只蚂蚁蚁。如果果这两只只蚂蚁所所经过的的点没有有重复(相遇点点除外)，则将将两只蚂蚂蚁所经经过的路路径相连连以构成成迷宫的的一条可可行路径径。因此此，从蚁蚁群的产产生到生生命周期期的结束束，将会会有一部部分蚂蚁蚁找到问问题的可可行解，但但可行解解的数量量小于蚁蚁群数的的一半。 信息素更更新规则则在每次迭代代中，针针对当前前最好解解所属的的边按公公式行信信息素更更新， ，其中为本次次迭代最最好解的的长度，为信息素的蒸发系数。

33、算法描述述Step11. 初初始化参参数，, Step22. 生生成2*只蚂蚁蚁，将其其中只放放到起点点以，另另外只放放到终点点Step33. whiile活活蚂蚁数数大于00 ddo for蚂蚁蚁 ddoif蚂蚁活活着annd 非空 theen (1)按公式式(2)计算转转移概率率; (2)按概率率选择下下一个点点; (3)根据蚂蚂蚁生命命周期(i). (iii). (iiii)情况，决决定蚂蚁蚁的死、活活状态; (44)如果果蚂蚁没没死亡，将将其所选选择的点点加入 中。end iifendend SStepp4. 计算本本次迭代代的最好好解，如如优于当当前最好好解，则则用其替替换当前前最好解解; SStepp5. 按公式式(3)更新路路径上的的信息素素; SStepp6. iff 小于于且未进进入停滞滞状态 tthenn (1)清清空所有有蚂蚁禁禁忌表中中的数据据; (2): =+1; (3)转转至Sttep22.else输出最优解解。end iifend iif5.4 本本章小结结从蚂蚁的基基本习性性和觅食食策略入入手，提提出了人人工蚂蚁蚁与真实实蚂蚁的的异同之之处，介介绍基本本蚁群算算