蚁群优化算法研究综述
一I
IIR'I'IHII_IIIIIII
-Review.Prospect《园陵—圆圆
蚁群优化算法研究综述
ResearchProgressofAntColonyOptimization
Algorithm
梅红李俊卿
(山东理工大学农业工程与食品科学学院,山东淄博255049)
摘要:介绍了蚁群优化算法的基本原理、流程和研究现状,重点评述了近年来蚁群优化算法在组合优化和
连续优化两个领域的研究现状,并展望了这一领域的研究方向。
关键词:蚁群优化算法组合优化连续优化
Abstract:Thispaperintroducesthebasicprinciple,procedureandcurrentsituationofantcolonyoptimizationalgorithm,emphasizes
on
thecurrentsituationofantcolonyoptimizationalgorithminthefieldsofcombinatorialand
continuouseoptimization.Furthermore,researchtendenciesinthisfieldarediscussed.
Keywords:antcolonyoptimizationalgorithm
combinatorialoptimization
continuouseoptimization
0引言尤其是蚂蚁的觅食行为,蚂蚁能够在较短的时间内寻找从蚁巢到食物源的最短路径。人们研究发现,蚂蚁在寻找食物的过程中,会随机搜索邻近的区域,一旦发现了食物源,蚂蚁将一部分食物带回蚁巢,同时,蚂蚁会在走过的路径上散发信息素。路径越短,散发的信息素越多,后来者选择该路径的概率就越大。于是,在信启、素的帮助下,蚂蚁问形成了一种间接的信息交流,很快就会搜寻到最短的路径上来。蚂蚁个体之间就是通过这种信息的交流来寻找从蚁巢到食物源的最短路径。蚁群算法本质上是进化算法中的一种新型随机性优化算法。该算法通过构造人工蚂蚁来模拟真实蚂蚁的行为,进行优化运算。但是,人工蚂蚁与真实蚂蚁也存在着以下不同之处:(1)人工蚂蚁有视觉;(2)人工蚂蚁有记忆能力;(3)人工蚂蚁生活在时间离散的环境中。相同之处在于蚂蚁都是通过协作搜寻最短路径以及都具有正反馈的特点。
1.2蚁群优化算法的两个主要部分
(1)信息素的更新信息素在算法中起着非常重
群智能足处理问题的一种新的方法,它源自于对昆虫及其他动物行为的模拟。其中研究最多,应用最成功的就是蚁群优化算法(ant
colonyoptimalalgorithm,
ACOA)。蚁群算法是一种随机搜索算法,同时,也是一。种新型的模拟进化算法,具有鲁棒性强、分布计算、并行性、信息正反馈、启发式智能搜索,以及易于与其他方法结合的特征,具有很强的发现较好解的能力。在求解节点树为5—100的组合优化问题上,选用合适的参数,其优化结果普遍好于遗传算法、进化算法和模拟退火算法…。1蚁群优化算法
1.1蚁群优化算法的基本原理
蚁群算法是由意大利学者M.Dorigo于20世纪90年代首次提出的,它是对真实蚂蚁群体觅食行为的模拟。蚂蚁是一类个体行为极其简单的昆虫,单个蚂蚁的行为带有随机性,但是由这些简单的个体所组成的蚁群却体现出极大的智能,能够完成相当复杂的任务。
梅红1974年生.女,博士生。主要研究方向为机器人动力学及智能控制。
2010.”I机电一体化13
万方数据
蚁群优化算法研究综述iIIIiIIiII
iiiiiiiiiiiiiiiiiiiiiiiiiiii萄iiiiii甬
要的作用,它能够引导蚂蚁选择质蹙好的路径,并为蚂蚁之间提供信息交流的渠道。每当蚂蚁的路径构建完毕,都要进行信息素的更新。一方面,要根据路径的长短增加信息素的数黾;另一方面,信息素也会随着时间挥发掉一部分,这样可以避免路径过早收敛。挥发同时也意味着遗忘,能够引导蚂蚁搜索新的区域。信息素的更新可以采取不同的方式。
(2)路径的构建
人工蚂蚁在信息素的帮助下,
根据概率原则进行解的构建。路径上的信息素越多,该路径被选择的概率就会越大。1.3基本蚁群算法的流程
(1)初始化包括算法参数和信息素矩阵的初始化,记录程序进行的统计信息变最的初始化以及蚂蚁路径的初始化等。开始的时候,所有的路径上都没有信息素,每一条路径被选择的概率都是一样的。因此,蚂蚁路径的初始化是随机的。
(2)质量评估计算所有蚂蚁选择的路径所对应的目标函数,评估路径的质鼍。路径越长,质鼍越差。
(3)信息素的更新根据路径的质量决定每一条路径上应散发的信息素,以增加高质镑的解被选中的概率,同时挥发掉一部分信息素,扩大搜索的范围,避免过快的收敛。信息素对算法的长远影响就是逐渐减少搜索空问的规模,使搜索的范围缩小到少数有潜力的路径上。
(4)路径选择每一次迭代的开始,蚂蚁的记忆首先被清空,然后根据路径上的信息素,利用概率选择机制分别重新构建自己的路径。蚂蚁以并行的方式构建解。
由步骤(2)至步骤(4)反复循环,终止条件可以满足以下任意一个:(1)算法找到的解与最优解的误差已经满足实际要求;(2)迭代次数达到最大值;(3)算法陷入停滞状态。
2组合优化问题的蚁群算法研究现状
蚁群算法是蚂蚁系统的改进形式,其最突出的特点就是提出了局部信,自、素更新。最初是以解决组合优化问题为主要目的。组合优化问题,顾名思义,就是寻找离散变最的最优组合。蚁群算法通过蚂蚁之间的合作来寻找这些变最取值的最佳组合。组合优化的问题
(s、,、力)可以定义为¨。:
14机电一体化I2010.”
万方数据
(1)一个离散变量的集合S,其中变量置对应的值满足菇,EDf={d:,d:,…,d‘ID。【},f=l,…,n;
(2)一个变量之间的约束条件集合力;(3)一个有待求出最小值的目标函数,;’
(4)一个由所有可能的可行分配组成的集合:J={5={(xf,菇I),…,(X。,茗。)}I茗i∈Di,s满足所有的约束}。如果对Vs∈_,,问题的解s‘∈_,
都满足以s’)≤.厂(s),那么就称s‘为全局最优解。全
局最优解的集合记为.,’,显然有厂∈_,。求解最优化问题就是寻找到一个解s’∈,‘。
在现实生活中,蚁群算法已经很成功地应用到旅行商、joh.shop调度问题、指派问题、序列求序、车辆路径问题、大规模集成电路综合布线等问题中。
虽然蚁群算法有许多优点,但是,这种算法也存在一砦缺陷,包括:(1)与其他方法相比,该算法一般需要较长的搜索时间;(2)算法容易出现停滞现象;(3)许多参数的设置凭借经验,没有充足的依据等。为了克服这些缺陷,人们提出了多种改进算法。文献[3]分析了应用蚁群算法求解实际问题时易产生的几个误区,分析了产生这些误区的原因,并提出了相应的对策。文献[4]在蚁群算法中吸收了微粒群算法的精华思想,提出了一种能够避免过早收敛的改进算法。文献[5]针对蚁群算法收敛慢、耗费时间的缺点,在使用蚁群算法解决较大规模的TSP问题时,对系统的初始化提出了新的方法,并通过实验对参数的设置提供比较精确的组合方式。文献[6]将蚁群算法与遗传算
法结合,算法同时兼具了基本蚁群算法和遗传算法的
优点,可以提高解的搜索效率。文献[7]在蚁群算法的基础上,引入变异运算,并且对蚁群算法的全局和局部更新规则进行改进,显著地降低r因蚁群算法陷入局部极小而可能导致系统出现的停滞现象。另外,传统
的蚁群算法中只有一个蚁群,没有充分挖掘蚁群算法
的并行性本质以及分布式计算等优良特性,而多重蚁群算法由几个蚁群来协同解决问题,引入了群体层的交互作用,从而更加有效地解决问题,同时保持了蚁群在搜索过程中的多样性。
3连续优化问题的蚁群算法研究现状
在现实生活中,许多问题不属于组合优化,而属于连续优化的范畴。连续优化的模型与组合优化类似,
—。11—IlL—i赢丽iIiII蕊IIIIIIiIiiII商————..——.—...—i.iiiiiiiii
Review.Prospect
i囝匿■圜团
只不过将变量的取值范围从一个离散的空间扩展到一个连续的空间,但是,这同时也意味着每一个变虽可以取无穷多个值,大大增加了求解的难度。优化的目标就是从每一个连续变最的取值范围内寻找一个最优值,形成最优组合。蚁群算法在组合优化的领域已经比较成熟,而在连续优化领域的研究则比较弱。自从蚁群算法被提出以来,人们就试图将蚁群算法用于连续问题的优化。蚁群算法用于连续问题的优化主要存在两种思路:基于连续区域离散化的蚁群连续优化算法和基于连续的信,窟、素和概率分布函数的蚁群连续优化算法。第二种思路更接近于连续优化的本质。
3.1基于连续区域离散化的蚁群连续优化3.1.1
网格法
网格法的思路为:首先根据问题的性质估计一下最优解的范罔,估计出各变鼍的取值范围。然而在变量区域内打网格,在网格点上求约束函数与目标函数的值,对于满足约束条件的点,再比较其目标函数的大小,从中选择小者,并把该网格点作为一次迭代的结果。最后在求出的点附近将分点加密,再打网格,并重复前述计算与比较,直到网格的间距小于预先给定的
精度后终止迭代。文献[8]采用了网格法解决连续空间优化问题的同时,构造了一个与蚁群转移概率相关
的评价函数。
3.1.2蚁群算法与遗传算法相结合
许多文献将蚁群算法与遗传算法相结合,将蚁群算法的应用范围从离散的区间拓展到连续区间。其中,文献[9]将蚁群优化算法与遗传算法相结合,对解的每一个分量的可能取值组成一个动态的候选组,并对候选组中的每一个值记录其信息最。在蚁群算法的每一次迭代中,首先根据信息最选择解分最的初值,然后使用交叉、变异操作来确定解的值。文献[10]将遗传算法与蚁群算法相结合,在蚁群算法中引入交叉与变异,将改进的蚁群算法引入到前向神经网络的优化训练中来,建立了基于该算法的前向神经网络训练模型。
3.1.3
其他算法
文献[11]提出了一种自适应蚁群算法。该算法提出了基于新的目标函数的信息素分配方案。文献[12]使用离散的点来近似表示连续函数的自变量,通过按
万方数据
特定规则运行的蚁群算法来求解。文献[13]在蚁群优化算法中融入了演化算法的种群与操作功能。3.2基于信息素和概率分布函数的蚁群连续优化
在组合优化的问题中,每一个待优化的参数都是由有限个离散的值组成,利用矩阵来存储所有参数值的信息素和概率。但是,在连续优化的问题中,解空间是以区域性方式表示,而不是以离散的点集方式表示。与之相对应,信息素和概率分布也应该是连续的,不能够采用矩阵的形式来存储。文献[14]提出了一种连续的草帽型的信息黾分布函数,并将其用于多极值连续函数寻优和非线性连续函数寻优。文献[15]提出了基于改进的高斯函数的概率密度函数,利用蚂蚁搜索到的解直接更新概率密度函数,引导蚂蚁进一步搜索。文献[16]提出蚁群算法求解连续空间优化问题的搜索策略,包括局部搜索、全局搜索和信息素强度更新规则。在全局搜索过程中,利用信息素强度和启发式函数确定蚂蚁移动方向;在局部搜索过程中,嵌入了确定性搜索以改善随机性搜索算法存在的缺陷,增强寻优性能,加快收敛速率。文献[14]提出在连续空间寻优蚁群算法与离散空间寻优蚁群算法之问,至少应有蚁群信息肇留存方式、蚁群在解空间中的寻优方式和蚁群行进策略三方面的不同。文献[17]提出了一种全新的由侦察蚁和觅食蚁协作搜索的快速连续蚁群算法。本文介绍了算法的基本原理和流程,并就算法在组合优化和连续优化两个应用领域的研究现状进行了综述。蚁群算法源自于对蚂蚁真实觅食行为的模仿,具有很强的鲁棒性、分布式计算以及易于与其他启发式算法结合的优点。理论研究和实际应用的实践表明了它是一种很有前途的仿生优化算法。作为一个前沿外研究者的关注。
由于蚁群算法的研究起步较晚,不像其他启发式多学者都在致力于对蚁群算法的研究和改进。目前该I下转第鲳页)
2010.1I
J机电一体化15
3.3基于改进搜索策略的蚁群连续优化
4结语
性的热点研究领域,蚁群算法正在引起越来越多国内算法那样已有系统的分析方法和坚实的数学基础,许
算法还有~些问题需要进一步研究和解决,主要体现在:(1)进一步提高算法的收敛速度;(2)对算法的收
微段加工柔性加减速算法研究
5结语
本文根据微段的加工特点,提出了微段加工的方法,根据方法的需要建立了两个微段加工模型。该方法保证了加速度连续,实现了柔性加工,且无需对减速点进行预测,从而提高了加工效率。
【3J
JeonJ
W,Hay
Y・A
generalized
of
industrial
approach
robots
on
forand
theCNC
accelerationdeceleration
眦chinet0018[J]・IEEE
TransactionsIndustrial
E18。啪nies,2000,47(1):133—139・
【4]Kaan
Jerk
E,YusufA・Highlimited
8p。。dcNc8y828mdesign・Part1:
generation
and
quintic
spline
trajectory
interpolation[J].InternationalJournal
ofMachineToolsand
参考文献
[1]
胡建华,廖文和,周儒荣・CNC系统中几种升降速控制曲线的研究与比较[J]・南京航空航天大学学报,1999,31(6):706—711.
[5]
Manufacture.200I,41(2):1323—1345.
NamS
H,Y鲫gMY.A8tudy
ona
genemlizedpammetric
interpolatorwithComputer-Aided
real—timejerk.1imitedacceleration『J1.
Design,2004,36(1):27—36.
[2]
KimD
I,Jeo“J
w,Kim
for
in
s・s。fiwaredustrial
acc8lerati。n/
and
CNC
[6]
王宇晗,肖凌剑,曾水生,等.小线段高速加工速度衔接数学模型[J].上海交通大学学报,2004,6.
d。。。l。rati。“methodsmhots
(上接第15页)
敛性进行理论研究;(3)能够解决的问题范罔仍有待扩展,包括动态优化、随机优化以及多目标优化;(4)系统的分析方法和数学基础,参数选取标准等;(5)蚁群算法与其他算法的互补性研究;(6)进一步加强算法在连续优化问题领域的研究。相信随着人们对
[10][9][8]
段海滨,马冠军,王道波,等.一种求解连续空间优化问题的改进蚁群算法[J].系统仿真学报,2007,19(5):
974—977.
陈峻,沈洁,秦玲.蚁群算法进行连续参数优化的新途径[J].系统工程理论与实践,2003(3):48—53.
王晶.蚁群算法优化前向神经网络的一种方法[J].计算机工程与应用,2006,25:53—55.
Li
仿生智能系统理论及应用研究的不断深入,蚁群算法这一新兴的仿生优化算法必将展现出强大的生命力和广阔的发展前景。
Yah・jun.wuTie・jun.An
adaptive
ant
colonysystem
algorithmforcontinuous。——spaceoptimization
problems
[J].JournalofZhejiang
UniversitySCIENCE,2003,4(1):
参考文献
李士勇.蚁群算法及其应用[M].哈尔滨:哈尔滨工业大学出版社。2004:1—2.
[2]
Dorigo
加一46.
[12]
陈烨.用于连续函数优化的蚁群算法[J].四川大学学报:工程科学版,2004,36(6):117一120.
[13]
程志刚,陈德钊,吴晓华.连续蚁群优化算法的研究[J].浙江大学学报:工学版,2005,39(8):1147一1151.
[14]
汪镭,吴启迪.蚁群算法在连续空间寻优问题求解中的应用[J].控制与决策,2003,18(1):45—48.
[15]
SochaK,DorigoM.Ant
colonyoptimizationforcontinuous
M,STUTZLET.蚁群优化[M].张军,胡晓敏,罗旭
耀,等译.北京:清华大学出版社,2007:203.
[3]
徐精明,曹先彬,王煦法.蚁群算法求解问题时易产生的误区及对策[J].计算机工程,2004,30(16):25—27.
[4]
张听,彭宏,郑肩伦.一种改进的蚁群算法[J].哈尔滨工程大学学报,2006,增刊:519—523.
[5]
吴春明,陈冶,姜明.蚁群算法中系统初始化及系统参数的研究[J].电子学报,2006,34(8):1531--1534.
[6]
张静乐,王世卿,王乐.具有新型遗传特征的蚁群算法【J].人工智能,2006,22(2):261—263.
[7]
马骏,张健沛,杨静,等.改进酗蚁群算法求解旅行Agent
[17][16]
domains[J].Eur.J.Oper.Res.(2006),doi:10.1016/j.
ejor.2006.06.046.
杨勇,宋晓峰,王建飞,等.蚁群算法求解连续空间优化问题[J].控制与决策,2003,18(5):573—576.
马卫,朱庆保.求解函数优化问题的快速连续蚁群算法[J].电子学报,2008,36(11):2120--2124.
问题[J].北京邮电大学学报,2008,31(6):46—9.
38机电一体化I2010.11
万方数据
蚁群优化算法研究综述
作者:作者单位:刊名:英文刊名:年,卷(期):
梅红, 李俊卿
山东理工大学,农业工程与食品科学学院,山东,淄博,255049机电一体化MECHATRONICS2010,16(11)
参考文献(17条)
1.李士勇 蚁群算法及其应用 2004
2.Dorigo M;ST(U)TZLE T;张军;胡晓敏,罗旭耀 蚁群优化 2007
3.徐精明;曹先彬;王煦法 蚁群算法求解问题时易产生的误区及对策[期刊论文]-计算机工程 2004(16)4.张昕;彭宏;郑肩伦 一种改进的蚁群算法[期刊论文]-哈尔滨工程大学学报 2006(z1)5.吴春明;陈冶;姜明 蚁群算法中系统初始化及系统参数的研究[期刊论文]-电子学报 2006(08)6.张静乐;王世卿;王乐 具有新型遗传特征的蚁群算法[期刊论文]-人工智能 2006(02)
7.马骏;张健沛;杨静 改进型蚁群算法求解旅行Agent 问题[期刊论文]-北京邮电大学学报 2008(06)8.段海滨;马冠军;王道波 一种求解连续空间优化问题的改进蚁群算法[期刊论文]-系统仿真学报 2007(05)9.陈峻;沈洁;秦玲 蚁群算法进行连续参数优化的新途径[期刊论文]-系统工程理论与实践 2003(03)10.王晶 蚁群算法优化前向神经网络的一种方法[期刊论文]-计算机工程与应用 2006(25)
11.Li Yan-jun;wu Tie-jun An adaptive ant colony system algorithm for continuous-space optimizationproblems[期刊论文]-Journal of Zhejiang University(Science Edition) 2003(01)12.陈烨 用于连续函数优化的蚁群算法[期刊论文]-四川大学学报(工程科学版) 2004(06)13.程志刚;陈德钊;吴晓华 连续蚁群优化算法的研究[期刊论文]-浙江大学学报(工学版) 2005(08)14.汪镭;吴启迪 蚁群算法在连续空间寻优问题求解中的应用[期刊论文]-控制与决策 2003(01)15.Socha K;Dorigo M Ant colony optimization for continuous domains[外文期刊] 2006(3)16.杨勇;宋晓峰;王建飞 蚁群算法求解连续空间优化问题[期刊论文]-控制与决策 2003(05)17.马卫;朱庆保 求解函数优化问题的快速连续蚁群算法[期刊论文]-电子学报 2008(11)
本文读者也读过(2条)
1. 李凯齐.刁兴春.曹建军.LI Kai-qi.DIAO Xing-chun.CAO Jian-jun 蚁群优化算法在求解随机组合优化问题中的应用综述[期刊论文]-计算机应用研究2010,27(12)
2. 朱庆保.ZHU Qing-bao 蚁群优化算法的收敛性分析[期刊论文]-控制与决策2006,21(7)
本文链接:http://d.wanfangdata.com.cn/Periodical_jdyth201011002.aspx