現(xiàn)代優(yōu)化算法蟻群算法PPT課件

1、I.I.模擬退火模擬退火II.II.遺傳算法遺傳算法III.III.蟻群優(yōu)化算法蟻群優(yōu)化算法第1頁(yè)/共39頁(yè)I.I.螞蟻搬家，天要下雨。螞蟻搬家，天要下雨。II.II. 螞蟻群體行為。螞蟻群體行為。a.a.相互協(xié)作的一群相互協(xié)作的一群螞蟻可以戰(zhàn)勝比自己強(qiáng)壯的昆蟲(chóng)，螞蟻可以戰(zhàn)勝比自己強(qiáng)壯的昆蟲(chóng)，并把它搬回巢；而單個(gè)螞蟻則不能。并把它搬回巢；而單個(gè)螞蟻則不能。b.b.相互協(xié)作的一群相互協(xié)作的一群螞蟻可以螞蟻可以很容易找到從蟻巢到食很容易找到從蟻巢到食物源的最短路徑，而單個(gè)螞蟻則不能。此外，螞物源的最短路徑，而單個(gè)螞蟻則不能。此外，螞蟻還能夠適應(yīng)環(huán)境的變化，例如在蟻群的運(yùn)動(dòng)路蟻還能夠適應(yīng)環(huán)境的變化，

2、例如在蟻群的運(yùn)動(dòng)路線上突然出現(xiàn)障礙物時(shí)，它們能夠很快地重新找線上突然出現(xiàn)障礙物時(shí)，它們能夠很快地重新找到最優(yōu)路徑。到最優(yōu)路徑。不但引起昆蟲(chóng)學(xué)家，而且也引不但引起昆蟲(chóng)學(xué)家，而且也引起數(shù)學(xué)及計(jì)算機(jī)方面的專家和工程師的興趣。起數(shù)學(xué)及計(jì)算機(jī)方面的專家和工程師的興趣。第2頁(yè)/共39頁(yè)昆蟲(chóng)學(xué)家通過(guò)大量的研究發(fā)現(xiàn)：昆蟲(chóng)學(xué)家通過(guò)大量的研究發(fā)現(xiàn)：螞蟻個(gè)體之間是通過(guò)信息螞蟻個(gè)體之間是通過(guò)信息交流達(dá)到找到從蟻巢到食物源的最短路徑的目的。交流達(dá)到找到從蟻巢到食物源的最短路徑的目的。I.螞蟻個(gè)體通過(guò)在其所經(jīng)過(guò)的路上留下一種稱之為螞蟻個(gè)體通過(guò)在其所經(jīng)過(guò)的路上留下一種稱之為“信息素信息素”（pheromone）或）或“跡跡

3、”的物質(zhì)來(lái)實(shí)現(xiàn)的物質(zhì)來(lái)實(shí)現(xiàn)與同伴之間的信息傳遞。與同伴之間的信息傳遞。II.隨后的螞蟻遇到信息素時(shí)，不僅能檢測(cè)出該物質(zhì)的隨后的螞蟻遇到信息素時(shí)，不僅能檢測(cè)出該物質(zhì)的存在以及量的多少，而且可根據(jù)信息素的濃度來(lái)指存在以及量的多少，而且可根據(jù)信息素的濃度來(lái)指導(dǎo)自己對(duì)前進(jìn)方向的選擇。導(dǎo)自己對(duì)前進(jìn)方向的選擇。第3頁(yè)/共39頁(yè)III. 信息素信息素隨著時(shí)間的推移會(huì)逐漸揮發(fā)掉，于是路徑的隨著時(shí)間的推移會(huì)逐漸揮發(fā)掉，于是路徑的長(zhǎng)短及其螞蟻的多少就對(duì)殘余信息素的強(qiáng)度產(chǎn)生影長(zhǎng)短及其螞蟻的多少就對(duì)殘余信息素的強(qiáng)度產(chǎn)生影響，反過(guò)來(lái)信息素的強(qiáng)弱又指導(dǎo)著其它螞蟻的行動(dòng)響，反過(guò)來(lái)信息素的強(qiáng)弱又指導(dǎo)著其它螞蟻的行動(dòng)方向。方向

4、。因此，某一路徑上走過(guò)的螞蟻越多，則后來(lái)者選擇該路徑因此，某一路徑上走過(guò)的螞蟻越多，則后來(lái)者選擇該路徑的概率就越大。這就構(gòu)成了螞蟻群體行為表現(xiàn)出的一種信的概率就越大。這就構(gòu)成了螞蟻群體行為表現(xiàn)出的一種信息正反饋現(xiàn)象，并實(shí)現(xiàn)找到息正反饋現(xiàn)象，并實(shí)現(xiàn)找到蟻巢到食物源的最短路徑蟻巢到食物源的最短路徑。第4頁(yè)/共39頁(yè)蟻群實(shí)現(xiàn)找到蟻群實(shí)現(xiàn)找到蟻巢到食物源的最短路徑示意圖蟻巢到食物源的最短路徑示意圖障礙物障礙物ABCDEHd=1d=1d=0.5d=0.5圖圖1圖圖1中設(shè)中設(shè)A是蟻巢，是蟻巢，E是食物源，是食物源，H、C為障礙物，由為障礙物，由于障礙物的存在，由于障礙物的存在，由A外出覓食或由外出覓食或由

5、E返回巢穴的螞返回巢穴的螞蟻只能經(jīng)由蟻只能經(jīng)由H或或C到達(dá)目的地。到達(dá)目的地。BH和和HD距離為距離為1單位，單位，BC和和DC距離為距離為0.5單位。單位。假設(shè)螞蟻以假設(shè)螞蟻以“1單位長(zhǎng)度單位長(zhǎng)度/單位時(shí)間單位時(shí)間”的速度往返于的速度往返于A和和E，每經(jīng)過(guò)一個(gè)單位時(shí)間各有，每經(jīng)過(guò)一個(gè)單位時(shí)間各有30只螞蟻離開(kāi)只螞蟻離開(kāi)A和和E到到達(dá)達(dá)B和和D。 第5頁(yè)/共39頁(yè)蟻群實(shí)現(xiàn)找到蟻群實(shí)現(xiàn)找到蟻巢到食物源的最短路徑示意圖蟻巢到食物源的最短路徑示意圖障礙物障礙物ABCDEH15151515初始時(shí)，各有初始時(shí)，各有30只螞蟻在只螞蟻在B和和D點(diǎn)遇到障礙物，開(kāi)始點(diǎn)遇到障礙物，開(kāi)始選擇路徑。由于此時(shí)路徑上無(wú)

6、跡，螞蟻便以相同的選擇路徑。由于此時(shí)路徑上無(wú)跡，螞蟻便以相同的概率隨機(jī)地走兩條路中的任意一條，因而概率隨機(jī)地走兩條路中的任意一條，因而15只選往只選往H，15只選往只選往C（圖（圖2）。）。經(jīng)過(guò)一個(gè)單位時(shí)間以后，路徑經(jīng)過(guò)一個(gè)單位時(shí)間以后，路徑BHD被被15只螞蟻爬過(guò)，只螞蟻爬過(guò)，而路徑而路徑BCD上則被上則被30只螞蟻爬過(guò)，只螞蟻爬過(guò)，BCD上的信息量上的信息量是是BHD上信息量的兩倍上信息量的兩倍。 圖圖2第6頁(yè)/共39頁(yè)蟻群實(shí)現(xiàn)找到蟻群實(shí)現(xiàn)找到蟻巢到食物源的最短路徑示意圖蟻巢到食物源的最短路徑示意圖障礙物障礙物ABCDEH10102020圖圖3此時(shí)，又有此時(shí)，又有30只螞蟻離開(kāi)只螞蟻離開(kāi)B

7、和和D，于是，于是20只選擇往只選擇往C方向，方向，而另外而另外10只則選往只則選往H（圖（圖3）。這樣，更多的信息量被）。這樣，更多的信息量被留在更短的路徑留在更短的路徑BCD上。上。隨著時(shí)間的推移和上述過(guò)程的重復(fù)，短路徑上的信息量隨著時(shí)間的推移和上述過(guò)程的重復(fù)，短路徑上的信息量便以更快的速度增長(zhǎng)，于是會(huì)有越來(lái)越多的螞蟻選擇這便以更快的速度增長(zhǎng)，于是會(huì)有越來(lái)越多的螞蟻選擇這條短路徑，以致最終完全選擇這條短路徑條短路徑，以致最終完全選擇這條短路徑BCD。 相對(duì)弱小，功能并不強(qiáng)大的個(gè)體是完成復(fù)雜的工作。相對(duì)弱小，功能并不強(qiáng)大的個(gè)體是完成復(fù)雜的工作。第7頁(yè)/共39頁(yè)一個(gè)著名的組合優(yōu)化問(wèn)題：一個(gè)著名

8、的組合優(yōu)化問(wèn)題：旅行商問(wèn)題（旅行商問(wèn)題（TSP, traveling salesman problem），一個(gè)商人欲到），一個(gè)商人欲到 n 個(gè)城市推銷個(gè)城市推銷商品，每個(gè)兩個(gè)城市商品，每個(gè)兩個(gè)城市 i 和和 j 之間的距離為之間的距離為 dij ，如何選擇一條道路使得商人每個(gè)，如何選擇一條道路使得商人每個(gè)城市走一遍后回到起點(diǎn)且所走路徑最短。城市走一遍后回到起點(diǎn)且所走路徑最短。第8頁(yè)/共39頁(yè)一般旅行商問(wèn)題一般旅行商問(wèn)題TSP，數(shù)學(xué)模型描述：，數(shù)學(xué)模型描述：jinjixnsnssxnjxnixtsxdijsjiijniijnjijjiijij,2,1,1,0,2,1,22,1,2,1,1,2,1

9、,1. .min,11選擇選擇 ij 路線為路線為1 1，否則為，否則為0 0避免產(chǎn)生回路避免產(chǎn)生回路走入城市走入城市j只有一次只有一次從城市從城市i出發(fā)只有一次出發(fā)只有一次第9頁(yè)/共39頁(yè)例子，一般旅行商例子，一般旅行商TSP問(wèn)題的解。問(wèn)題的解。ABDEC如圖所示，從如圖所示，從A城市出發(fā)回到城市出發(fā)回到A城城市一個(gè)市一個(gè)TSP問(wèn)題的解是問(wèn)題的解是ABCEDA，即圖中紅色線條路徑。即圖中紅色線條路徑。這個(gè)解滿足以上四個(gè)約束條件。這個(gè)解滿足以上四個(gè)約束條件。第10頁(yè)/共39頁(yè)NP問(wèn)題：?jiǎn)栴}：至今為止，還沒(méi)有一個(gè)有能求得最優(yōu)解的多項(xiàng)式時(shí)間算法的組合優(yōu)化至今為止，還沒(méi)有一個(gè)有能求得最優(yōu)解的多項(xiàng)式時(shí)

10、間算法的組合優(yōu)化問(wèn)題稱為問(wèn)題稱為NP問(wèn)題。問(wèn)題。TSP問(wèn)題就是一個(gè)著名的問(wèn)題就是一個(gè)著名的NP問(wèn)題。問(wèn)題。在如何解決這個(gè)問(wèn)題方面已經(jīng)有了大量的研在如何解決這個(gè)問(wèn)題方面已經(jīng)有了大量的研究。這其中包括遺傳算法，退火算法，動(dòng)態(tài)規(guī)劃等等。究。這其中包括遺傳算法，退火算法，動(dòng)態(tài)規(guī)劃等等。第11頁(yè)/共39頁(yè)TSP問(wèn)題與蟻群尋徑行為比較：?jiǎn)栴}與蟻群尋徑行為比較：TSP問(wèn)題問(wèn)題蟻群尋徑行為蟻群尋徑行為解解路徑路徑尋優(yōu)過(guò)程尋優(yōu)過(guò)程選擇路徑選擇路徑最短路徑（最優(yōu)解）最短路徑（最優(yōu)解）最短路徑最短路徑第12頁(yè)/共39頁(yè)在在20世紀(jì)世紀(jì)90年代，意大利學(xué)者年代，意大利學(xué)者Dorigo等人從生物進(jìn)化的機(jī)理中受到啟發(fā)，等

11、人從生物進(jìn)化的機(jī)理中受到啟發(fā)，通過(guò)模擬自然界螞蟻尋徑的行為，提出了一種全新的模擬進(jìn)化算法，通過(guò)模擬自然界螞蟻尋徑的行為，提出了一種全新的模擬進(jìn)化算法，蟻蟻群優(yōu)化算法群優(yōu)化算法。并用該方法求解。并用該方法求解TSP問(wèn)題（及其他組合優(yōu)化問(wèn)題，如分配問(wèn)題（及其他組合優(yōu)化問(wèn)題，如分配問(wèn)題、問(wèn)題、Job-shop 調(diào)度問(wèn)題等），取得了一系列較好的實(shí)驗(yàn)結(jié)果。調(diào)度問(wèn)題等），取得了一系列較好的實(shí)驗(yàn)結(jié)果。 第13頁(yè)/共39頁(yè)蟻群優(yōu)化算法的核心思想有三條：蟻群優(yōu)化算法的核心思想有三條：第一，選擇機(jī)制：跡越多的路徑，被選中的概率越大；第一，選擇機(jī)制：跡越多的路徑，被選中的概率越大；第二，跡更新機(jī)制：路徑越短，跡增加

12、越快；第二，跡更新機(jī)制：路徑越短，跡增加越快；第三，協(xié)作機(jī)制：個(gè)體之間通過(guò)跡進(jìn)行信息交流。第三，協(xié)作機(jī)制：個(gè)體之間通過(guò)跡進(jìn)行信息交流。第14頁(yè)/共39頁(yè)蟻群優(yōu)化算法實(shí)現(xiàn)（以蟻群優(yōu)化算法實(shí)現(xiàn)（以TSPTSP問(wèn)題為例）：?jiǎn)栴}為例）：第一步，第一步，初始化，將初始化，將m只螞蟻放入到只螞蟻放入到n個(gè)隨機(jī)選擇的城市中。個(gè)隨機(jī)選擇的城市中。第二步，第二步，選擇機(jī)制：選擇機(jī)制：每一只螞蟻每一步的行動(dòng)是，根據(jù)一定的依據(jù)選擇下一個(gè)每一只螞蟻每一步的行動(dòng)是，根據(jù)一定的依據(jù)選擇下一個(gè)它還沒(méi)有訪問(wèn)的城市；它還沒(méi)有訪問(wèn)的城市；第三步，第三步，跡更新機(jī)制：跡更新機(jī)制：在完成一步（從一個(gè)城市到達(dá)另外一個(gè)城市）或者一個(gè)在完

13、成一步（從一個(gè)城市到達(dá)另外一個(gè)城市）或者一個(gè)循環(huán)（完成對(duì)所有循環(huán)（完成對(duì)所有n個(gè)城市的訪問(wèn)）后，更新所有路徑上的殘留信息濃度。個(gè)城市的訪問(wèn)）后，更新所有路徑上的殘留信息濃度。 第四步，第四步，判斷是否停止算法，停止則輸出最優(yōu)結(jié)果；否則，返回判斷是否停止算法，停止則輸出最優(yōu)結(jié)果；否則，返回第二步第二步。第15頁(yè)/共39頁(yè)選擇機(jī)制，選擇下一個(gè)城市的依據(jù)主要是兩點(diǎn)：選擇機(jī)制，選擇下一個(gè)城市的依據(jù)主要是兩點(diǎn)：1）t 時(shí)刻連接城市時(shí)刻連接城市 i 和和 j 的路徑上殘留信息（跡）的濃度的路徑上殘留信息（跡）的濃度 。2）由城市）由城市 i 轉(zhuǎn)移到城市轉(zhuǎn)移到城市 j 的啟發(fā)信息，該啟發(fā)信息是由要解決的問(wèn)題

14、給出的的啟發(fā)信息，該啟發(fā)信息是由要解決的問(wèn)題給出的 ，在，在TSP問(wèn)題中一般取問(wèn)題中一般取 ，其中，其中， 表示城市表示城市 i，j 間的距離，間的距離， 在這里可以稱為先驗(yàn)知識(shí)。在這里可以稱為先驗(yàn)知識(shí)。 tijijijijd1ijdij第16頁(yè)/共39頁(yè)選擇機(jī)制，選擇機(jī)制，那么，那么，t 時(shí)刻位于城市時(shí)刻位于城市 i 的螞蟻的螞蟻 k 選擇城市選擇城市 j 為目標(biāo)城市的概率是：為目標(biāo)城市的概率是： kiNlililijijkijtttPkiNj ：殘留信息的相對(duì)重要程度；：殘留信息的相對(duì)重要程度；：?jiǎn)l(fā)信息的相對(duì)重要程度；：?jiǎn)l(fā)信息的相對(duì)重要程度；：所有可能的目標(biāo)城市，即還沒(méi)：所有可能的目標(biāo)

15、城市，即還沒(méi)有訪問(wèn)的城市。為了避免對(duì)同有訪問(wèn)的城市。為了避免對(duì)同一個(gè)城市的多次訪問(wèn)，每一只一個(gè)城市的多次訪問(wèn)，每一只螞蟻都保存一個(gè)列表螞蟻都保存一個(gè)列表tabu(k)，用于記錄到目前為止已經(jīng)訪問(wèn)用于記錄到目前為止已經(jīng)訪問(wèn)的城市；的城市；：t時(shí)刻螞蟻由時(shí)刻螞蟻由 i 城市到城市到 j 城市的概城市的概率。率。 kiN tPkij第17頁(yè)/共39頁(yè)跡更新機(jī)制，跡更新機(jī)制，為了避免殘留信息過(guò)多引起的殘留信息淹沒(méi)啟發(fā)信息的問(wèn)題，在每一只螞蟻完為了避免殘留信息過(guò)多引起的殘留信息淹沒(méi)啟發(fā)信息的問(wèn)題，在每一只螞蟻完成對(duì)所有成對(duì)所有n個(gè)城市的訪問(wèn)后（也即一個(gè)循環(huán)結(jié)束后）或每走一步（從一個(gè)城市個(gè)城市的訪問(wèn)后（也

16、即一個(gè)循環(huán)結(jié)束后）或每走一步（從一個(gè)城市到下一個(gè)城市后），必須對(duì)殘留信息進(jìn)行更新處理，到下一個(gè)城市后），必須對(duì)殘留信息進(jìn)行更新處理， Morigo介紹三種跡更新機(jī)介紹三種跡更新機(jī)制：制：1）ant-cycle算法算法2）ant-density算法算法3）ant-quantity算法算法第18頁(yè)/共39頁(yè)跡更新機(jī)制跡更新機(jī)制ant-cycle算法，算法，在每一只螞蟻完成對(duì)所有在每一只螞蟻完成對(duì)所有n個(gè)城市的訪問(wèn)后，對(duì)舊的信息進(jìn)行削弱，將最新的個(gè)城市的訪問(wèn)后，對(duì)舊的信息進(jìn)行削弱，將最新的螞蟻訪問(wèn)路徑的信息加入螞蟻訪問(wèn)路徑的信息加入 。 ij mkkijijijtnt1kkijLQ/ ：殘留信息的保

17、留部分；：殘留信息的保留部分； ：殘留信息被削弱的部分，小于：殘留信息被削弱的部分，小于1； ：螞蟻：螞蟻k在時(shí)間段在時(shí)間段t到到t+n內(nèi)的訪問(wèn)過(guò)程中，在內(nèi)的訪問(wèn)過(guò)程中，在i到到j(luò)的路徑的路徑上留下的殘留信息濃度；上留下的殘留信息濃度；Q ：為常量；：為常量；Lk ：螞蟻：螞蟻k在本次循環(huán)中所選擇路徑的總長(zhǎng)度。在本次循環(huán)中所選擇路徑的總長(zhǎng)度。 1kij第19頁(yè)/共39頁(yè)跡更新機(jī)制跡更新機(jī)制ant-cycle算法，算法，kkijLQ/ ：螞蟻：螞蟻k在時(shí)間段在時(shí)間段t到到t+n內(nèi)的訪問(wèn)過(guò)程中，在內(nèi)的訪問(wèn)過(guò)程中，在i到到j(luò)的路徑的路徑上留下的殘留信息濃度；上留下的殘留信息濃度；Q ：為常量；：為常

18、量；Lk ：螞蟻：螞蟻k在本次循環(huán)中所選擇路徑的總長(zhǎng)度；如果沒(méi)有在本次循環(huán)中所選擇路徑的總長(zhǎng)度；如果沒(méi)有選擇選擇i到到j(luò)的路徑，則的路徑，則 kij0kij第20頁(yè)/共39頁(yè)跡更新機(jī)制跡更新機(jī)制ant-density算法，算法，在每一只螞蟻完成下一個(gè)個(gè)城市的訪問(wèn)后，對(duì)舊的信息進(jìn)行削弱，將最新的螞在每一只螞蟻完成下一個(gè)個(gè)城市的訪問(wèn)后，對(duì)舊的信息進(jìn)行削弱，將最新的螞蟻訪問(wèn)路徑的信息加入蟻訪問(wèn)路徑的信息加入 。 ij mkkijijijtt11Qkij0kij螞蟻螞蟻k選擇選擇i到到j(luò)的路徑的路徑螞蟻螞蟻k沒(méi)有選擇沒(méi)有選擇i到到j(luò)的路徑的路徑第21頁(yè)/共39頁(yè)跡更新機(jī)制跡更新機(jī)制ant-quanti

19、ty算法，算法，在每一只螞蟻完成下一個(gè)個(gè)城市的訪問(wèn)后，對(duì)舊的信息進(jìn)行削弱，將最新的螞在每一只螞蟻完成下一個(gè)個(gè)城市的訪問(wèn)后，對(duì)舊的信息進(jìn)行削弱，將最新的螞蟻訪問(wèn)路徑的信息加入蟻訪問(wèn)路徑的信息加入 。 ij mkkijijijtt11ijkijdQ/0kij螞蟻螞蟻k選擇選擇i到到j(luò)的路徑的路徑螞蟻螞蟻k沒(méi)有選擇沒(méi)有選擇i到到j(luò)的路徑的路徑第22頁(yè)/共39頁(yè)跡更新機(jī)制跡更新機(jī)制三種算法的比較，三種算法的比較，ant-cycle算法的效果最好，這是因?yàn)樗玫氖撬惴ǖ男Ч詈?，這是因?yàn)樗玫氖侨中畔⑷中畔/Lk；ant-density、ant-quantity算法用的是算法用的是局部信息局部信息

20、Q、Q/dij。 第23頁(yè)/共39頁(yè)跡更新機(jī)制跡更新機(jī)制優(yōu)點(diǎn)：優(yōu)點(diǎn)：1）保證了殘留信息不至于無(wú)限累積，如果路徑?jīng)]有被選中，那么上面的）保證了殘留信息不至于無(wú)限累積，如果路徑?jīng)]有被選中，那么上面的殘留信息會(huì)隨時(shí)間的推移而逐漸減弱，這使算法能殘留信息會(huì)隨時(shí)間的推移而逐漸減弱，這使算法能“忘記忘記”不好的不好的路徑；路徑；2）即使路徑經(jīng)常被訪問(wèn)也不至于因?yàn)椋┘词孤窂浇?jīng)常被訪問(wèn)也不至于因?yàn)?的累積，而產(chǎn)生的累積，而產(chǎn)生 使啟使啟發(fā)信息的作用無(wú)法體現(xiàn)。發(fā)信息的作用無(wú)法體現(xiàn)。 ijijij第24頁(yè)/共39頁(yè)NC=0，將，將m只螞蟻放到只螞蟻放到n個(gè)節(jié)點(diǎn)上個(gè)節(jié)點(diǎn)上開(kāi)始開(kāi)始對(duì)所有螞蟻置初始城市到對(duì)所有螞蟻置初始城市到tabu（k）NC=MAX嗎？嗎？對(duì)所有螞蟻計(jì)算概率，選擇下一個(gè)城市并將對(duì)所有螞蟻計(jì)算概率，選擇下一個(gè)城市并將螞蟻移到下一個(gè)城市螞蟻移到下一個(gè)城市j，將，將j加入到加入到tabu（k）tabu（k）滿