中山大學(xué)ABC算法ppt模版

1、信息學(xué)院 郭浩TSP問題算法原理算法實(shí)現(xiàn)一、一、TSP問題問題 實(shí)例實(shí)例TSP問題很多實(shí)際問題都屬于TSP問題的范疇 1、旅游景區(qū)規(guī)劃問題，描述的是游客應(yīng)如何規(guī)劃旅游線路，使得所經(jīng)過的路徑總和最小；2、物流配送問題，對車輛的配送網(wǎng)絡(luò)進(jìn)行優(yōu)化，縮短配送時(shí)間，從而提高顧客滿意度；3、公交線路規(guī)劃問題只在規(guī)劃路徑網(wǎng)絡(luò)，尋找最優(yōu)的公交路線設(shè)置，從而滿足群體的需求。.TSP問題旅行商問題(TSP，traveling salesman problem)是一個(gè)為學(xué)術(shù)界廣泛研究的問題，長期以來它吸引了眾多學(xué)者對其進(jìn)行研究。深入地研究TSP問題能夠?yàn)榻鉀Q實(shí)際的管理問題提供一定的理論基礎(chǔ)。思考：群體智能算法群體智

2、能算法(Swarm Intelligence Algorithm，SIA)是模擬自然界生物的群體行為而構(gòu)造的隨機(jī)優(yōu)化算法，是在群體智能領(lǐng)域中隨著計(jì)算智能研究的逐步深入而產(chǎn)生的一種新興的計(jì)算智能模式，它是群體智能研究中的一個(gè)重要分支。群體智能算法是從某種由大量個(gè)體表現(xiàn)出來的群體行為出發(fā)，從它們的群體行為中提取模型，為這些行為建立一些規(guī)則，從而提出優(yōu)化算法。在群體智能算法中，每一個(gè)個(gè)體都是具有經(jīng)驗(yàn)和智慧的智能體(Agent)，個(gè)體之間存在互相作用機(jī)制，通過相互作用形成強(qiáng)大的群體智慧，并用于解決那些因?yàn)殡y以建立有效的形式化模型而用傳統(tǒng)優(yōu)化方法又難以解決甚至無法解決的問題。群體智能算法自上世紀(jì)90年代

3、基于螞蟻覓食行為的蟻群算法(Ant Colony Optimization，ACO)提出以來，相繼產(chǎn)生了以飛翔的鳥類為模型的粒子群算法（Particle Swarm Optimization，PSO）、基于魚類覓食行為的人工魚群算法（Artificial Fish swarm Algorithm，AFA）、基于青蛙覓食行為的蛙跳算法(Shuffled Frog Leaping Algorithm，SFLA)以及模擬蜜蜂行為的人工蜂群算法（Artificial Bee Colony，ABC）等。二、人工蜂群算法的原理二、人工蜂群算法的原理算法原理蜂群的智能模型中有三個(gè)基本組成元素：食物源（foo

4、d sources）、雇傭蜂（employed foragers，EF）、非雇傭蜂(unemployed foragers，UF)；兩種最為基本的行為模式：為食物源招募（recruit）蜜蜂和放棄（abandon）某個(gè)食物源算法原理食物源：食物源的價(jià)值由多個(gè)因素控制，如：它距離蜂巢的遠(yuǎn)近；食物源花蜜的豐富程度；獲得食物的困難程度等。算法中使用“食物源的收益率”(profitability)，來綜合代表以上各因素。雇傭蜂：也稱作引領(lǐng)蜂,模型中引領(lǐng)蜂的數(shù)量通常是與食物源對應(yīng)的。引領(lǐng)蜂具有記憶功能，將自己搜索到的食物源的相關(guān)信息(距離蜂巢的遠(yuǎn)近、方向、花蜜的豐富程度等)存儲起來，并以一定的概率分享給

5、其他的蜜蜂。非雇傭蜂：有兩種非雇傭蜂。偵察蜂（scout bees）：在算法的開始和過程中，始終伴隨著偵察蜂對食物源的“探索行為。偵察蜂通常在蜂巢周圍搜索附近的食物源；根據(jù)觀察，蜂群中的偵察蜂數(shù)量大約占整個(gè)蜂群數(shù)量的5一20。跟隨蜂(onlooker bees)：蜂巢附近等待引領(lǐng)蜂共享食物源信息的蜜蜂，他們觀察引領(lǐng)蜂的舞蹈，選擇自己認(rèn)為滿意的蜜蜂進(jìn)行跟隨。算法原理算法原理假設(shè)有兩個(gè)已經(jīng)發(fā)現(xiàn)的蜜源A、B，剛開始時(shí)非雇傭蜂沒有關(guān)于蜜源的任何信息，有兩種選擇：(1) 作為偵察蜂，自發(fā)尋找蜂巢附近的蜜源（S線）。(2) 在觀察到其他蜜蜂的搖擺舞后,它可以被招募并開始按照獲得的信息尋找蜜源。非雇傭蜂發(fā)現(xiàn)

6、新的蜜源后，蜜蜂依靠自身的能力記住蜜源的位置，并迅速開始采蜜，因此，非雇傭蜂變成了雇傭蜂，蜜蜂采完蜜回到蜂箱后，它有以下幾種選擇:（1）放棄蜜源(收益度不高)，成為待工的跟隨蜂(UF)。（2）在返回同一蜜源前，跳搖擺舞招募蜂巢其它伙伴(EF1)。（3）不招募其它蜜蜂，繼續(xù)采蜜(EF2)。算法原理初始時(shí)刻,所有蜜蜂沒有任何先驗(yàn)知識，其角色都是偵察蜂。隨機(jī)搜索到食物源后，偵察蜂返回蜂巢的舞蹈區(qū)，根據(jù)食物源收益度的相對大小。偵察蜂可以轉(zhuǎn)變?yōu)樯鲜鋈魏我环N蜜蜂。轉(zhuǎn)變的原則如下：當(dāng)所采集食物源的收益度相對很低時(shí)，它可以再次成為偵察蜂搜尋附近的食物源，其轉(zhuǎn)變結(jié)果是放棄上次采集的食物源；當(dāng)所采集食物源的收益度

7、排名小于臨界值(如排名在后50%)時(shí)，它可以在觀察完舞蹈后成為跟隨蜂，并前往相應(yīng)的食物源采蜜；當(dāng)所采集食物源的收益度排名高于臨界值時(shí)，它成為引領(lǐng)蜂，繼續(xù)在同一食物源采蜜,并在舞蹈區(qū)招募更多的蜜蜂采集相應(yīng)食物源（EF1）。算法原理人工蜂群算法在搜索收益度最優(yōu)解的過程中，引領(lǐng)蜂有保持優(yōu)良蜜源的作用；跟隨蜂增加優(yōu)良蜜源對應(yīng)的蜜蜂數(shù)目，起到提高算法收斂速度的作用；偵察蜂隨機(jī)搜索新蜜源，能幫助算法跳出局部最優(yōu)。人工蜂群算法循環(huán)結(jié)束條件通常可以設(shè)為循環(huán)次數(shù)遞減為零、前N個(gè)收益度的花蜜源相同或者前多個(gè)花蜜源相同等。算法原理ABC算法在求解優(yōu)化問題時(shí)，食物源的位置被抽象成解空間中的點(diǎn)，蜜蜂采蜜(食物源)的過程

8、也就是搜尋最優(yōu)解的過程?？紤]全局優(yōu)化問題(P), 則問題(P)的多個(gè)可行解的一個(gè)結(jié)合稱為一個(gè)種群，種群中每個(gè)元素(可行解)稱為一個(gè)食物源，每個(gè)食物源的優(yōu)劣程度取決于待優(yōu)化問題所確定的適應(yīng)度值，解的個(gè)數(shù)(SN)等于引領(lǐng)蜂或跟隨蜂的個(gè)數(shù)。我們用d維向量 來 表示第i個(gè)食物源的位置。首先，ABC算法生成含有SN個(gè)解(食物源)的初始種群，每個(gè)解 是一個(gè)d維的向量。然后，蜜蜂對所有的食物源進(jìn)行循環(huán)搜索，循環(huán)次數(shù)為C(C=1，2， ，MCN)。ix算法原理引領(lǐng)蜂首先對相應(yīng)的食物源(解)進(jìn)行一次鄰域搜索，如果搜索到的食物源(解)的花蜜質(zhì)量(適應(yīng)度)優(yōu)于以前的，則用新的食物源位置代替舊的食物源位置，否則保持舊

9、的食物源位置不變。所有的引領(lǐng)蜂完成搜索之后，回到舞蹈區(qū)把食物源花蜜質(zhì)量的信息通過跳搖擺舞傳達(dá)給跟隨蜂。跟隨蜂根據(jù)得到的信息按照概率選擇食物源?；墼蕉嗟氖澄镌矗贿x擇的概率越大。跟隨蜂選中食物源后，也進(jìn)行一次鄰域搜索，并保留較好的解。ABC算法就是通過如此重復(fù)的搜索，最終來找到最優(yōu)解。算法流程(1) 初始化種群的解為 ，i=1，SN，并計(jì)算每個(gè)解的適應(yīng)度值；(2) 引領(lǐng)蜂根據(jù)公式（這兩個(gè)數(shù)都是隨機(jī)選取的，但是k不能等于i(k是鄰域的一個(gè)解)。 是一個(gè)隨機(jī)數(shù)，它控制鄰域的生成范圍，隨著搜索接近最優(yōu)解，鄰域的范圍會逐漸減?。┳鲟徲蛩阉鳟a(chǎn)生新解 ，并且計(jì)算其適應(yīng)度值；(3) 如果 新解的適應(yīng)度值好于

10、原解 ，則用前者替換后者，將新解作為當(dāng)前最好解，否則保留不變；ixiv算法流程(4) 計(jì)算的適應(yīng)度值，并根據(jù)公式（ 是第i個(gè)解的適應(yīng)度值，SN是解的個(gè)數(shù)）計(jì)算與 相關(guān)的概率值 ；(5) 跟隨蜂根據(jù)概率值選擇食物源(解)，并根據(jù)上一頁的公式進(jìn)行鄰域搜索產(chǎn)生新解，計(jì)算其適應(yīng)度值；(6) 同(3)；(7) 判斷是否有要放棄的解，如果存在，則偵察蜂根據(jù)公式產(chǎn)生一個(gè)新解代替它；(8) 記錄迄今為止最好的解；(9) 判斷是否滿足循環(huán)終止條件，如滿足則輸出最優(yōu)結(jié)果，否則返回(2)ixip算法特點(diǎn)1、它是一種自然算法。模擬自然界中蜂群高效的尋找食物源的機(jī)制。2、具有角色分工、角色轉(zhuǎn)換機(jī)制。蜂群中的蜜蜂因角色不

11、同而分別采用不同的搜索方式，并且角色之間可以相互轉(zhuǎn)換。3、較強(qiáng)的協(xié)同工作能力。蜂群在對路徑進(jìn)行選擇時(shí)，不同角色之間利用信息交互方式，傾向于選擇以前蜜蜂搜索到較為豐富的食物源路徑，從而形成正反饋機(jī)制，并能以較大概率找到最優(yōu)解。4、魯棒性。結(jié)合概率規(guī)則和隨機(jī)性選擇進(jìn)行目標(biāo)的搜索，不必具有先驗(yàn)的知識，具有魯棒性和適應(yīng)性。5、可以與其他啟發(fā)式算法結(jié)合使用。人工蜂群算法之所以能夠較快的發(fā)現(xiàn)最優(yōu)解，主要是因?yàn)樗惴ㄖ幸I(lǐng)蜂和跟隨蜂在尋找最短路徑時(shí)形成的正反饋機(jī)制，從而加快了算法的收斂速度。算法實(shí)現(xiàn)所有城市的任一種排列即是問題的一個(gè)解，解空間由若干解構(gòu)成，因此初始化解空間就是隨機(jī)產(chǎn)生多個(gè)不同的城市序列。以n個(gè)

12、城市為例，從1到n對其進(jìn)行編號，那么完成一次旅行的路徑就用1到n的一個(gè)排列組合來表示。在人工蜂群算法中，每一個(gè)引領(lǐng)蜂或者跟隨蜂的位置就對應(yīng)一個(gè)路徑的組合，食物源的豐富程度對應(yīng)這條路徑的長度，用適應(yīng)度函數(shù)值來描述食物源的豐富程度，也就是說，適應(yīng)度函數(shù)值越小的引領(lǐng)蜂或者跟隨蜂所在的位置，所代表的路徑也最優(yōu)。算法實(shí)現(xiàn)算法具體實(shí)現(xiàn)過程中，先給出城市的坐標(biāo)（即城市的位置），再計(jì)算出完全圖的賦權(quán)鄰接矩陣，蜂群初始化后，計(jì)算出初始種群的適應(yīng)度函數(shù)值，找出當(dāng)前的最小值和相應(yīng)的位置并記錄下來。引領(lǐng)蜂的采蜜過程，也就是位置的更新，我們選取這只引領(lǐng)蜂所代表的路徑中的任意兩處進(jìn)行位置調(diào)換，形成新的位置，并計(jì)算新位置對

13、應(yīng)的適應(yīng)度函數(shù)值，與已經(jīng)記錄的最小值進(jìn)行比較，如果比它更優(yōu)，則替換當(dāng)前的最小值，否則保持不變。跟隨蜂的跟隨過程，采取的是輪盤賭概率選擇法，計(jì)算好每只引領(lǐng)蜂被跟隨的概率，然后跟隨蜂按照相應(yīng)的概率選取要跟隨的引領(lǐng)蜂，并進(jìn)行采蜜（與引領(lǐng)蜂的采蜜過程一樣），按照貪婪準(zhǔn)則，保留最優(yōu)的解。如果某只引領(lǐng)蜂或者跟隨蜂采蜜了limit次過后，仍舊沒有發(fā)現(xiàn)更好的解，則轉(zhuǎn)化為偵察蜂，對其置于一個(gè)隨機(jī)的初試路徑，再繼續(xù)搜索。按照以上所述的三種蜂的采蜜與轉(zhuǎn)換過程，進(jìn)行算法的迭代，最后找出那條滿足條件的最優(yōu)路徑，并保證這條路徑的長度最短。算法實(shí)現(xiàn)仿真驗(yàn)證一選用burma14.tsp問題進(jìn)行實(shí)驗(yàn)仿真，參數(shù)設(shè)置為NP=20，

14、（ employed bees+onlooker bees）Foodnumber=10，limit=50，maxCycle=500。運(yùn)行10次，得到結(jié)果如下表所示：TSPLIB(http:/www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp/)TSP的標(biāo)準(zhǔn)測試庫運(yùn)行次數(shù)最優(yōu)路徑最小距離19 118137561214432110931.879126543142110911813712630.878535431421109118137126530.878547126543142191011813731.375551434561

15、2713811910121430.878563142811091113712654331.2088711181371265431421091131.226981821434561271311910131.2088911910121434561271381130.87851014211091181371265431430.8785仿真驗(yàn)證二選用ulysses22.tsp問題進(jìn)行實(shí)驗(yàn)仿真，參數(shù)設(shè)置為NP=60,Foodnumber=30,limit=100,maxCycle=500。下表為人工蜂群算法運(yùn)行10次的仿真結(jié)果。結(jié)論一有隨機(jī)性在里面每次運(yùn)行結(jié)果不一樣 所以以后運(yùn)用算法時(shí)應(yīng)多次運(yùn)行，求得最

16、優(yōu)解擴(kuò)展驗(yàn)證 另外16個(gè)點(diǎn)Elapsed time is 1.848382 seconds.最優(yōu)路徑1-5-3-7-2-8-15-16-10-4-11-14-6-12-9-13-1最小距離31.857119個(gè)點(diǎn)（極限！）Elapsed time is 1.617617 seconds.最優(yōu)路徑9-12-6-14-11-17-16-10-4-19-15-8-2-7-3-18-5-1-13-9最小距離35.965420個(gè)點(diǎn)Elapsed time is 0.985919 seconds.最優(yōu)路徑17-12-9-13-6-14-11-7-19-20-18-5-1-3-4-10-2-8-15-16-1

17、7最小距離42.0124Elapsed time is 2.074763 seconds.最優(yōu)路徑3-5-1-18-17-20-14-6-13-9-23-12-15-8-21-24-2-16-4-11-10-25-22-19-7-3最小距離42.7088 25個(gè)點(diǎn)擴(kuò)展驗(yàn)證 30個(gè)點(diǎn)Elapsed time is 1.664646 seconds.最優(yōu)路徑8-21-29-27-1-5-18-17-13-12-10-26-4-28-22-19-7-3-11-23-9-6-14-20-16-2-25-24-15-30-8最小距離66.4799NP=200 5000次 Elapsed time is

18、80.025833 seconds.最優(yōu)路徑3-7-19-22-25-24-15-30-8-21-2-16-26-10-28-4-9-12-23-13-6-14-11-20-18-5-1-17-27-29-3最小距離54.389250個(gè)點(diǎn)Elapsed time is 2350.784131 seconds.最優(yōu)路徑21-39-15-50-8-31-26-2-29-36-43-32-12-40-6-13-34-9-23-46-16-10-4-48-38-35-49-44-7-19-22-25-42-41-5-1-37-45-18-17-20-14-28-47-3-11-33-27-30-24-21最小距離79.8903NP=600 maxCycle=50000 結(jié)論二只適用于小規(guī)模的TSP問題如何提升解決大規(guī)模TSP問題是該算法重要研究方向Limit=10 Limit=50 maxCycle=500 Elapsed time is 9.019615 seconds.最優(yōu)路徑6-12-9-13-1-5-18-3-20-7-19-4-10-16-2-8-15-17-11-14-6最小距離38.8781 maxCycle=50 Elapsed time is 1.628429 seconds.最優(yōu)路徑15-19-11-4-10-