蚁群算法的基本原理
15页1、2.1蚁群算法的基本原理蚁群优化算法是模拟蚂蚁觅食的原理,设计出的一种群集智能算法。蚂蚁在 觅食过程中能够在其经过的路径上留下一种称之为信息素的物质,并在觅食过程 中能够感知这种物质的强度,并指导自己行动方向,它们总是朝着该物质强度高 的方向移动,因此大量蚂蚁组成的集体觅食就表现为一种对信息素的正反馈现 象。某一条路径越短,路径上经过的蚂蚁越多,其信息素遗留的也就越多,信息 素的浓度也就越高,蚂蚁选择这条路径的几率也就越高,由此构成的正反馈过程, 从而逐渐的逼近最优路径,找到最优路径。蚂蚁在觅食过程时,是以信息素作为媒介而间接进行信息交流,当蚂蚁从食 物源走到蚁穴,或者从蚁穴走到食物源时,都会在经过的路径上释放信息素,从 而形成了一条含有信息素的路径,蚂蚁可以感觉出路径上信息素浓度的大小,并 且以较高的概率选择信息素浓度较高的路径。15 cm(a)/(b)人工蚂蚁的搜索主要包括三种智能行为:(1)蚂蚁的记忆行为。一只蚂蚁搜索过的路径在下次搜索时就不再被该蚂蚁选 择,因此在蚁群算法中建立禁忌表进行模拟。(2)蚂蚁利用信息素进行相互通信。蚂蚁在所选择的路径上会释放一种信息素 的物质,当其他
2、蚂蚁进行路径选择时,会根据路径上的信息素浓度进行选择,这 样信息素就成为蚂蚁之间进行通信的媒介。(3)蚂蚁的集群活动。通过一只蚂蚁的运动很难达到事物源,但整个蚁群进行 搜索就完全不同。当某些路径上通过的蚂蚁越来越多时,路径上留下的信息素数 量也就越多,导致信息素强度增大,蚂蚁选择该路径的概率随之增加,从而进一 步增加该路径的信息素强度,而通过的蚂蚁比较少的路径上的信息素会随着时间 的推移而挥发,从而变得越来越少。蚂蚁系统是最早的蚁群算法。其搜索过程大致如下:在初始时刻,m只蚂蚁随机放置于城市中,各条路径上的信息素初始值相等, 设为:(0)为信息素初始值,可设m,;L,L是由最近邻启发式方法构ij00mm造的路径长度。其次,蚂蚁k(k 1,2, m),按照随机比例规则选择下一步要转移的城市,其选择概率为:pk(t)ijij(t)ij(t) ll dj j, j allowed(t)(t)kisiss allowedk0,否则其中, 为边(i j)上的信息素,1d为从城市i转移到城市j的启发式jij 1 ij因子,allowed为蚂蚁k下一步被允许访问的城市集合。k为了不让蚂蚁选择已经访问
3、过的城市,采用禁忌表tabu来记录蚂蚁k当前k所走过的城市。经过t时刻,所有蚂蚁都完成一次周游,计算每只蚂蚁所走过的路径长度,并保存最短的路径长度,同时,更新各边上的信息素。首先是信息素挥发,其次是蚂蚁在它们所经过的边上释放信息素,其公式如下:(1 ) ,其中 为信息素挥发系数,且01。ijijijmijk1为:kij1d,如果边(i,j)在路径Tk上 ij0,否则3.2)k,其中k是第k只蚂蚁向它经过的边释放的信息素,定义 ijij根据(3.2)可知,蚂蚁构建的路径长度d越小,则路径上各条边就会获得 ij 更多的信息素,则在以后的迭代中就更有可能被其他的蚂蚁选择。蚂蚁完成一次循环后,清空禁忌表,重新回到初始城市,准备下一次周游。 大量的仿真实验发现,蚂蚁系统在解决小规模TSP问题时性能尚可,能较 快的发现最优解,但随着测试问题规模的扩大,AS算法的性能下降的比较严重, 容易出现停滞现象。因此,出现了大量的针对其缺点的改进算法。精英蚂蚁系统11是对基本AS算法的第一次改进,它首先由Dorigo等人中 提出,它的设计思想是对算法每次循环之后给予最优路径额外的信息素量。找出 这个解的蚂蚁称
4、为精英蚂蚁。将这条最优路径记为T bs (best-so-far tour十对路径T bs的额外强化是通过 向Tbs中的每一条边增加e/Lbs大小的信息素得到的,其中e是一个参数,它定义 了给予路径Tbs的权值大小,Lbs代表了Tbs的长度。这样相应的信息素的更新公 式如式(3.3):(t 1) (1) (t) m k(t) e bs(t)(3.3)ijijijijk1其中,k (t)的定义方法跟以前的相同,bs (t)的定义则如式(3.4):ijijbs (t)ij0,if (i,j) T bsotherwise3.4)Dorig。等人的文章列举的计算结果表明,使用精英策略并选取一个适当的e值将 使得 AS 算法不但可以得到更好的解,而且能够在更少的迭代次数下得到一些更 好的解。最大景小蚂蚁系统(MM AS MB)是到目前为止解决TSP问题最好的ACO 算法方案之一MM AS算法是在AS算法的基础之上,主要作了如下的改进:(1) 为避免算法过早收敛于局部最优解,将各条路径可能的外激素浓度限制于, ,超出这个范围的值被强制设为 或者是 ,可以有效地避免某条 min max min ma
《蚁群算法的基本原理》由会员鲁**分享,可在线阅读,更多相关《蚁群算法的基本原理》请在金锄头文库上搜索。
河北省南宫市奋飞中学高一数学下学期第三次月考试题
钢结构件加工项目商业计划书写作范文
2021年二年级语文上学期期末考试考点检测浙教版
2023幼儿园母亲节活动策划方案.doc
铜仁市中医药项目融资计划书模板范文
南开大学21春《移动电子商务》离线作业一辅导答案77
企业员工辞职申请书
“计划人生和成才发展”专题团日活动总结
时间名词1时间名词2短语分析
某燃气公司安全运营表格资料汇编
大连理工大学21春《商业银行经营管理》离线作业1辅导答案90
等式的性质 (2)
互联网金融武汉大学毕业论文
感恩节活动方案策划合集15篇
公司准备购入一设备以扩充生产能力
小班优秀教案《吃火锅》
360手表问题汇总
《溶液中的离子反应》专题测试题汇总
采购设备的技术参数及标准配置要求
三年级英语下册LessonWSomanyants练习无答案川教版三起
2022-11-15 14页
2022-11-01 18页
2023-02-04 6页
2023-08-23 3页
2023-02-07 17页
2023-04-18 6页
2023-10-23 17页
2023-05-19 17页
2024-02-24 16页
2023-10-09 16页