《蚁群算法研究进展及其在石油化工中的应用》由会员分享，可在线阅读，更多相关《蚁群算法研究进展及其在石油化工中的应用（6页珍藏版）》请在金锄头文库上搜索。
1、综述与专论蚁群算法研究进展及其在石油化工中的应用王 宇（华东理工大学化工学院，上海 200237）摘要：蚁群法是新型的群智能优化法，具有鲁棒性、分布并行机制和易融入启发式信息等特点，能用于优化离散和连续问题，可以避免陷入局部最优解。本文重点介绍了蚁群算法的机理及其改进算法，并总结了该算法在石油化工领域的应用。关键词：蚁群算法；改进；优化；应用Progress of ant colony algorithm and its application in petrochemical engineering fieldsWang Yu(College of Chemical Engineering,
2、East China University of Science and Technology,Shanghai 200237,China)Abstract:Ant colony algorithm is a novel category of swarm intelligence optimization methods. It has such merits as robustness,parallel distribution mechanism,integration of heuristic information etc and can be used to optimize wi
3、th continuous or discrete parameters or a combination of both types without falling into lacal solution.This paper focus on the ant colony algorithms mechanism and the introduction of its improved algorithm. Last,the applications of ant colony algorithm in petrochemical engineering fields are roundl
4、y summarized.Key words:ant colony algorithm；improvement；optimization；application / 文档可自由编辑打印0 前言自仿生学创立以来，科学家受自然界启示，发明了许多试图通过模拟自然生态系统机制来求解复杂优化问题的仿生优化方法，如遗传算法，模拟退火算法、禁忌搜索算法、粒子群算法1等，这些算法解决了许多传统的复杂优化问题，现阶段已经成为比较成熟的优化算法。90年代以后，随着组合优化问题的扩大也难度的增加，许多传统算法在解决这类问题时存在着收敛速度慢，容易陷入局部最优解等缺陷。1991年，意大利学者Dorigo M2模仿蚂蚁
5、群体觅食行为提出了一种新的智能优化算法蚁群算法(Ant Colony Algorithm)。蚁群算法具有分布式计算，无中心控制和分布式个体之间间接通信的特征，易于与其它优化算法结合。该法引入正反馈并行机制，具有较强的鲁棒性、并行性、易于实现等优点3。该算法目前已经在很多领域有了成功的应用，从离散问题到连续问题，从一维静态优化问题到多为动态优化问题，如用ACA法解著名的TSP4、QAP5、JOB-SHOP调度6等组合优化问题，都能比其它优化算法更快地得到较优解。总的来说，蚁群算法已经成为国际计算智能领域关注的热点课题，是每年一度的IEEE Swarm Intelligence Symposium
6、中的重要内容。2000年，Dorigo M和 Bonabeau E等7在国际顶级学术杂志Nature上发表了蚁群算法研究综述，将这一研究推向国际学术界的前沿。目前蚁群算法虽然没有形成严格的理论基础，但其作为一种新兴的进化算法已在智能优化领域表现出了强大的生命力8。1 蚁群算法的基本原理1.1 真实蚁群的觅食特性蚂蚁是一种社会性昆虫，蚂蚁之间可以相互协作完成复杂的任务。单个蚂蚁的行为较为简单，但是由简单个体所组成的蚂蚁群体却表现出了极为复杂的行为。真实蚁群在觅食时能够在蚁穴和食物之间找到一条最短路径，并且在遇到如出现新障碍物等环境变化时，蚁群又可以相互协作找到一条新的最短的路径。蚁群在觅食路径上
7、释放信息素，单个蚂蚁通过感知路径上的信息素强度按概率选择下一步的行进方向，而蚂蚁之间则通过感知和释放信息素完成了间接的信息传递。当觅食路径上有了新的障碍物时，信息素轨迹暂时被隔断，此时蚂蚁随机地选择下一步的行进方向，而恰好选择了障碍物附近新的最短路径的那些蚂蚁将最先重构起连续的信息素轨迹，久而久之，选择短路径的蚂蚁越来越多，使得短路径上的信息素的强度越发大于较长路径上的信息素强度，从而使得后续的蚂蚁以较大的概率选择短路径，这种自身催化过程形成的信息正反馈机制使得蚁群最终可以找到新的最短路径。91.2 蚁群算法的基本原理蚁群算法是采用人工蚂蚁模拟真实蚂蚁觅食的行走路线来表示待求问题可行解的一种方
8、法，属于随机搜索算法。每只人工蚂蚁在解空间中读独立地搜索可行解，并在所得的解上留下一定的信息量。解的性能越好，蚂蚁留在其上的信息量就越大，而信息量越大的解被再次选择的可能性也越大。在算法的初级阶段，所有解上的信息量相同，随着算法的推进，较优解上的信息量逐渐增加，算法最终收敛到最优解或近似最优解10。蚁群优化算法的核心思想有三条：第一，选择机制：迹越多的路径，被选中的概率越大；第二，迹更新机制：路径越短，迹增加越快；第三，协作机制：个体之间通过迹进行信息交流。1.3 蚁群算法模型11 引入如下符号：m表示算法中蚂蚁的数量；dij(i，j= 1，2，n)表示边 (i，j)之 间的距离，n为节点个数
9、；ij (t)表示 t时刻在ij上残留的信息量，初始时刻，各边信息量相等。蚂蚁k在t时刻由节点转移到节点j的概率为： (1-1) 其中：ij为先验知识或成为能见度，针对具体问题更具启发式规则而定；为边ij上残留信息的重要程度；为启发信息的重要程度；tabuk用以记录蚂蚁k当前所走过的城市。随着时间的推移，以前留下的信息逐渐消逝，用参数1-表示信息消逝程度，当蚂蚁完成一次循环后，各路径上的信息量根据下式做调整： （1-2） (1-3) 其中：ijk表示第k只蚂蚁在本次循环中留在边ij上的信息量；ij表示本次循环中边ij上信息量的增量；Q为常数；Lk表示第k只蚂蚁在本次循环中所走过的路径长度。根据
10、信息素更新策略的不同，Dorigo M提出了三种不同的蚁群算法模型，分别为蚁周模型（Ant-Cycle Model）,蚁量模型（Ant-Quantity Model）及蚁密模型(Ant-Density Model)，三种模型的区别在于ijk的求法不同：1) 蚁周模型: (1-4)2) 蚁量模型: (1-5)3）蚁密模型: (1-6)它们的区别：蚁周模型利用整体信息，蚂蚁完成以个循环后才更新所有路径上的信息素；蚁量模型和蚁密模型利用局部信息，蚂蚁每走一步就要更新路径上的信息素；蚁周模型应用比较广泛。NNYY图1-1 蚁群算法计算框图Fig1-1 The flow chart of ant col
11、ony algorithm当所有蚂蚁都完成一次周游后，因每只蚂蚁本次周游的禁忌表已满，此时应及时清空，准备下一次周游。当周游次数达到设定值时算法结束。蚁群算法的计算框图1如图（1-1）2 改进的蚁群算法 蚁群算法针对一维静态优化与多维动态优化、连续问题与离散问题都能适用，具有较强的鲁棒性、并行性、易于实现等优点，它在智能优化领域的地位越来越不能被忽视，但是该法仍然存在一些缺陷，如：算法一般需要较长的搜索时间，当搜索进行到一定程度后，所有个体发现的解完全一致，不能对解空间进一步搜索。原因就在于信息素轨迹更行规则中不被选用的弧段上的信息素轨迹的差异会变得越来越大，而蚂蚁始终沿着信息素轨迹高的弧段爬
12、行，这就导致当前不被选用的弧段今后被蚂蚁选择的概率越变越小，进而使算法只会在某些局部最优解附近徘徊，出现停滞现象。为了克服这两个缺陷，不少科学家又相继提出各种改进的蚁群算法。蚁群算法的改进主要有两种策略，一种是调整蚁群算法本身，如自动更新信息素12方法，通过调整信息素量，在一定程度上解决了蚁群在广大空间中搜索和及时寻得最优解之间的矛盾，有利于跳离局部最优；在蚁群算法中引入交叉策略13；引入信息素扩散模型14等。另一种广泛采用的策略，就是将蚁群算法与其它优化算法相结合，相互取长补短，改善算法的适用性及快速收敛的全局最优的能力，如蚁群法与模拟退火法15、遗传算法16、混沌优化17、粒子群算法18、
13、人工免疫算法19等。下面介绍几种典型了改进算法：1） 带精英策略的蚂蚁系统带精英的蚂蚁系统（Ant System with elitist strategy, ASelite）是最早的改进蚂蚁系统。之所以用精英这个词，是因为在某些方面类似于遗传算法中所使用的精英策略。总的来说，在遗传算法中，如果应用选择(selection)、重组(recombination)和突变 (mutation)这些遗传算子，一代中的最适应个体 (一次循环中的最优解)有可能不会被保留在下一代中。在这种情况下，那个最适应个体的遗传信息将会丢失。因此，在遗传算法中，精英策略的思想就是为了保留住一代中的最适应个体。类似地，在
14、Aselite20中，为了使到目前为止所找出的最优解在下一循环中对蚂蚁更有吸引力，在每次循环之后给予最优解以额外的信息量。这样的解被称为全局最优解，找出这个解的蚂蚁被称为精英蚂蚁 (elitist ants)。信息素量按式（2-1）更新： (2-1)（2-2） 其中：ij表示精英的蚂蚁引起的路径（i,j）上信息素的增加；是精英蚂蚁的个数；L为所找出的最优解的路径长度。使用精英策略可以使蚂蚁系统找出更优的解，并且在运行过程很早的阶段就能找到这些解。但是，如果所使用的精英蚂蚁过多，搜索会很快集中在最优值周围，从而导致搜索早熟收敛，即所有蚂蚁都沿同一路径移动，而不能跳出局部最优找到全局最优。因此，要
15、相使此改进算法快速收敛又能找到全局最优，精英蚂蚁数量的选择是非常重要的，直接影响算法的性能16。2） 最大-最小蚂蚁系统最大-最小蚂蚁系统（Max-Min Ant）最早是由T.Stutzle和H.H.Hoos21在2000年提出的。这是目前为止解决TSP和QAP等组合优化问题比较好的一类ACO算法。它与ACS在某些方面类似，如在算法的每次迭代中只对最佳路径上的信息素轨迹进行更新，这样能更好地利用历史信息。但MMAS的特点是它引入了特别的机制来防止过早的停滞现象。MMAS通过限定各条路径上信息素轨迹浓度的上下限lmin， lmax，超出这个范围的值被强制设为lmin或lmax，从而有效地避免了某条路径上的信息素轨迹浓度远大于其余路径。另外，在算法启动时，将各条路径上的信息素轨迹的起始浓度设为lmax，这就可以充分地进行寻优。由于仅用信息素轨迹浓度限制的策略不能彻底消除停滞现象，因此，MMAS还引入了信息素轨迹平滑机制，让轨迹浓度的增加与lmax和当前浓度ij之间的差值成正比22。3） 蚁群系统蚁群系统(ACS)是Gambardella23等在1996年提出的。蚁群系统与基本蚁群算法的本质区别在于它对蚂蚁寻路的规则
