蚂蚁算法在现实生活中的应用.doc

蚂蚁算法在现实生活中的应用摘要：蚁群优化算法（简称ACO）是一种近年来才发展起来的新颖的仿生型的智能优化算法，具有正反馈、分布计算和启发性搜索等特点。作为计算智能和群智能的重要分支之一，蚁群优化算法的研究方兴末艾，备受瞩目。蚁群优化算法的思想来源于我们真实世界中的蚂蚁群体的智能特性。在现实生活中，单个蚂蚁并不具备将食物以最短的路径运回到蚁巢的智能行为，然而由许多蚂蚁所构成的蚂蚁群体在经过一段时间的调整以后，通过个体之间的相互配合与协作，最后能够使整个蚁群沿着某条最短的路径将食物搬回到蚁巢。关键词：蚁群优化算法，智能特性，备受瞩目在科学实践与工程技术中，人们经常遇到大量的、各式各样的最优化问题，并需要对它们进行求解，而传统的优化方法出于其计算时间依赖于问题的规模与结构，很难满足人们的要求。于是，技术难题的解决呼唤先进的理论与算法，智能优化技术的出现与发展为解决这些优化问题提供了途径。蚁群优化算法(Ant Colony Optimization，ACO)是近年来发展的一种新颖的仿生型的智能优化算法，是一种很有前途的优化算法，是当前智能优化领域中的研究热点，也是我们研究的主要内容。闻此，我们首先从智能的角度，对人工智能、计算智能和群智能进行了简要回顾；而后，从智能优化技术的角度，对一些新出现的优化算法进行了简单介绍：晟后，确定了本文的研究重点，给出了论文的写作思路和缔构安排。 1、 蚁群算法概述1.1 蚁群算法的基本原理在蚂蚁觅食时存在着一种有趣的现象:蚂蚁在缺乏行走经验以及在无法对路径的拓扑和距离信息知悉的情况下，总是能够顺利地找到觅食的最短路径。即使路径在中途发生了改变，如被人为地添加了障碍亦是如此，换言之，蚂蚁在寻找最短路径时具有自适应性。如图2.1-2.3所示，其中的十字星表示蚂蚁。在图2.1中，上下路径相等，蚂蚁随机选择一条路径，路径上蚂蚁的数量几乎相等;在图1.2中，虽然加入了障碍物，但是由于上下路径的长度不变，因此两条路径上的蚂蚁数量也几乎相等;在图1.3中，加入了障碍物，但是很显然，上面的路径长度更短，最后蚂蚁均选择上面的路径。 图1.1蚁群算法原理图(未设置障碍) 图1.2蚁群算法原理图(设置障碍，不改变距离) 图1.3蚁群算法原理图(设置障碍，改变距离) 从生物学上来说，蚂蚁虽然没有语言，但是它们能够通过信息素来完成信息的交换。交换的过程是这样的:当蚂蚁在从巢穴移动到食物的时候会挥发信息素，这样在某条路径上蚂蚁越多，信息素的强度也会越来越大，从而吸引更多的蚂蚁。 假定每只蚂蚁在单位时间挥发的信息素是一样的，同时信息素挥发的速度也一样。以图1.3为例，蚂蚁在开始阶段距离随机地选择路径AB与CD，即两边的蚂蚁数量一样多，因此挥发的信息素总量也相等，由于信息素挥发的速度也一样，这样在AB的距离小于CD的距离的情况，较短的路径AB的信息素强度大于路径CD，因而更多地蚂蚁选择AB，直至所有的蚂蚁都选择AB。从这一过程不难看出，虽然，障碍物的加入有可能改变路径的长度，但是改变之后，信息素的强度会跟着发生变化从而保证蚂蚁总能找到最短路径。 从上面的过程不难看出，蚂蚁在寻找最短路径时需要多个机制的支持:首先，需要选择机制，即蚂蚁以更大的概率选择信息素强度大的路径，反之，概率越小;其次，信息素更新机制。这包括两部分，一是信息素的释放机制，二是信息素的挥发机制;最后，需要个体之间的协调机制。 蚁群算法就是对生物学上的蚂蚁觅食路径选择的模拟，通过各个“蚂蚁”的个体行为达到影响群体行为的目的。同时，蚁群算法中的“蚂蚁”和生物学上的蚂蚁是有所区别的，更确切地说，前者具有后者和“人为”的双重属性，也正是因为人工蚂蚁的双重属性才使得蚁群算法能够有效工作。 生物学的蚂蚁和人工蚂蚁的共同点表现在以下四个方面: 1.并行异步性。生物学的蚂蚁和人工蚂蚁都能够不通过其他蚂蚁得出问题的可行解，这个解往往不是最优的，但是通过对各个蚂蚁解进行综合处理能够对具体问题进行求解; 2.对信息素进行反馈。这是蚂蚁觅食过程中路径选择以及蚁群算法的基础。对信息素的反馈使得蚁群算法具有正反馈的特点; 3.信息素挥发。这也是蚁群算法的重要部分，如果缺少信息素挥发的过程，那么信息素将会不断增多，影响整个算法的搜索能力; 4.局部搜索能力。虽然蚂蚁并不具有对整体路径的判断力，但是具有判断局部信息的能力。 生物学的蚂蚁和人工蚂蚁的不同点表现在以下四个方面，这主要是为了算法的需要进行的: 1.生物学的蚂蚁的状态是连续的，但是工人蚂蚁是离散的，跳跃的; 2.生物学的蚂蚁不具有记忆功能，而人工蚂蚁可以记忆本身的状态; 3.生物学的蚂蚁释放信息素的时间是不固定的，而且各只蚂蚁信息素的释放相同，但是在实际应用中，信息素的释放时间是可以根据问题释放，释放的多少也可以随意设定甚至可以选择性更新; 4.人工蚂蚁可以根据解决问题的需要进行功能扩充。1.2 蚂蚁算法的基本模型 通常运用TSP(Travel Salesman Problem)对蚁群算法的模型进行阐述。通常而言，TSP用有向图G=(N ，A)进行描述，其中各个顶点N=1,2,，n,代表各个城市，城市之间的距离：(dj)nn；目标函数： 其中W=（i1,i2,in)为城市1,2, 3.n的一个排列。 根据上述描述，蚁群算法遵循以下几个步骤: 首先，设置最大迭代次数NC，并初始化蚂蚁以及路径的信息素=c这一参数会对蚂蚁路径的选择造成影响。 在某一时刻，蚂蚁k从转移到j的概率Pijk由公式(1)进行计算: 式(1.1)中的allowedk的含义是蚂蚁k能够访问的节点列表，每次蚂蚁访问一个城市该集合的个数减一，当allowedk为空时就说明蚂蚁k完成对各个城市的遍历，这样该蚂蚁就寻找到了问题的解。为启发因子，其取值通常与两个城市之间的距离有关，距离越大，其值越小，反之，其值越大，这样蚂蚁就以更大的概率选择距离最短的路径。为信息素的重要程度标识，为启发因子的重要程度标识。信息素的更新按照如下规则:式(2.1)中的(0 1)的含义是城市之间路径上的信息素挥发系数，其值越大，说明信息素挥发的越快，反之说明信息素挥发的越慢。的含义是在一次迭代中，路径(ij )上的信息素的变化量。对应的，4弓的含义是蚂蚁k在一次迭代中留在边(j )上的信息素量。的计算公式:Q为一固定数，Lk为k只蚂蚁总路径的长度。当迭代次数为NC时，算法结束。1.3 蚁群算法的特点蚁群算法具有一系列特点，这些特点有有利的方面也有一些不足，其中有利的方面主要体现在正反馈性、鲁棒性、分布异步等方面;其不足首先表现在求解的质量并不是最优，这是由其求解问题的复杂性决定的;其次，可能陷入局部最优的情况;最后，它耗时较长，尤其当问题的规模较大的时候时间令人无法接受。2、蚁群算法的优化思路及常见的蚁群优化算法2.1 蚁群算法的优化思路对蚁群算法进行优化需要对基本蚁群算法过程进行分析。从基础蚁群算法中可知，蚂蚁对路径进行选择有两个影响因子:一是信息素的强度，二是城市距离。在信息素初始化的时候，每个路径的值相同，因此第一条最短的距离往往决定与城市距离。但是事实上，第一条路径最短只是局部最短而不是整体最短。由于正反馈作用的存在，这条路径的信息素会越来越强，选择该路径的蚂蚁也越来越多，导致陷入局部最优。鉴于此，对蚁群算法的优化可以从信息素的挥发和增加机制进行优化。同时，在基本蚁群算法中如果信息素的增加速度趋向于零，那么正反馈作用就会十分不明显，那么蚂蚁就可能随机选择路径，路径搜索类似于无条件搜索导致收敛的速度过慢。 因此对蚁群算法的改进主要可以从信息素更新机制和局部优化等方面来进行。2.2 降低蚁群算法停滞性的方法基本蚁群算法可能出现过早陷入局部最优的现象，解决这一问题的主要思路就是对信息素更新机制进行改进。改进的常用方法有信息素挥发和信息素控制两种：1. 信息素的挥发： 由于正反馈作用的存在，信息素可能在时间内在某一条路径聚集。为了防止这一情形，有必要减少信息素(信息素挥发)以减少蚂蚁选择这一路径的概率。值得一提的是，信息素挥发的参数选择十分重要，如果挥发过快，可能导致搜索时间过长，收敛过慢的现象发生;挥发速度过慢则可能出现过早陷入局部最优的情形。 2. 信息素的控制在基础蚁群算法中，蚂蚁无不例外地选择信息素较强的路径，事实上信息素较强的路径并不一定是全局最优，这一点与爬山算法十分相似，因此有必要探索别的路径。这可以通过设置信息素允许的最大值和最小值来实现。设置最大值的目的就是减少信息素对蚂蚁选择路径的影响;设置最小值的目的就是鼓励一些蚂蚁选择信息素较弱的路径。这样就能够一定程度提高算法的随机搜索能力。3、 基于蚂蚁优化算法的现实应用 最近几年, 蚁群算法在离散优化问题上取得了很多成功的应用, 很多是针对 NP- 难问题, ACO可以很快的取得高质量的解。另外, ACO在通信网络中动态选择最短路径、工业 上的调度等问题也有成功应用。为了证明一种新的启发式算法的有效性, 通常的做法是针对不同问题, 将启发式算法与已知算法的性能加以比较。ACO 最初在解决 TSP问题上得到了成功, 到目前为止, 已经在一百多种 NP- 难问题上进行了实验, 这些问题大体可分为以下几类: 路径问题; 指派问题; 调度问题; 集合问题等。另外, 在机器学习和生物信息科学领域也取得了成功应用, 一方面, 蚂蚁找到的解可以用局部搜索策略加以改进; 另一方面, 因为局部搜索策略产生适当的初始解是很困难的, 而 ACO的概率性、适应性解的迭代过程非常适合用来解决此类问题。 3.1 在通信网络中的应用通信网络中网络优化问题的一些特征与蚁群优化算法的特征匹配的很好。惠普公司和英国电信公司在20世纪90年代中后期都开展了这方面的研究, 应用蚁群路由算法 (Ant Colony Routing, ACR), 每只蚂蚁根据它在网络上的经验与性能, 动态更新路由表项 ( Routing- Table Entries)。一个广泛应用的例子就是 Ant Net算法, 在不同的网络、不同的负 载类型下进行的实验表明, Ant Net算法以其良好的适应性、 鲁棒性比其他同类算法更优。3.2 在工业问题中的应用在工业社会的实际应用领域, 蚁群算法引起了国际上众多企业的关注。 Euro Bios公司首先把蚁群算法应用于求解现实世界中不同类型的调度问题。同时, Ant Optima公司以蚁群算法为工具, 成功地开发出多种工业优化的软件工具, 例如 DYVOIL产品成功地解决了瑞士某企业的车辆燃油分配管理问题; ANTROUTE产品则解决了一些大型连锁超市集团企业的运输车辆调度与路由问题。此外, 国外的企业还把蚁群算法应用于大型制造商生产线的设计、网络路由与平衡的规划、水利设施的建设、数据挖掘、金融现金流的分析与预测等广泛的实际应用领域。Bios Group为法国 Air Liquid公 司设计的车辆路线选择方案也得到了成功应用。其他的应用有 Gravel、Price和 Gagn将ACO应用在铝制造中心的工业调度; Bautista和 Pereira应用ACO解决多目标多约束条件下的装配线平衡问题。然而在国内, 蚁群算法在工业企业中的应用尚未成熟, 还处于刚刚起步和探索的阶段。4、 当前研究热点 随着研究的深入, 更多富于挑战性的问题开始受到关注, 如目标函数和约束的随机属性, 数据的多状态、动态改变等; 另外连续优化问题、ACO 的并行实现等问题也逐渐成为热点。 4.1 动态优化问题 动态问题的特征是搜索空间随着时间变化。随着搜索的进行, 搜索条件、实例的定义的变化导致解的质量的变化, 必须调整搜索方向。动态组合优化问题的应用有网络路由问题、一些动态变化的TSP问题 (城市间距离的变化, 或者访问城市的动态增减)和动态车辆路线选择问题等。4.2 多目标优化 对于多目标问题, 通常的做法是根据其相对重要性对其进行分类或者加权操作, 如果参数或者权重无法给与优先权, 则可以寻找一组最优的非受控的解。应用有投资组合问题、二次分配问题等。4.3 并行实现 蚁群算法本身隐含着一定的并行性, 单只蚂蚁在一次循环中独立于其他蚂蚁。因此, 本质上蚁群算法应以分布式的协同优化计算方式为特征, 而在串行计算机上对蚁群算法的进行模拟并不能真正体现蚁群算法的本质特征, 进一步的研究工作还应开展蚁群算法的并行机实现。在研究蚁群算法并行机实现问题时, 需要解决对蚁群算法并行化过程中并行计算模型的选择以及对蚁群算法的分解、映射方法的改进等问题, 还需要解决在对蚁群算法并行化过程中粒度处理标准的问题, 使并行处理过程具有较好的可扩展性, 并具有良好的负载均衡性。4.4 连续优化 将用于组合优化问题的算法用在连续问题上的最简单的做法是将变量的定义域化分为一组间隔的集合。若变量的定义域很大, 而要求的精度很高的时候, 这样的方法并不可行。对此, 有人提出了一种基于ACO的算法, 可以解决变量连续或连续与离散混合的问题。将蚁群算法应用在连续优化问题上最近几年刚刚开始研究, 前景广阔。4.5 与其他优化算法的融合在寻找最优解的过程中加入针对具体问题的局部搜索算法, 如遗传算法、免疫算法等, 利用蚁群算法的全局性避开了局部极优, 利用局部搜索算法加快了求解的进程。和其他仿生算法的结合, 形成混合仿生算法模型会使求解问题更加有效。从现有研究成果来看, 这些智能融合大多是一些初步尝试, 多数是针对具体问题进行的, 所解决的问题不同, 其融合策略也存在多种差异, 应该在现有成果上继续研究, 探索蚁群算法与一种或几种仿生优化算法相融合的统一机制。 另外, 与一些新兴的、影响不是很大的仿生优化算法 (如人工鱼群算法、混合蛙跳算法、蜂群算法、情感计算等 )之间的融合至今还存在着研究空白, 将其进行智能融合并解决实际问题, 容易产生许多创新性研究成果。5、 结论目前, 已经有越来越多的人开始关注和研究蚁群算法, 大多数的研究者着眼于蚁群算法在经典 NP- 难问题中的应用, 对动态问题、随机问题和多目标优化问题方面做的工作较少, 可以预见, 在不久的将来, 这必将成为一个主要的研究方向。另外, 对算法理论的研究也是今后工作的重点。对蚁群算法的研究必将是一个长期的研究课题。参考文献1 张纪会，徐心和一种新的进