蚁群优化算法研究综述.pdf

万方数据
一I蚁群优化算法研究综述梅红李俊卿-Review．Prospect《园陵—圆圆AlgorithmOptimization(山东理工大学农业工程与食品科学学院，山东淄博255049)ResearchProgressofAntColony摘要：介绍了蚁群优化算法的基本原理、流程和研究现状，重点评述了近年来蚁群优化算法在组合优化和连续优化两个领域的研究现状，并展望了这一领域的研究方向。关键词：蚁群优化算法组合优化连续优化0引言群智能足处理问题的一种新的方法，它源自于对昆虫及其他动物行为的模拟。其中研究最多，应用最成功的就是蚁群优化算法(antACOA)。蚁群算法是一种随机搜索算法，同时，也是一。种新型的模拟进化算法，具有鲁棒性强、分布计算、并行性、信息正反馈、启发式智能搜索，以及易于与其他方法结合的特征，具有很强的发现较好解的能力。在求解节点树为5—100的组合优化问题上，选用合适的参数，其优化结果普遍好于遗传算法、进化算法和模拟退火算法⋯。1蚁群优化算法1．1蚁群优化算法的基本原理蚁群算法是由意大利学者M．Dorigo于20世纪90年代首次提出的，它是对真实蚂蚁群体觅食行为的模拟。蚂蚁是一类个体行为极其简单的昆虫，单个蚂蚁的行为带有随机性，但是由这些简单的个体所组成的蚁群却体现出极大的智能，能够完成相当复杂的任务。尤其是蚂蚁的觅食行为，蚂蚁能够在较短的时间内寻找从蚁巢到食物源的最短路径。人们研究发现，蚂蚁在寻找食物的过程中，会随机搜索邻近的区域，一旦发现了食物源，蚂蚁将一部分食物带回蚁巢，同时，蚂蚁会在走过的路径上散发信息素。路径越短，散发的信息素越多，后来者选择该路径的概率就越大。于是，在信启、素的帮助下，蚂蚁问形成了一种间接的信息交流，很快就会搜寻到最短的路径上来。蚂蚁个体之间就是通过这种信息的交流来寻找从蚁巢到食物源的最短路径。蚁群算法本质上是进化算法中的一种新型随机性优化算法。该算法通过构造人工蚂蚁来模拟真实蚂蚁的行为，进行优化运算。但是，人工蚂蚁与真实蚂蚁也存在着以下不同之处：(1)人工蚂蚁有视觉；(2)人工蚂蚁有记忆能力；(3)人工蚂蚁生活在时间离散的环境中。相同之处在于蚂蚁都是通过协作搜寻最短路径以及都具有正反馈的特点。1．2蚁群优化算法的两个主要部分(1)信息素的更新信息素在算法中起着非常重梅红1974年生．女，博士生。主要研究方向为机器人动力学及智能控制。Abstract：Thispaperintroducesthebasicprinciple，procedureandsituationcolonyoptimizationalgorithm，emphasizesalgorithminfieldscombinatorialcontinuouseoptimization．Furthermore，researchtendenciesthisfieldarediscussed．Keywords：antoptimalalgorithm，2010．”I机电一体化13currentantonII'IHII_R'IIII
万方数据

iiiiiiiiiiiiiiiiiiiiiiiiiiii萄iiiiii甬(s、，、力)可以定义为¨。：Df={d：，d：，⋯，d‘I都满足以s’)≤．厂(s)，那么就称s‘为全局最优解。全法结合，算法同时兼具了基本蚁群算法和遗传算法的的蚁群算法中只有一个蚁群，没有充分挖掘蚁群算法蚁群优化算法研究综述iIIIiIIIiIIII要的作用，它能够引导蚂蚁选择质蹙好的路径，并为蚂蚁之间提供信息交流的渠道。每当蚂蚁的路径构建完毕，都要进行信息素的更新。一方面，要根据路径的长短增加信息素的数黾；另一方面，信息素也会随着时间挥发掉一部分，这样可以避免路径过早收敛。挥发同时也意味着遗忘，能够引导蚂蚁搜索新的区域。信息素的更新可以采取不同的方式。(2)路径的构建人工蚂蚁在信息素的帮助下，根据概率原则进行解的构建。路径上的信息素越多，该路径被选择的概率就会越大。1．3基本蚁群算法的流程(1)初始化包括算法参数和信息素矩阵的初始化，记录程序进行的统计信息变最的初始化以及蚂蚁路径的初始化等。开始的时候，所有的路径上都没有信息素，每一条路径被选择的概率都是一样的。因此，蚂蚁路径的初始化是随机的。(2)质量评估计算所有蚂蚁选择的路径所对应的目标函数，评估路径的质鼍。路径越长，质鼍越差。(3)信息素的更新根据路径的质量决定每一条路径上应散发的信息素，以增加高质镑的解被选中的概率，同时挥发掉一部分信息素，扩大搜索的范围，避免过快的收敛。信息素对算法的长远影响就是逐渐减少搜索空问的规模，使搜索的范围缩小到少数有潜力的路径上。(4)路径选择每一次迭代的开始，蚂蚁的记忆首先被清空，然后根据路径上的信息素，利用概率选择机制分