蚁群算法发展课件

蚁群算法蚂蚁的生物学特征

蚂蚁是一种既渺小而又平常的社会性昆虫。生物学家通过对蚂蚁的长期观察研究发现，每只蚂蚁的智能并不高，但它们却能协同工作，集中食物，建筑蚁穴并抚养后代，依靠群体能力发挥出超出个体的智能。蚂蚁有复杂的社会体制，“蚂蚁”城市往往有5000万个成员。蚂蚁有四种不同的蚁型：蚁后、雄蚁、工蚁和兵蚁。

蚂蚁的生物学特征寻找食物蚂蚁寻找食物过程中总会自动找到一条最短路径。蚁群算法的基本原理

蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为信息素(pheromone)的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。蚁群算法的基本原理

在蚁群寻找食物时，它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素。当它们碰到一个还没有走过的路口时，就随机地挑选一条路径前行。与此同时释放出与路径长度有关的信息素。路径越长，释放的激索浓度越低。当后来的蚂蚁再次碰到这个路口的时候，选择激素浓度较高路径概率就会相对较大。这样形成一个正反馈。最优路径上的激索浓度越来越大。而其它的路径上激素浓度却会随着时间的流逝而消减。最终整个蚁群会找出最优路径。简化蚂蚁的寻食过程蚂蚁从A点出发，速度相同，食物在D点，可能随机选择路线ABD或ACD。假设初始时每条分配路线一只蚂蚁，每个时间单位行走一步，本图为经过9个时间单位时的情形：走ABD的蚂蚁到达终点，而走ACD的蚂蚁刚好走到C点，为一半路程。简化蚂蚁的寻食过程

假设蚂蚁每经过一处所留下的信息素为一个单位，则经过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路线。这也就是前面所提到的正反馈效应。蚁群算法模型的建立对蚂蚁个体的抽象 蚁群算法是对自然界真实蚂蚁觅食行为的一种模拟，因此首先必须对真实蚂蚁进行抽象，而不可能也没必要对蚂蚁个体进行完全再现。把蚂蚁能够有效刻画出真实蚁群中能为算法所借鉴的特征抽象出来，同时建立与算法模型无关的因素。蚁群算法模型的建立问题空间的描述 蚁群算法所求解的问题空间可用一个重要的数学工具——图（graph）来描述。寻找路径的抽象 把觅食过程抽象成算法中解的构造过程，将信息素抽象为存在于图的边上的轨迹。在每一节点上人工蚂蚁感知相邻节点边上的信息素浓度。蚁群算法模型的建立启发因子的引入 蚁群算法的自组织性，似的系统的演化需要耗费较长的时间，而实际应用时对算法运行时间的要求也是必不可少的。因此引入一个启发因子，给蚁群算法一个初始的引导，增加算法的时间有效性。

蚁群算法的基本步骤

基本蚁群算法的优缺点优点较强的鲁棒性、全局性、普遍性分布式计算易于与其它方法结合缺点需要较长的计算时间，容易停滞所有路径的信息素增量，会导致错误的引导信息素的均匀分配策略未体现出路段的重要性蚁群算法的应用一、物流中的应用蚁群算法可以用于网络的优化用以解决不同领域的不同问题,比如说运输工具、运输路线、运输人员的选择方案等,比较典型的例子有指派问题、运输问题、车辆路径问题等。

二、聚类中的应用蚁群算法在聚类问题中的应用产生了蚁群聚类算法。蚁群聚类算法是一种全局优化的启发式算法。能根据聚类中心的信息素把周围数据归并到一起,从而得到数据分类。蚁群算法的应用三、机器人中的应用在机器人的应用中,蚁群算法可以帮助搜索最优路径,帮助确定机器人的行动路径。四、其他应用旅行商问题Job-Shop调度问题网络路由问题大规模集成电路综合布线问题图像处理蚁群算法的发展趋势蚁群算法主要的应用领域还是离散的应用域,而在连续域的应用相对较少。随着算法研究的深入,连续域问题的解决难度会降低,算法中的参数比如说信息素,将会由线性的发展到更加复杂的数学关系,甚至是时变的,使整个算法构成一个动态的、实时的、连续的、多维的复杂系统。随着多核电脑的普及以及电脑计算性能的提高,