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

第五章 蚁群算法在迷宫电脑鼠中的应用5.1 引言许多智能问题，如下棋游戏、战略决策、机器人路径规划等都可以转化为寻找迷宫最优路径问题。传统解决迷宫最优路径问题的算法通常会随着迷宫规模的增大、复杂性的增加，算法的空间和时间复杂性呈指数增加，从而很难用于求解大规模的问题实例。从蚁群觅食过程中能够发现蚁巢与食物源之间的最短路径受到启发，并利用该过程与著名的旅行商问题( Traveling Salesman Problem, TSP)之间的相似性，意大利学者M. Dorigo等人提出了一种新型的模拟进化算法-蚁群算法1,2。对TSP问题的求解结果显示，蚁群算法具有极强的鲁棒性和发现较好解的能力，但同时也存在一些缺陷，如收敛速度慢、易出现停滞现象等2。目前，蚁群算法已在组合优化、计算机网络路由、连续函数优化、机器人路径规划、数据挖掘、电网优化等领域取得了突出的成就2-5，实践证明该算法是一种解决优化问题特别是组合优化问题的有力工具。5.2 迷宫的基本信息及常用迷宫搜寻策略5.2.1 迷宫的基本信息从比赛规则中得知，迷宫是由一个个18cm18cm大小的方格组成的，迷宫大小为1616，即行列各有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中的元素(城市)未遍历完,即=0) and ( i+dii=0) and (j+dji 0。迷宫可行解的构造在利用蚁群算法求解迷宫最短路径问题时，为了使每只蚂蚁能以尽可能高的概率生成可行解，本文采用两组数量相等的蚁群分别从迷宫的起点和终点同时出发，每只蚂蚁按公式(2)确定的概率在迷宫中漫游。为尽量避免生成无效路径，为蚂蚁分配一张禁忌表。该表记录蚂蚁当前走过的点集，以避免选择已经走过的点。则对任意一只蚂蚁，在移动过程中可以定义如下的生命周期:蚂蚁走进死角，除非沿原路返回一步或多步，不能再朝前移动，则将该蚂蚁从系统中删除;蚂蚁到达另一组蚁群的出发点，此时该蚂蚁