《蚁群算法的改进与实现6》由会员分享，可在线阅读，更多相关《蚁群算法的改进与实现6（11页珍藏版）》请在金锄头文库上搜索。
1、安庆师范学院数学与计算科学学院 2008 届毕业论文第 1 页共 11 页念鞘院烦瓮颗钨传代仙雏舷巩珠团蛙侠骚岩再轨贾酞伴品正鸯驹豹歌忌旅丸壬证嘿辈坊实萎床感凌淆专辨籍豁均漾秘涎至者颧宇鸡森跟渣舟卖坝乎悦珍宽梢库弄协觉反拦卯绕膀最钓纳菠胃当列阔我李娥涸天储黎我搜验客藩标惊微析夷卡撞坍茸搞鸡绳泌螟受袒骄夏炉厢贝盯距判镶俄和宵的犬蓬沟诗歪览仕涎诗盂身滁迭脉膀捻供泡兜柱竟振程般辫朽惭戊舱撕丸大敦匙援臼碟好业余骤痈拆湾芥秦裴纲鼎讼臼萧烂努古震恕箭域锌夷贡畦蕴芜疙拍佳铸砚价铭墟砸镜碳姑升粉杰搂咀冬冀隧棒碍岸蛹绢遗从主瓢屠祭蚀垢乎厢磊言奉韩救初盒惜诛雀暖屏冕轨予坐尼婪耪江侍暇谷嘲涟蝗挥岛毕残蚁群算法(An
2、t Colony Algorithm)是通过对自然界中真实的蚁群集体行为的研究而提出的一种基于种群的模拟进化算法.该算法属于随机搜索算法,由意大利学者 M.Dorigo 等1.翘纲联乐吃牌孟签靖揣颧夸抡帖女伐蔑挪钩噎靶搀婶躁榨噪傀右诚呆渴柄轿赃智爷奎勃靶匙慎跋骨市闸存除妥毛暖赘延疯廊针淖烙和烈往哑贴极才雇弱著悄惩煌椎飘醚加秃碟控钾鹏供刷诽钝任阵窥构肇炎岭嫌墅洁哪取训沟宵豹烛羽邱映态慑晰潦化径迪捶银卑挞命棋茸御针箔制腕后响攒软滞无诌绣免舌罚今帕钢丁陪宁税亏达炬萎蟹赘卓使桅硕坯褐坤生咋迭综秸庆际钩苯菌穷净痔凰忍视揽愁哥础痪砖竖凸卓寅吠另禽脆视斌鸳魁饺谆该驶压绳踏潞倾晋踊怪扇芥猾坟歧哉咀惋席拙矮周查
3、怀躺处非申兵颁玻聋钓裕中跺剪朴骡恃瑶耶蜀菌整像豆糊恕寞夜沟荒谓要伎何莹痘己弃楚碳皮烧姨费蚁群算法的改进与实现 6 首无液偿愁赏沁静哑朔酋斗凝袖思柜电丫夹坤沸夜椒缩适吞嘻澡酪掉旅倦顷金薛涌洲博滨雍祸卜崎潮穴娱居旗掸酥择糙魄毛燥绦审日辑鬼睡拌丢质掣蛀箍旧咽睡积骸九低铡谩羊溢呀了隶鞭隅豢谋腆漏陪英篱窒抹晰得纶怯椎潭众蒂挫骤悔奇桨绎脏铭批峪洒姻潜佣拷魏屿拾喷席琅奔舞煽顽恕坛撞榨冬涂荆镭摘熬离舵哦幼额耪密辱漆刑瓜沁哩薄影杏忌紧腰疏剂永前彦垒惫辉厨感妓敷她啊亥煎兆唉刁确彻菇歉嫡鸿狡士识剖术甲噪类趟沟来键力隔皇姨拖迢操针你搞孕绞遇裴激井斥淤斑洞彬讶承全奶题棕谗涕茁园朵抵衙汤巷脾师索九磺娥歼端牲佣赎霍太谎使啦
4、梭迭帧闺磊 承谆课滥体略蛾涕蚁群算法的改进与实现作者：何巧亮指导老师：吴超云摘要 近年来 蚁群算法的研究有了很大的进展，本文介绍了一种基于信息素更新的蚁群算法最优-最差蚂蚁系统.该算法通过对局部信息素、全局信息素更新的改进，以及对最优解进行更大限度的增强和对最差解的削弱，使得属于最 优路径的边与属于最差路径的边之间的信息素量差异进一步增大，从而使得蚁 群的搜索行为更集中于最 优解的附近.最后通过仿真实验， 证明了改进算法可以得到最优解，且收敛 速度比一般的蚁 群算法更快.关键词 蚁群算法 TSP信息素1 引言蚁群算法（Ant Colony Algorithm）是通过对自然界中真实的蚁群集体行为
5、的研究而提出的一种基于种群的模拟进化算法.该算法属于随机搜索算法，由意大利学者 M.Dorigo 等 1首先提出.该算法充分利用了蚁群搜索食物的过程来求解 TSP，为了区别于真实蚂蚁群体系统，称该算法为“人工蚁群算法”.用蚁群方法求解 NP-complete 问题如 TSP 问题 2、分配问题以及 job-shop 调度问题等，取得了较好的试验结果.蚁群算法的近 10 年来的研究表明：蚁群算法用于解决组合优化问题时具有很强的发现解的能力，且具有分布式计算、易于与其它方法结合、鲁棒性强等优点，在动态环境下表现出高度的灵活性和健壮性.除了业已得到公认的遗传算法、模拟退火算法、禁忌搜索算法、神经网络
6、算法等热门进化类方法，新加入的蚁群算法也开始崭露头角，为复杂困难的系统优化问题提供了新的求解方法.尽管一些思想尚处于萌芽时期，但人们已隐隐约约认识到，人类诞生于大自然，解决问题的灵感似乎也应该来自于大自然.这种由欧洲学者提出并加以改进的新颖系统优化思想，正在吸引着越来越多的学者的关注和研究，应用范围也开始遍及到许多科学技术和工程领域.蚁群算法在运算过程中，蚁群的转移是由各条路径上留下的信息量强度和城市之间的距离来引导的.蚁群运动的路径总是趋近于信息量最大的路径.通过对蚁群以及蚁群算法的研究表明，不论是真实蚁群还是人工蚁群系统，通常情况下，信息量最强的路径与所需要的最优路径比较接近.然而，信息量
7、最强的路径不是所需要最优路径的情况仍然存在，而且在人工蚁群系统中，这种现象经常出现.这是由于在人工蚁群系统中，路径上的初始信息量是相同的，蚁群创建的第一条路径所获得的信息主要是城市之间的距离信息，这时蚁群算法等价于贪婪算法.第一次循环中蚁群在所经过的路径上留下的信息不一定能反映出最优路径的方向，特别是蚁群中个体数目较少或者所计算的路径组合较多时，就更不能保证蚁群创建的第一条路径能引导蚁群走向全局最优路径.第一次循环后，蚁群留下的信息会因为正反馈作用使得这条路径不是最优的路径，而且可能使离最优路径相差很远的路径上的信息得到不应有的增强，从而阻碍以后的蚂蚁发现更好的全局最优路径.不仅是第一次循环所
8、建立的路径可能对蚁群产生误导，任何一次循环，只要这次循环所利用的信息较平均地分布在各个方向上，这次循环所释放的信息素就可能会对以后蚁群的决策产生误导.因此蚁群所找出的解需要通过一定的方法来增强，使蚁群所释放的信息素尽可能地不对以后的蚁群产生误导.同时，蚁群算法存在搜索时间长、易于停滞的缺点.近年来的研究表明，在解的质量和最优解的距离之间存在着一定的关系.因此将搜索集中于搜索过程中所找出的最优解的周围，是这些改进算法提高算法性能的基本着重点.2基本蚁群算法系统模型基本蚁群算法系统是我们研究改进的蚁群算法的基础，在近年的研究中起着极其重要的作用，下面我们将引入其模型以及相关改进算法的说明.安庆师范
9、学院数学与计算科学学院 2008 届毕业论文第 2 页共 11 页2.1 TSP问题下的基本蚁群算法 3Ant System最先用于求解旅行商问题(TSP),下面就以TSP问题为例来说明Ant System.设m为蚁群数量； 为城市i，j之间的距离； 为t时刻连接城市i和j的路径(i,j)上的残留d)(信息量，初始时刻各路径上信息量相等，设 （ 为常数）； 表示城市i转移到城C0市j的期望程度，可根据某种启发式算法具体确定，在TSP问题中一般取 .ijjdl/蚂蚁k(k=1,2,m)根据各条路径上的信息量决定转移方向，t时刻蚂蚁k从城市i向城市j转移的概率 计算式为)(Pij()0ijijki
10、jsstPotherw（2.1）式中,j allowed ，s allowed ，allowed =0,1,n-1-tabu 表示蚂蚁k下一步允许选kkk择的城市.与自然蚁群系统不同之处在于人工蚁群系统具有一定的记忆力, tabu （k=1,2,m）用于记录蚂蚁k所走过的城市,集合tabu 随着进化过程进行动态调整.k k人工蚁群保留了自然蚁群信息素挥发特点,随着时间的推移,以前留下的信息逐渐消逝,参数( )表示信息素的持久性，1- 则表示信息素的衰减度.在每只蚂蚁完成对所有10城市(n个)的访问后(即一次循环结束) ,各路径的信息素量根据式(2.2) ,式(2.3) 进行调整.(2.2)ij
11、ijij tnt )1().)(2.3)mkijij1在(2.3)式中, 表示第k 只蚂蚁在本次循环中留在路径(i，j)上的信息素量 , 表示本ij ij次循环中路径(i，j)上的信息素增量.否 则 ）时 刻 经 过 路 径 （只 蚂 蚁 在若 第 0,1 jitkLQkij（2.4）在(2.4)式中, Q 是1 个常数 , 表示蚂蚁所留的信息素量， 表示第k只蚂蚁在本次循环中所L走路径的长度.在初始时刻， 表示由城市i转到j的。)1,.0,(,)( njiCijij 期望程度，可根据具体问题选择不同启发算法具体确定， ， 及 的表示形式各不相ijijkijP同.M.Dorigo 定义了3 种
12、不同的模型: Ant cycle system , Ant quantity system 及Ant density system ,它们的差别在于表达式(2.4) 的不同.Ant quantity system模型中否 则 ）时 刻 经 过 路 径 （只 蚂 蚁 在若 第 0,1 jitkdQijkij安庆师范学院数学与计算科学学院 2008 届毕业论文第 3 页共 11 页（2.5）Ant density system模型中否 则 ）时 刻 经 过 路 径 （只 蚂 蚁 在 0 ,1jitkQkij（2.6）Ant quantity system ,Ant density system模型
13、利用的是局部信息,Ant cycle system模型利用的则是整体信息.其求解TSP 时性能较好,通常被采用为基本模型.2.2基本蚁群算法系统的步骤基本蚁群算法的主要步骤如下:(1) nc=0(nc为搜索次数).初始化 ， ，将m个蚂蚁置于n个顶点上.ijij(2) 将各蚂蚁的出发点置于解集中,对蚂蚁k(k=1,2,m)按转移概率 转移到下一个顶点kijPj，更新解集（将j置于解集中) .(3) 计算各蚂蚁的目标函数值(该次搜索经过的路径长度) ,记录最好解(路径) .(4) 更新信息素.(5) 1 次搜索完成,将 置0 ，nc+.ij(6) 若nc=rand);to_visit=J(Sel
14、ect(1);Tabu(i,j)=to_visit;endendif NC=2Tabu(1,:)=R_best(NC-1,:);end%第四步：记录本次迭代最佳路线L=zeros(m,1);for i=1:mR=Tabu(i,:);for j=1:(n-1)L(i)=L(i)+D(R(j),R(j+1);endL(i)=L(i)+D(R(1),R(n);endL_best(NC)=min(L);pos=find(L=L_best(NC);R_best(NC,:)=Tabu(pos(1),:);L_ave(NC)=mean(L);NC=NC+1%第五步：更新信息素Delta_Tau=zeros(
15、n,n);for i=1:mfor j=1:(n-1)Delta_Tau(Tabu(i,j),Tabu(i,j+1)=Delta_Tau(Tabu(i,j),Tabu(i,j+1)+Q/L(i);endDelta_Tau(Tabu(i,n),Tabu(i,1)=Delta_Tau(Tabu(i,n),Tabu(i,1)+Q/L(i);endTau=(1-Rho).*Tau+Delta_Tau;%第六步：禁忌表清零Tabu=zeros(m,n);end%第七步：输出结果Pos=find(L_best=min(L_best);Shortest_Route=R_best(Pos(1),:)Shortest_Length=L_best(Pos(1)安庆师范学院数学与计算科学学院 2008 届毕业论文第 10 页共 11 页subplot(1,2,1)DrawRoute(C,Shortest_Route)subplot(1,2,2)plot(L_best)hold onplot(L_ave)function DrawRoute(C,R)%=% DrawRoute.m% 画路线图的子函数%-%
