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

第五章 蚁群算法在迷宫电脑鼠中的应用5.1 引言许多智能问题，如下棋游戏、战略决策、机器人路径规划等都可以转化为寻找迷宫最优路径问题。传统解决迷宫最优路径问题的算法通常会随着迷宫规模的增大、复杂性的增加，算法的空间和时间复杂性呈指数增加，从而很难用于求解大规模的问题实例。从蚁群觅食过程中能够发现蚁巢与食物源之间的最短路径受到启发，并利用该过程与著名的旅行商问题(TravelingSalesman Problem, TSP)之间的相似性，意大利学者M. Dorigo等人提出了一种新型的模拟进化算法-蚁群算法1,2。对TSP问题的求解结果显示，蚁群算法具有极强的鲁棒性和发现较好解的能力，但同时也存在一些缺陷，如收敛速度慢、易出现停滞现象等2。目前，蚁群算法已在组合优化、计算机网络路由、连续函数优化、机器人路径规划、数据挖掘、电网优化等领域取得了突出的成就2-5，实践证明该算法是一种解决优化问题特别是组合优化问题的有力工具。5.2 迷迷宫的基基本信息息及常用用迷宫搜搜寻策略略5.2.11 迷宫宫的基本本信息从比赛规则则中得知知，迷宫宫是由一一个个118cmm×18ccm大小小的方格格组成的的，迷宫宫大小为为16××16，即即行列各各有166个方格格。若将将三维迷迷宫转化化成二维维图形,迷宫可可用图55.1表表示.图 5.11 迷迷宫行列列与坐标标对应关关系5.2.22 常用用搜寻法法则和策策略5.2.22.1迷宫宫搜寻法法则设定搜寻法法则和策策略是为为了电脑脑鼠可以以以最快快的方式式找到终终点，到到达目标标后随即即从所走过过的路径径中找出出一条可行路径径返回起起点，然然后再做做冲刺，直直达目的的；法则则的设定定很重要要，它可可以使电电脑鼠不不多走冤冤枉路，可可节省很很多时间间而制胜胜。每一只电脑脑鼠到达达一方格格时它最最多有三三个方向向可前进进，最少少则因为为三面都都有墙，没没有可以以前进的的方向；当遇到到二个以以上的可可选择方方向时，由由于不同同场合需需要而有有不同优优先搜寻寻的方向向顺序，常常见的法法则有以以下几种种：右手法则则：遇叉叉路时，以以右边为为优先前前进方向向，然后后直线方方向，左左边方向向；左手法则则：遇叉叉路时，以以左边为为优先前前进方向向，然后后直线方方向，右右边方向向；中左法则则：与右右手法则则相似，不不过方向向选择顺顺序改为为直线优优先，然然后左边边，右边边；中右法则则：遇叉叉路时，以以直线为为优先前前进方向向，然后后右边方方向，左左边方向向；求心法则则：遇叉叉路时，以以距中心心最短的的那个方方向优先先，然后后依次选选择。乱数法则则：以电电脑鼠的随机值作为为下一前前进方向向。5.2.22.2迷宫宫搜寻策策略迷宫搜寻模模式有全全迷宫搜搜寻策略略和部分分迷宫搜搜寻策略略两种：全迷宫搜搜寻策略略：电脑脑鼠以任任一搜寻寻法则前前进到达达终点后后，电脑脑鼠会反反身继续续前进，然然后以原原设定的的搜寻法法则，时时时检查查未走过过的路，直直到每一一方格都都搜寻过过后，才才回起点点。部分迷宫宫搜寻策策略：电电脑鼠以以任一搜搜寻法则则前进到到达终点点后，电电脑鼠将将沿原路路线返回回起点，不不再进行行其它搜搜寻。如果比赛规规则不计计算搜寻寻时间，可可采用全全迷宫搜搜寻策略略，待地地毯式的的搜寻过过所有方方格后，再再计算最最佳路径径，作最最后的冲冲刺，冲冲刺成绩绩一定相相当不错错。由于于新制国国际比赛赛规则加加入搜寻寻时间的的成绩计计量，因因此我们们必须考考虑部分分迷宫搜搜寻策略略，甚至至还可能能须考虑虑加入求求心法则则，截路路径功能能等更智智慧的法法则来协协助；此此时找到到的路径径可能不不是最佳佳路径，但但保证花花的时间间最短。5.2.33迷宫问问题经典典算法求解迷宫问问题，经经典算法法有深度度优先搜搜索和广广度优先先搜索两两种。深度优先先搜索(DFSS)：从从入口出出发，顺顺着某一一方向向向前探索索，若能能走通，则则继续往往前走；否则沿沿原路退退回(回溯)，换一一个方向向再继续续探索直至所所有可能能的通路路都探索索到为止止。如果果恰好某某一步探探索到出出口，则则就找到到了从入入口到出出口的路路径。为为了保证证在任何何位置上上都能沿沿原路退退回，防防止死循循环，需需要使用用堆栈来来保存大大量记录录。而要要求解迷迷宫最短短路径，则则必须用用深度优优先搜索索出所有有到达出出口的路路径，通通过比较较得到最最短距离离的路径径这样样也必然然要求增增加数据据空间来来保存搜搜索过程程中当前前最短路路径增增加了空空间复杂杂度。广度优先先搜索(BFSS)：从从入口出出发，离离开入口口后依次次访问与与当前位位置邻接接的单元元格(上下左左右方向向)，然后后分别从从这些相相邻单元元格出发发依次访访问它们们的邻接接格，并并使“先被访访问的单单元格的的邻接格格先于后被访访问的单单元格的的邻接格格”被访问问，直至至访问到到迷宫出出口，则则找到了了迷宫问问题的最最优解，即即迷宫最最短路径径。该算算法的显显著特点点是“层层推推进”，探索索点会随随着探索索的深入入急剧增增加，相相应地，需需要大量量的空间间用来保保存探索索过程的的记录空间复复杂度大大。与此同时，上上述两种种算法都都比较抽抽象复杂杂，编程程实现容容易出现现问题调试比比较困难难，因此此在本篇篇论文中中提出了了一种新新的容易易理解和和调试的的算法，该该算法复复杂度较较低，求求解较大大规模的的迷宫问问题也有有不俗的的表现。5.3蚁群群算法在在迷宫电电脑鼠中中的应用用5.3.11 蚁群群算法的的基本知知识5.3.11.1 蚂蚁的的基本习习性 蚂蚂蚁是最最古老的的社会昆昆虫之一一，它的的个体结结构和行行为虽简简单，但但是由这这些简单单个体构构成的蚂蚂蚁群体体，却表表现出高高度结构构化的社社会组织织.蚂蚁蚁王国俨俨然是一一个小小小“社会”。这里，有有专司产产卵的后后蚁;有有为数众众多的从从事觅食食打猎、兴兴建屋穴穴、抚育育后代的的工蚁;有负责责守卫门门户、对对敌作战战的兵蚁蚁;还有有专备后后蚁招婿婿纳赘的雄蚁蚁等等.蚂蚁是社会会性昆虫虫，组成成社会的的三要素素之一就就是社会会成员除除有组织织、有分分工之外外，还有有相互的的通讯和和信息传传递。研究究表明，蚁蚁群有着着奇妙的的信息系系统，其中包包括视觉觉信号、声声音通讯讯和更为为独特的的无声语语育，即即包括化化学物质质不同的的组合、触触角信号号和身体体动作在在内的多多个征集集系统，来来策动其其他个体体.蚂蚁蚁特有的的控制自自身环境境的能力力，是在在高级形形式的社社会性行行为及不不断进化化过程中中获得的的。5.3.11.2蚂蚂蚁的觅觅食策略略觅食行为是是蚁群一一个重要要而有趣趣的行为为.据昆昆虫学家家的观察察和研究究，发现现蚂蚁有有能力在在没有任任何可见见提示下下找出从从蚁穴到到食物源源的最短短路径，并并且能随随环境变变化适应应性地搜搜索新的的路径，产产生新的的选择.虽然单单个蚂蚁蚁的行为为极其简简单，但但由大量量的蚂蚁蚁个体组组成蚂蚁蚁群体却却表现出出极其复复杂的行行为，能能够完成成复杂的的任务。1生物学家和和仿生学学家经过过大量的的细致观观察研究究发现，蚂蚂蚁在觅觅食走过过的路径径上释放放一种妈妈蚁特有有的分泌泌物-信息激激素(PPherromoone).蚂蚁蚁个体之之间正是是通过这这种信息息激素进进行信息息传递，从从而能相相互协作作，完成成复杂任任务.在在一定范范围内蚂蚂蚁能够够察觉到到这种信信息激素素并指导导它的行行为，当当一些路路径通过过的蚂蚁蚁越多，则则留下的的信息激激素轨迹迹(trraill )也也就越多多，招致致后来更更多的蚂蚂蚁选择择该路径径的概率率也越高高，于是是越发增增加了该该路径的的信息素素强度.这种选选择过程程称之为为蚂蚁的的自催化化过程，形形成一种种正反馈馈机制，可可理解为为增强型型学习系系统.蚂蚂蚁最终终可以发发现最短短路径.自然界中蚁蚁群的自自组织行行为引起起了昆虫虫学家的的注意.Deuuuu-bouurg等等通过“双桥实实验”对蚁群群的觅食食行为进进行了研研究如图图5.22所示，对对称双桥桥(两座座桥的长长度相同同)A、B将蚁巢与食物源分开，蚂蚁从蚁巢自由地向食物源移动.实验结果显示，在初始阶段出现一段时间的震荡(由于某些随机因素，使通过某座桥上的蚂蚁数急剧增多或减少)后，蚂蚁趋向于走同一条路径.在该实验中，绝大部分蚂蚁选择A桥. 在实验初期期，A, B两两座桥上上都没有有外激素素存在，蚂蚂蚁将以以相同的的概率选选择A、BB两座桥桥，故此此时蚂蚁蚁在两座座桥上留留下的外外激素量量相等.经过一一段时间间后，由由于随机波波动致使使大部分分蚂蚁选选择A桥桥(也有有可能为为B桥)，因此此更多的的外激素素将会留留在A桥桥上，致致使A桥桥对后来来的蚂蚁蚁有更大大的吸引引力.随随着时问问的推移移，A桥桥上的蚂蚂蚁数将将越来越越多,而而B桥上上正好相相反.SG.ooaaLLsy等等人给出出了上述实验验的概率模型型.首先先，假定定桥上残残留的外外激素量量与过去去一段时时间经过过该桥的的蚂蚁数数成正比比(这意意味着不不考虑外外激素蒸蒸发的情情况);其次，某某一时刻刻蚂蚁按按桥上外外激素量量的多少少来选择择某座桥桥，即蚂蚂蚁选择择某座桥桥的概率率与经过过该桥的的蚂蚁数数成正比比.当所所有m只蚂蚁蚁都经过过两座桥桥以后，设设Am, Ann分别为为经过AA桥和BB桥的蚂蚂蚁数(Am+ Ann=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.)蚁蚁群在蚁蚁巢和食食物源之之间的路路径上移移动(b)路径径上出现现障碍物物(c)较短短路径上上的外激激素以更更快的速速度增加加(d)所有有的蚂蚁蚁都选择择较短的的路径5.1.11.3 人工蚂蚂蚁与真真实蚂蚁蚁的异同同比较相同点比比较蚁群算法是是从自然然中真实实蚂蚁觅觅食的群群体行为为得到启启发而提提出的，其其很多观观点都来来源于真真实蚁群群，因此此算法中中所定义义的人工工蚂蚁与与真实蚂蚂蚁存在在如下共共同点。都存在一一个群体体中个体体相互交交流通信信的机制制。人工工蚂蚁与与真实蚂蚂蚁都存存在一种种改变当当前所处处环境的的机制：真实蚂蚂蚁在经经过的路路径上留留下信息息素，人人工蚂蚁蚁改变在在其所经经过路径径上存储储的数字字信息，该该信息就就是算法法中所定定义的信信息量，它它记录了了蚂蚁当当前解和和历史解解的性能能状态，而而且可被被其他后后继人工工蚂蚁读读写。都要完成成一个相相同的任任务。人人工蚂蚁蚁与真实实蚂蚁都都要完成成一个相相同的任任务，即即寻找一一条从源源节点（巢巢穴）到到目的节节点（食食物）的的最短路路径。利用当前前信息进进行路径径选择的的随机选选择策略略。人工工蚂蚁与与真实蚂蚂蚁从某某一个节节点到下下一个节节点的移移动是利利用概率率选择策策略实现现的，概概率选择择策略只只利用当当前的信信息去预预测未来来的情况况，而不不能利用用未来的的信息，故故选择策策略在时时间和空空间都是是局部的的。不同点比比较在从真实蚁蚁群行为为获得启启发而构构造蚁群群算法的的过程中中，人工工蚂蚁还还具备了了真实蚂蚂蚁所不不具有的的一些特特性。人工蚂蚁蚁存在于于一个离离散的空空间中，他他们的移移动式从从一个状状态到另另外一个个状态的的转换。人工蚂蚁蚁具有记记忆起本本身过去去行为的的内在状状态。人工蚂蚁蚁存在于于一个与与时间无无关联的的环境之之中。人工不是是完全盲盲目的，它它还受到到问题空空间特征征的启发发。例如如有的问问题中人人工蚂蚁蚁在产生生一个解解后改变变信息量量，而有有的问题题中人工工蚂蚁每每作出一一步选择择就更改改信息量量，但无无论哪种种方法，信信息量的的更新并并不是随随机都可可以进行行的。为了改善善算法的的优化效效率，人人工蚂蚁蚁可增加加一些性性能，如如预测未未来、局局部优化化、回退退等，这这些行为为在真实实蚂蚁行行为中是是不存在在的。在在很多具具体的应应用中，人人工蚂蚁蚁可在局局部优化化过程中中相互交交换信息息，还有有一些蚁蚁群算法法中的人人工蚂蚁蚁可实现现简单的的预测。5.3.11.4 蚁群群算法的的基本特特点蚁群优化算算法是从从自然界界中蚂蚁蚁的觅食食行为受受到启发发而提出出的一种种模拟进进化算法法。ACCO算法法可以看看成是一一种基于于解空间间参数化化概率分分布模型型的搜索索算法框框架，其其中解空空间参数化化概率模模型的参参数就是是信息素素，因而而这种模模型就是是信息素素模型.在基于于模型的的搜索算算法框架架中，可可行解通通过在一一个解空空间参数数化概率率分布模模型上的的搜索产产生，此此模型的的参数用用以前产产生的解解来进行行更新，使使得在新新模型上上的搜索索能集中中在高质质量的解解搜索空空间内.这种方方法的有有效性建建立在高高质量的的解总是是包含好好的解构构成元素素的假设设前提下下.通过过学习这这些解构构成元素素对解的的质量的的影响有有助于找找到一种种机制，并并通过解解构成元元素的最最佳组合合来构造造出高质质量的解。蚁群优优化算法法的主要要特点概概括如下下:采用分布布式控制制，不存存在中心心控制;每个个体体只能感感知局部部的信息息，不能能直接使使用全局局信息;个体可改改变环境境，并通通过环境境来进行行间接通通讯机制制;具有自组组织性，即即群体的的复杂行行为是通通过个体体的交互互过程中中突现出出来的智智能;是一类概概率型的的全局搜搜索方法法，这种种非确定定性使算算法能够够有更多多的机会会求得全全局最优优解;其优化过过程不依依赖于优优化问题题本身的的严格数数学性质质，诸如如连续性性、可导导性及目目标函数数和约束束函数的的精确数数学描述述;是一类基基于多主主体的智智能算法法，各主主体间通通过相互互协作来来更好地地适应环环境;具有潜在在的并行行性，其其搜索过过程不是是从一点点出发，而而是同时时从多个个点同时时进行.这种分分布式多多智能体体的协作作过程是是异步并并发进行行的，分分布并行行模式将将大大提提高整个个算法的的运行效效率和快快速反应应能力。5.3.22 基本本蚁群算算法的原原理及算算法实现现5.3.22.1 基本蚁蚁群算法法的机制制原理模拟蚂蚁蚁群体觅觅食行为为的蚁群群算是作作为一种种新的计计算智能能模式引引入的,该算法法基于如如下基本本假设：蚂蚁之间间通过信信息素和和环境进进行通信信.每只只蚂蚁仅仅更具其其周围的的局部环环境做出出反应,也只对对其周围围的局部部环境产产生影响响。蚂蚁对环环境的反反应由其其内部模模式决定定.因为为蚂蚁是是基因生生物,蚂蚂蚁的行行为实际际上是其其基因的的适应性性表现,即蚂蚁蚁是反应应型适应应性主体。在个体水水平上,每只蚂蚂蚁仅根根据环境境做出独独立选择择;在群群体水平平上,单单质蚂蚁蚁的行为为是随机机的,但但蚁群可可通过自自组织过过程形成成高度有有序的群群体行为为。由上述假设设和分析析可见,基本蚁蚁群算法法的寻优优机制包包括两个个基本段段:适应应阶段和和协作阶阶段.在在适应阶阶段,各各候选解解根据积积累的信信息不断断调整自自身结构构,路径径上经过过的蚂蚁蚁越多,信息量量越大,则该路路径越容容易被选选择;时时间越长长,信息息量会越越小;在在协作阶阶段,候候选解之之间通过过信息交交流,以以期望产产生性能能更好的的解,类类似于学学习自动动机的学学习机制制。蚁群算法实实际上是是一类智智能多主主体系统统,其自自组织机机制使得得蚁群算算法不需需要对所所求问题题的每一一个方面面都有详详尽的认认识.自自组织本本质上是是蚁群算算法机制制在没有有外界作作用下使使系统熵熵增加的的动态过过程,体体现了从从无序到到有序的的动态演演化,其其逻辑结结构如图图5.44所示。信息素更新管理组合优化问题信息素,决策点问题表达个体B信息素个体A信息素蚁群活动规划图5.4 基本蚁蚁群算法法的逻辑辑结构由图5.44可见,先将具具体的组组合优化化问题表表述成规规范的格格式,然然后利用用蚁群算算法在“探索(expplorratiion)”和“利用(expploiitattionn)”之间根根据信息息素这一一反馈载载体确定定决策点点,同时时按照相相应的信信息素根根新规则则对每只只蚂蚁个个体的信信息素进进行增量量构建,随后从从整体角角度规划划出蚁群群活动的的行为方方向,周周而复始始,即可可求出组组合优化化问题的的最优解解。5.3.22.2基本蚁蚁群算法法的数学学模型设bi(tt)表示示t时刻刻位于元元素i的的蚂蚁数数目,为为t时刻刻路径上上的信息息量,nn表示TTSP规规模,mm为蚁群群蚂蚁的的总数目目,则mm=;=是t时时刻各条条路径上上信息量量相等,并设=connst,基本蚁蚁群算法法的寻优优是通过过有向图图g=(C,LL,)实现现的. 蚂蚁在在运动过过程中,根据各各条路径径上的信信息量决决定其转转移方向向.这里里用禁忌忌表来记记录蚂蚁蚁k当前前所走过过的城市市,集合合随着进进化过程程做动态态调整.在搜索索过程中中,蚂蚁蚁根据各各路径上上的信息息量及路路径的启启发信息息来计算算状态转转移概率率.表示示t时刻刻蚂蚁由由元素(城市)i转移到到元素(城市)j的状态态转移概概率 式(5.11)式中,表示示蚂蚁下下一步允允许选择择的城市市;为信信息启发发式因子子,表示示轨迹的的相对重重要性,反映了了蚂蚁在在运动过过程中所所积累的的信息在在蚂蚁运运动时所所起的作作用,其其值越大大,则改改蚂蚁越越倾向于于选择其其他蚂蚁蚁经过的的路径,蚂蚁之之间协作作性越强强;为期期望启发发式因子子,表示示能见度度的相对对重要性性,反映映了蚂蚁蚁在运动动过程中中启发信信息在蚂蚂蚁选择择路径中中的受重重视的成成度,其其值越大大,则该该状态转转移概率率越接近近于贪心心规则;为启发发函数,其表达达式如下下式(5.22)式中,表示示相邻两两个城市市之间的的距离.对蚂蚁蚁而言,越小,则越大大,也越越大.显显然,该该启发函函数表示示蚂蚁从从元素(城市)i转移移到元素素(城市市)j的的期望程程度.为了避免免残留信信息素过过多引起起残留信信息淹没没启发信信息,在在每只蚂蚂蚁走完完了一步步或者完完成对所所有n个个城市的的遍历(也即一一个循环环结束)后,要要对残留留信息进进行更新新处理.这种更更新策略略模仿了了人类大大脑记忆忆的特点点,在新新信息不不断存如如大脑的的同时,存储在在大脑中中的旧信信息随着着时间的的推移逐逐渐淡化化,甚至至忘记.由此,t+nn时刻路路径上的的信息量量可按如如下规则则进行调调整 式(55.3)式(5.44)式中,表示示信息素素挥发系系数,则则表示信信息素残残留因子子,为了了防止信信息的无无限积累累,的取取值范围围为:;表示本本次循环环中路径径(i, j)上的信信息素增增量,初初始时刻刻,)表示示第只蚂蚂蚁在本本次循环环中留在在路径(i, j)上上的信息息量.根据信息息素更新新策略的的不同，Dorrigoo M提提出了三三种不同同的基本本蚁群算算法模型型,分别别称之为为Antt-Cyyclee模型、Antt-Quuanttityy模型及及Antt-Deensiity模模型,其其差别在在于求发发不同.在Antt-Cyyclee模型中中式(5.55)式中,Q表表示信息息素强度度,它在在一定程程度上影影响了算算法的收收敛速度度;表示示第只蚂蚂蚁在本本次循环环中所走走路径的的总长度度.在Antt-Quuanttityy模型中中式(5.66)在Ant-Dennsitty模型型中式(5.77)区别:式(5.66)和式式(5.7)中中利用的的是局部部信息,即蚂蚁蚁走完一一步后更更新路径径上的信信息素;而式(5.55)中利利用的是是整体信信息,即即蚂蚁完完成了一一个循环环后更新新所有路路径上的的信息素素,在求求解TSSP时性性能较好好,因此此通常采采用式(5.55)作为为蚁群算算法的基基本模型型.此外外，在DDoriigo MM等人的的论文中中还对蚁蚁群算法法提出了了一些讨讨论，其其中包括括不同的的蚁群初初始分布布对求解解的影响响等，还还提出了了所谓的的精英策策略(eelittistt sttrattegyy)，以以强化精精英蚂蚁蚁(发现现迄今最最好路径径的蚂蚁蚁)的影影响.结结果发现现，对精精英蚂蚁蚁数而言言有一个个最优的的范围:低于此范围围，增加加精英蚂蚂蚁数可可较早地地发现更更好的路路径，高高于此范围围，精英英蚂蚁会会在搜索索早期迫迫使寻优过程程始终在在次优解解附近，导导致性能能变差。5.3.22.2 基基本蚁群群算法的的实现步步骤及程程序结构构流程以TSP为为例,基基本蚁群群算法的的具体实实现步骤骤如下:参数初始始化.令令时间tt=0和和循环次次数=00,设置置最大循循环次数数,将m只只蚂蚁置置于个元元素(城城市)上上,令有有向图每每条边的的初始化化信息量量,其中中表示常常数,且且初始化化时刻。循环次数数=+1.蚂蚁的禁禁忌表索索引号=1蚂蚁数目目=+1.蚂蚁个体体根据状状态转换换概率公公式计算算的概率率选择元元素(城城市)jj并前进进,.修改禁忌忌表指针针,即选选择好之之后将蚂蚂蚁移动动到新的的元素(城市),并把把该元素素(城市市)移动动到该蚂蚂蚁个体体的禁忌忌表中.若集合CC中的元元素(城城市)未未遍历完完,即<<,则跳跳转到第第步,否否则执行行第步.根据公式式和式更新每每条路径径上的信信息量.若满足结结束条件件,即如如果循环环次数，则循环环结束并并输出程程序计算算结果,否则晴晴空禁忌忌表并跳跳转到第第步.根据上述的的基本蚁蚁群算法法实现步步骤,可可得出基基本蚁群群算法的的程序结结构框图图,如下下图所示示.5.3.33 蚁群群算法的的应用蚁群算法能能够将问问题求解解的快速速性、全全局优化化特性和和有限时时间内答答案的合合理性结结合起来来，因此此对于能能够直接接转化为为路径优优化问题题的组合合类寻优优问题，能能取得比比较理想想的效果果。5.3.33.1大规规模集成成电路的的线网布布局在大规模集集成电路路的线网网布局中中，需要要根据电电路和工工艺的要要求完成成芯片上上单元或或功能模模块的布布局，然然后实现现它们之之间的互互连。此此问题可可看作是是寻找一一个网格平平面上两两端点之之间绕过过障碍的最短短路径问问题，线线网上的的每个AAgennt根据据启发策策略 ,像蚂蚁蚁一样在在开关盒盒网格爬爬行，所所经之处处便设置置一条金金属线，历历经一个个线网的的所有引引脚之后后，线网网便布通通。应用用蚁群算算法，可可以找到到成本最最低、最最合理的的线网布布局，而而且由于于其本身身的并行行性，比比较适合合于解决决此类问问题。5.3.33.2通信网网络路由由近年来，许许多学者者将蚁群群算法应应用于通通讯领域域，特别别是通信信网络中中的路由由问题。通通信网络络的路由由是通过过路由表表进行的的，在每每个节点点的路由由表中，对对每个目目的节点点都列出出了与该该节点相相连的节节点，当当有数据据包到达达时，通通过查询询路由表表可知下下一个将将要到达达的节点点。网络络信息的的分布性性、动态态性、随随机性和和异步性性与蚁群群算法非非常相似似，都是是利用局局部信息息发现解解.间接接通讯方方式和随随机状态态的转换换。Dooriggo，DDiCaaro和和Gammbarrdellla首首先将蚁蚁群算法法应用于于网络路路由问题题，并称称这种算算法为AAntNNet。5.3.33.3蚁群算算法在电电力系统统中的应应用电力系统优优化是一一个复杂杂的系统统工程，它它包括无无功优化化、经济济负荷分分配、电电网优化化及机组组最优投投人等一一系列问问题，其其中很多多是高维维、非凸凸、非线线性的优优化问题题。其中中.机组组最优投投人问题题是寻求求一个周周期内各各个负荷荷水平下下机组的的最优组组合方式式及开停停机计划划，使运运行费用用最小。利利用状态态、决策策及路径径概念.将机组组最优投投人问题题设计成成类似旅旅行商问问题的模模式，从从而可方方便地利利用蚁群群算法来来求解。还还有人将将蚁群算算法编入入水力发发电规划划能源管管理软件件，可很很好地节节约能源源。此外外，对于于电力系系统中的的故障检检测，蚁蚁群算法法也表现现出较好好的应用用前景。由由于故障障地点的的估计信信息来自自保护继继电器和和电路断断路器，那那么对所所有故障障部分的的估计可可以看作作是一个个组合优优化问题题。蚁群群算法适适合处理理此类组组合优化化问题.因为整整个算法法过程没没有任何何监督，并并且个体体之间可可以并行行处理，但但对于蚁蚁群算法法实际应应用中的的可靠性性问题还还需讲一一步探讨讨。5.3.33.4 机器器人路径径规划问问题机器人路径径规划就就是在障障碍有界界空间内内找到一一条从出出发点到到目标位位置的无无碰撞且且能满足足一些特特定要求求的满息息路径近近几年许许多学者者开始用用蚁群算算法在这这方面进行了了一系列列出色的的研究工工作。为有效效地解决决机器人人避障问问题，并并扩展其其对具体体问题的的适应性性，在蚁蚁群算法法中通过过调整避避障系数数，可以以得到不不同的优优化轨迹迹樊晓平平等对复复杂环境境下的机器器人路径径规划进进行了初初步尝试试，但更更多的工工作有待待进一步步展开。澳大利亚学学者Ruusseell设计了了一种用用于移动机机器人的的气味传传感器导导航机制制，并深深入分析析了蚁群群算法在在该领域域应用的的鲁棒性，瑞瑞士学者者Micchaeel等将将蚁群算算法的程程序编入入微型机机器人中中，使众众多微型型机器人人像蚂蚁蚁一样协协同工作，完完成复杂杂任务。这项研研究成果果己被国国际著名名刊物Naaturre报报道。5.3.33.5 车辆辆路径问问题(VVRP)VRP(vvehiiclee rooutiingpprobblemm)研究究的是交交通运输输问题，在己知知车辆的的载重量和各各客户点点需求量量的前提提下，求至至少需要要多少车车辆，才才能满足足需求且且车辆的的总行程程最短目目前除了了一些经经典的智智能算法法以外，采采用TSP风风格的蚁蚁群算法法同样可可求解VVRP，求求解时可可将车辆辆模拟成成蚂蚁。近几年年，国内内外学者者在用蚁蚁群算法法求解VVRP方方面的研究究取得了了很多成成果，但但模拟效效果距离离现实中中的VRRP问题题还有很很大差距距因此，这这方面的的研究还还有待于于进一步步深化。此外，蚁群群算法还还在数据据挖掘、参参数辨识识、图像像处理、图图形着色色、分析析化学、岩岩石力学学以及生生命科学学等领域域的应用用取得了了很大进进展。5.3.44 蚁群群算法在在迷宫问问题中的的应用5.3.44.1 蚁群算算法在机机器人路路径规划划中的应应用机器人是一一种具有有高度灵灵活性的的自动化化机器，所所不同的的是这种种机器具具备一些些与人或或生物相相似的智智能能力力，如感感知能力力、规划划能力、动动作能力力和协同同能力等等。机器器人技术术作为220世纪纪人类最最伟大的的发明之之一，至至今已有有40多多年的发发展历史史。路径规划技技术是移移动机器器人领域域中的核核心问题题之一，也也是机器器人学中中研究人人工智能能问题的的一个重重要方面面。机器器人路径径规划是是指机器器人按照照某一性性能指标标搜索一一条从起起始状态态到目标标状态的的最优或或者近似似最优的的无碰撞撞路径，它它是实现现机器人人控制和和导航的的基础之之一。一一般可将将机器人人路径规规划算法法划分为为全局规规划和局局部规划划两类。虽虽机器人人系统是是一个松松散结构构的分布布式系统统，其优优点在于于既可独独立工作作，又可可在需要要时进行行写作，在在任务未未知的环环境中，确确定有哪哪些任务务需要多多个机器器人协作作是一个个重要而而艰巨的的任务。未未来的智智能机器器人能具具有感知知、规划划和控制制等高层层能力。它它们能从从周围的的环境中中收集知知识，构构造一个个关于环环境的符符号化的的世界模模型，并并且利用用这些模模型来规规划、执执行由应应用者下下达的高高层任务务。其中中的规划划模块能能生成大大部分的的机器人人要执行行的命令令，其目目标是实实现机器器人的使使用者在在较高层层次上给给机器人人下达一一些较宏宏观的任任务，由由机器人人系统自自身来填填充那些些较低层层的细节节问题。全全局路径径规划则则是规划划模块中中一个重重要组成成部分。今今年来，蚁蚁群算法法在机器器人路径径规划、多多机器人人协作、机机器人控控制等方方面均取取得了丰丰富的研研究成果果。5.3.44.2 改进蚁蚁群算法法原理与与在迷宫宫问题中中的实现现迷宫最优优路径问问题图2为长mm（此处处m=66）,宽宽n(此此处n=8)的的长方形形区域，在在其上任任意一点点（0im-11;0jn-11)上涂涂有灰色色或白色色，其中中灰色表表示可以以经过，白白色表示示不能经经过，且且对位于于点的蚂蚂蚁，每每次只能能按图33所示的的方向移移动一步步。则迷迷宫最优优路径问问题即为为:从长长方形区区域上的的某一点点出发，沿沿可行路路径到达达某一终终点，使使其经过过的路径径长度最最短。求解迷宫宫问题的的蚁群算算法 点的下一一步可行行点集。对于给给定的迷迷宫问题题，可用用一个一一维数组组来存储储。如对对图2所所示的迷迷宫问题题，对涂涂有灰色色的点用用1表示，白白色用00表示，则则得到如如下数组组M：M=因位于(ii, jj)点的的蚂蚁只只能沿图图3所示示的8个个方向之之一前进进一步，假假设可以以到达的的下一点点的坐标标为，则则其中di, djj两个一一维数组组，其值值为,，图 位于点点的蚂蚁蚁可移动动方位图图则点的下一一步可行行点集可可由过程程1完成成。过程程1:proceedurre GettAllloweedPoointtsforp=0 tto7beginn if(i+ddiii>=0) aand(i+ddiii<=m-11) annd(j+djji>=00) annd(jj+djji<=n-11) annd MM(i+dii，j+dji) = 1then将点(i+dii, j+dji)加入到到列表中中；end蚂蚁选择择路径的的规则 考考虑到从从点只能能到达中中的点集集，而中中的元素素最多只只有8个个，故定定义如下下的数据据结构来来存储与与该位置置相邻位位置问的的信息素素:#defiine M 166 /迷迷宫的行行数 #deffinee NN 116 /迷宫的的列数typeddef sstruuctint ii, jj; dooublle ppherromoone33; Poointt phheroomonne; /存储储从到可可达点问问的信息息素 Poiint pheerommonee Maaze pheerommonee MMNN;/存储储迷宫中中的所有有点及其其相关的的信息素素则对位于处处的蚂蚁蚁，按公公式(22)选择择下一个个可行点点其中，为蚂蚂蚁当前前可到达达的点集集，其元元素为中中的点除除去蚂蚁蚁已经过过的点;表示点点与点之间间的信息息素，其其初始值值为一较较小的正正常数，后后随算法法的运行行将会逐逐渐改变变.表示示信息素素的重要要程度，且且> 00。迷宫可行行解的构构造在利用蚁群群算法求求解迷宫宫最短路路径问题题时，为为了使每每只蚂蚁蚁能以尽尽可能高高的概率率生成可可行解，本本文采用用两组数数量相等等的蚁群群分别从从迷宫的的起点和和终点同同时出发发，每只只蚂蚁按按公式(2)确确定的概概率在迷迷宫中漫漫游。为为尽量避避免生成成无效路路径，为为蚂蚁分分配一张张禁忌表表。该表表记录蚂蚂蚁当前前走过的的点集，以以避免选选择已经经走过的的点。则则对任意意一只蚂蚂蚁，在在移动过过程中可可以定义义如下的的生命周周期:蚂蚁走走进死角角，除非非沿原路路返回一一步或多多步，不不能再朝朝前移动动，则将将该蚂蚁蚁从系统统中删除除;蚂蚁到到达另一一组蚁群群的出发发点，此此时该蚂蚂蚁走过过的路径径为一条条可行路路径;蚂蚁碰碰到另一一组的某某只蚂蚁蚁。如果果这两只只蚂蚁所所经过的的点没有有重复(相遇点点除外)，则将将两只蚂蚂蚁所经经过的路路径相连连以构成成迷宫的的一条可可行路径径。因此此，从蚁蚁群的产产生到生生命周期期的结束束，将会会有一部部分蚂蚁蚁找到问问题的可可行解，但但可行解解的数量量小于蚁蚁群数的的一半。 信息素更更新规则则在每次迭代代中，针针对当前前最好解解所属的的边按公公式行信信息素更更新， ，其中为本次次迭代最最好解的的长度，为信息素的蒸发系数。算法描述述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 本本章小结结从蚂蚁的基基本习性性和觅食食策略入入手，提提出了人人工蚂蚁蚁与真实实蚂蚁的的异同之之处，介介绍基本本蚁群算算