企业管理第五章电脑鼠控制策略与算法研究.docx

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

33、的蒸发系系数。算法描描述Stepp1. 初始化化参数，, Stepp2. 生成22*只蚂蚂蚁，将将其中只只放到起起点以，另外只只放到终终点Stepp3. whhilee活蚂蚁蚁数大于于0 do for蚂蚂蚁 doif蚂蚁蚁活着aand 非空空 thhen (1)按公式式(2)计算转转移概率率; (2)按概率率选择下下一个点点; (3)根据蚂蚂蚁生命命周期(i). (iii). (iiii)情况，决定蚂蚂蚁的死死、活状状态; (44)如果果蚂蚁没没死亡，将其所所选择的的点加入入 中。end ifendend Steep4. 计算算本次迭迭代的最最好解，如优于于当前最最好解，则用其其替换当当前最好好解; Steep5. 按公公式(33)更新新路径上上的信息息素; Steep6. iif 小小于且未未进入停停滞状态态 theen (1)清空所所有蚂蚁蚁禁忌表表中的数数据;