蚁群算法中参数设置的研究

第22卷第1期2008年1月山东理工大学学报(自然科学版)

JournalofShandongUniversityofTechnology(NaturalScienceEdition)Vol.22No.1Jan.2008

文章编号:1672-6197(2008)01-0007-05

蚁群算法中参数设置的研究

徐红梅,陈义保,刘加光,王燕涛

(烟台大学机电汽车工程学院,山东烟台264005)

摘　要:蚁群算法是一种新的随机优化算法,它利用人工蚂蚁在其途经路上释放信息素寻优,体现了正反馈、分布式、多anent协同性和并行性等特点,蚁群算法中的各参数对计算结果有很大影响.介绍了蚁群算法原理和模型(以TSP问题为例),对基本蚁群算法参数的合理选取进行了实验分析,给出了算法参数选取的基本原则,.关键词:蚁群算法;信息素;组合优化;旅行商问题中图分类号:TP301.6Thetheantcolonyalgorithm

XU2,CHENYi2bao,LIUJia2guang,WANGYan2tao

(SchoolofElectromechanicalAutomobileEngineering,YantaiUniversity,Yantai264005,China)

Abstract:AntColonyAlgorithmisanewstochasticoptimizationalgorithmusingartificialantsre2leasingpheromoneonthepath,characterizedwithapositivefeedback,distributedcomputation,multi2agentsynergyandparallelalgorithm.Theparametershaveanimportantroleintheresultofantcolonyalgorithm.TheprincipleandmodelofAntColonyAlgorithmwereintroducedandrea2sonableexperimentswerecarriedoutontheparametersofthisalgorithm,includingbasicprinciplesfortheparameterselection,whicharebeneficialtotheapplicationanddevelopmentoftheantcolonyalgorithminoptimizationproblems.

Keywords:antcolonyalgorithm;pheromone;combinatorialoptimization;TSP(travelingsalesmanproblem)

　　群智能理论的基本原理源于生物社会系统(biologysocialsystem)[1],是由简单个体组成的群落与环境以及个体之间的互动行为,这种生物社会性的模拟系统利用局部信息产生难以估量的群体行为.群智能理论研究的典型算法是蚁群算法(antcolonyalgorithm)和粒子群算法(particle

swarmoptimization,PSO).蚁群算法是由意大

利学者Dorigo.M等人于20世纪90年代初提出的一种新型的模拟进化算法[2],该算法采用了正反馈并行自催化机制,易于与其他方法结合,而且具有较强的鲁棒性[3],在解决许多复杂优化问题方面已经展现出其优异的性能和巨大的发展潜

收稿日期:2007209210

基金项目:国家自然科学基金资助项目(50465001);山东省中青年科学家奖励基金(2006BS05008)作者简介:徐红梅(19822),女,硕士研究生.

8山东理工大学学报(自然科学版)2008年　

力.蚁群算法最早成功应用于解决著名的旅行商问题,并且取得了较优的解[4],但进化速度慢,易陷入局部最优是其最主要的缺点.本文通过多组实验对其参数设置进行了研究,并提出了如何通过设定参数进一步改善求解.蚁组成的集体行为便表现出一种信息正反馈现象:某一路径上走过的蚂蚁越多

,则后来者选择该路径的概率就越大.

以图1为例说明蚁群系统的工作原理[2].在图1(a)中,从Nest(巢穴)到Food(食物源)的路径上存在着觅食的蚂蚁,忽然某一时刻路径上出现了一个Obstacle(障碍物),将单一的路径分为两条长短不等的路径,如图1(b)所示.此时走到分叉路口的蚂蚁必须对前进的方向做出选择,而影响蚂蚁选择的因素是路径上的信息素浓度,浓度越高的路径蚂蚁选择它的概率就越大.初始时刻,因为所有路径上均没有信息素,蚂蚁随机选择路径,如图1(c)所示.但由于上方的路径比下方的路径短,,此时上方路径的信,这将影响由食物源返,它们会以较大的概率选择,随着时间的推移,大部分的蚂蚁会沿此路径觅食,如图1(d)所示.

1　蚁群优化算法

1.1　基本算法原理

自然界中蚁群觅食要经若干条路径从蚁穴到达食物源,但是最终所有的蚂蚁选择了一条最短的路径进行觅食.蚁群算法就是模拟自然界中蚂蚁觅食行为而提出的一种模拟进化优化算法.它采用有记忆的人工蚂蚁,蚂蚁会在所经过的路径上留下一种挥发性分泌物(pheromone,以下称为信息素),信息素随着时间的推移会逐渐挥发消失.其强度,

.(a)　　　　　　　　　　　　　　　　　　　　(b)

(c)　　　　　　　　　　　　　　　　　　　　(d)

图1　蚂蚁觅食示意图

1.2　基本AS模型算法=1,2,…,n)在运动过程中,根据各条路径上的

k

(t)表示在t时刻信息素的浓度决定转移方向,pij

以平面上n个城市的TSP问题为例说明基本蚁群算法模型.n个城市的TSP问题就是指旅行商按一定的顺序访问n个城市中的每个城市,使得每个城市都能被访问且仅能被访问一次,最后回到起点,而使花费的代价最小,即最短路径.

为模拟实际蚂蚁的行为引入如下记号:设m是蚁群中蚂蚁的数量,dij(i,j,…,n)表示城市i

和城市j之间的距离,τij(t)表示t时刻在城市i和城市j连线信息素.初始时刻,各条路径上信息素的浓度相同,设τij(0)=C(C为常数).蚂蚁k(k

蚂蚁k从城市i转移到城市j的概率;tabuk(k=1,2,…,n)为蚂蚁k已走过城市的集合,开始时

tabuk中只有一个元素,即蚂蚁k的出发城市,随

着搜索的进行,tabuk中的元素不断增加.ηij为启发性因子,这里为路径的能见度,即1/dij,dij为城

市i到j的欧氏距离;α为信息启发因子,表示轨迹的相对重要性;β为期望启发因子,表示能见度的相对重要性.s为蚂蚁k下一步允许选择的城市集合中的城市;alloweddk表示蚂蚁k下一步允许选择的城市.pkij(t)计算公式为

第1期　　　　　　　　　　　　　　　徐红梅,等:蚁群算法中参数设置的研究9

(1)

p(t)=k

ij

s<alloweddk

∑

αβ

ηαβ

[τ[ηis(t)] is(t)]

,若j∈allowedk

0,　　　　　　　　　　　　否则

　　为了避免残留信息素过多引起残留信息淹

没启发信息,在每只蚂蚁走完一步或者完成对所有n个城市的遍历(也即一个循环结束)后,要对路径上信息素的浓度根据(2)式更新.

τ) τtij(t)ij(t+n)=(1-ρij(t)+Δ

m(2)

k

Δτij(t)=∑Δτij(t)

k=1

法的搜索空间尽可能的大,以寻找那些可能存在

最优解的解区间;同时,又要充分利用蚂蚁群体内当前所具有的有效信息,使得蚁群算法搜索的侧重点放在那些可能具有较高适应值的个体所在的区间内,从而以较大的概率收敛到全局最优解[526].本文以eil51TSP为例,利用Ant2Cycle模型研究参数对最优路径的影响.实验时,设m=32,α=1,β=4,ρ=0.5,Q=100,迭代次数为1000,采用依次改变各参数,其余的用默认设置,每个参数计算20次

,.2.1ρ表示信息素挥发系数,1-ρ表示信息素残留式中,

ρ<[0,1);Δτ因子,ij(t)表示本次循环中路径(i,j)

k

τΔτ上的信息素增量,初始时刻Δij(0)=0;ij表示第

k只蚂蚁在本次循环中留在路径(i,j)上的信息量.

M.Dorigo曾给出3种不同的模型[1],分别称之为AntCycleSystem,AntQuantitySystem,AntDensity

kτSystem,它们的差别在于Δij在Ant2Cycle模型中:

kΔτij(t)=

,若第k(i,j)Lk

,它是通7,蚁群算法的全局搜索能力及算法的稳定性越强,但是蚂蚁数目过多时,会使大量曾被搜索过的路径上的信息素的变化趋于平均,信息正反馈作用减弱,虽然全局搜索的随机性加强,但收敛速度变慢;反之,蚂蚁数目过少时,特别是对于规模较大的问题时,使得那些从未被搜索到 …… 此处隐藏：5405字，全部文档内容请下载后查看。喜欢就下载吧 ……