蚁群算法（共12篇）
蚁群算法 篇1
蚁群算法是受到人们对自然界中真实的蚁群群体行为的研究成果的启发而提的, 是一种基于种群的模拟进化算法, 属于随机搜索算法, Dorigo[1]等人充分利用了蚁群搜索食物的过程与著名的旅行商问题 (TSP) 之间的相似性, 吸取了昆虫王国中蚂蚁的行为特性, 通过人工模拟蚂蚁搜索食物的过程 (即通过个体之间的信息交流与相互协作最终找到从蚁穴到食物源的最短路径) 来求解TSP问题。为了区别于真实蚂蚁群体系统, 称这种算法为蚁群算法。
1、蚁群算法的基本原理
在自然界真实的蚁群觅食过程中, 蚁群在没有视觉的情况下通过个体之间交换信息素, 能够在较短的时间内找到食物和蚁巢之间的最短路径。生物学家的研究已经表明, 一只蚂蚁的记忆和智能是非常有限的, 但是, 由于蚂蚁之间可以通过一些信息素进行协同作用, 实现蚂蚁之间的信息交流和传递, 可以共同做出令人惊讶的行为。
为了阐述蚁群算法的机理[2], 下面以蚂蚁搜索食物的过程为例, 分析蚂蚁是如何通过上述的信息交流和传递的协同作用, 最终找到从蚁穴到食物源的最短路径的。
图1.1中, A为蚁穴, E为食物源, 从A到E有两条路径可走, ABE是长路径, ACE是短路径。蚂蚁走过一条线路以后, 在其路径上会留下信息素气味, 后来的蚂蚁就是根据留在各路径上的这种气味的强度选择应该移动的方向。图1.1 (a) 表示起始时的情况, 假定蚁穴中有4只蚂蚁, 分别用1, 2, 3, 4表示。开始时蚁穴中蚂蚁1, 2向食物源E移动, 由于线路ABE和ACE均没有蚂蚁通过, 在这两条路径上都没有原始的信息素气味, 因此蚂蚁1和2选择这两条线路的机会均等。假设蚂蚁1选择ABE线路, 蚂蚁2选择ACE线路, 并且假定各个蚂蚁行走的速度相同, 当蚂蚁2到达食物源E时, 蚂蚁1还在途中, 如图1.1 (b) 所示。蚂蚁2到达食物源以后就返回, 这时从B点返回也有两条线路的选择, 而哪一条线路上的信息素气味重, 就选择哪一条。因为蚂蚁1还在途中, 没有到达终点, 即此时在EBA线路上靠近B端处, 蚂蚁1还没有留下信息素气味, 所以蚂蚁2返回蚁穴的路径只有一个选择, 就是由原路返回。当蚂蚁2返回到A端时, 蚂蚁3开始出发, 蚂蚁3的线路选择将必定是ACE, 因这时ACE线路上信息素的气味比ABE线路上重 (ACE路径上已有蚂蚁两次通过) , 如图1.1 (c) 所示。当蚂蚁1到达食物源B点时, 由于同样的理由, 蚂蚁1所选择的返回线路必将是ECA, 如图1.1 (d) 所示。如此继续下去, 由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象:沿路径ACE移动的蚂蚁越多, 则后来者选择该路径的概率就越大, 这正是蚁穴到食物源的最短路径。蚂蚁个体之间就是通过这种信息的交流达到最佳食物搜索的目的[3]。
在自然界中, 蚁群的这种寻找路径的过程表现为正反馈的过程, 与人工蚁群的寻优算法极为一致。如果我们将在优化求解中那些只具备简单功能的单元看作"蚂蚁", 那么上述寻找路径的过程可以用于解释人工蚂蚁的寻优过程。[4]
由以上分析可知, 人工蚁群和自然界蚁群的相似之处在于:两者优先选择的都是含"信息素"浓度较大的路径;人工蚁群和自然界蚁群的区别在于:
(1) 人工蚂蚁具有记忆或智能功能, 它能够记忆已经访问过的节点。
(2) 人工蚂蚁具有一定的视觉, 人工蚁群在选择下一条路径的时候, 并不是完全盲目的, 而是按一定的算法规律有意识得寻找最短路径。
(3) 人工蚂蚁的生活环境是时域离散的。
2、蚁群算法的特点
从蚁群算法的原理不难看出, 蚁群的觅食行为实际上是一种分布式的协同优化机制。单只蚂蚁虽然能够找到从蚁巢到食物源的一条路径, 但找到最短路径的可能性极小, 只有当多只蚂蚁组成蚁群时, 其集体行为才表现出蚂蚁的智能 (发现最短路径的能力) 。在寻找最短路径的过程中, 蚁群使用了一种间接的通信方式, 即通过向所经过的路径上释放一定量的外激素, 其它蚂蚁通过感知这种物质的强弱来选择下一条要走的路。
在蚁群的觅食行为中, 另一个重要的方面是自催化机制和解的隐式评估。自催化机制实际上是一种正反馈机制, 解的隐式评估指蚁群将先走完较短的路径。自催化机制和解的隐式评估相结合, 极大地提高了问题的求解效率。即对于越短的路径, 蚂蚁将越早走完, 从而使更多的蚂蚁将会选择该路径。当然在使用自催化机制时, 要努力避免早熟现象。在蚁群算法中, 使用外激素蒸发和随机状态转移来弥补自催化机制的缺陷。蚁群算法的主要特点概括如下:
(1) 采用分布式控制, 不存在中心控制。
(2) 每个个体只能感知局部的信息, 不能直接使用全局信息。
(3) 个体可改变环境, 并通过环境来进行间接通讯。
(4) 具有自组织性, 即群体的复杂行为是通过个体的交互过程中突现出来的。
(5) 是一类概率型的全局搜索方法, 这种非确定性使算法能够有更多的机会求得全局最优解。
(6) 其优化过程不依赖于优化问题本身的严格数学性质, 诸如连续性、可导性, 及目标函数和约束函数的精确数学描述。
(7) 是一类基于多主体的智能算法, 各主体间通过相互协作来更好的适应环境。
(8) 具有潜在的并行性, 其搜索过程不是从一点出发, 而是同时从多个点同时进行。这种分布式多智能体的协作过程是异步并发进行的, 分布并行模式将大大提高整个算法的运行效率和快速反应能力。
3、蚁群算法的应用
对蚁群算法的应用研究一直非常活跃。由于蚁群算法不依赖于问题的具体领域, 所以在很多学科有广泛的应用。
(l) 组合优化
继M.Dorigo首先将蚁群算法应用于TSP问题之后, V Maniezzo[5]等人将蚁群算法应用于QAP。最近几年, Gambardella[6], Taillard[7]和Stutzle[8]也发表了一些用蚁群算法求解QAP问题的文章。目前, ACO己是求解QAP问题最有效的算法之一。A Colomi[9]等人首先将蚁群算法应用于车间作业调度问题 (Jobshop Scheduling Problem, 简称JSP) 。Costa和Herz[10]提出增强的蚁群算法, 并将其应用于分配类型的问题。该算法在求解图的作色问题时, 得到了完全可以和其它启发式算法相媲美的结果。
(2) 通讯领域
蚁群算法在通讯网络领域 (特别是解决网络路由问题) 方面的应用研究受到越来越多学者的关注。由于网络中信息的分布式性、动态性、随机性和异步性与蚁群算法一非常相似, 如利用局部信息发现解, 间接的通讯方式和随机状态的转换。Di Caro和Dorigo己在相关的文献中将蚁群算法应用于网络路由问题, 并称这种算法为Ant Net[11]。
(3) 大规模集成电路的线网布局
在大规模集成电路的线网布局中, 需要根据电路和工艺的要求完成芯片上单元或功能模块的布局, 然后实现它们之间的互连。此问题可看作是寻找一个网格平面上两端点之间绕过障碍的最短路径问题。线网上的每个Agent根据启发策略, 像蚂蚁一样在开关盒网格上爬行, 所经之处便设置一条金属线, 历经一个线网的所有引脚之后, 线网便布通了[12]。应用蚁群算法, 可以找到成本最低、最合理的线网布局, 而且由于其本身的并行性, 比较适合于解决此类问题。
(4) 函数优化
虽然蚁群算法在离散空间的寻优能力十分突出, 但是对于连续空间的优化也是蚁群算法应用的领域之一, 也是评价蚁群算法性能的主要方法[13,14]。
此外, 蚁群算法在计算机领域、机器人设计与控制领域、数据挖掘、系统辨识、化工领域等方面也有广泛应用。特别需要指出的是:由于蚁群算法在求解复杂组合优化问题方面具有并行化、正反馈、鲁棒性强等先天优越性, 所以在解决一些组合优化问题时所取得的结果无论是在解的质量上, 还是在收敛速度上都要优于或至少等效于模拟退火以及其它一些启发式算法[2]。
摘要：本世纪50年代中期创立了仿生学, 人们从生物进化的机理中受到启发, 提出了许多用于解决复杂优化问题的新方法, 如遗传算法、蚁群算法、进化规划、进化策略等。研究成果已经显示出这些算法在求解复杂优化问题 (特别是离散优化问题) 方面的具有很强的优越性。本文将对蚁群算法做详细的介绍。
关键词：蚁群算法,复杂优化,组合优化
蚁群算法 篇2
多机协同攻击逻辑的蚁群算法研究
针对协同空战中多目标的`攻击逻辑问题,首先以攻击优势和目标战役价值为准则建立攻击逻辑决策模型,然后结合蚁群算法的思想,分析了蚁群算法的状态转移、局部调整和全局调整规则,给出攻击逻辑的求解算法,最后以具体仿真算例,证明文中给出的算法能有效地完成多机协同攻击逻辑决策任务.
作 者：李永宾 张凤鸣 李俊涛 LI Yong-bin ZHANG Feng-ming LI Jun-tao 作者单位：李永宾,LI Yong-bin(空军工程大学科研部,西安,710051)张凤鸣,李俊涛,ZHANG Feng-ming,LI Jun-tao(空军工程大学工程学院,西安,710038)
刊 名：电光与控制 ISTIC PKU英文刊名：ELECTRONICS OPTICS & CONTROL 年，卷(期)：2006 13(6) 分类号：V27 V323 关键词：攻击逻辑 蚁群算法 攻击优势 目标战役价值基于蚁群算法的水果图像分割技术 篇3
关键词：水果图像；蚁群算法；图像分割；四维向量
中图分类号： TP391.41；S126文献标志码： A文章编号：1002-1302（2014）09-0380-02
收稿日期：2014-06-22
基金项目：江苏省自然科学基金（编号：BK2012128）。
作者简介：杨业娟 （1981—），女，江苏盐城人，硕士，讲师，研究方向为图形图像处理、数据挖掘、管理信息系统。E-mail：yangyejuanvip@126.com。随着计算机技术的发展，尤其是手机等移动数字成像设备的广泛应用，利用移动数字成像设备进行各领域的图像识别和处理已经成为未来发展趋势，其应用的关键在于根据应用需求解决图像中关注目标的检测和识别。首先需要通过图像分割技术从采集的图片中把目标对象与其所在环境互不重叠地划分成多个区域。再针对确定的目标对象所在区域，对被识别对象进行特征的提取与识别，从而帮助用户进一步完成其所需要的图像识别和处理应用。由于目标对象在采样成像过程中存在自然光源不稳定、目标对象移动、目标对象与环境中附属物之间以及多个目标对象之间的遮挡等问题，造成移动数字成像设备在图像识别与目标对象定位的工作中效率低，很难找到一种适合各类采摘目标的通用图像分割方法。郭艾侠等提出一种基于探索性分析的荔枝果实与枝叶的识别方法，通过在YCbCr严肃空间内，合理设定Cr分量阈值实现对荔枝果实的准确分割[1]；张善文等采用Ostu算法实现对植物病害图像中叶片的有效分割[2]；周洪刚等采用Ostu分割算法与面积阈值法相结合实现对成熟柑橘的自动识别[3]；郭艾侠等将二次阈值分割方法应用于分割荔枝果实图像，取得了较好的分割效果[4]；谢忠红等结合图像颜色模型，通过采用Ostu算法自动实现了对彩色水果图像的精确分割[5]；王开义等结合分水岭与改进的马尔科夫随机场模型对马铃薯丁粘连图像进行分割[6]。受到以上研究成果的启发，本研究尝试将蚁群算法（ant colony algorithm，ACA）[7-8]这一来源于生物种群仿真的启发式寻优算法对具有复杂背景的水果图像进行分割。
1水果图像分割算法
要实现对图像中目标信息的准确识别，就必须考虑识别图像的内容区域构成。通过移动数字成像设备对自然环境下水果的采样图像一般都是复合图像内容，在整个图像中主要包括：水果实体、部分细小果枝和叶片、背景环境和其他一些细缝或者阴影所产生的浅黑色等多种图像的区域。要实现对图像中水果目标的识别提取，有必要对图像进行区域分割，从而便于后续找出对应的水果图像。
为了解决水果图像中各部位的分类识别问题，文献[1-2]通过对强光、普通光和逆光3种光线照射条件下获取的水果图像进行探索性数据分析，发现该研究对象的果实体与叶片等主体内容的颜色为偏红、偏绿和偏褐等，建立了水果图像YCbCr色彩空间中最佳色彩模型为Cr单通道图，并以此为基础设定出合理的阈值分割水果图像的YCbCr色彩图，通过去除图像中的叶片、侧枝以及环境等背景信息，取得了较好的识别效果。但是在实际生活中不同水果具有不同的颜色特点；水果目标与其背景之间有的存在较大的颜色差别，导致水果识别时用单通道分量图进行分割处理虽然可以缩短图像处理时间，但是会影响目标识别效率。若采用K-Means、C-Means等模糊聚类的图像分割方法对水果图像进行处理时，对于背景颜色与水果颜色差异较小的情况，该方法会把与水果颜色相近的背景区域和水果同类化，导致水果与背景的误分类。考虑移动数字成像设备对自然环境下水果的图像采集一般都是RGB彩色图像，并且水果自身的颜色具有多样性，本研究尝试将蚁群算法应用于水果图像分割处理。
实地拍摄的水果图像一般为RGB彩色图像，人们肉眼识别水果也多是通过水果的颜色特征，单通道分量图的图像分割方法不能充分利用图像中丰富的颜色信息，因此识别效率和实用性不佳。本研究基于蚁群算法进行图像分割，则要充分利用图像中的颜色特征来构建模糊聚类处理方法。以原始图像的R、G、B 3 色直方圖为基础，选择3色直方图的k个峰值点作为水果图像的颜色聚类中心特征，将大量的像素聚类分析循环计算简化为仅在少数几个聚类中心峰值点之间的分析比较，通过引导蚁群算子在聚类中心附近进行迭代计算，从而提高计算效率。
由于水果表皮上通常都含有一定量的蜡质层，很多水果在成像时会有明显的反光现象，这种反光在水果图像中通常以亮斑或亮度增强区域的形式表现出来，亮斑从颜色角度可看作R、G、B 3色的综合影响，因此会对图像的划分造成干扰。为了削弱亮斑对图像分割的干扰，需要对亮度进行处理，对亮度较大的区域需要进行3色的综合弱化，通过一群算子迭代将其与相邻像素同化。
在水果图像中，水果目标果体和背景的区域划分通常还需要考虑图像在像素梯度方面的特征，一般果体、枝、叶和背景物的内部像素梯度变化较小，而边界和噪声的像素梯度变化较大，而且内部梯度变化较小的像素占多数，边界像素数又大于噪声像素数，因此可以在水果图像的R、G、B 3色直方图及图像梯度基础上进行如下处理：以k个聚类中心为计算核心逐一检验，聚类中心的3色直方特征对应的像素个数较多的，则该聚类中心一般情况在果体、枝、叶和背景物的内部，令其梯度特征为零；而对聚类中心的3色直方特征对应的像素个数较少的，令其梯度值为最大梯度列的均值。
对于二维的水果图像，根据上面的像素梯度划分和图像中不同类别像素的相邻像素梯度特征表现，定义邻域特征：（1）
梯度为零的聚类中心，令其邻域特征为8，则该聚类中心为像素区块内部；（2）
对于梯度值较高的聚类中心，若3色特征对应的像素数目较多，则可令其邻域特征点数目为6，则该聚类中心为边界；（3）
梯度值较高的聚类中心，如果灰度特征对应的像素个数较少，令其邻域特征为3，则该聚类中心为噪声。
综合上述3原色、亮度、梯度和邻域的影响，本研究构建的蚁群图像分割处理算法如下：
所选定初始聚类中心表示为：Ci（P，B，G，N），i=1，…，k。对于给定水果图像P，定义每个像素Pj 可作为1只蚂蚁，每只蚂蚁则将3原色、亮度、梯度和邻域作为特征的四维向量，图像分割求解实质上是这些蚂蚁搜索食物源的聚类问题求解过程。任意图像像素点Pi 到Pj 的欧氏距离为lij：
蚁群算法发展评述 篇4
蚂蚁作为一种社会性昆虫, 其单个个体的行为能力是有限的, 但是当这些个体组成群体时, 却可以完成许多复杂的工作, 其中最令人称奇的是蚁群在觅食过程中总可以找到一条从蚁巢到食物源的最短路径。经研究发现:蚂蚁在觅食过程中能够在所经过的路径上留下一种称为信息素的物质, 而且蚂蚁在觅食过程中能够感知这种物质的存在及其强度, 并以此指导自己的运动方向, 它们倾向于朝着该物质强度高的方向移动。因此, 由大量蚂蚁组成的集体觅食行为就表现出一种信息正反馈现象:某一路径越短, 该路径上走过的蚂蚁就越多, 所留下的信息素强度也就越大, 后来者选择该路径的概率也就越大。蚂蚁个体之间通过这种信息交流来选择最短路径并达到搜索食物的目的。受蚁群觅食行为的启发, M.Dorigo和他的同事们于20世纪90年代提出了第一个蚁群优化算法 (Ant Colony Optimization Algorithm, 简称ACOA) —蚂蚁系统 (Ant System, 简称AS) 。蚁群优化算法已经被成功地用于解决各种复杂的组合优化 (Hard Combinatorial Optimization, 简称HCO) 问题, 并且取得了令人欣喜的效果。蚁群优化算法具有较好的鲁棒性, 并行分布式计算及易于与其他启发式方法结合等优点。但同时也有收敛速度慢, 容易发生停滞及容易陷入局部最优解等不足。当前, 对蚁群算法的研究主要集中在如何改进蚁群算法。
1 基本蚁群算法
蚂蚁算法首先被成功地用于解决TSP问题, 下面就以TSP问题为例来介绍蚁群算法。给定n座城市, 所谓TSP问题就是寻找一条经过每座城市一次且仅一次的长度最短的闭环路径。设dij代表城市i和j之间的距离, 由平面上两点之间的距离公式可得dij=[ (xi-xj) 2+ (yi-yj) 2]1/2。TSP问题的实例可以用一个完全图G= (N, E) 来表示, 其中N是图的顶点的集合, 这些顶点代表实际问题中的城市, E是图的边的集合, 这些边把图完全连接起来。TSP问题可分为对称型和不对称型两种。在对称型TSP问题中, 城市之间的距离和访问城市的顺序是没有关系的, 也就是对每一对顶点来说dij=dji。在不对称型TSP问题中, 至少存在一对顶点, 对这对顶点来说dij≠dji。在这里我们所选用的实例为对称型TSP问题。设bi (t) (i=1, ···, n) 表示在时刻t位于城市i上的蚂蚁的数量;表示总的蚂蚁的数量;τij表示在时刻t边 (i, j) 上的信息素的浓度, 在对称型TSP问题中τij=τji;ηij表示蚂蚁有城市i转移到城市j的启发式因子, 这个值在算法的运行过程中保持不变, 一般取作ηij=1/dij (dij为城市之间的距离) ;pijk (t) 表示在时刻t蚂蚁k有城市i转移到城市j的概率。为了模拟真实蚂蚁以及考虑到实际问题的情况, 每只蚂蚁应具有以下特征:
每只蚂蚁以一定的概率来选择下一个要访问的城市, 此概率为城市之间的距离以及连接城市的边上的信息素浓度的函数。
为了使蚂蚁走过的路径符合问题的约束条件, 直到一次周游完成之前, 不允许蚂蚁访问已经被访问过的城市。此过程可以用禁忌表来实现, 设tabuk为蚂蚁k的禁忌表, 当蚂蚁访问过城市i以后, 便将i加入禁忌表, 直到一次周游完成之前, 位于禁忌表中的城市是不能被再次访问的城市。
完成一次周游以后, 蚂蚁在其所经过的边上留下相应数量的信息素。
基本的蚁群算法AS可以简单表述如下:在算法的初始时刻, 将m只蚂蚁随机地放到n座城市上, 各条边上的信息素的浓度被设置为τij (0) =c (c为很小的正常数) 。然后, 蚂蚁便以一定的概率来选择下一座要访问的城市, 在时刻t, 蚂蚁k在城市i选择下一座城市j的概率pkij (t) 可表述为:
其中allowedk={N-tabuk}, α和β分别表示信息浓度和启发式因子的重要程度。当所有蚂蚁完成一次周游以后, 各条边上的信息素的更新按如下规则进行。
其中ρ (0≤ρ<1) 表示信息素的残留系数, 1-ρ表示信息数的挥发系数。△τkij (t) 表示蚂蚁k在其所经过的边上所留下的信息素的数量。挥发机制有助于避免边上的信息无限地聚集下去, 没有蚂蚁经过的边上的信息素的数量会呈指数级地减少, 这样一些不好的路径将会被遗忘。在AS中, △τkij (t) 的定义如下:
这里Q是一个常数, Lk表示第k只蚂蚁所经过的路径的长度。M.Dorigo还提出了另外两种△τkij (t) 的定义:
众多研究表明, 蚁群算法具有发现较好解的能力。但与其他算法相比, 该算法收敛速度慢, 需要较长的搜索时间。另外, 该算法容易出现停滞现象, 也就是说, 搜索到一定程度以后, 所有个体发现的解完全一致, 不能对解空间进行进一步的搜索, 不利于发现更好的解。
2 对基本蚁群算法的改进
鉴于蚁群算法的缺点, 对蚁群算法的改进主要从两方面进行。一是加快算法的收敛速度;二是避免过早地出现停滞现象。有许多算法都从这两方面对蚁群算法进行了改进, 如M。Dorigo等人提出的蚁群系统 (ACS) , T.Stützle等人提出的最大最小蚂蚁系统 (MMAS) 等。
2.1 蚁群系统
ACS在状态转移规则和信息素更新规则方面对AS进行了改进:
2.1.1 状态转移规则
在城市r, 第k只蚂蚁选择下一个城市s的规则为:
其中Jk (r) 表示还没有被访问的城市, τ (r, u) 表示城市r与城市u之间的信息素, η (r, u) 表示城市r和城市u之间的启发式因子, β表示启发式因子的相对强弱, q是在区间[0···1]上呈均匀分布的一个随机数, 0≤q0≤1。一只位于城市r上的蚂蚁在选择转移到下一座城市s之前, 首先生成一个随机数q (0≤q≤1) , 如果q≤q0, 则从第k只蚂蚁所有可以转移的城市中选择一个[τ (r, u) ]·[η (r, u) ]β最大的进行转移。否则, 按下式来选择下一座城市。
这种状态转移规则既有利对解空间进行全局搜索, 又能克服蚁群算法收敛速度慢以及易陷入局部最优解的缺点。
2.1.2 ACS的全局更新规则
在ACS中, 只有全局最优解所属路径上的信息素才会被更新, 更新规则如下式所示。
其中,
0<α<1表示信息素挥发系数, Lgb表示求得的全局最优路径的长度。由于只有全局最优解所属路径上的信息素才会被更新, 从而加强了算法的正反馈作用, 加快了算法的收敛速度。
2.1.3 ACS的局部更新规则
在构造解的过程中, 蚂蚁每进行一次转移, 都要对其所经过的边上的信息素进行更新, 其更新规则如下。
其中, 0<ρ<1。△τ (r, s) 的取值一般有三种:△τ (r, s) =0, △τ (r, s) =τ0, 。实验表明第一种的效果较差, 第二种和第三种的效果较好。局部更新规则的作用便是对每条边上的信息素进行动态更新, 每当一只蚂蚁经过一条边以后, 这条边上的信息素便会减少, 这样便减少了已经被选择的路径被再次选择的概率, 从而有利于对解空间进行全局搜索。
2.2 最大最小蚂蚁系统
MMAS主要从三个方面对AS进行了改进: (1) 在所有蚂蚁完成一次周游以后只允许最优解所属路径上的信息素被更新, 信息素的更新规则如下:
其中, △τijbest=1/f (sbest) , f (sbest) 表示最优解的路径的长度。这样便加快了算法的收敛速度。 (2) 各条边上的信息素的量被限制在[τmin, τmax]范围内, 这样便不会出现某些边上的信息素的量远大于其他边的情况, 有效地避免了算法收敛于非全局最优解以及收敛中的停滞现象。 (3) 在初始时刻, 每条边上的信息素的值被初始化为τmax, 这样能够增强对解空间的搜索能力, 有助于发现更多的可行解。另外, 在MMAS中增加了信息素平滑 (pheromone trail smoothing, 简称PTS) 机制。在算法运行过程中, 当已经收敛或快接近收敛时, 该机制用来对信息素进行调整, 更新规则如下:
其中, 0<δ<1, τij (t) 和τ*ij (t) 分别表示信息素更新前后的值。信息素平滑机制的目的是通过增加选择信息素浓度较低的路径的概率来达到对解空间进行进一步搜索的能力。MMAS是目前解决复杂的组合优化问题的最优算法之一。
3 蚁群算法的应用
自从蚁群算法在TSP问题上的应用取得成功以来, 蚁群算法的应用已经不断地渗透到了领域。将蚁群算法应用于通信中的路由问题, 目前可以解决包括带宽、延时、包丢失率和最小花费等约束条件在内的QoS组播路由问题, 比现有的链路状态路由算法具有明显的优越性;将蚁群算法应用于电力系统, 可以寻求一个周期内各个负荷水平下机组的最优组合方式以及开停机计划, 从而使运行费用最小;将蚁群算法应用于二次分配问题, 在二次此问题中分配费用是分配方式的函数, 从而可以寻求一种分配方式, 使分配费用最小;将蚁群算法应用于生产调度问题, 因为蚁群算法机制可以不断地从过去的加工经历中学习, 能很自然地适应外部环境的变化, 从而可以实现动态调度, 这种动态调度比静态调度具有更好的应用前景。
4 结束语
经过十几年的发展, 蚁群算法已经被证明是求解优化问题的有效工具, 但是该算法还
不像遗传算法和人工神经网络那么成熟, 还缺少足够的理论支持。在今后的工作中, 还要对以下方面作进一步的研究:
(1) 加强对蚁群算法的理论研究。虽然说现在蚁群算法已经被成功地用于解决各种复杂的组合优化问题, 但现在蚁群算法的多数成果都是基于大量实验的数据分析, 还没有坚实的数学基础, 其中各种参数的选取也比较复杂, 所以从算法的理论方面还有许多需要解决的问题。
(2) 研究蚁群算法的并行实现, 蚁群算法的群体特性为其并行实现提供了坚实的基础。
(3) 研究蚁群算法与其他算法的结合, 蚁群算法具有很好的耦合性, 例如与局部搜索算法结合往往可以取得较好的结果。
(4) 研究蚁群算法与其他的概率学习算法的关系, 这样有助了解蚁群算法的工作原理。
参考文献
[1]DORIGO M, MANIEZZO V, COLORNI A.Ant system:optimization bya colony of cooperating agents[M].IEEE Trans.on Systems, Man, andCybernetics-Part B:Cybernetics, 1996 (1) .
[2]DORIGO M, GAMBARDELLA LM.Ant colony system:a cooperativelearning approach to the traveling salesman problem[M].IEEETrans.on Evolutionary Computation, 1997 (1) .
[3]ST?TZLE T, HOOS HH.MAX-MIN ant system.Future GenerationComputer Systems 2000.
[4]DORIGO M, BLUM C.Ant colony optimization theory:a survey[M].Theoretical Computer Science, 2005.
[5]STUTZLE T, HOOS HH.MAX-MIN ant system and local search forthe traveling salesman problem[C].In:IEEE Int'1 Conf.on Evolu-tionary Computations.Indianapolis:IEEE Press, 1997.
[6]吴斌, 史忠植.一种基于蚁群算法的TSP问题分段求解算法[J].计算机学报, 2001 (12) .
[7]孙力娟, 王良俊, 王汝传.改进的蚁群算法及其在TSP中的应用研究[J].通信学报, 2004 (10) .
[8]朱庆保, 杨志军.基于变异和动态信息素更新的蚁群优化算法[J].软件学报, 2004 (2) .
蚁群算法 篇5
基于改进蚁群算法的无人机侦察航路规划研究
蚁群算法是一种新的源于大自然生物界的仿生随机优化方法,在一系列组合优化问题求解中取得了成效.本文将蚁群算法引入无人机侦察航路的规划,对基本蚁群算法提出了改进,提供了一种新的有效的航路优化算法,并对无人机的侦察航路进行了仿真计算.仿真结果表明改进的`蚁群算法克服了基本蚁群算法的收敛速度慢、易于过早陷入局部最优的缺点,仿真结果验证了该算法的有效性.
作 者：蒋定定 李万泉 JANG Ding-Ding LI Wan-Quan 作者单位：海军航空工程学院,青岛分院,山东,青岛,266041刊 名：飞机设计英文刊名：AIRCRAFT DESIGN年，卷(期)：28(2)分类号：V279+.2关键词：蚁群算法 无人机 航路规划 生物信息
蚁群算法 篇6
关键词： 蚁群算法； 信息素策略； 能见度
中图分类号： TP 391.4文献标志码： Adoi： 10.3969/j.issn.10055630.2015.03.016
Abstract： The highthroughput monoclonal colony selection instrument is a highend equipment applied to biological cell engineering which contains the technologies of optical imaging， image recognition and automatic control. For the 12×8 probe array and the targets in random order， only the optimization of selected path and order can improve the throughput. Thus， this paper presents the principle of the basic ant colony algorithm and optimizes the selection path based on the algorithm. Then results of the experiment prove the method can greatly improve the selection efficiency.
Keywords： ant colony algorithm； pheromone update strategy； visiability
引言单克隆菌落挑选仪是集光学成像、图像识别和自动控制等技术于一身，应用于生物工程领域的一种高端仪器，在我国处于起步研制阶段。在经过诱变和培养的数以万计的菌株中，仅有百分之几是符合要求的高性能菌株。传统的挑选菌株方式是通过目视菌落形态颜色等特征，人工方式取出优质菌株，该方法不仅重复性差，而且效率极低。为了提高挑选效率和可靠性，美国、德国、瑞士等国相继开发出基于光学成像和图像识别技术的单克隆菌落挑选仪。其工作原理是对菌落图像进行分析，通过分析菌落形态、大小、圆度、长短径比和颜色等特征，进而标记出高性能菌落[12]，并利用机械手带动探针实现菌落的挑取和转移。单克隆菌落挑选仪的一个重要考核指标是单位时间内能完成的操作数量（即通量），通量与机械手行走的路径直接相关。因此为了实现高通量，需要找到最科学合理的挑选路径，这也是仪器研发面临的重要问题之一。图1菌落挑选仪探针阵列
Fig.1Probe array on selection instrument菌落挑选仪探针阵列如图1所示，机械手末端为12×8的探针阵列，菌落目标则随机分布在圆形培养皿区域内。随机械手移动到相应位置，探针逐一伸出，每根探针挑取一个目标后，一次性放入标准96孔深孔板。在设计初期，每次挑选匹配间隔距离最小的探针和菌落目标，以期通过减小单次运动量缩短总路径长度，该方法称为最近点法。最近点法是一种贪心算法，单次运动量对路径优化具有启发性，但不是决定性的。针对这一典型的组合优化问题，本文使用蚁群算法进行优化。
1蚁群算法及其在路径优化中的实现
1.1蚁群算法蚁群算法是一种模拟蚂蚁群体觅食行为的仿生优化算法[3]，觅食过程中，虽然每只蚂蚁的智能和认知水平有限，但是通过个体与个体之间基于生物化学物质的通信，相互影响，最终能适应苛刻的环境，解决复杂的问题，这是一种群体智能。图2为反映群体智能的双桥实验。
如图2（a）所示蚁穴A与食物D之间存在障碍，起初蚁穴中的蚂蚁随机地寻找能绕过障碍搬运食物的路径，同时在这些路径上留下能被同伴嗅觉捕捉的信息素。不同的路径长度不一，如图（b）中的ABD、ACD，蚂蚁往返在较短的路径上将留下更多的信息素，随着信息素的浓度的差异，大多数的蚂蚁将选择较短的路径如图（c）所示。蚁群算法即仿照蚂蚁群的这种行为特征，利用一组数据作为算子间通信的生物信息素，启发算法进行寻优搜索，可以解决复杂的组合优化问题。假设有n个目标地点，开始有m只蚂蚁随机地分布在n个地点上，记t时刻i到j的路径lij上的信息素强度为τij（t），在t+1时刻，m只蚂蚁各自向下一目标移动，为了防止蚂蚁反复经过同一目标，需设置禁忌表tabu，记录已经去过的目标，随移动进程变动。蚂蚁k在t时间内选择i到j的路径lij的概率可以根据路径上的信息素计算出[4]Pkij（t）=[τij（t）]α·[ηij（t）]β∑sallowedk[τis（t）]α·[ηis（t）]βjallowedk
0else（1）式中：allowedk表示蚂蚁k下一步允许选择的目标，即全部目标集合C减去k的禁忌表集合；α为信息启发因子，表征信息素在路径选择时的作用；β为期望启发因子，表征距离启发因素（能见度）在路径选择时的作用；ηij为启发函数，是路径长度dij的倒数。每次蚂蚁完成了一条路径，就会更新各处的信息素。遍历过n个城市后在路径lij上的信息素为τij（t+n）=ρτij（t）+Δτij（2）
Δτij =∑mk=1Δτkij（3）式中，ρ为挥发系数，Δτij为在该次移动中由其他蚂蚁留下的信息素，Δτkij为蚂蚁k在路径lij上留下的信息素。根据基本的信息素策略[3]，信息素表达式为Δτkij=QLk第k只蚂蚁经过路径lij
nlc202309011923
0第k只蚂蚁并未经过路径lij（4）式中，Q为为信息素强度，Lk为蚂蚁走过的长度。
1.2蚁群算法在挑选仪单克隆菌落挑选仪优化中的实现蚁群算法可用在求解旅行商问题，旅行商问题（travelling salesman problem，TSP）即为一名旅行商需要去拜访若干城市，寻找只拜访各城市一次后返回出发点的最短路线的问题。其数学模型描述[5]为C={c1，c2，…，cn}为城市，L={lijci，cjC} 是集合C中元素两两之间的路径集合，dij为lij长度。G=（C，L）是一个有向图，求解旅行商问题是从G中找到长度最短的Hamilton圈。区别于传统旅行商问题，在对挑选仪进行优化时，需要做以下处理：（1）在对挑选仪路径优化时，相对目标移动的不是一个点，而是矩形探针阵列（以下称运动针盘），算法中的每次移动取决于运动针盘上要使用的探针p以及目标菌落t，组合集合C={（p，t）p∈P，t∈T}（P，T分别为96枚探针的集合和96处菌落目标的集合），由于探针和菌落均不重复使用，故约束任意两个C的元素ck=（pi，ti）和cl=（pj，tj），有pi≠pj且ti≠tj。（2）运动针盘安装在正交的二维导轨组成的机械手上，由伺服电机驱动，以脉冲信号控制。在常加速度模式下，伺服电机接收到指定脉冲信号开始以a=0.3 g起步加速，加速至预先设定的工作速率vm，脉冲停止时开始减速刹车[6]。在统计行程时依据机械手运动的两个特点①两条导轨分别由各自电机驱动，定位时间由两条导轨中行程长的一维决定；②电机的行程和时间对应关系可视为为线性关系t=vma+svm。（3）蚁群算法工作建立在个体通信的基础上，对于大规模TSP问题，使用蚁群算法会产生极其庞大的运算开销，本文研究的探针与目标组合数达到了962，完整的信息素记录可能多达几千万组，因此平衡通信开销和搜索空间的充分性是改进蚁群算法的必要工作。算法工作者为改进蚁群算法提出了多种信息素更新策略[7]。在解决本问题时，引入能见度阈值的概念，运动针盘可选路径很多时（如在最开始的几步），决定运动方向前先根据各目标位置进行初步过滤，忽略运动跨度较大的路径上的信息素，这种跨越必然是不合理的。一种阈值设置方法Qd=w（dmin+dmax），其中系数w∈（0，1），dmin、dmax分别为未使用的各探针与各目标的距离的最小、最大值。此外，在算法程序中设置信息素字典动态记录路径被采用的概率，信息素持续挥发值小于一定值时，将此记录删除以节省存储空间。
2模拟仿真实验
2.1实验设计本文根据蚁群算法编写了优化程序，并设计了仿真实验测试优化效果。在直径9 cm的区域内随机生成96个点作为菌落目标，探针排列为12列8行，相邻间隔9 mm，在菌落区域移动仿真图见图3。根据菌落挑选仪在图像捕获时刻的位置关系，将两者初始相对位置设定为常数。目标排列的形状与探针形状相符的程度决定着最优解的大小，极端情况下，目标排列与探针阵列完全相同，则整个挑选过程只需一次移动。为了减少“巧合”造成的影响，实验通过对多组目标优化，分析最优解的收敛情况。
2.2实验结果实验参数[89]中α=2.5、β=4.5、ρ=0.5、Q=400、m=20。绘制出平均路径长度收敛曲线如图4，由图中可见，算法在1次迭代将最优解值收敛到415 mm，在5次内开始优于最近点法，随迭代次数增加，收敛逐渐趋于平缓。图5反映了不同样本分别用最近点法和蚁群算法优化最终结果的差异。经过蚁群算法优化，路径总长度相比最近点法得到进一步缩短，而且没有因样本差异产生显著波动。
3结论本文针对单克隆挑选仪研发中遇到的挑选路径优化问题，结合机械手运动特点，将探针与目标组合，构成抽象城市的概念，根据蚁群算法，对最优挑选步骤进行了启发式优化，并采取适当的信息素策略控制运算规模。模拟实验结果表明，蚁群算法的应用有效地减少了菌落挑选探针的移动距离，从而提高了仪器通量。参考文献：
[1]周莹莉，曾立波，刘均堂，等.基于图像处理的菌落自动计数方法及其实现[J].数据采集与处理，2003，18（4）：460464.
[2]陈东科.加强形态学检查提高细菌鉴定的准确性[J].实验与检测医学，2012，30（5）：419422.
[3]ERIC B，MARCO D，GUY T.Swarm intelligence：from natural to artificial systems[M].Oxford：Oxford University Press，1999.
[4]李士勇，陈永强，李研.蚁群算法及其应用[M].哈尔滨：哈尔滨工业大学出版社，2004.
[5]段海滨.蚁群算法原理及其应用[M].北京：科学出版社，2005.
[6]黄兆斌，黄云龙，余世明.几种步进电机加减速方法的对比研究及其应用[J].机电工程，2011，28（8）：951974.
[7]岑宇森，熊芳敏，曾碧卿.基于新型信息素更新策略的蚁群算法[J].计算机应用研究，2010，27（6）：20802083.
[8]詹士昌，徐婕，吴俊.蚁群算法中有关算法参数的最优选择[J].科技通报，2003，19（5）：381386.
[9]吴春明，陈治，姜明.蚁群算法中系统初始化及系统参数的研究[J].电子学报，2006，（8）：15301533.
（编辑：张磊）
蚁群算法与粒子群算法的比较研究 篇7
由简单个体组成的群落与环境以及个体之间的互动行为称群智能(swarm intelligence)。群智能算法作为一种新兴的演化计算技术已成为越来越多研究者的关注焦点,群智能在没有集中控制且不提供全局模型的前提下,为寻找复杂的分布式问题求解方案提供了基础。目前,群智能理论研究领域主要有两种算法:蚁群算法(Ant Colony Optimization,ACO)和粒子群算法(Particle Swarm Algorithm,PSO),前者是蚂蚁群落食物采集过程的模拟,后者是鸟群觅食过程的模拟。本文对这两种算法的原理、模型、应用等方面进行比较分析,并对这两种算法的改进以及与其它算法的混合做出总结。
一、蚁群算法
蚁群算法是由Colorni、Dorigo和Maniezzo通过对蚁群觅食行为的研究,于1991年提出的一种仿生进化算法[1],利用蚁群在搜索食物源的过程中所体现出来的寻优能力来解决一些离散系统优化中的问题。蚂蚁是一种社会性昆虫,通过一种特有的通信机制,其群体行为展现出高度协作性,能够完成复杂的任务,并且,蚂蚁还能够适应环境变化随时调整搜索路径。作为一种随机搜索处算法,与其他模型进化算法一样,ACO也是通过侯选解组成的群体的进化过程来寻求最优解。
蚁群算法首先被成功应用于旅行商问题(TSP)上,以此为例算法的寻优过程[2]:设有m只蚂蚁,每只蚂蚁根据信息素浓度选择下一个城市(tij(t)为t时刻城市i和j之间路径上残留的信息素浓度,dij(i,j=1,2,...,n)表示城市i和j之间的距离),规定蚂蚁走合法路线,除非周游完成,不允许转到已访问城市。完成周游后,更新蚂蚁访问过的每一条边上的信息素。
初始时刻,各路径的信息量tij(0)相等,m只蚂蚁被放置到不同的城市上。蚂蚁k(k=1,2...,m)在运动过程中,根据各条路径上信息量决定转移方向,表示在t时刻蚂蚁k由位置i转移到j的概率。
其中,allowedk表示蚂蚁k下一步允许转移到的城市集合,随k的行进而改变;信息量τij(t)随时间的推移会逐步衰减,用1-ρ表示它的衰减程度;α,β分别表示蚂蚁在运动过程中积累信息量及启发式因子在蚂蚁选择路径中所起的不同作用;ηij为由城市i转到j的期望程度,可根据某种启发算法而定。
经过n个时刻,蚂蚁k走完所有城市,完成一次循环。此时,根据式(2)一(4)更新各路径的信息素:
其中:ρ表示信息素挥发系数,Δtij表示本次循环中路径ij上的信息量增量,表示蚂蚁k在本次循环中在城市i和j之间留下的信息量,其计算方法根据不同模型而定,最常用的是ant-cycle system:
其中:Lk表示蚂蚁k环游一周的路径长度,Q为常数。
算法流程如图1所示:
二、粒子群算法
Kennedy和Eberhart于1995年受鸟群觅食行为的启发提出了粒子群优化算法(Particle Swarm Optimization,PSO)[3]。PSO中,每个优化问题的解视为d维搜索空间中的一个粒子,粒子在搜索空间中以一定速度飞行,所有的粒子都有一个由被目标函数决定的适应值,并且知道自己到目前为止发现的最好位置,每个粒子利用个体和全局最好位置更新位置和速度。
假设m个粒子组成一个种群并在D维空间搜索,第i个粒子在第t代的位置表示为一个D维的向量Xi(t)=(xi1,,xi2,…,xD),飞翔速度为Vi(t)=(vi1,vi2,...,vD),粒子本身历史最佳位置为Pi(t)=(pi1,pi2,...,pD),群体历史最佳位置为Pg(t)=(pg1,pg2,...,pD)。PSO算法迭代公式如下:
其中,w为惯性权重,使粒子保持运动的惯性,使其有扩展搜索空间的趋势;c1和c2为加速系数,代表了将每个粒子拉向Pi和Pg的随机加速项的权重;r1和r2是两个独立的介于[0,1]之间的随机数,t为进化代数。
算法流程如图2所示:
三、两种算法的比较分析
1算法各自优缺点
(1)由于群智能算法采用的是概率搜索算法,ACO和PSO具有共同的优点[4]:
①鲁棒性:由于算法无集中控制约束,不会因个别个体的故障而影响整个问题的求解。
②扩展性:信息交流方式是非直接的,通信开销少。
③并行分布性:可充分利用多处理器,适合于网络环境下的工作状态。
④优化过程无需依赖具体问题的数学特性,例如可微、线性等。
⑤算法简单容易实现:系统中个体能力简单,执行时间短。
另外,PSO还具有如下优点:
①群体搜索,并具有记忆功能,保留个体和全局的最优信息;
②协同搜索,同时利用个体和全局的最优信息指导进一步搜索。
(2)ACO和PSO也存在着局限性:
①优化性能在很大程度上依赖于参数设定,受初始值影响较大。
②容易产生早熟收敛。
另外,ACO收敛速度慢,只有小部分的ACO算法能够被证明是值收敛的,并且在实际应用中常常出现一种有害的搜索偏向现象,即二级欺骗现象。
PSO局部搜索能力差,搜索精度不高,并在理论研究上尚未完善,缺少算法设计的指导原则。
2应用领域
●ACO本质上适合于求解离散组合优化问题,在旅行商问题上取得成功应用后陆续渗透到其它领域。在指派、调度、子集、带约束满足等组合优化问题时达到了高效的优化性能。并在图着色、电路设计、二次分配问题、数据聚类分析、武器攻击目标分配和优化、大规模集成电路设计、网络路由优化、数据挖掘、车辆路径规划、区域性无线电频率自动分配、集合覆盖等优化领域得到了成功应用。
●PSO本质上适合于处理连续优化问题,但如果对求解问题进行变形或修正速度和位置更新公式也能将其应用于离散优化问题上。并且,鉴于其通用性和有效性,在解决一些典型优化问题时,其性能甚至超过了遗传算法,已成功应用于训练人工神经网络、函数优化、约束优化、多目标优化、动态优化、参数优化、组合优化、模糊系统控制、电力系统、信号处理、模式识别、生物医学等领域中。
3与其它算法混合
由于ACO与PSO具有容易与其它算法结合的特点,根据各算法的优缺点,在算法中结合其它优化技术,以提高算法的优化性能。
①蚁群算法与差分演化结合:针对蚁群算法对参数控制的依赖性、早熟和停滞等现象,以及易与其他算法结合的特点,将差分演化算法应用到蚁群算法的参数选取中,将蚁群算法的参数作为差分演化算法解空间的向量元素,自适应地寻找蚁群算法最优参数组合的同时求解问题的最优解。
②蚁群算法与粒子群算法结合:针对蚁群算法容易出现早熟现象以及算法执行时间过长的缺点,将粒子群算法引入到蚁群算法中,让蚂蚁也具有粒子的特性。
③粒子群算法与模拟退火结合:先利用PSO算法的快速搜索能力得到一个较优的群体,然后利用SA的突跳能力对部分较好的个体进行优化。
④粒子群算法与遗传算法结合:针对PSO容易早熟的缺点,在PSO中引入启发性变异机制,以扩展了算法的搜索区域,提高了算法的速度和精度且不容易陷入局部最优。
⑤粒子群算法与差分演化结合:针对粒子群算法易陷入局部极小点、搜索精度不高等缺点,在算法改进方面引用差分演化算法的变异操作,从而避免算法收敛到局部。
四、展望
群智能算法采用分布式计算机制、鲁棒性强、可扩充性好、优化效率高、并且简单易于实现,为解决实际优化问题提供了新的途径和方法。除了本文提出的ACO和PSO,群智能算法还包括研究蜜蜂通过与环境之间的信息交互实现安排工作的蜂群算法[5]、李晓磊博士通过模拟鱼群觅食行为和生存活动提出的鱼群算法[6]。作为一门新兴领域,群智能算法尚缺乏系统的分析和坚实的数学基础,实现技术不规范,在适应度函数选取、参数设置、收敛理论等方面还需要做进一步研究与探索。在此基础上,对算法加以改进或混合其他技术,以提高算法优化性能也是值得深入研究的一个方向。并且需不断拓宽其应用领域,以进一步推广群智能算法的应用。
参考文献
[1]A.Colorni,M.Dorigo,G.Theraulaz.Swarm intelligence: From natural to artificial systems[M].New York:Oxford Universyty Press,1999.
[2]宋雪梅,李兵.蚁群算法及其应用[J].河北理工学院学报,2006年2月,第28卷第1期:42-45.
[3]Kennedy J,Eberhart R.Particle Swarm Optimization[R].In:IEEE International Conference on Neural Networks,perth,Australia 1995:1942-1948.
蚁群算法 篇8
20世纪以来, 随着科技的不断进步, 传统的手工劳动已不能适应社会的快速发展, 机器时代顺应而生。为更好地将机器劳作代替手工劳动, 且高效率完成工作任务, 各种控制机器的智能算法随之产生。本文按照3种智能算法——蚁群算法、模拟退火算法、遗传算法的时代产生顺序, 依次介绍3种算法的由来及其应用领域, 并将3种算法在求解方面和收敛速度方面进行了分析比较。
模拟退火是1953年Metropolis等人根据物理中固体加温、等温、冷却过程提出的, 该过程与实际生活中的一些组合优化问题具有通融性, 目前已在工程中得到广泛应用。遗传算法是1975年J.Holland教授依据达尔文的“适者生存, 优胜劣汰”的自然进化机制首先提出的。该算法在求解过程中, 能够自动适应和控制搜索方向, 在机器学习、信号处理、自适应控制等领域得到较好应用。蚁群算法是1991年Dorigo等人提出的一种新型智能算法, 该算法思想源于自然界中蚂蚁觅食行为, 蚂蚁在觅食过程中会寻找最短路径, 故蚁群算法最早应用于解决TSP问题, 初见成效后, 陆续应用到静态、动态组合优化问题中。3种算法在智能计算中都发挥着重要作用。
2算法实现
本节以传统TSP问题为研究对象, 分别介绍3种算法——蚁群算法、模拟退火算法、遗传算法在解决TSP问题时的算法实现流程。
2.1蚁群算法实现流程
本节给出使用蚁群算法解决TSP问题的流程图, 如图1所示。
2.2 模拟退火算法实现过程
本节利用伪程序阐述使用模拟退火算法求解TSP问题, 过程如图2所示。
上述过程中, T是初始温度, S是初始值, S’是当前回路产生的新回路, f (S) 是路径总长度。
2.3 遗传算法实现过程
遗传算法解决TSP问题的实现过程如下所示。
步骤一:种群初始化。在众多染色体编码方法中选择实数编码解决TSP问题。初始化种群数量、染色体基因个数、交叉概率、变异概率、迭代次数等。
步骤二:写出适应度函数。对于TSP问题, 觉得算法好坏的指标是总距离。根据染色体可计算出总距离, 距离越短, 适应度函数越好。
步骤三:选择算子。程序采用轮盘赌策略, “优胜劣汰”的思想, 并且在每代中保存适应度最好的个体。
步骤四:交叉算子。采用单个染色体指定位置交叉的思想, 防止程序过早陷入局部收敛。
步骤五:变异算子。根据变异概率, 随机选择变异个体, 随机选取染色体中的基因进行交换实现变异过程。
3 三种算法的比较
本节验证蚁群算法在求解质量和收敛速度方面的优劣, 待比较算法为模拟退火算法和遗传算法。实验过程分为两组:第一组比较三种算法在所得解质量方面的优劣, 第二组比较三种算法在收敛速度上的快慢。
3.1 求解质量对比
求解质量对比可描述为在相同条件下, 即随机生成5组数据, 每组数据包含50个不同城市, 组成五个完整的TSP问题, 得到蚁群算法与模拟退火、遗传算法所得解质量的优劣。在随机产生的问题上的运行结果如表1所示。
从表1可以看出, 蚁群算法求解的质量最高, 其他两种算法——模拟退火、遗传算法求解质量不及蚁群算法。
3.2 收敛速度对比
收敛速度可以作为评判算法性能优劣的一个重要指标。本节对蚁群、模拟退火、遗传算法在收敛速度方面进行比较。实验过程包含三个城市数量在50到100之间的几何问题, 三种算法在几何问题上的仿真结果如表2所示。
从表2可以看出, 随着城市数量的增加, 3种算法收敛到最优解的迭代次数差距也随之增大。当城市数量为50时, 蚁群系统在第2412代收敛到最优解, 而模拟退火算法在68512代收敛到最优解, 与蚁群算法收敛速度相差一个数量级, 遗传算法介于蚁群系统和模拟退火算法之间, 在第25000代收敛到最优解。以上结果表明:蚁群算法的收敛速度最快。
4 结语
蚁群算法与模拟退火、遗传算法在细节上具有差异, 如蚁群算法适用于小规模智能计算、遗传算法可能陷入局部最优解等, 但3种算法都具有较强的鲁棒性, 算法间可以相互融合, 也可与其他启发式算法融合, 改善算法的性能。
参考文献
[1]程飞.改进蚁群算法及其应用研究[D].江西:江西理工大学, 2013.
[2]何小锋, 马良.带时间窗车辆路径问题的量子蚁群算法[J].系统工程理论与实践, 2013, 33 (5) :1255-1261.
蚁群优化算法应用研究 篇9
蚁群算法本质是一个复杂的智能搜索算法,具有较强的鲁棒性、良好的正反馈性能、优良的分布式计算机制、易于与其他优化算法相结合等特点。如今,该算法已经成为智能优化算法中的研究热点,对它的研究已经渗入到多种不同的应用领域。
1 基本蚁群算法原理
在自然界中,单个的蚂蚁个体行为极为简单,但由多个蚂蚁所组成的群体却成功地在搜寻食物等方面表现出复杂的行为。研究发现,蚂蚁总能找到巢穴与食源之间最短路径。蚁群算法就是借鉴和吸取现实世界中蚂蚁这种集体寻径行为来寻求函数的最优解。
蚂蚁个体之间通过一种称为信息素的物质进行信息传递,蚂蚁在移动过程中通过感知遗留在路径上的该种物质来指导自己的运动方向,并在自己经过的路径上留下该类物质。这样,大量蚂蚁所组成的群体便构成了一种信息正反馈,从而成功地实现了食物搜索,最短路径选择等行为。为了具体说明蚁群算法的原理,举出人工蚁群路径搜索的例子。
如图1所示,路径AB、ED、DH、HB长度分别为1,BC和BD长度分别为0.5。如图1(a)所示,在t=0时刻,有30只蚂蚁分别在A点和B点,蚂蚁单位时间内行程为1并留下1个浓度的信息素。如图1(b)所示,在t=1时刻,A点和E点的蚂蚁同时到达B点和E点,由于此前路径上没有信息素,它们随机选取路径,在DH、HB、BC、DC上将各有15只蚂蚁。如图1(c)所示,在t=2时刻,将有30只蚂蚁到达H点,而有15只蚂蚁分别到达B点和D点,在这段时间内,遗留在BC、CD上的信息素将是DH或是HB的两倍。而蚂蚁是根据遗留在路径上信息素的强弱来选择自己前进的方向,信息素强路径的将会吸引更多的蚂蚁,因此在后续的选择中,选择DC或是BC蚂蚁数量将是DH和HB的两倍,所以,20只蚂蚁选择BC,10只选择BH。如此反复进行下去,直至所有的蚂蚁都选择最短的路径BCD或是DCB。通过上面的例子,可以简单的说明蚁群算法主要的特点:
1)正反馈性。蚂蚁群体行为表现出正反馈过程,通过反馈机制的调整,可对系统的较最优解起到一个自增强的作用,从而使问题的解向着全局最优的方向演变,最终能有效的获得全局最优解。
2)并行性。蚁群算法是一个本质并行的算法,个体之间不断的进行信息的交流与传递,相互协作,有利于最优解的发现,从而在很大程度上减少了陷于局部最优的可能。
2 算法描述[1]
蚁群算法首次提出是用于解决TSP问题,因此我们就以求解n个城市的TSP问题为例来说明基本蚁群算法的求解过程。
TSP问题是一个典型的离散优化问题。其定义是:给定n个城市,TSP等价于寻找一条只经过各个城市一次且长度最短的闭合路径。令dij为城市i和j之间的距离,在欧式空间中,。。
假设蚁群数量为m,τkij(t)表示t时刻在ij上遗留的信息素。在初始时刻,各条路径上的信息素是相等的,τij(0)=C(C为常数),蚂蚁k(k=1,2,,m)在运动的过程中根据各条路径上遗留的信息素决定移动方向。pkij(t)表示t时刻蚂蚁k由城市i选择城市j的转移概率
allowedk={0,1,………,n-1}表示蚂蚁k下一步允许选择的城市,α和β分别反映了蚂蚁在运动的过程中所积累的信息和启发信息在蚂蚁选择路径中的相对重要性,ηij为由城市i转移到城市j的期望程度,在TSP问题中取ηij=1/dij。建立禁忌表tabuF(F=1,2,……n)记录在t时刻蚂蚁已经走过的城市,不允许该蚂蚁在本次循环中再经过这些城市。当本次循环结束以后,禁忌表将被用来计算改蚂蚁当前所经过的路径长度。之后,禁忌表将被清空,用以准备下一次循环。经过n个时刻,蚂蚁完成一次循环,各条路径上的信息素根据下式调整:
用△τkij表示第k只蚂蚁在本次循环中留在路上的信息素,则,ρ为信息素残留系数,1-ρ表示信息素的消逝程度。
根据具体的算法的不同,△τij、△kij和pkij(t)表达形式也有所不同,可根据具体问题而定。M.Dorigo曾给出三种不同的模型,分别是蚁周系统、蚁量系统、蚁密系统。经过一系列标准测试问题的测试,蚁周系统的性能要优于其他两种算法,故常用的就是蚁周系统更新模式:
其中,Lk为第k只蚂蚁在本次循环中所走的路径长度。
3 蚁群算法的改进[2,3,4,5,6,7]
基本蚁群算法具有很强的全局搜索能力,但是也存在一些问题,例如:搜索时间过长,执行过程中容易出现停滞现象,当问题规模较大时存在陷入局部最优解的可能。因此,很多学者对蚁群算法进行了改进。
3.1 基于优化排序的蚂蚁系统
蚁群算法和遗传算法一样,都有一个共同的缺陷就是容易陷入局部最优解。当路径差别不大,解元素之间的差异减少,致使选择概率的差异也随之减少,从而阻止了对最优解进一步的搜索。借用遗传算法中适应度排序法,将每次循环以后生成的路径进行排序,依照序列的顺序进行信息素加权更新。
3.2 最大最小蚂蚁系统
为了防止过早的算法停滞现象,德国学者T.Stuetzle和H.Hoos提出了最大最小蚂蚁系统(Max-Min Ant System,MMAS),其特点是在算法中引入了信息素最大值和最小值限制。当某条路径上的信息素大于上限,就强制为上限值;小于则为下限值,通过设定信息素的上下限。这样一方面避免了某条路径上的信息素远大于其他路径的信息素浓度,从而有效的降低了过早停滞的可能;另一方面,不会因为某条路径的信息素浓度过低而丧失发现新路径的可能。
有实验表明,MMAS算法较传统的蚁群算法相比,在寻优的有效性方面和防止算法的过早停滞方面具有更好的效果,但是,仅采用最大最小信息素的限制还不足在较长的时间里持久消除停滞现象,因此,可以对其进行进一步改进,如在算法中引入信息素平滑机制等。
3.3 自适应蚁群算法
为了既能保持蚁群算法全局搜索能力,又能提高搜索速度,王颖等人提出了自适应蚁群算法。该算法能在进行过程中自适应的改变ρ值,ρ的初始值取ρ(t0),当算法求得的最优解在固定的N次循环内没有明显得改进时候,对ρ值作出适当的调整。
式中,ρmin为ρ的最小值,可以防止ρ过小而降低算法的全局搜索能力。通过多种实验表明,该算法比一般的算法具有更好的收敛速度和稳定性,更适合于求解大规模的TSP。
4 结论
蚁群算法是一种新的仿生进化计算方法,已经在TSP、图与组合优化、Job-shop等问题上取得了成功的应用,并具有其独特的优越性。但由于蚁群算法还是一种新型的优化算法,其研究刚刚开始,还没像遗传算法和模拟退火算法等那样形成系统的分析方法和坚实的数学基础,因此算法中一些参数的确定目前还没理论上的依据,以公布的实验结果都是针对特定问题而言。
总之,蚁群算法作为一种新兴的研究领域,将会得到不断深入的研究,其模型将会更加丰富,也将相应的得到更加广泛的应用。
摘要：蚁群算法是一种新型的进化算法,在离散函数和连续函数优化中都有着广泛的应用前景。该文简要对算法的研究现状做以概述,介绍该算法的基本原理、算法的模型和若干改进算法。
关键词：蚁群算法,基本原理,改进算法
参考文献
[1]段海滨.蚁群算法原理及其应用[M].北京:科学出版社,2005.
[2]吴庆洪,张纪会,徐心和.具有变异特征的蚁群算法[J].计算机研究与发展,1999,36(10):1240-1245.
[3]段海滨,王道波.蚁群算法的全局收敛性研究及改进[J].系统工程与电子技术,2004,26(10).
[4]邵晓巍,邵长胜,赵长安.利用信息量留存的蚁群遗传算法[J].控制与决策,2004,19(10).
[5]段海滨,王道波.一种快速全局优化的改进蚁群算法及仿真[J].信息与控制,2004,33(2).
[6]张纪会,徐心和.一种新的进化算法——蚁群算法[J].系统工程理论与实践,1999(3).
蚁群算法的参数选择研究 篇10
1 基本蚁群算法
蚁群算法是由Colorni、Dorigo和Maniezzo于20世纪90年代初通过模拟自然界中蚂蚁集体寻径的行为而提出的一种基于种群的启发式仿生进化算法[1]。由于蚁群算法具有分布性、并行性、全局性、鲁棒性强等特点,已经在求解NP-难问题和众多应用问题中显示出良好的优化性能和发展潜力。
以TSP问题为例,采用常用的any-cycle模型,简单阐述蚁群算法的基本原理:
设有m只蚂蚁,每只蚂蚁访问n个城市,规定蚂蚁走合法路线,除非周游完成,不允许转到已访问城市。初始时刻,各路径的信息量τij(0)相等,m只蚂蚁被放置到不同的城市上。蚂蚁k(k=1,2...,m)在运动过程中,根据各条路径上信息量和前方路径的长短决定转移方向,Pkij(t)表示在t时刻蚂蚁k由城市i转移到j的概率:
其中:
allowedk—蚂蚁k下一步允许转移到的城市集合,随k的行进而改变;
τij(t)—t时刻路径(i,j)上的信息量;
α—信息启发式因子;
β—期望启发式因子;
ηij(t)—城市i转到j的期望程度,一般取:ηij(t)=1/dij(dij表示相邻两个城市的距离);
当蚂蚁k完成周游后,根据式(2)-(4)更新蚂蚁访问过的每一条边上的信息素:
其中:
ρ—信息素挥发系数;
Δτij(t)—本次循环中路径(i,j)上的信息量增量;
Δτkij(t)—蚂蚁k本次循环中在路径(i,j)上留下的信息素数量;
Lk—蚂蚁k环游一周的路径长度;
Q—信息素强度因子,常量。
众多的研究已经表明蚁群算法具有很强的发现较好解的能力,但作为启发式概率型优化算法,蚁群算法存在着早熟收敛,对参数依赖性强的缺点。对于不同版本的蚁群算法或具体的应用问题,甚至不同的具体实例,算法需要不同的参数设置来获取最优的性能。传统对参数的设置是根据应用者有限的经验习惯人为地调整,往往需要做大量的数据测试,不仅耗费时间而且影响了算法最优性能的发挥,成为蚁群算法应用的一大缺陷。
2 控制参数对算法性能的影响[2]
蚁群算法含有一系列对算法性能有重要影响的控制参数,包括:
1)启发式因子α和β:α表示信息素的重要性,反映了蚁群在运动过程中所残留的信息量在指导蚁群搜索中的相对重要程度。α越大,信息素在路径选择上所起作用越大,蚂蚁选择以前走过路径的可能性就越大,搜索的随机性减弱;α越小,易使蚁群算法过早陷入局部最优。当α=0时,将不会利用信息素信息,搜索降为贪婪搜索。
β表示能见度的重要性,反映了启发式信息在指导蚁群搜索过程中的相对重要程度。这些启发式信息表现为寻优过程中先验性、确定性因素。β越大,城市之间距离对路径选择所起作用越大,蚂蚁在局部点上选择局部最短路径的可能性越大,虽然加快了收敛速度,但减弱了随机性,易于陷入局部最优。当β=0时,将忽略对有吸引力的解的显式倾向,算法等同于性能较差的简单蚁群优化(SACO)。
α和β决定了以往的搜索经验和问题的固有启发信息之间的相对重要性,出现在绝大部分的蚁群算法中,对算法性能的影响至关重要,是最重要的两个参数。由于α和β是在信息素浓度和启发式信息之间取得平衡的转移概率Pkij的两大决定因子,通过调节α和β可以很好地处理探索--开发之间的关系。
2)信息素挥发系数ρ:模仿人类记忆特点,随着新信息的增加,旧的信息将逐步忘却、削弱,故引入ρ表示信息素的挥发率,为了防止信息的无限积累,ρ的取值范围设定为[0,1]。
ρ的大小直接关系到蚁群算法的全局搜索能力及其收敛速度;ρ增大,则信息素挥发加快,对过去的历史经验不太敏感,突出最近路径上留下的信息对选择的影响。
相应地,用1-ρ表示信息的残留系数。1-ρ反映了蚂蚁个体之间相互影响的强弱,其大小对蚁群算法的收敛性能影响非常大。在0.1-0.99范围内,1-ρ与迭代次数近似成正比,这是由于1-ρ很大,路径上的残留信息占主导地位,信息正反馈作用相对较弱,搜索的随机性增强,因而蚁群算法的收敛速度慢。若1-ρ较小时,正反馈作用占主导地位,搜索的随机性减弱,导致收敛速度快,但易陷于局部最优。
3)信息素强度因子Q:Q表示蚂蚁循环一周或一个过程释放在所经路径上的信息素总量。在一定程度上影响处算法的收敛速度,Q越大,则每次蚂蚁经过所留下的信息素越多,在已遍历路径上信息素的累积越快,加强蚁群搜索时的正反馈性,有助于算法的快速收敛。
4)蚂蚁数量m:蚁群算法成功在于多只蚂蚁的共同协作行为,通过释放信息素,蚂蚁之间相互传递有关搜索空间的经验与知识。对同一规模的处理问题,m越大,即蚂蚁数量多,会提高蚁群算法的全局搜索能力和稳定性,但数量过多会导致大量曾被搜索过的路径上的信息量变化趋于平均,信息正反馈作用减弱,随机性增强,收敛速度变慢。反之,如果m越小,即蚂蚁数目太少,会使从来未被搜索到的解上的信息量减小到接近于0,全局搜索的随机性减弱,虽然提高了收敛速度,但算法稳定性差,出现早熟现象。另一个就是对计算复杂度的影响,使用的蚂蚁越多,需要建立的路径就越多,对信息素释放的计算也就越多。
3 参数选择
控制参数直接影响算法的性能,包括找到的解的质量及其计算开销。参数选择在算法应用中显得尤其重要,为了提高算法的性能,必须优化相关的控制参数。自从Dorigo等对AS系统中的参数下选取进行了初步研究[3]以来,很多学者在实验基础上进行了深入研究并提供了一些参数设置参考值和优化参数值的启发式方法。
1)人工设置参数:叶志伟等对α、β和ρ这三个对算法的影响较大的参数的最优配置进行了研究,得出:在any-cycle模型中,α=1,β=5,ρ=0.5时,算法性能最优;ant-density模型中,α=1,β=10,ρ=0.1时,算法性能最优;ant-quantity模型中,α=1,β=5,ρ=0.001时,算法性能最优[4];而蒋玲艳等在分析了这三个参数不同组合对算法性能的影响基础上,总结出参数设置规则:当α∈[0.1,0.3],β∈[3,6],ρ∈[0.01,0.3]时,算法总体上有较好的性能,不易早熟,而且所需的迭代次数较少[5]。
对于所有参数(α、β、ρ、Q、m),段海滨提出了调整步骤[6]:首先根据“城市规模/蚂蚁数目≈1.5”的原则确定蚂蚁数目m;然后粗调取值范围较大的α、β和Q;最后微调取值范围较小的ρ。詹士昌等指出当α∈[1,5],β∈[1,5],ρ=0.3,Q=100,(n为城市规模)时基本蚁群算法能较快地求得最优解[7]。张毅等则提出了最优的算法参数组合为:α=1、β=5、ρ=0.6、Q=1000、m=城市规模。在该算法参数设置原则下,基本蚁群算法对任意TSP问题总能比较快速地求得全局最优解[8]。
人工设置参数需要大量的数据测试,蚁群中的所有蚂蚁均采用相同的参数,而且只能为算法设定一个合适的初始参数,而不能在执行过程中随时调整参数,影响了算法的性能。
2)自适应调整参数:针对人工设置参数的局限,学者们提出了自适应地调整参数的改进算法,主要是利用蚁群算法具有容易与其它优化算法或局部搜索算法结合的优点,在蚁群算法中混合其它启发式算法以对其参数进行训练和优化,主要有:
(1)运用遗传算法优化蚁群算法的控制参数[9]:利用遗传算法快速性、随机性、全局收敛性的特点,每条染色体代表蚁群算法的一个参数值集合,通过选择、交叉和变异等操作不断优化蚁群算法参数。
(2)运用粒子群优化算法优化蚁群算法的控制参数[10]:粒子群优化算法具有非常快地逼迫最优解的速度,可以有效对蚁群算法的控制参数进行优化。粒子被表示成一个多维的实数编码串,代表蚁群算法的一个参数值集合,再引入适应度函数并结合粒子群算法得到各参数的最优组合。
(3)运用差分演化算法优化蚁群算法的控制参数:将蚁群算法的参数作为差分演化算法解空间的向量元素,自适应地寻找蚁群算法最优参数组合的同时求解问题的最优解。
在蚁群算法中引入其它启发式算法的混合算法,不仅使蚁群算法有效摆脱了对参数设置的依赖,而且克服了早熟收敛的缺点,大大提高了算法发现最优解的能力,具有更好的全局优化性能。
此外,研究者还提出了根据蚁群算法的不同进化阶段或当连续几代进化后的最优解没有明显变化时,自适应调整参数,以提高最优解的求解质量的改进方案[11]。这类改进算法能够有效提高算法的优化性能,但这些方法并不是通用的,只能使用于特定的算法模型或针对特定的问题。
4 小结
蚁群算法作为一种随机算法,其性能很大程度上受算法参数的影响,好的参数可以使算法快速收敛于优质解,而参数设置不当,将导致算法找到的解质量差,容易陷于局部最优,并且收敛速度慢甚至不收敛。由于蚁群算法参数空间的庞大性和各参数之间的关联性,很难设置最优参数组合以使蚁群算法优化性能最佳,至今还没有完善的理论依据,没有参数选择方面的公式可循,通常根据经验而定。因此,对蚁群算法的参数进行深入分析,了解参数之间的关联,提出好的参数设置方案,以便更合理地设置参数或者自适应地调整参数是非常有意义的,不仅能有效地提高算法的优化性能,而且完善了算法的理论研究,进一步推广蚁群算法在优化领域上的应用。
摘要：蚁群算法由于具有鲁棒性,并行分布性,执行简单,解决了许多复杂优化和NP-难问题,展现出良好的优化性能和广阔的发展前景,但算法性能很大程度上取决于参数的设置,对初始值的依赖性强。该文在介绍蚁群算法原理的基础上,详细分析算法各个控制参数对算法性能的影响,并从人工设置和自适应调整两方面对参数选择方法做了比较和总结。
关键词：蚁群算法,参数选择,人工设置,自适应调整
参考文献
[1]Colorni A,Dorigo M,Maniezzo V.Distributed Optimization by Ant Colonies[C]//The First European Conference on Artificial Life.France:Elsevier,1991:134-142.
[2]汪定伟.智能优化方法[M].北京:高等教育出版社,2007.
[3]Dorigo M,Maniezzo V,Colorni A.Ant system:optimization by a Colony of Cooperating Agents[J].IEEE Transactions on System,Man and Cybernetics,1996,26(1):29-41.
[4]叶志伟,郑肇葆.蚁群算法中参数α,β,ρ设置的研究-以TSP问题为例[J].武汉大学学报,2004,29(7):597-601.
[5]蒋玲艳,张军,钟树鸿.蚁群算法的参数分析[J].计算机工程与应用,2007,43(20):31-36.
[6]段海滨.蚁群算法原理及应用[M].北京:科学出版社,2005.
[7]詹士昌,徐婕,吴俊.蚁群算法中关键参数的选择[J].科技通报,2003,19(5):381-386.
[8]张毅,梁艳春.蚁群算法中求解参数最优选择[J].分析计算机应用研究,2007(8).
[9]Botee H,Bonabeau E.Evolving Ant Colony Optimization[J].Complex Systems,1998,1(2):149-159.
[10]闵克学,郭宏伟,张毅,等.基于蚁群和粒子群优化的混合算法求解TSP问题[J].吉林大学学报信息科学版,2006,24(4):402-405.
蚁群算法 篇11
[关键词] MAX-MIN蚁群算法时间窗车辆路径问题优化
一、VRPTW模型的建立
带有时间窗口的车辆路径问题是典型的多目标组合优化NP-hard问题,因此需要通过合理的构造数学模型来安排车辆配送路线，达到提高配送效率同时又能够产生巨大的社会和经济效益的目的。
VRPTW包括一些客户和仓库，每个客户有一定的需求和时间窗口。每个客户只能由一辆车一次服务完成，还要保证每个客户只能被精确的访问一次，同时不能违背时间窗口约束。其目的是要找到一个可行解使得车辆数最少并且总行程最小。
二、最大最小蚁群算法
为克服在Ant．Q中可能出现的停滞现象,Thomas Stutzle等提出了MMAS算法。该算法具有比基本蚁群算法更贪婪的搜索模式，其主要的改进有以下几点:首先,MMAS在运行期间更多的利用最优解信息，即每次迭代后仅允许一只最优的蚂蚁增加信息素。其次,该算法限定了信息素浓度的上下限，有效避免了在搜索中过早收敛于非全局最优解。
将m只蚂蚁随机放到n个客户中，为t时刻支路(i,j)上的信息素强度，每只蚂蚁都可认为是根据状态转移策略来选择下一个客户，并遵循信息素全局更新规则和信息素限制规则。
1.状态转移策略
针对VRPTW自身的特点，我们定义其状态转移概率为:
其中h∈allowedk={n-tabuk};ηij为启发信息;α(α≥0)代表信息素的权重，β(β≥0)代表启发信息的权重;μij=di0+dj0-dij为节约值; δij为紧迫性因子。
2.信息素更新规则
在MMAS中，只允许其中的最优路径更新信息素，其更新规则为:
其中，为该次迭代sib或全局最优路径sgb的目标函数。
3.信息素限制规则
为了降低算法搜索中的早期停滞问题，该算法限定了信息素浓度允许值的上下限，即
。若，则;若，则。
在搜索过程中,当得到最优解时,按下式便得到一个动态变化的:
为了提高算法的收敛性，我们一般先给定一个Pbest，然后根据下式来选定一个 ：
三、算例分析及结论
设某仓库使用完全相同的车辆把货物运往8个客户，车辆的载重能力为8吨，车速为50公里每小时，客户所需货物的重量，服务时间及访问时间窗口的具体要求由Tab.1给出。客户之间的距离如Tab.2所示。问题是寻找合适的路径，使得车辆运行总成本最小。
实验开始，将每个客户都放置一只蚂蚁，蚂蚁的个数与客户数相同。取α=1，β=3，γ=3，λ=1，ρ=0.8，θ=10。采用本文的算法，得到的最优解为:第一辆车：0-2-7-4-0;第二辆车：0-3-1-0;第三辆车：0-8-5-6-0。
将求解的结果与Clarke-Wright算法和遗传算法比较,从Tab.3中可以看出MMAS不失为带时间窗车辆路径问题的一个较优解。
四、结语
本文将MMAS算法应用于VRPTW问题中，充分发挥了其超强的贪婪搜索能力，获得了较为满意的实验效果。这次成功尝试再次表明了该算法在组合优化领域中是具有强大竞争力的，同时也证明了用这种方法解决具有一定的理论参考价值和实际意义。
参考文献:
[1]吴启迪汪 镭:智能蚁群算法及应用[M].上海科技出版社，2004，4
[2]刘云忠宣慧玉:动态蚁群算法在带时间窗车辆路径问题中的应用[J].中国科学工程,2005,12(7):35－40
蚁群算法 篇12
关键词：蚁群算法,网络路由
1 引言
蚁群算法最初是由M.Dorigo等人于1991年提出的。后来蚁群算法引起了很多领域研究者的注意与关注。蚁群算法是通过分布式求解模式来解决优越问题,经过很多学者的改进,目前已发展成相对成熟的算法体系。它能够将全局优化特征与问题求解的快速性、有限时间内答案的合理性相结合,快速找到最优解。而Ad Hoc网络环境中路由的选择类似于蚁群寻找食物的场景,所以将蚁群算法应用到Ad Hoc移动网络的网络路由选择是比较合适的一种算法。
2 蚁群算法概念
2.1 蚁群觅食过程
所有蚂蚁在不知道哪里有食物的情况下,在周围寻找食物。当有一只蚂蚁找到食物后,会释放一种挥发性物质———信息素扩散到周围,该信息素的扩散范围由近及远渐渐减少,它能吸引周围蚂蚁过来,这样越来越多的蚂蚁找到了该食物。有些发现信息素的蚂蚁会另辟捷径找到这个食物,如果这些蚂蚁新开辟的路径比其他路径短,则逐渐地更多的蚂蚁会吸引到这条路上来。最后,随着越来越多的蚂蚁往该食物的目的地移动,并且大多数蚂蚁会按照最短路径去找到该食物。
2.2 蚁群算法的特点
蚁群算法是通过个体间相对简单的信息传递,得出从源点到目的地之间的最短路径,它是一种集体寻优的算法。根据分析,我们得出蚁群算法有很多特点,主要有几点,如图1所示。
并行性:蚁群算法具有并行性。在蚁群搜索算法中,每只蚂蚁都是同时进行搜索的,彼此独立,它在空间多点同时开始独立解搜素,一方面使得算法具有较强的全局并行搜索能力,另一方面使得算法的可靠性增加。
较强的鲁棒性:蚁群算法不需要知道初始路线,不依赖于初始路线的选择,在搜索过程中可自发完成不需要人工干预。
正反馈性:在2.1一节中蚁群觅食过程中,我们发现最优路径的搜索直接依赖与最短路径上信息素的多少,信息素的积累是一个正反馈的过程。在不限定初始路径的情况下,给予微小的触动,就会使得正反馈不断累积找到最优解,所以正反馈是蚁群算法得以演化成最优解的一个重要的特点。
自组织性:系统论中有自组织和它组织两类,而蚁群算法属于一种自组织的算法。该算法不需要外界的特定干预就可自己搜寻出最优解,所以说它是一种自组织算法。当蚁群算法开始时,每个蚂蚁无序的随机的寻找路径,经过一段时间,信息素积累,自发的越来越多的蚂蚁找到了最优路径的过程,从无序到有序的过程。
3 Ad hoc网络路由
3.1 概述
Ad hoc网络又称为自组织网,无基础设施网或多跳网,它是一种无中心的移动自组织网络。在Ad Hoc的整个网络中,很多个终端节点都是可移动的,没有固定的基础设施,每个节点都可以任意方式地动态地与其它节点进行关联。这样使得两个无法直接进行通讯的节点可以借助网络中的其他节点进行转发通讯。而在网络中的每个节点都有路由功能,它能够发现并维持与其他节点的关联。
目前,由于无线通信和终端技术的不断发展,Ad Hoc网络在民用环境下也得到了发展,如需要在没有有线基础设施的地区进行临时通信时,可以很方便地通过搭建Ad Hoc网络实现。在Ad Hoc网络中,当两个移动主机在彼此的通信覆盖范围内时,它们可以直接通信。但是由于移动主机的通信覆盖范围有限,如果两个相距较远的主机要进行通信,则需要通过它们之间的移动主机B的转发才能实现。因此在Ad Hoc网络中,主机同时还是路由器,担负着寻找路由和转发报文的工作。在Ad Hoc网络中,每个主机的通信范围有限,因此路由一般都由多跳组成,数据通过多个主机的转发才能到达目的地。故Ad Hoc网络也被称为多跳无线网络。
3.2 Ad Hoc网络的特点
Ad Hoc网络作为一种新的组网方式具有很多特点。
带宽有限:由于Ad Hoc网络中没有有线基础设施的支持,主机节点之间的通讯都是通过无线网络传输的,所以在Ad Hoc网络中的无线通讯带宽有限。
动态变化:由于Ad Hoc网络中所有的主机节点是可以移动的,主机之间的关系会不断发生变化,所以网络的主机节点是动态变化的。
独立性:Ad Hoc网络最大的特点就是不依赖现有的网络通信设施,具有一定的独立性,适合灾难救助、偏远地区通信等应用。
主机能源有限:由于在网络中的主机都是移动式的,如便携计算机、pad等,这些主机的能源主要由电池提供,因此Ad Hoc网络有能源有限的特点。
分布式特性:在Ad Hoc网络中没有中心控制节点,主机通过分布式协议互联。一旦网络的某个或某些节点发生故障,其余的节点仍然能够正常工作。
物理安全有限:Ad Hoc网络的分布式特性相对于集中式的网络具有一定的抗毁性。
生存周期短:Ad Hoc网络主要用于临时的通信需求,相对与有线网络,它的生存时间一般比较短。
4 蚁群算法应用到网络路由算法
在网络路由处理中,网络的流量分布不断变化,网络链路或结点也会随机地失效或重新加入。蚁群的自身催化与正向反馈机制正好符合了这类问题的求解特点,因而,蚁群算法在网络领域得到一定应用。蚁群觅食行为所呈现出的并行与分布特性使得算法特别适合于并行化处理。因而,实现算法的并行化执行对于大量复杂的实际应用问题的求解来说是极具潜力的。
设网络中有四个节点1,2,3,4。要实现1和4之间的通信,由于无线网络通讯距离有限或者延迟方面的限制,1和4之间无法直接进行通信,但是它们可以借助2和3进行通讯转发,但是借助2和3通讯会有2条通信支路:1-2-4和1-3-4,这两条通讯支路的长度是不同的,如图2所示。
我们应用蚁群算法的思路,假设在节点1有两只蚂蚁,蚂蚁A和B由节点1向节点4爬行,而与此同时,在节点4处也有两只蚂蚁,正在向节点1爬行。由于最开始,在2和3两条路上的信息素是不存在的,所以蚂蚁选择两条路的概率是相同的。我们假设蚂蚁A和蚂蚁C按照1-2-4和4-2-1的路线爬行,蚂蚁B和D按照1-3-4和4-3-1的路线爬行。假设蚂蚁行进的速度近似相同,一段时间之后蚂蚁B和蚂蚁D经过支路1-3-4和4-3-1的路线分别到达节点1和节点2,而蚂蚁A和蚂蚁C依然还在1-2-4和4-2-1的路线中,如图3所示。
在蚂蚁行进的过程中,每个蚂蚁均留下了同样数量信息素的痕迹。这时路线1-3-4上留下的信息素明显要高于路线1-2-4上的信息素浓度,如果之后还有其他蚂蚁需要从1到达4节点时,受信息素的诱导,选择1-3-4的概率很大。一段时间后,选择走路线1-3-4的蚂蚁会越来越多,而选择走1-2-4的蚂蚁会越来越少,最后呈现较强信息素痕迹的那些支路会变成形成一条从节点1到节点4的最短路径。
5 结束语
由于蚁群算法的各种特点与Ad hoc网络中的场景非常类似,使其在这方面的应用非常成功。随着蚁群算法的不断改进和各种技术领域的不断发展,蚁群算法的应用进展以蚁群算法为代表的蚁群智能已成为当今分布式人工智能研究的一个热点,许多源于蜂群和蚁群模型设计的算法己越来越多地被应用于企业的运转模式的研究,该算法还被用于求解Job-Shop调度问题、二次指派问题以及多维背包问题等。
参考文献
[1]詹士昌,徐婕,吴俊.蚁群算法中有关算法参数的最优选择[J].科技通报,2003年05期.
[2]胡小兵,黄席樾.对一类带聚类特征TSP问题的蚁群算法求解[J].系统仿真学报,2004年12期.
[3]周四望等.无线传感器网络中基于数据融合的移动代理曲线动态路由算法研究[J].计算机学报,2007.30(6):894-904.
[4]王开义,赵春江,胥桂仙,宋晓宇.GIS领域最短路径搜索问题的一种高效实现[J].中国图象图形学报.
[5]冀俊忠,黄振,刘椿年.基于聚类和分段优化的蚁群算法[J].北京工业大学学报,2008年04期.
[6]徐京,张彦,辛阳等.高速网络内容监控系统的关键技术分析.信息网络安全,2012(10)29-35.