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

第五章蚁群算法在迷宫电脑鼠中的应用5.1引言许多智能问题，如下棋游戏、战略决策、机器人路径规划等都可以转化为寻找迷宫最优路径问题。传统解决迷宫最优路径问题的算法通常会随着迷宫规模的增大、复杂性的增加，算法的空间和时间复杂性呈指数增加，从而很难用于求解大规模的问题实例。从蚁群觅食过程中能够发现蚁巢与食物源之间的最短路径受到启发，并利用该过程与著名的旅行商问题(TravelingSalesmanProblem,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桥的概率为:hmhmhmAkBkAkAmP)()()()(式(5.0)而选择B桥的概率为:)(1)(mPmPAB其中参数h和k用来匹配真实实验数据.第(m+1)只蚂蚁首先按式(5.0)计算选择概率PA(m)，然后生成一个在区间[0,1]上一致分布的随机数a，如果a≤PA(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基本蚁群算法的机制原理模拟蚂蚁群体觅食行为的蚁群算是作为一种新的计算智能模式引入的,该算法基于如下基本假设：⑴蚂蚁之间通过信息素和环境进行通信.每只蚂蚁仅更具其周围的局部环境做出反应,也只对其周围的局部环境产生影响。⑵蚂蚁对环境的反应由其内部模式决定.因为蚂蚁