文档网

一种改进蚂蚁算法的MATLAB仿真

132

ACADEMICRESEARCH

学术研究

一种改进蚂蚁算法的MATLAB仿真

田紫君1赵梦晗2

(1.北京联合大学北京100101:2.北京联合大学北京100101)

摘要:蚂蚁算法是一种新型的模拟进化算法,也是一种随机型智能搜索算法。在介绍了基本蚂蚁算法基础上,针对基本蚂蚁算法存在的计算复杂,易陷入局部最优等缺陷,提出了一种基于信息熵的自适应改进蚂蚁算法,信息熵来度量蚂蚁系统的复杂性,用均值熵调节算法的系数使算法实现自适应。经MATLAB仿真试验结果表明,改进的算法有较好的收敛性、稳定性,优于基本蚂蚁算法。

关键词:蚂蚁算法;自适应;仿真

1.引言

蚂蚁算法是由Dorigo等…提出的解决组合优化问题的一种多agent方法。1992年,Dorigo在他的博士论文中用蚂蚁算法解决经典的离散组合优化问题中的旅行商问题(TSP)、二次分配问题(QAP)等,并得出了理想的结论。蚂蚁算法因其很强的鲁棒性、分布式的计算和比较容易与其他算法工具相结合的优点而越来越受到人们的关注。把它在TSP问题中的经典原型经过少量改动就可以在很多情况下应用。例如:几乎不用对蚂蚁算法作任何改动就可以解决非对称TSP问题《ATSP)ⅢJ:在TSP蚂蚁算法的基础上对瓦(f)的定义稍作改动,用最长加工时间代替tI,就可以解决车间调度问题(JSP)。蚂蚁算法在解决其他如二次分配(QAP)瞄J、作业排序I引、图形着色【bJ等问题上均有出色的表现。蚂蚁算法的传统应用主要集中在离散优化领域。近年来,蚂蚁算法的应用范围已经扩大到连续问题的求解:Bilchev和Parmee等Ibl把蚂蚁算法的应用引入工程设计领域iWangLei和WuQidil71用蚂蚁算法求解线性系统优化问题和一维函数最值问题;ChenLing和ShengJie等Ⅲ1利用蚂蚁算法求解非线性规划问题也是很有意义的尝试。

同时很多学者又提出了改进的蚂蚁算法。如试图将蚂蚁算法与Q一学习算法相结合I构Ant—Q算法憎J。Stc】tzle和HoosIl训提出的最大一最小蚂蚁算{MAX—MINAntSystem,MMAS)。Bullnheimer,Hartl和Strauss¨”提出的ASrank对经典蚂蚁算法

(AntSystem:AS)中按照蚂蚁寻优路径的长短划分级别,实

上信息量相等,设t。(o)=c(c为常数),蚂蚁七岱=1,2,…,m)

在运动过程中,根据各条路径上信息量决定移动方向,p:O)表

示在t时刻蚂蚁由位置i转移到位置J的概率,

咖J揣小%㈩

p;:{D:T1埘圹”‘(1)

J‘Ⅵ

【o,otherwise

其中,%=如,l,…,疗一1}-tabuI表示蚂蚁k下一步允许选择的城市。人工蚁用tabut伍=1,2,…,m)来记忆目前已走过

的城市。随着时间的推移,以前留下的信息素逐渐消逝,用参数1一P表示信息的消逝程度,经过疗个时刻,蚂蚁完成一个循环,各路径上的信息量根据下式作调整:

‘FO+疗)=P~(f)+△‘F(2)

其中,缸Ⅳ=∑缸;,缸;表示第七只蚂蚁在本次循环中

留在路径扩上的信息量,缸。表示本次循环中留在路径{『上的信息量。

缸;:层蚂蚍本循环经勘(3)

Io,否则

其中,Q为常数,厶表示第只蚂蚁在本次循环中所走路径的长度。在初始时刻,tⅣ(O)=C(const),

△fH=0,其中,

i,J=O,l,…,/11一l。Ⅱ,p分别表示蚂蚁运动过程中所积累的信息及启发因子在路径选择中所起的作用。t1F表示由城市f转

行不同的信息素更新策略。Middendorf和Martinll21提出多群蚂蚁算法,利用多个蚁群并行处理,每完成一次迭代,蚁群之间进行一次信息交换。

MATLAB是MATrixLABoratory的缩写,最初是在1980年由美国的CleveMoler博士研制的。其目的是为线性代数等课程提供一种方便可行的实验手段。由于MATLAB软件提供了可靠的数值运算、图像及图形显示与处理和高水平的图形界面功能,以及与其他高级程序设计语言,如C、FORTRAN等的接口,很快引起了控制理论领域、图像信号处理领域,以及生物医学工程等相关领域研究人员的注意.并用MATLAB软件开发了数以百计的各种应用工具箱,使得MATLAB软件成为控制界研究人员的有力工具。

移到,的期望程度,可据某启发算法确定。据△t:的不同,

M.Dorigo给出了三种模型,分别称为蚂蚁循环系统(antcyclesystem,即上式),蚂蚁数量系统(antquantitysystem(

density

缸;2于)),蚂蚁密度系统(ant

度是一与路径无关的常数Q)。

3.改进蚂蚁算法及其仿真试验

3.1改进蚂蚁算法

system,残留浓

2.基本蚂蚁算法

现以TSP问题求解为例说明基本蚁群算法模型:设m是蚁

群中蚂蚁的个数,以为城市数,以O,J=1,2,…,一)为城市i和

城市,之间的距离,抚O)表示t时刻位于城市f的蚂蚁个数,

m=∑包O),tFO)表示t时刻在f

J连线上残留的信息量,

T1∥为蚂蚁由城市i转移到城市,的期望信息。这一启发式信息

由所解决的问题给出,此问题中,t1。=土。初始时刻,各条路径

dH

用信息熵可以作为系统复杂性的度量。熵(entropy)是简单巨系统的一个基本概念。其最早是在热力学中由克劳修斯提出的,用以描述系统的状态,而后被引入多个领域,从而有了玻尔兹曼(L.Boltzmann)熵、信息熵、概率测度熵。其中,信息熵是由申农(Shannon)将热力学熵引入信息论而提出的,其为不确定方法的一重要概念,常被用于较粗略的给出不确定性的度量。对于离散型随机变量,其信息熵为

万方数据

相关文档
热门文档
你可能喜欢
  • 无线传感网
  • 蚁群算法MATLAB仿真
  • MATLAB仿真论文
  • MATLAB仿真实例
  • MATLAB电路仿真
  • 控制系统仿真
  • 机械工程控制基础实验报告
  • 小世界网络
评论