第三部分蟻群算法

第三部分蟻群算法演示文稿當(dāng)前1頁，總共39頁。優(yōu)選第三部分蟻群算法當(dāng)前2頁，總共39頁。主要內(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)的模型與實現(xiàn)3.3.2螞蟻系統(tǒng)的參數(shù)設(shè)置和基本屬性當(dāng)前3頁，總共39頁。主要內(nèi)容改進的蟻群優(yōu)化算法3.4.1螞蟻系統(tǒng)的優(yōu)點與不足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)用 型當(dāng)前4頁，總共39頁。3.1群智能3.1.1群智能的概念群智能（

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

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