应用篇-第11章-蚁群算法的仿真与实现.pptx

第11章 蚁群算法的仿真与实现;11.1 蚁群算法介绍;蚁群算法是从自然界中真实蚂蚁觅食的群体行为得到启发而提出的，其很多观点都来源于真实蚁群，因此算法中所定义的人丁蚂蚁与真实蚂蚁存在如下共同点。 （1）都存在一个群体中个体相互交流通信的机制 （2）都要完成一个相同的任务 （3）利用当前信息进行路径选择的随机选择策略 ;在从真实蚁群行为获得启发而构造蚁群算法的过程中，人工蚂蚁还具备了真实蚂蚁所不具有的一些特性： (1) 人工蚂蚁存在于一个离散的空间中，它们的移动是从一个状态到另一个状态 的转换； (2) 人工蚂蚁具有一个记忆其本身过去行为的内在状态； (3) 人工蚂蚁存在于一个与时间无关联的环境之中； (4) 人工蚂蚁不是完全盲从的，它还受到问题空间特征的启发。例如有的问题中 人工蚂蚁在产生一个解后改变信息量，而有的问题中人工蚂蚁每作出一步选择 就更改信息量，但无论哪种方法，信息量的更新井不是随时都可进行的； (5) 为了改善算法的优化效率，人工蚂蚁可增加一些性能，如预测未来、局部优 化、回退等，这些行为在真实蚂蚁中是不存在的。在很多具体应用中，人工蚂 蚁可在局部优化过程中相互交换信息，还有一些改进蚁群算法中的人工蚂蚁可 实现简单预测。 ;11.2 蚁群算法原理;模拟蚂蚁群体觅食行为的蚁群算法是作为一种新的计算智能模式引入的，该算法基于如下基本假设： （1）蚂蚁之间通过信息素和环境进行通信。每只蚂蚁仅根据其周围的局部环境做出反应，也只对其周围的局部环境产生影响。 （2）蚂蚁对环境的反应由其内部模式决定。因为蚂蚁是基因生物，蚂蚁的行为实际上是其基因的适应性表现，即蚂蚁是反应型适应性主体。 （3）在个体水平上，每只蚂蚁仅根据环境做出独立选择；在群体水平上，单只蚂蚁的行为是随机的，但蚁群可通过自组织过程形成高度有序的群体行为。 ;由于蚁群算法是对自然界中真实蚂蚁觅食行为的一种模拟，是一种机理上的应用，因此首先必须对真实蚂蚁进行抽象，而不可能也没必要对蚂蚁个体进行完全再现。抽象的目的就是为了能够更加有效??刻画出真实蚁群中能够为算法所借鉴的机理，同时摒弃与建立算法模型无关的因素。这样抽象出来的人工蚂蚁可以看做是一个简单的智能体，能够完成所求问题简单解的构造过程，也能通过一种通信手段相互影响。;自然界中的真实蚂蚁存在于一个三维的环境中，而问题空间的求解一般是在平面内进行的，因此需要将蚂蚁觅食的三维空间抽象为一个平面。这一点比较容易理解，因为蚂蚁觅食所走的路径本来就存在于一个二维空间（平面或者曲面）上。另外一个问题是真实蚂蚁是在一个连续的二维平面中行走的，而我们无法用计算机直接来完整的描述一个连续的平面，因为计算机处理的是离散事件，因此必须将连续的平面离散化由一组点组成的离散平面，人工蚂蚁可在抽象出来的点上自由运动。这个抽象过程的可行性在于，尽管蚂蚁是在连续平面行动，但其行动经过的总是离散点，因此抽象过程只是提高了平面点离散分布的粒度，与其觅食行为的本身机理没有任何冲突。 基于上述分析，很容易得到蚁群算法所求解的问题空间可用一个重要的数学工具——图( graph)来描述。在工程实际中的很多问题都可以用图来描述，这便使蚁群算法的广泛应用成为可能。;真实蚂蚁在觅食过程中主要按照所处环境中的信息量来决定其前进的方向，而人工蚂蚁是在平面的节点上运动的，因此可把觅食过程抽象成算法中解的构造过程，将信息素抽象为存在于图的边上的轨迹。在每一节点，人工蚂蚁感知连接该节点与相邻节点边上的信息素轨迹浓度，并根据该浓度大小决定走向下一节点的概率。用任意两个节点分别表示蚂蚁的巢穴（初始节点）和食物源（目标节点），人工蚂蚁从初始节点按照一定状态转移概率选择下一节点，依此类推，最终选择行走到目标节点，这样便得到了所求问题的一个可行解。;自然界中的真实蚂蚁总是在所经路径上连续不断地留下信息素，而信息素也会随着时间的推移而连续不断地挥发。由于计算机处理的事件只能是离散事件，所以必须使信息素的挥发离散发生。通常的做法是，当蚂蚁完成从某一节点到下一节点的移动后，即经过一个时间单位之后，进行一次信息素的挥发，而这种在离散时间点进行信息素挥发的方式与蚂蚁觅食过程的机理是完全相符的。;以上几点是对真实蚂蚁觅食行为的抽象，整个过程体现了蚁群算法的自组织性，但是这种自组织系统存在一个缺陷，即系统的演化需要耗费较长的时间。而实际应用时对算法运行时间的要求也是必不可少的，因此在决定蚂蚁行走方向的状态转移概率时，引入了一个随机有哪些信誉好的足球投注网站的过程，即引入了启发因子，根据所求问题空间的具体特征，给蚁群算法一个初始的引导，这个过程极大地增加了算法的时间有效性，从而使蚁群算法的有效应用成为可能。 以上几点是对真实蚂蚁觅食行为的抽象，整个过程体现了蚁群算法的自组织性，但是这种自组织系统