第三部分蟻群算法

第三部分蟻群算法演示文稿目前一頁(yè)\總數(shù)三十九頁(yè)\編于五點(diǎn)優(yōu)選第三部分蟻群算法目前二頁(yè)\總數(shù)三十九頁(yè)\編于五點(diǎn)主要內(nèi)容3.1群智能3.1.1群智能的概念3.1.2群智能算法3.2蟻群優(yōu)化算法原理3.2.1蟻群算法的起源3.2.2蟻群算法的原理分析基本蟻群優(yōu)化算法3.3.1螞蟻系統(tǒng)的模型與實(shí)現(xiàn)3.3.2螞蟻系統(tǒng)的參數(shù)設(shè)置和基本屬性目前三頁(yè)\總數(shù)三十九頁(yè)\編于五點(diǎn)主要內(nèi)容改進(jìn)的蟻群優(yōu)化算法3.4.1螞蟻系統(tǒng)的優(yōu)點(diǎn)與不足3.4.2帶精英策略的螞蟻系統(tǒng)基于排序的螞蟻系統(tǒng)最大－最小螞蟻系統(tǒng)3.4.5蟻群系統(tǒng)各種蟻群優(yōu)化算法的比較3.5蟻群優(yōu)化算法的應(yīng)用典型應(yīng)用3.5.2車間作業(yè)調(diào)度（JSP）醫(yī)學(xué)診斷的數(shù)據(jù)挖掘3.5.4蟻群算法在電信路由優(yōu)化中的應(yīng)用 型目前四頁(yè)\總數(shù)三十九頁(yè)\編于五點(diǎn)3.1群智能3.1.1群智能的概念群智能（

SwarmIntelligence,SI）人們把群居昆蟲的集體行為稱作“群智能”（“群體智能”、“群集智能”、“集群智能”等）特點(diǎn)個(gè)體的行為很簡(jiǎn)單，但當(dāng)它們一起協(xié)同工作時(shí)，卻能夠突現(xiàn)出非常復(fù)雜（智能）的行為特征。目前五頁(yè)\總數(shù)三十九頁(yè)\編于五點(diǎn)3.1群智能3.1.2群智能的算法描述群智能作為一種新興的演化計(jì)算技術(shù)已成為研究焦點(diǎn)，它與人工生命，特別是進(jìn)化策略以及遺傳算法有著極為特殊的關(guān)系。特性指無(wú)智能的主體通過(guò)合作表現(xiàn)出智能行為的特性，在沒(méi)有集中控制且不提供全局模型的前提下，為尋找復(fù)雜的分布式問(wèn)題求解方案提供了基礎(chǔ)。目前六頁(yè)\總數(shù)三十九頁(yè)\編于五點(diǎn)3.1群智能3.1.2群智能的算法優(yōu)點(diǎn)與大多數(shù)基于梯度的應(yīng)用優(yōu)化算法不同，群智能依靠的是概率搜索算法。雖然概率搜索算法通常要采用較多的評(píng)價(jià)函數(shù)，但是與梯度方法及傳統(tǒng)的演化算法相比，其優(yōu)點(diǎn)還是顯著的穩(wěn)健性：無(wú)集中控制約束，不會(huì)因個(gè)別個(gè)體的故障影響整個(gè)問(wèn)題的求解，確保了系統(tǒng)具備更強(qiáng)的魯棒性；擴(kuò)展性：活動(dòng)既不受中央控制，也不受局部監(jiān)管，以非直接的信息交流方式確保了系統(tǒng)的擴(kuò)展性并行性：并行分布式算法模型，可充分利用多處理器靈活性：對(duì)問(wèn)題定義的連續(xù)性無(wú)特殊要求；易行性：算法實(shí)現(xiàn)簡(jiǎn)單。典型算法蟻群算法（螞蟻覓食）粒子群算法（鳥群捕食）目前七頁(yè)\總數(shù)三十九頁(yè)\編于五點(diǎn)3.2蟻群優(yōu)化算法原理3.2.1蟻群算法的起源20世紀(jì)50年代中期創(chuàng)立了仿生學(xué)，人們從生物進(jìn)化的機(jī)理中受到啟發(fā)。提出了許多用以解決復(fù)雜優(yōu)化問(wèn)題的新方法，如進(jìn)化規(guī)劃、進(jìn)化策略、遺傳算法等，這些算法成功地解決了一些實(shí)際問(wèn)題。20世紀(jì)90年代意大利學(xué)者M(jìn)．Dorigo，V．Maniezzo，A．Colorni等從生物進(jìn)化的機(jī)制中受到啟發(fā)，通過(guò)模擬自然界螞蟻搜索路徑的行為，提出來(lái)一種新型的模擬進(jìn)化算法——蟻群算法，是群智能理論研究領(lǐng)域的一種主要算法。這種方法能夠被用于解決大多數(shù)優(yōu)化問(wèn)題或者能夠轉(zhuǎn)化為優(yōu)化求解的問(wèn)題?，F(xiàn)在其應(yīng)用領(lǐng)域已擴(kuò)展到多目標(biāo)優(yōu)化、數(shù)據(jù)分類、數(shù)據(jù)聚類、模式識(shí)別、電信QoS管理、生物系統(tǒng)建模、流程規(guī)劃、信號(hào)處理、機(jī)器人控制、決策支持以及仿真和系統(tǒng)辯識(shí)等方面．雖然研究時(shí)間不長(zhǎng)，但是現(xiàn)在的研究顯示出，蟻群算法在求解復(fù)雜優(yōu)化問(wèn)題（特別是離散優(yōu)化問(wèn)題）方面有一定優(yōu)勢(shì)。目前八頁(yè)\總數(shù)三十九頁(yè)\編于五點(diǎn)3.2蟻群優(yōu)化算法原理3.2.1蟻群算法的起源蟻群的自組織行為“雙橋?qū)嶒?yàn)”螞蟻在運(yùn)動(dòng)過(guò)程中，通過(guò)遺留在來(lái)往路徑上的揮發(fā)性化學(xué)物質(zhì)（信息素,Pheromone）來(lái)進(jìn)行通信和協(xié)調(diào)。因此由大量螞蟻組成的蟻群集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過(guò)的螞蟻越多，則后來(lái)者選擇該路徑的概率就越大。目前九頁(yè)\總數(shù)三十九頁(yè)\編于五點(diǎn)3.2蟻群優(yōu)化算法原理3.2.1蟻群算法的起源蟻群的自組織行為“雙橋?qū)嶒?yàn)”目前十頁(yè)\總數(shù)三十九頁(yè)\編于五點(diǎn)3.2蟻群優(yōu)化算法原理3.2.1蟻群算法的起源提出蟻群系統(tǒng)1992年，意大利學(xué)者M(jìn).Dorigo在其博士論文中提出螞蟻系統(tǒng)（AntSystem）。近年來(lái)，M.Dorigo等人進(jìn)一步將螞蟻算法發(fā)展為一種通用的優(yōu)化技術(shù)——蟻群優(yōu)化（antcolonyoptimization,ACO）。目前十一頁(yè)\總數(shù)三十九頁(yè)\編于五點(diǎn)3.2蟻群優(yōu)化算法原理3.2.2蟻群算法的原理分析蟻巢 食物螞蟻從A點(diǎn)出發(fā)，速度相同，食物在D點(diǎn)，隨機(jī)選擇路線ABD或ACD。假設(shè)初始時(shí)每條分配路線一只螞蟻，每個(gè)時(shí)間單位行走一步。經(jīng)過(guò)9個(gè)時(shí)間單位時(shí)：走ABD的螞蟻到達(dá)終點(diǎn)，走ACD的螞蟻剛好走到C點(diǎn)，為一半路程。目前十二頁(yè)\總數(shù)三十九頁(yè)\編于五點(diǎn)3.2蟻群優(yōu)化算法原理3.2.2蟻群算法的原理分析食物蟻巢經(jīng)過(guò)18個(gè)時(shí)間單位時(shí)：走ABD的螞蟻到達(dá)終點(diǎn)后得到食物又返回了起點(diǎn)A，而走ACD的螞蟻剛好走到D點(diǎn)。假設(shè)螞蟻每經(jīng)過(guò)一處所留下的信息素為一個(gè)單位，則經(jīng)過(guò)36個(gè)時(shí)間單位后，所有開(kāi)始一起出發(fā)的螞蟻都經(jīng)過(guò)不同路徑從D點(diǎn)取得了食物，此時(shí)ABD的路線往返了2趟，每一處的信息素為4個(gè)單位，而ACD的路線往返了一趟，每一處的信息素為2個(gè)單位，其比值為2：1。目前十三頁(yè)\總數(shù)三十九頁(yè)\編于五點(diǎn)3.2蟻群優(yōu)化算法原理3.2.2蟻群算法的原理分析蟻巢食物尋找食物的過(guò)程繼續(xù)進(jìn)行，則按信息素的指導(dǎo)，蟻群在ABD路線上增派一只螞蟻（共2只），而ACD路線上仍然為一只螞蟻。再經(jīng)過(guò)36個(gè)時(shí)間單位后，兩條線路上的信息素單位積累為12和4，比值為3：1。若按以上規(guī)則繼續(xù)，蟻群在ABD路線上再增派一只螞蟻（共3只），而ACD路線上仍然為一只螞蟻。再經(jīng)過(guò)36個(gè)時(shí)間單位后，兩條線路上的信息素單位積累為24和6，比值為

1。則按信息素的指導(dǎo)，最后的極限是所有的螞蟻只選擇ABD路線。（正反饋目前十四頁(yè)\總數(shù)三十九頁(yè)\編于五點(diǎn)3.2蟻群優(yōu)化算法原理3.2.2蟻群算法的原理分析基于以上蟻群尋找食物時(shí)的最優(yōu)路徑選擇問(wèn)題，可以構(gòu)造人工蟻群，來(lái)解決最優(yōu)化問(wèn)題，如TSP問(wèn)題。人工蟻群中把具有簡(jiǎn)單功能的工作單元看作螞蟻。二者的相似之處在于都是優(yōu)先選擇信息素濃度大的路徑。較短路徑的信息素濃度高，所以能夠最終被所有螞蟻選擇，也就是最終的優(yōu)化結(jié)果。兩者的區(qū)別在于人工蟻群有一定的記憶能力，能夠記憶已經(jīng)訪問(wèn)過(guò)的節(jié)點(diǎn)。同時(shí)，人工蟻群再選擇下一條路徑的時(shí)候是按一定算法規(guī)律有意識(shí)地尋找最短路徑，而不是盲目的。例如在TSP問(wèn)題中，可以預(yù)先知道當(dāng)前城市到下一個(gè)目的地的距離。目前十五頁(yè)\總數(shù)三十九頁(yè)\編于五點(diǎn)3.3基本蟻群優(yōu)化算法基本蟻群優(yōu)化算法3.3.1螞蟻系統(tǒng)的模型與實(shí)現(xiàn)解決TSP問(wèn)題在算法的初始時(shí)刻，將m只螞蟻隨機(jī)放到n座城市;將每只螞蟻k的禁忌表tabuk(s)的第一個(gè)元素tabuk(1)設(shè)置為它當(dāng)前所在城市;設(shè)各路徑上的信息素τij(0)=C（C為一較小的常數(shù)）;目前十六頁(yè)\總數(shù)三十九頁(yè)\編于五點(diǎn)3.3基本蟻群優(yōu)化算法基本蟻群優(yōu)化算法3.3.1螞蟻系統(tǒng)的模型與實(shí)現(xiàn)解決TSP問(wèn)題每只螞蟻根據(jù)路徑上的信息素和啟發(fā)式信息（兩城市間距離）獨(dú)立地選擇下一座城市：在時(shí)刻t，螞蟻k從城市i轉(zhuǎn)移到城市j的概率為§bat)]([)]([htijα、β分別表示信息素和啟發(fā)式因子的相對(duì)重要程度iJj?)(,a¨=??kbat)]([)]([htkijtp)(isai)Js(kaiJj?)(,0?)(iJk表示允許螞蟻k下一步可k訪問(wèn)的城市集合{}dtabuniJ/1,2,1)(=-=hLijk目前十七頁(yè)\總數(shù)三十九頁(yè)\編于五點(diǎn)3.3基本蟻群優(yōu)化算法基本蟻群優(yōu)化算法3.3.1螞蟻系統(tǒng)的模型與實(shí)現(xiàn)解決TSP問(wèn)題當(dāng)所有螞蟻完成一次周游后，各路徑上的信息素將進(jìn)行更新：tnt)()1()(D+-=+trtijQ§ijk在本次周游中經(jīng)過(guò)邊若螞蟻,m?=a¨kij=kij,D=DtLka?否則,01k其中，ρ（0<ρ<1）表示路徑上信息素的揮發(fā)系數(shù)，為正常數(shù)，Lk表示第k只螞蟻在本次周游中所走過(guò)路徑的長(zhǎng)度。目前十八頁(yè)\總數(shù)三十九頁(yè)\編于五點(diǎn)3.3基本蟻群優(yōu)化算法基本蟻群優(yōu)化算法3.3.1螞蟻系統(tǒng)的模型與實(shí)現(xiàn)算法流程目前十九頁(yè)\總數(shù)三十九頁(yè)\編于五點(diǎn)3.3基本蟻群優(yōu)化算法基本蟻群優(yōu)化算法3.3.1螞蟻系統(tǒng)的模型與實(shí)現(xiàn)初始參數(shù)城市數(shù)30;螞蟻數(shù)30；α=1;β=5;ρ=0.5;最大迭代代數(shù)200;Q=100;§bahtt)]([)]([ijiJj?)(,a=??kbahtt)]([)]([kijtp)(¨isa)(iJskaiJj?)(,0?k{}dtabuniJ/1,2,1)(=-=hLijkD+-=+trttnt)()1()(ijQ§ijk經(jīng)過(guò)邊螞蟻,m?=a¨kij=kij,D=DtLka?否則,0k1目前二十頁(yè)\總數(shù)三十九頁(yè)\編于五點(diǎn)3.3基本蟻群優(yōu)化算法基本蟻群優(yōu)化算法3.3.1螞蟻系統(tǒng)的模型與實(shí)現(xiàn)蟻群的規(guī)模和停止規(guī)則蟻群規(guī)模對(duì)于TSP來(lái)說(shuō)，一般情況下蟻群中螞蟻的個(gè)數(shù)不超過(guò)TSP圖中節(jié)點(diǎn)的個(gè)數(shù)。終止條件給定一個(gè)外循環(huán)的最大數(shù)目，表明已經(jīng)有足夠的螞蟻工作；當(dāng)前最優(yōu)解連續(xù)K次相同而停止，其中K是一個(gè)給定的整數(shù)，表示算法已經(jīng)收斂，不再需要繼續(xù)；目標(biāo)值控制規(guī)則，給定優(yōu)化問(wèn)題（目標(biāo)最小化）的一個(gè)下界和一個(gè)誤差值，當(dāng)算法得到的目標(biāo)值同下界之差小于給定的誤差值時(shí)，算法終止。目前二十一頁(yè)\總數(shù)三十九頁(yè)\編于五點(diǎn)3.3基本蟻群優(yōu)化算法基本蟻群優(yōu)化算法3.3.1螞蟻系統(tǒng)的模型與實(shí)現(xiàn)運(yùn)行結(jié)果目前二十二頁(yè)\總數(shù)三十九頁(yè)\編于五點(diǎn)3.3基本蟻群優(yōu)化算法基本蟻群優(yōu)化算法3.3.1螞蟻系統(tǒng)的模型與實(shí)現(xiàn)運(yùn)行結(jié)果目前二十三頁(yè)\總數(shù)三十九頁(yè)\編于五點(diǎn)3.3基本蟻群優(yōu)化算法基本蟻群優(yōu)化算法3.3.1螞蟻系統(tǒng)的模型與實(shí)現(xiàn)運(yùn)行結(jié)果目前二十四頁(yè)\總數(shù)三十九頁(yè)\編于五點(diǎn)3.3基本蟻群優(yōu)化算法基本蟻群優(yōu)化算法3.3.1螞蟻系統(tǒng)的模型與實(shí)現(xiàn)運(yùn)行結(jié)果目前二十五頁(yè)\總數(shù)三十九頁(yè)\編于五點(diǎn)3.3基本蟻群優(yōu)化算法基本蟻群優(yōu)化算法3.3.1螞蟻系統(tǒng)的模型與實(shí)現(xiàn)運(yùn)行結(jié)果目前二十六頁(yè)\總數(shù)三十九頁(yè)\編于五點(diǎn)3.3基本蟻群優(yōu)化算法基本蟻群優(yōu)化算法3.3.1螞蟻系統(tǒng)的模型與實(shí)現(xiàn)運(yùn)行結(jié)果目前二十七頁(yè)\總數(shù)三十九頁(yè)\編于五點(diǎn)3.3基本蟻群優(yōu)化算法基本蟻群優(yōu)化算法3.3.1螞蟻系統(tǒng)的模型與實(shí)現(xiàn)最初提出的AS有三種模型：蟻密模型Ant-density蟻量模型Ant-quantity蟻周模型Ant-cycle。在Ant-density和Ant-quantity中螞蟻在兩個(gè)位置節(jié)點(diǎn)間每移動(dòng)一次后即更新信息素（局部信息）；而在Ant-cycle中，當(dāng)所有的螞蟻都完成了自己的行程后（全局信息），才對(duì)信息素進(jìn)行更新，而且每個(gè)螞蟻所釋放的信息素被表達(dá)為反映相應(yīng)行程質(zhì)量的函數(shù)。目前二十八頁(yè)\總數(shù)三十九頁(yè)\編于五點(diǎn)3.3基本蟻群優(yōu)化算法基本蟻群優(yōu)化算法3.3.1螞蟻系統(tǒng)的模型與實(shí)現(xiàn)三種模型ant-cycle：（蟻周）ant-quantity：（蟻量）ant-density:（蟻密）Q§在本次周游中經(jīng)過(guò)螞蟻, ijkLa¨kt=Dijka?否則,0Q§+經(jīng)過(guò)和在時(shí)刻螞蟻1, ijtkda¨kt=Dijija?否則,0§ +經(jīng)過(guò)和在時(shí)刻螞蟻1, ijtkQk=Dtij否則,0?¨其中，Q為正常數(shù)，Lk表示第k只螞蟻在本次周游中所走過(guò)路徑的長(zhǎng)度，dij為i與j之間的距離。目前二十九頁(yè)\總數(shù)三十九頁(yè)\編于五點(diǎn)3.3基本蟻群優(yōu)化算法基本蟻群優(yōu)化算法3.3.1螞蟻系統(tǒng)的模型與實(shí)現(xiàn)三種模型的比較模型ant-density,ant-quantity,ant-cycle的比較(M.Dorigo,1996)參數(shù)集模型最好參數(shù)集平均結(jié)果最好結(jié)果α＝1,β=5,ρ=0.01

426.740

424.635ant-densityant-quantityα＝1,β=5,ρ=0.01

427.315

426.255￠ant-cycleα＝1,β=5,ρ=0.5

424.250

423.741目前三十頁(yè)\總數(shù)三十九頁(yè)\編于五點(diǎn)3.3基本蟻群優(yōu)化算法基本蟻群優(yōu)化算法3.3.2螞蟻系統(tǒng)的參數(shù)設(shè)置和基本屬性信息素的分布目前三十一頁(yè)\總數(shù)三十九頁(yè)\編于五點(diǎn)3.3基本蟻群優(yōu)化算法基本蟻群優(yōu)化算法3.3.2螞蟻系統(tǒng)的參數(shù)設(shè)置和基本屬性信息素的分布揮發(fā)系數(shù)的影響：tntD+-=+trt)()1()(ijQ§ijk經(jīng)過(guò)邊螞蟻,m?=a¨kij,kijt=D=DLka?否則,0k1ρ＝0.05 ρ＝0.95目前三十二頁(yè)\總數(shù)三十九頁(yè)\編于五點(diǎn)3.3基本蟻群優(yōu)化算法基本蟻群優(yōu)化算法3.3.2螞蟻系統(tǒng)的參數(shù)設(shè)置和基本屬性參數(shù)α、β對(duì)算法性能的影響停滯現(xiàn)象（Stagnationbehavior）：所有螞蟻都選擇相同的路徑，即系統(tǒng)不再搜索更好的解。原因在于較好路徑上的信息素遠(yuǎn)大于其他邊上的，從而使所有螞蟻都選擇該路徑。目前三十三頁(yè)\總數(shù)三十九頁(yè)\編于五點(diǎn)3.3基本蟻群優(yōu)化算法基本蟻群優(yōu)化算法3.3.2螞蟻系統(tǒng)的參數(shù)設(shè)置和基本屬性參數(shù)α、β對(duì)算法性能的影響α取較大值時(shí)，意味著在選擇路徑時(shí)，路徑上的信息素非常重要；當(dāng)α取較小