搜索
蚁群算法AntColonyAlgorithm1蚁群优化算法概念1.1蚁群算法原理1.2简化的蚂蚁寻食过程1.3蚁群现象1.4蚂蚁简单规则的两个方面1.4蚁群算法与TSP问题1.5初始的蚁群优化算法—基于图的蚁群系统（GBAS）1.1蚁群算法原理蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为外激素(pheromone)的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。为了说明蚁群算法的原理，先简要介绍一下蚂蚁搜寻食物的具体过程：在蚁群寻找食物时，它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素。当它们碰到一个还没有走过的路口时．就随机地挑选一条路径前行。与此同时释放出与路径长度有关的信息素。路径越长，释放的激索浓度越低.当后来的蚂蚁再次碰到这个路口的时候．选择激素浓度较高路径概率就会相对较大。这样形成一个正反馈。最优路径上的激索浓度越来越大．而其它的路径上激素浓度却会随着时间的流逝而消减。最终整个蚁群会找出最优路径。1.2简化的蚂蚁寻食过程蚂蚁从A点出发，速度相同，食物在D点，可能随机选择路线ABD或ACD。假设初始时每条分配路线一只蚂蚁，每个时间单位行走一步，本图为经过9个时间单位时的情形：走ABD的蚂蚁到达终点，而走ACD的蚂蚁刚好走到C点，为一半路程。本图为从开始算起，经过18个时间单位时的情形：走ABD的蚂蚁到达终点后得到食物又返回了起点A，而走ACD的蚂蚁刚好走到D点。假设蚂蚁每经过一处所留下的信息素为一个单位，则经过36个时间单位后，所有开始一起出发的蚂蚁都经过不同路径从D点取得了食物，此时ABD的路线往返了2趟，每一处的信息素为4个单位，而ACD的路线往返了一趟，每一处的信息素为2个单位，其比值为2：1。寻找食物的过程继续进行，则按信息素的指导，蚁群在ABD路线上增派一只蚂蚁（共2只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为12和4，比值为3：1。若按以上规则继续，蚁群在ABD路线上再增派一只蚂蚁（共3只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为24和6，比值为4：1。若继续进行，则按信息素的指导，最终所有的蚂蚁会放弃ACD路线，而都选择ABD路线。这是正反馈效应。信息素的更新方式有2种：一是挥发：也就是所有路径上的信息素以一定的比率进行减少，模拟自然蚁群的信息素随时间挥发的过程；二是增强：给评价值“好”(有蚂蚁走过)的边增加信息素。1.3蚁群现象蚂蚁正常行进，突然环境变化，增加了障碍物蚁群现象：蚂蚁以同等概率选择各条路径，紧接着，随着时间的增加较短路径信息浓度高，选择该路径的蚂蚁逐渐增多。蚁群现象：蚂蚁最终绕过障碍物找到最优路径1.4蚂蚁简单规则的两个方面：1多样性：蚂蚁在觅食的时候路线不一，随机性的向着某个方向行走，打破常规，进行创新。2正反馈：优化的路线不断被保存并加大自身概率，保证了相对优良的信息能够被保存下来。多样性保证了系统的创新能力，正反馈保证了优良特性能够得到强化，两者要恰到好处的结合。1.5蚁群算法在TSP问题中的应用旅行商问题，即TSP问题又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路经的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。算法步骤如下：按的不同取法，可形成三种类型的蚂蚁算法模型：（1）Ant-CircleSystem模型，有式中，Q为常量，为第k只蚂蚁在本次循环中所走路径的长度。（2）Ant-QuantitySystem模型ij,kij0kkQL若第只蚂蚁在本次循环中经过，否则ijkkLijij,ktt+1ijd0kQ若第只蚂蚁在时刻和之间经过，否则（3）Ant-DensitySystem模型很明显在后两种模型中，利用的都是局部信息，而第一种模型利用的是整体信息。这三种模型在求解不同问题时各有优势。ij,ktt+1ij0kQ若第只蚂蚁在时刻和之间经过，否则这样循环，最终得到了最优路线。实际的概率公式：定义为他时刻蚂蚁k（k=1,2,3…,n）由城市i到城市j的选择概率，在旅行商问题中，通常取而和则分别为残留信息和启发信息的相对重要程度系数。()kijpt()1/ijtijdh=ab蚁群算法所研究问题谢谢！！！