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

第五章 蚁群算法在迷宫电脑鼠中的应用5.1 引言许多智能问题，如下棋游戏、战略决策、机器人路径规划等都可以转化为寻找迷宫最优路径问题。传统解决迷宫最优路径问题的算法通常会随着迷宫规模的增大、复杂性的增加，算法的空间和时间复杂性呈指数增加，从而很难用于求解大规模的问题实例。从蚁群觅食过程中能够发现蚁巢与食物源之间的最短路径受到启发，并利用该过程与著名的旅行商问题( Traveling Salesman Problem, TSP)之间的相似性，意大利学者M. Dorigo等人提出了一种新型的模拟进化算法-蚁群算法1,2。对TSP问题的求解结果显示，蚁群算法具有极强的鲁棒性和发现较好解的能力，但同时也存在一些缺陷，如收敛速度慢、易出现停滞现象等2。目前，蚁群算法已在组合优化、计算机网络路由、连续函数优化、机器人路径规划、数据挖掘、电网优化等领域取得了突出的成就2-5，实践证明该算法是一种解决优化问题特别是组合优化问题的有力工具。5.2 迷宫的基本信息及常用迷宫搜寻策略5.2.1 迷宫的基本信息从比赛规则中得知，迷宫是由一个个18cm×18cm大小的方格组成的，迷宫大小为16×16，即行列各有16个方格。若将三维迷宫转化成二维图形,迷宫可用图5.1表示.图 5.1 迷宫行列与坐标对应关系5.2.2 常用搜寻法则和策略5.2.2.1迷宫搜寻法则设定搜寻法则和策略是为了电脑鼠可以以最快的方式找到终点，到达目标后随即从所走过的路径中找出一条可行路径返回起点，然后再做冲刺，直达目的；法则的设定很重要，它可以使电脑鼠不多走冤枉路，可节省很多时间而制胜。每一只电脑鼠到达一方格时它最多有三个方向可前进，最少则因为三面都有墙，没有可以前进的方向；当遇到二个以上的可选择方向时，由于不同场合需要而有不同优先搜寻的方向顺序，常见的法则有以下几种：右手法则：遇叉路时，以右边为优先前进方向，然后直线方向，左边方向；左手法则：遇叉路时，以左边为优先前进方向，然后直线方向，右边方向；中左法则：与右手法则相似，不过方向选择顺序改为直线优先，然后左边，右边；中右法则：遇叉路时，以直线为优先前进方向，然后右边方向，左边方向；求心法则：遇叉路时，以距中心最短的那个方向优先，然后依次选择。乱数法则：以电脑鼠的随机值作为下一前进方向。5.2.2.2迷宫搜寻策略迷宫搜寻模式有全迷宫搜寻策略和部分迷宫搜寻策略两种：全迷宫搜寻策略：电脑鼠以任一搜寻法则前进到达终点后，电脑鼠会反身继续前进，然后以原设定的搜寻法则，时时检查未走过的路，直到每一方格都搜寻过后，才回起点。部分迷宫搜寻策略：电脑鼠以任一搜寻法则前进到达终点后，电脑鼠将沿原路线返回起点，不再进行其它搜寻。如果比赛规则不计算搜寻时间，可采用全迷宫搜寻策略，待地毯式的搜寻过所有方格后，再计算最佳路径，作最后的冲刺，冲刺成绩一定相当不错。由于新制国际比赛规则加入搜寻时间的成绩计量，因此我们必须考虑部分迷宫搜寻策略，甚至还可能须考虑加入求心法则，截路径功能等更智慧的法则来协助；此时找到的路径可能不是最佳路径，但保证花的时间最短。5.2.3 迷宫问题经典算法求解迷宫问题，经典算法有深度优先搜索和广度优先搜索两种。深度优先搜索(DFS)：从入口出发，顺着某一方向向前探索，若能走通，则继续往前走；否则沿原路退回(回溯)，换一个方向再继续探索直至所有可能的通路都探索到为止。如果恰好某一步探索到出口，则就找到了从入口到出口的路径。为了保证在任何位置上都能沿原路退回，防止死循环，需要使用堆栈来保存大量记录。而要求解迷宫最短路径，则必须用深度优先搜索出所有到达出口的路径，通过比较得到最短距离的路径这样也必然要求增加数据空间来保存搜索过程中当前最短路径增加了空间复杂度。广度优先搜索(BFS)：从入口出发，离开入口后依次访问与当前位置邻接的单元格(上下左右方向)，然后分别从这些相邻单元格出发依次访问它们的邻接格，并使“先被访问的单元格的邻接格先于后被访问的单元格的邻接格”被访问，直至访问到迷宫出口，则找到了迷宫问题的最优解，即迷宫最短路径。该算法的显著特点是“层层推进”，探索点会随着探索的深入急剧增加，相应地，需要大量的空间用来保存探索过程的记录空间复杂度大。与此同时，上述两种算法都比较抽象复杂，编程实现容易出现问题调试比较困难，因此在本篇论文中提出了一种新的容易理解和调试的算法，该算法复杂度较低，求解较大规模的迷宫问题也有不俗的表现。5.3蚁群算法在迷宫电脑鼠中的应用5.3.1 蚁群算法的基本知识5.3.1.1 蚂蚁的基本习性 蚂蚁是最古老的社会昆虫之一，它的个体结构和行为虽简单，但是由这些简单个体构成的蚂蚁群体，却表现出高度结构化的社会组织.蚂蚁王国俨然是一个小小“社会”。这里，有专司产卵的后蚁;有为数众多的从事觅食打猎、兴建屋穴、抚育后代的工蚁;有负责守卫门户、对敌作战的兵蚁;还有专备后蚁招婿纳赘的雄蚁等等.蚂蚁是社会性昆虫，组成社会的三要素之一就是社会成员除有组织、有分工之外，还有相互的通讯和信息传递。研究表明，蚁群有着奇妙的信息系统，其中包括视觉信号、声音通讯和更为独特的无声语育，即包括化学物质不同的组合、触角信号和身体动作在内的多个征集系统，来策动其他个体.蚂蚁特有的控制自身环境的能力，是在高级形式的社会性行为及不断进化过程中获得的。5.3.1.2蚂蚁的觅食策略觅食行为是蚁群一个重要而有趣的行为.据昆虫学家的观察和研究，发现蚂蚁有能力在没有任何可见提示下找出从蚁穴到食物源的最短路径，并且能随环境变化适应性地搜索新的路径，产生新的选择.虽然单个蚂蚁的行为极其简单，但由大量的蚂蚁个体组成蚂蚁群体却表现出极其复杂的行为，能够完成复杂的任务。1生物学家和仿生学家经过大量的细致观察研究发现，蚂蚁在觅食走过的路径上释放一种妈蚁特有的分泌物-信息激素(Pheromone).蚂蚁个体之间正是通过这种信息激素进行信息传递，从而能相互协作，完成复杂任务.在一定范围内蚂蚁能够察觉到这种信息激素并指导它的行为，当一些路径通过的蚂蚁越多，则留下的信息激素轨迹(trail )也就越多，招致后来更多的蚂蚁选择该路径的概率也越高，于是越发增加了该路径的信息素强度.这种选择过程称之为蚂蚁的自催化过程，形成一种正反馈机制，可理解为增强型学习系统.蚂蚁最终可以发现最短路径.自然界中蚁群的自组织行为引起了昆虫学家的注意.Deuuu-bourg等通过“双桥实验”对蚁群的觅食行为进行了研究如图5.2所示，对称双桥(两座桥的长度相同)A、B将蚁巢与食物源分开，蚂蚁从蚁巢自由地向食物源移动.实验结果显示，在初始阶段出现一段时间的震荡(由于某些随机因素，使通过某座桥上的蚂蚁数急剧增多或减少)后，蚂蚁趋向于走同一条路径. 在该实验中，绝大部分蚂蚁选择A桥. 在实验初期，A, B两座桥上都没有外激素存在，蚂蚁将以相同的概率选择A、B两座桥，故此时蚂蚁在两座桥上留下的外激素量相等.经过一段时间后，由于随机波动致使大部分蚂蚁选择A桥(也有可能为B桥)，因此更多的外激素将会留在A桥上，致使A桥对后来的蚂蚁有更大的吸引力.随着时问的推移，A桥上的蚂蚁数将越来越多,而B桥上正好相反.SG.oaaLsy等人给出了上述实验的概率模型.首先，假定桥上残留的外激素量与过去一段时间经过该桥的蚂蚁数成正比(这意味着不考虑外激素蒸发的情况);其次，某一时刻蚂蚁按桥上外激素量的多少来选择某座桥，即蚂蚁选择某座桥的概率与经过该桥的蚂蚁数成正比.当所有m只蚂蚁都经过两座桥以后，设Am, An分别为经过A桥和B桥的蚂蚁数(Am+ An=m),则第m+ 1只蚂蚁选择A桥的概率为: 式(5.0)而选择B桥的概率为:其中参数h和k用来匹配真实实验数据.第(m+1)只蚂蚁首先按式(5.0)计算选择概率PA(m)，然后生成一个在区间0,1上一致分布的随机数a，如果aPA(m)，则选择A桥，否则选择B桥. 图5.2双桥实验除能够找到蚁巢和食物源之间的最短路径外，蚁群还有极强的适应环境的能力，如图5.3所示，在蚁群经过的路线上突然出现障碍物时，蚁群能够很快重新找到新的最优路径。图5.3 蚁群的自适应行为(a.)蚁群在蚁巢和食物源之间的路径上移动(b)路径上出现障碍物(c)较短路径上的外激素以更快的速度增加(d)所有的蚂蚁都选择较短的路径5.1.1.3 人工蚂蚁与真实蚂蚁的异同比较相同点比较蚁群算法是从自然中真实蚂蚁觅食的群体行为得到启发而提出的，其很多观点都来源于真实蚁群，因此算法中所定义的人工蚂蚁与真实蚂蚁存在如下共同点。都存在一个群体中个体相互交流通信的机制。人工蚂蚁与真实蚂蚁都存在一种改变当前所处环境的机制：真实蚂蚁在经过的路径上留下信息素，人工蚂蚁改变在其所经过路径上存储的数字信息，该信息就是算法中所定义的信息量，它记录了蚂蚁当前解和历史解的性能状态，而且可被其他后继人工蚂蚁读写。都要完成一个相同的任务。人工蚂蚁与真实蚂蚁都要完成一个相同的任务，即寻找一条从源节点（巢穴）到目的节点（食物）的最短路径。利用当前信息进行路径选择的随机选择策略。人工蚂蚁与真实蚂蚁从某一个节点到下一个节点的移动是利用概率选择策略实现的，概率选择策略只利用当前的信息去预测未来的情况，而不能利用未来的信息，故选择策略在时间和空间都是局部的。不同点比较在从真实蚁群行为获得启发而构造蚁群算法的过程中，人工蚂蚁还具备了真实蚂蚁所不具有的一些特性。人工蚂蚁存在于一个离散的空间中，他们的移动式从一个状态到另外一个状态的转换。人工蚂蚁具有记忆起本身过去行为的内在状态。人工蚂蚁存在于一个与时间无关联的环境之中。人工不是完全盲目的，它还受到问题空间特征的启发。例如有的问题中人工蚂蚁在产生一个解后改变信息量，而有的问题中人工蚂蚁每作出一步选择就更改信息量，但无论哪种方法，信息量的更新并不是随机都可以进行的。为了改善算法的优化效率，人工蚂蚁可增加一些性能，如预测未来、局部优化、回退等，这些行为在真实蚂蚁行为中是不存在的。在很多具体的应用中，人工蚂蚁可在局部优化过程中相互交换信息，还有一些蚁群算法中的人工蚂蚁可实现简单的预测。5.3.1.4 蚁群算法的基本特点蚁群优化算法是从自然界中蚂蚁的觅食行为受到启发而提出的一种模拟进化算法。ACO算法可以看成是一种基于解空间参数化概率分布模型的搜索算法框架，其中解空间参数化概率模型的参数就是信息素，因而这种模型就是信息素模型.在基于模型的搜索算法框架中，可行解通过在一个解空间参数化概率分布模型上的搜索产生，此模型的参数用以前产生的解来进行更新，使得在新模型上的搜索能集中在高质量的解搜索空间内.这种方法的有效性建立在高质量的解总是包含好的解构成元素的假设前提下.通过学习这些解构成元素对解的质量的影响有助于找到一种机制，并通过解构成元素的最佳组合来构造出高质量的解。蚁群优化算法的主要特点概括如下:采用分布式控制，不存在中心控制;每个个体只能感知局部的信息，不能直接使用全局信息; 个体可改变环境，并通过环境来进行间接通讯机制; 具有自组织性，即群体的复杂行为是通过个体的交互过程中突现出来的智能; 是一类概率型的全局搜索方法，这种非确定性使算法能够有更多的机会求得全局最优解; 其优化过程不依赖于优化问题本身的严格数学性质，诸如连续性、可导性及目标函数和约束函数的精确数学描述; 是一类基于多主体的智能算法，各主体间通过相互协作来更好地适应环境; 具有潜在的并行性，其搜索过程不是从一点出发，而是同时从多个点同时进行.这种分布式多智能体的协作过程是异步并发进行的，分布并行模式将大大提高整个算法的运行效率和快速反应能力。5.3.2 基本蚁群算法的原理及算法实现5.3.2.1 基本蚁群算法的机制原理模拟蚂蚁群体觅食行为的蚁群算是作为一种新的计算智能模式引入的,该算法基于如下基本假设：蚂蚁之间通过信息素和环境进行通信.每只蚂蚁仅更具其周围的局部环境做出反应,也只对其周围的局部环境产生影响。蚂蚁对环境的反应由其内部模式决定.因为蚂蚁是基因生物,蚂蚁的行为实际上是其基因的适应性表现,即蚂蚁是反应型适应性主体。在个体水平上,每只蚂蚁仅根据环境做出独立选择;在群体水平上,单质蚂蚁的行为是随机的,但蚁群可通过自组织过程形成高度有序的群体行为。由上述假设和分析可见,基本蚁群算法的寻优机制包括两个基本段:适应阶段和协作阶段.在适应阶段,各候选解根据积累的信息不断调整自身结构,路径上经过的蚂蚁越多,信息量越大,则该路径越容易被选择;时间越长,信息量会越小;在协作阶段,候选解之间通过信息交流,以期望产生性能更好的解,类似于学习自动机的学习机制。蚁群算法实际上是一类智能多主体系统,其自组织机制使得蚁群算法不需要对所求问题的每一个方面都有详尽的认识.自组织本质上是蚁群算法机制在没有外界作用下使系统熵增加的动态过程,体现了从无序到有序的动态演化,其逻辑结构如图5.4所示。信息素更新管理组合优化问题信息素,决策点问题表达个体B信息素个体A信息素蚁群活动规划图5.4 基本蚁群算法的逻辑结构由图5.4可见,先将具体的组合优化问题表述成规范的格式,然后利用蚁群算法在“探索(exploration)”和“利用(exploitation)”之间根据信息素这一反馈载体确定决策点,同时按照相应的信息素根新规则对每只蚂蚁个体的信息素进行增量构建,随后从整体角度规划出蚁群活动的行为方向,周而复始,即可求出组合优化问题的最优解。5.3.2.2基本蚁群算法的数学模型设bi(t)表示t时刻位于元素i的蚂蚁数目,为t时刻路径上的信息量,n表示TSP规模,m为蚁群蚂蚁的总数目,则m=;=是t时刻各条路径上信息量相等,并设=const,基本蚁群算法的寻优是通过有向图g=(C,L, )实现的. 蚂蚁在运动过程中,根据各条路径上的信息量决定其转移方向.这里用禁忌表来记录蚂蚁k当前所走过的城市,集合随着进化过程做动态调整.在搜索过程中,蚂蚁根据各路径上的信息量及路径的启发信息来计算状态转移概率.表示t时刻蚂蚁由元素(城市)i转移到元素(城市)j的状态转移概率 式(5.1)式中,表示蚂蚁下一步允许选择的城市;为信息启发式因子,表示轨迹的相对重要性,反映了蚂蚁在运动过程中所积累的信息在蚂蚁运动时所起的作用,其值越大,则改蚂蚁越倾向于选择其他蚂蚁经过的路径,蚂蚁之间协作性越强;为期望启发式因子,表示能见度的相对重要性,反映了蚂蚁在运动过程中启发信息在蚂蚁选择路径中的受重视的成度,其值越大,则该状态转移概率越接近于贪心规则;为启发函数,其表达式如下 式(5.2)式中, 表示相邻两个城市之间的距离.对蚂蚁而言, 越小,则越大, 也越大.显然,该启发函数表示蚂蚁从元素(城市)i转移到元素(城市)j的期望程度.为了避免残留信息素过多引起残留信息淹没启发信息,在每只蚂蚁走完了一步或者完成对所有n个城市的遍历(也即一个循环结束)后,要对残留信息进行更新处理.这种更新策略模仿了人类大脑记忆的特点,在新信息不断存如大脑的同时,存储在大脑中的旧信息随着时间的推移逐渐淡化,甚至忘记.由此,t+n时刻路径上的信息量可按如下规则进行调整 式(5.3) 式(5.4)式中,表示信息素挥发系数,则表示信息素残留因子,为了防止信息的无限积累, 的取值范围为:; 表示本次循环中路径(i, j)上的信息素增量,初始时刻,)表示第只蚂蚁在本次循环中留在路径(i, j)上的信息量.根据信息素更新策略的不同，Dorigo M提出了三种不同的基本蚁群算法模型,分别称之为Ant-Cycle模型、Ant-Quantity模型及Ant-Density模型,其差别在于求发不同.在Ant-Cycle模型中 式(5.5)式中,Q表示信息素强度,它在一定程度上影响了算法的收敛速度; 表示第只蚂蚁在本次循环中所走路径的总长度.在Ant-Quantity模型中 式(5.6)在Ant-Density模型中 式(5.7)区别: 式(5.6)和式(5.7)中利用的是局部信息,即蚂蚁走完一步后更新路径上的信息素;而式(5.5)中利用的是整体信息,即蚂蚁完成了一个循环后更新所有路径上的信息素,在求解TSP时性能较好,因此通常采用式(5.5)作为蚁群算法的基本模型. 此外，在Dorigo M等人的论文中还对蚁群算法提出了一些讨论，其中包括不同的蚁群初始分布对求解的影响等，还提出了所谓的精英策略(elitist strategy)，以强化精英蚂蚁(发现迄今最好路径的蚂蚁)的影响.结果发现，对精英蚂蚁数而言有一个最优的范围:低于此范围，增加精英蚂蚁数可较早地发现更好的路径，高于此范围，精英蚂蚁会在搜索早期迫使寻优过程始终在次优解附近，导致性能变差。5.3.2.2 基本蚁群算法的实现步骤及程序结构流程以TSP为例,基本蚁群算法的具体实现步骤如下:参数初始化.令时间t=0和循环次数=0,设置最大循环次数,将m只蚂蚁置于个元素(城市)上,令有向图每条边的初始化信息量,其中表示常数,且初始化时刻。循环次数=+1.蚂蚁的禁忌表索引号=1蚂蚁数目=+1.蚂蚁个体根据状态转换概率公式计算的概率选择元素(城市)j并前进,.修改禁忌表指针,即选择好之后将蚂蚁移动到新的元素(城市),并把该元素(城市)移动到该蚂蚁个体的禁忌表中.若集合C中的元素(城市)未遍历完,即<,则跳转到第步,否则执行第步.根据公式和式更新每条路径上的信息量.若满足结束条件,即如果循环次数，则循环结束并输出程序计算结果,否则晴空禁忌表并跳转到第步.根据上述的基本蚁群算法实现步骤,可得出基本蚁群算法的程序结构框图,如下图所示.5.3.3 蚁群算法的应用蚁群算法能够将问题求解的快速性、全局优化特性和有限时间内答案的合理性结合起来，因此对于能够直接转化为路径优化问题的组合类寻优问题，能取得比较理想的效果。5.3.3.1大规模集成电路的线网布局在大规模集成电路的线网布局中，需要根据电路和工艺的要求完成芯片上单元或功能模块的布局，然后实现它们之间的互连。此问题可看作是寻找一个网格平面上两端点之间绕过障碍的最短路径问题，线网上的每个Agent根据启发策略 ,像蚂蚁一样在开关盒网格爬行，所经之处便设置一条金属线，历经一个线网的所有引脚之后，线网便布通。应用蚁群算法，可以找到成本最低、最合理的线网布局，而且由于其本身的并行性，比较适合于解决此类问题。5.3.3.2通信网络路由近年来，许多学者将蚁群算法应用于通讯领域，特别是通信网络中的路由问题。通信网络的路由是通过路由表进行的，在每个节点的路由表中，对每个目的节点都列出了与该节点相连的节点，当有数据包到达时，通过查询路由表可知下一个将要到达的节点。网络信息的分布性、动态性、随机性和异步性与蚁群算法非常相似，都是利用局部信息发现解.间接通讯方式和随机状态的转换。Dorigo，DiCaro和Gambardella首先将蚁群算法应用于网络路由问题，并称这种算法为AntNet。5.3.3.3蚁群算法在电力系统中的应用电力系统优化是一个复杂的系统工程，它包括无功优化、经济负荷分配、电网优化及机组最优投人等一系列问题，其中很多是高维、非凸、非线性的优化问题。其中.机组最优投人问题是寻求一个周期内各个负荷水平下机组的最优组合方式及开停机计划，使运行费用最小。利用状态、决策及路径概念.将机组最优投人问题设计成类似旅行商问题的模式，从而可方便地利用蚁群算法来求解。还有人将蚁群算法编入水力发电规划能源管理软件，可很好地节约能源。此外，对于电力系统中的故障检测，蚁群算法也表现出较好的应用前景。由于故障地点的估计信息来自保护继电器和电路断路器，那么对所有故障部分的估计可以看作是一个组合优化问题。蚁群算法适合处理此类组合优化问题.因为整个算法过程没有任何监督，并且个体之间可以并行处理，但对于蚁群算法实际应用中的可靠性问题还需讲一步探讨。5.3.3.4 机器人路径规划问题 机器人路径规划就是在障碍有界空间内找到一条从出发点到目标位置的无碰撞且能满足一些特定要求的满息路径近几年许多学者开始用蚁群算法在这方面进行了一系列出色的研究工作。为有效地解决机器人避障问题，并扩展其对具体问题的适应性，在蚁群算法中通过调整避障系数，可以得到不同的优化轨迹樊晓平等对复杂环境下的机器人路径规划进行了初步尝试，但更多的工作有待进一步展开。澳大利亚学者Russell设计了一种用于移动机器人的气味传感器导航机制，并深入分析了蚁群算法在该领域应用的鲁棒性，瑞士学者Michael等将蚁群算法的程序编入微型机器人中，使众多微型机器人像蚂蚁一样协同工作，完成复杂任务。这项研究成果己被国际著名刊物Nature报道。5.3.3.5 车辆路径问题(VRP) VRP(vehicle routing problem)研究的是交通运输问题，在己知车辆的载重量和各客户点需求量的前提下，求至少需要多少车辆，才能满足需求且车辆的总行程最短目前除了一些经典的智能算法以外，采用TSP风格的蚁群算法同样可求解VRP，求解时可将车辆模拟成蚂蚁。近几年，国内外学者在用蚁群算法求解VRP方面的研究取得了很多成果，但模拟效果距离现实中的VRP问题还有很大差距因此，这方面的研究还有待于进一步深化。 此外，蚁群算法还在数据挖掘、参数辨识、图像处理、图形着色、分析化学、岩石力学以及生命科学等领域的应用取得了很大进展。5.3.4 蚁群算法在迷宫问题中的应用5.3.4.1 蚁群算法在机器人路径规划中的应用机器人是一种具有高度灵活性的自动化机器，所不同的是这种机器具备一些与人或生物相似的智能能力，如感知能力、规划能力、动作能力和协同能力等。机器人技术作为20世纪人类最伟大的发明之一，至今已有40多年的发展历史。路径规划技术是移动机器人领域中的核心问题之一，也是机器人学中研究人工智能问题的一个重要方面。机器人路径规划是指机器人按照某一性能指标搜索一条从起始状态到目标状态的最优或者近似最优的无碰撞路径，它是实现机器人控制和导航的基础之一。一般可将机器人路径规划算法划分为全局规划和局部规划两类。虽机器人系统是一个松散结构的分布式系统，其优点在于既可独立工作，又可在需要时进行写作，在任务未知的环境中，确定有哪些任务需要多个机器人协作是一个重要而艰巨的任务。未来的智能机器人能具有感知、规划和控制等高层能力。它们能从周围的环境中收集知识，构造一个关于环境的符号化的世界模型，并且利用这些模型来规划、执行由应用者下达的高层任务。其中的规划模块能生成大部分的机器人要执行的命令，其目标是实现机器人的使用者在较高层次上给机器人下达一些较宏观的任务，由机器人系统自身来填充那些较低层的细节问题。全局路径规划则是规划模块中一个重要组成部分。今年来，蚁群算法在机器人路径规划、多机器人协作、机器人控制等方面均取得了丰富的研究成果。5.3.4.2 改进蚁群算法原理与在迷宫问题中的实现迷宫最优路径问题图2为长m（此处m=6）,宽n(此处n=8)的长方形区域，在其上任意一点（0im-1;0jn-1)上涂有灰色或白色，其中灰色表示可以经过，白色表示不能经过，且对位于点的蚂蚁，每次只能按图3所示的方向移动一步。则迷宫最优路径问题即为:从长方形区域上的某一点出发，沿可行路径到达某一终点，使其经过的路径长度最短。求解迷宫问题的蚁群算法 点的下一步可行点集。对于给定的迷宫问题，可用一个一维数组来存储。如对图2所示的迷宫问题，对涂有灰色的点用1表示，白色用0表示，则得到如下数组M：M=因位于(i, j)点的蚂蚁只能沿图3所示的8个方向之一前进一步，假设可以到达的下一点的坐标为，则 其中di, dj两个一维数组，其值为,，图 位于点的蚂蚁可移动方位图则点的下一步可行点集可由过程1完成。过程1:procedure GetAllowedPoints for p= 0 to 7begin if( i+dii>=0) and ( i+dii<=m-1) and (j+dji>=0) and (j+dji<=n-1) and M(i+dii，j+dji) = 1then将点(i+dii, j+dji)加入到列表中；end 蚂蚁选择路径的规则 考虑到从点只能到达中的点集，而中的元素最多只有8个，故定义如下的数据结构来存储与该位置相邻位置问的信息素: #define M 16 /迷宫的行数 #define N 16 /迷宫的列数typedef struct int i, j; double pheromone33; Point pheromone; /存储从到可达点问的信息素 Point pheromone Maze pheromone MN;/存储迷宫中的所有点及其相关的信息素则对位于处的蚂蚁，按公式(2)选择下一个可行点 其中，为蚂蚁当前可到达的点集，其元素为中的点除去蚂蚁已经过的点;表示点与点之间的信息素，其初始值为一较小的正常数，后随算法的运行将会逐渐改变.表示信息素的重要程度，且> 0。迷宫可行解的构造在利用蚁群算法求解迷宫最短路径问题时，为了使每只蚂蚁能以尽可能高的概率生成可行解，本文采用两组数量相等的蚁群分别从迷宫的起点和终点同时出发，每只蚂蚁按公式(2)确定的概率在迷宫中漫游。为尽量避免生成无效路径，为蚂蚁分配一张禁忌表。该表记录蚂蚁当前走过的点集，以避免选择已经走过的点。则对任意一只蚂蚁，在移动过程中可以定义如下的生命周期:蚂蚁走进死角，除非沿原路返回一步或多步，不能再朝前移动，则将该蚂蚁从系统中删除;蚂蚁到达另一组蚁群的出发点，此时该蚂蚁走过的路径为一条可行路径;蚂蚁碰到另一组的某只蚂蚁。如果这两只蚂蚁所经过的点没有重复(相遇点除外)，则将两只蚂蚁所经过的路径相连以构成迷宫的一条可行路径。因此，从蚁群的产生到生命周期的结束，将会有一部分蚂蚁找到问题的可行解，但可行解的数量小于蚁群数的一半。 信息素更新规则在每次迭代中，针对当前最好解所属的边按公式行信息素更新， ， 其中为本次迭代最好解的长度，为信息素的蒸发系数。算法描述 Step1. 初始化参数，, Step2. 生成2*只蚂蚁，将其中只放到起点以，另外只放到终点Step3. while活蚂蚁数大于0 do for 蚂蚁 doif蚂蚁活着and 非空 then (1)按公式(2)计算转移概率; (2)按概率选择下一个点; (3)根据蚂蚁生命周期(i). (ii). (iii)情况，决定蚂蚁的死、活状态; (4)如果蚂蚁没死亡，将其所选择的点加入 中。end ifendend Step4. 计算本次迭代的最好解，如优于当前最好解，则用其替换当前最好解; Step5. 按公式(3)更新路径上的信息素; Step6. if 小于且未进入停滞状态 then (1)清空所有蚂蚁禁忌表中的数据; (2): =+1; (3)转至Step2.else输出最优解。end ifend if5.4 本章小结从蚂蚁的基本习性和觅食策略入手，提出了人工蚂蚁与真实蚂蚁的异同之处，介绍基本蚁群算法的机制原理和数学模型，以及蚁群算法的应用。然后根据迷宫电脑鼠比赛的特点，提出了一种改进的蚁群算法并给出了算法的基本流程图。针对迷宫问题的特点，首先将蚁群分成两组，然后每组蚂蚁分别从迷宫的起点和终点出发，每只蚂蚁按路径上残留的信息素独立地选择前进的道路。根据蚂蚁在迷宫中的行走状态，为蚂蚁定义了3种不同类型的生命周期，并根据蚂蚁在每次移动后所处的状态，生成问题的可行解。在每一轮迭代后，将生成的最好解与当前最优解进行比较，从而发现最优解。