企业管理第五章电脑鼠控制策略与算法研究
第五章 蚁群算法在迷宫电脑鼠中的应用5.1 引言许多智能问题，如下棋游戏、战略决策、机器人路径规划等都可以转化为寻找迷宫最优路径问题。传统解决迷宫最优路径问题的算法通常会随着迷宫规模的增大、复杂性的增加，算法的空间和时间复杂性呈指数增加，从而很难用于求解大规模的问题实例。从蚁群觅食过程中能够发现蚁巢与食物源之间的最短路径受到启发，并利用该过程与著名的旅行商问题(TravelingSalesman Problem, TSP)之间的相似性，意大利学者M. Dorigo等人提出了一种新型的模拟进化算法-蚁群算法1,2。对TSP问题的求解结果显示，蚁群算法具有极强的鲁棒性和发现较好解的能力，但同时也存在一些缺陷，如收敛速度慢、易出现停滞现象等2。目前，蚁群算法已在组合优化、计算机网络路由、连续函数优化、机器人路径规划、数据挖掘、电网优化等领域取得了突出的成就2-5，实践证明该算法是一种解决优化问题特别是组合优化问题的有力工具。5.2 迷宫的基本信息及常用迷宫搜寻策略5.2.1 迷迷宫的基基本信息息从比赛规规则中得得知，迷迷宫是由由一个个个18ccm×18ccm大小小的方格格组成的的，迷宫宫大小为为16××16，即行列列各有116个方方格。若若将三维维迷宫转转化成二二维图形形,迷宫宫可用图图5.11表示.图 5.1 迷宫行行列与坐坐标对应应关系5.2.2 常常用搜寻寻法则和和策略5.2.2.11迷宫搜搜寻法则则设定搜寻寻法则和和策略是是为了电电脑鼠可可以以最最快的方方式找到到终点，到达目目标后随随即从所走过过的路径径中找出出一条可行路径径返回起起点，然然后再做做冲刺，直达目目的；法法则的设设定很重重要，它它可以使使电脑鼠鼠不多走走冤枉路路，可节节省很多多时间而而制胜。每一只电电脑鼠到到达一方方格时它它最多有有三个方方向可前前进，最最少则因因为三面面都有墙墙，没有有可以前前进的方方向；当当遇到二二个以上上的可选选择方向向时，由由于不同同场合需需要而有有不同优优先搜寻寻的方向向顺序，常见的的法则有有以下几几种：右手法法则：遇遇叉路时时，以右右边为优优先前进进方向，然后直直线方向向，左边边方向；左手法法则：遇遇叉路时时，以左左边为优优先前进进方向，然后直直线方向向，右边边方向；中左法法则：与与右手法法则相似似，不过过方向选选择顺序序改为直直线优先先，然后后左边，右边；中右法法则：遇遇叉路时时，以直直线为优优先前进进方向，然后右右边方向向，左边边方向；求心法法则：遇遇叉路时时，以距距中心最最短的那那个方向向优先，然后依依次选择择。乱数法法则：以以电脑鼠鼠的随机值作为为下一前前进方向向。5.2.2.22迷宫搜搜寻策略略迷宫搜寻寻模式有有全迷宫宫搜寻策策略和部部分迷宫宫搜寻策策略两种种：全迷宫宫搜寻策策略：电电脑鼠以以任一搜搜寻法则则前进到到达终点点后，电电脑鼠会会反身继继续前进进，然后后以原设设定的搜搜寻法则则，时时时检查未未走过的的路，直直到每一一方格都都搜寻过过后，才才回起点点。部分迷迷宫搜寻寻策略：电脑鼠鼠以任一一搜寻法法则前进进到达终终点后，电脑鼠鼠将沿原原路线返返回起点点，不再再进行其其它搜寻寻。如果比赛赛规则不不计算搜搜寻时间间，可采采用全迷迷宫搜寻寻策略，待地毯毯式的搜搜寻过所所有方格格后，再再计算最最佳路径径，作最最后的冲冲刺，冲冲刺成绩绩一定相相当不错错。由于于新制国国际比赛赛规则加加入搜寻寻时间的的成绩计计量，因因此我们们必须考考虑部分分迷宫搜搜寻策略略，甚至至还可能能须考虑虑加入求求心法则则，截路路径功能能等更智智慧的法法则来协协助；此此时找到到的路径径可能不不是最佳佳路径，但保证证花的时时间最短短。5.2.3迷宫宫问题经经典算法法求解迷宫宫问题，经典算算法有深深度优先先搜索和和广度优优先搜索索两种。深度优优先搜索索(DFFS)：从入口口出发，顺着某某一方向向向前探探索，若若能走通通，则继继续往前前走；否否则沿原原路退回回(回溯)，换一一个方向向再继续续探索直至所所有可能能的通路路都探索索到为止止。如果果恰好某某一步探探索到出出口，则则就找到到了从入入口到出出口的路路径。为为了保证证在任何何位置上上都能沿沿原路退退回，防防止死循循环，需需要使用用堆栈来来保存大大量记录录。而要要求解迷迷宫最短短路径，则必须须用深度度优先搜搜索出所所有到达达出口的的路径，通过比比较得到到最短距距离的路路径这这样也必必然要求求增加数数据空间间来保存存搜索过过程中当当前最短短路径增加了了空间复复杂度。广度优优先搜索索(BFFS)：从入口口出发，离开入入口后依依次访问问与当前前位置邻邻接的单单元格(上下左左右方向向)，然后后分别从从这些相相邻单元元格出发发依次访访问它们们的邻接接格，并并使“先被访访问的单单元格的的邻接格格先于后被访访问的单单元格的的邻接格格”被访问问，直至至访问到到迷宫出出口，则则找到了了迷宫问问题的最最优解，即迷宫宫最短路路径。该该算法的的显著特特点是“层层推推进”，探索索点会随随着探索索的深入入急剧增增加，相相应地，需要大大量的空空间用来来保存探探索过程程的记录录空间间复杂度度大。与此同时时，上述述两种算算法都比比较抽象象复杂，编程实实现容易易出现问问题调调试比较较困难，因此在在本篇论论文中提提出了一一种新的的容易理理解和调调试的算算法，该该算法复复杂度较较低，求求解较大大规模的的迷宫问问题也有有不俗的的表现。5.3蚁蚁群算法法在迷宫宫电脑鼠鼠中的应应用5.3.1 蚁蚁群算法法的基本本知识5.3.1.11 蚂蚁蚁的基本本习性 蚂蚁是是最古老老的社会会昆虫之之一，它它的个体体结构和和行为虽虽简单，但是由由这些简简单个体体构成的的蚂蚁群群体，却却表现出出高度结结构化的的社会组组织.蚂蚂蚁王国国俨然是是一个小小小“社会”。这里，有专司司产卵的的后蚁;有为数数众多的的从事觅觅食打猎猎、兴建建屋穴、抚育后后代的工工蚁;有有负责守守卫门户户、对敌敌作战的的兵蚁;还有专专备后蚁蚁招婿纳纳赘的雄蚁蚁等等.蚂蚁是社社会性昆昆虫，组组成社会会的三要要素之一一就是社社会成员员除有组组织、有有分工之之外，还还有相互互的通讯讯和信息息传递。研究表明，蚁蚁群有着着奇妙的的信息系系统，其中包包括视觉觉信号、声音通通讯和更更为独特特的无声声语育，即包括括化学物物质不同同的组合合、触角角信号和和身体动动作在内内的多个个征集系系统，来来策动其其他个体体.蚂蚁蚁特有的的控制自自身环境境的能力力，是在在高级形形式的社社会性行行为及不不断进化化过程中中获得的的。5.3.1.22蚂蚁的的觅食策策略觅食行为为是蚁群群一个重重要而有有趣的行行为.据据昆虫学学家的观观察和研研究，发发现蚂蚁蚁有能力力在没有有任何可可见提示示下找出出从蚁穴穴到食物物源的最最短路径径，并且且能随环环境变化化适应性性地搜索索新的路路径，产产生新的的选择.虽然单单个蚂蚁蚁的行为为极其简简单，但但由大量量的蚂蚁蚁个体组组成蚂蚁蚁群体却却表现出出极其复复杂的行行为，能能够完成成复杂的的任务。1生物学家家和仿生生学家经经过大量量的细致致观察研研究发现现，蚂蚁蚁在觅食食走过的的路径上上释放一一种妈蚁蚁特有的的分泌物物-信息息激素(Pheerommonee).蚂蚂蚁个体体之间正正是通过过这种信信息激素素进行信信息传递递，从而而能相互互协作，完成复复杂任务务.在一一定范围围内蚂蚁蚁能够察察觉到这这种信息息激素并并指导它它的行为为，当一一些路径径通过的的蚂蚁越越多，则则留下的的信息激激素轨迹迹(trraill )也也就越多多，招致致后来更更多的蚂蚂蚁选择择该路径径的概率率也越高高，于是是越发增增加了该该路径的的信息素素强度.这种选选择过程程称之为为蚂蚁的的自催化化过程，形成一一种正反反馈机制制，可理理解为增增强型学学习系统统.蚂蚁蚁最终可可以发现现最短路路径.自然界中中蚁群的的自组织织行为引引起了昆昆虫学家家的注意意.Deuuuu-bouurg等等通过“双桥实实验”对蚁群群的觅食食行为进进行了研研究如图图5.22所示，对称双双桥(两两座桥的的长度相相同)AA、B将蚁巢巢与食物物源分开开，蚂蚁蚁从蚁巢巢自由地地向食物源移移动.实实验结果果显示，在初始始阶段出出现一段段时间的的震荡(由于某某些随机机因素，使通过过某座桥桥上的蚂蚂蚁数急急剧增多多或减少少)后，蚂蚁趋趋向于走同一一条路径径.在该该实验中中，绝大大部分蚂蚂蚁选择择A桥. 在实验初初期，AA, BB两座桥桥上都没没有外激激素存在在，蚂蚁蚁将以相相同的概概率选择择A、BB两座桥桥，故此此时蚂蚁蚁在两座座桥上留留下的外外激素量量相等.经过一一段时间间后，由由于随机波波动致使使大部分分蚂蚁选选择A桥桥(也有有可能为为B桥)，因此此更多的的外激素素将会留留在A桥桥上，致致使A桥桥对后来来的蚂蚁蚁有更大大的吸引引力.随随着时问问的推移移，A桥桥上的蚂蚂蚁数将将越来越越多,而而B桥上上正好相相反.SG.ooaaLLsy等等人给出出了上述实验验的概率模型型.首先先，假定定桥上残残留的外外激素量量与过去去一段时时间经过过该桥的的蚂蚁数数成正比比(这意意味着不不考虑外外激素蒸蒸发的情情况);其次，某一时时刻蚂蚁蚁按桥上上外激素素量的多多少来选选择某座座桥，即即蚂蚁选选择某座座桥的概概率与经经过该桥桥的蚂蚁蚁数成正正比.当当所有mm只蚂蚁蚁都经过过两座桥桥以后，设Amm, AAn分别别为经过过A桥和和B桥的的蚂蚁数数(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 蚁群群的自适适应行为为(a.)蚁群在在蚁巢和和食物源源之间的的路径上上移动(b)路路径上出出现障碍碍物(c)较较短路径径上的外外激素以以更快的的速度增增加(d)所所有的蚂蚂蚁都选选择较短短的路径径5.1.1.33 人工工蚂蚁与与真实蚂蚂蚁的异异同比较较相同点点比较蚁群算法法是从自自然中真真实蚂蚁蚁觅食的的群体行行为得到到启发而而提出的的，其很很多观点点都来源源于真实实蚁群，因此算算法中所所定义的的人工蚂蚂蚁与真真实蚂蚁蚁存在如如下共同同点。都存在在一个群群体中个个体相互互交流通通信的机机制。人人工蚂蚁蚁与真实实蚂蚁都都存在一一种改变变当前所所处环境境的机制制：真实实蚂蚁在在经过的的路径上上留下信信息素，人工蚂蚂蚁改变变在其所所经过路路径上存存储的数数字信息息，该信信息就是是算法中中所定义义的信息息量，它它记录了了蚂蚁当当前解和和历史解解的性能能状态，而且可可被其他他后继人人工蚂蚁蚁读写。都要完完成一个个相同的的任务。人工蚂蚂蚁与真真实蚂蚁蚁都要完完成一个个相同的的任务，即寻找找一条从从源节点点（巢穴穴）到目目的节点点（食物物）的最最短路径径。利用当当前信息息进行路路径选择择的随机机选择策策略。人人工蚂蚁蚁与真实实蚂蚁从从某一个个节点到到下一个个节点的的移动是是利用概概率选择择策略实实现的，
