《智能控制理論和方法》課件第7章

第7章蟻群算法及其在智能控制中的應(yīng)用7.1引言7.2蟻群覓食奧秘7.3基本人工蟻群算法7.4改進(jìn)的蟻群優(yōu)化算法7.5用蟻群算法求解JobShop問題

7.1引言

20世紀(jì)90年代意大利學(xué)者M(jìn)arcoDorigo等人通過觀察蟻群覓食的過程，發(fā)現(xiàn)眾多螞蟻在尋找食物的過程中，總能夠找到一條從螞蟻巢穴到食物源之間的最短路徑。M.Dorigo等人對(duì)這一發(fā)現(xiàn)產(chǎn)生了濃厚的研究興趣。于是，重新在實(shí)驗(yàn)室中對(duì)蟻群覓食行為進(jìn)行了實(shí)驗(yàn)，即當(dāng)蟻群在螞蟻巢穴和食物之間建立取食路徑后，人為地在螞蟻巢穴和食物之間設(shè)置一定的障礙物。研究發(fā)現(xiàn)，在人為設(shè)置障礙物之后，蟻群經(jīng)過一段時(shí)間的探索，又重新走出一條螞蟻巢穴到食物之間的最短路徑。通過對(duì)蟻群覓食機(jī)制的深入研究，M.Dorigo等人提出了蟻群算法[1]。進(jìn)一步的實(shí)驗(yàn)表明，蟻群算法具有正反饋、分布式計(jì)算以及貪婪的啟發(fā)式搜索等特點(diǎn)。這些特點(diǎn)為更好地解決復(fù)雜的組合優(yōu)化問題提供了可能。用這種算法來求解旅行商問題[2]，即TSP(TravelingSalesmanProblem)問題時(shí)，結(jié)果比較理想。

7.2蟻群覓食奧秘

7.2.1蟻群覓食

螞蟻屬節(jié)肢動(dòng)物門，昆蟲綱、膜翅目、蟻科，有成千上萬種。任何一種都是群體生活，建有獨(dú)特的螞蟻社會(huì)，具有合作、品級(jí)分化和個(gè)體利他等特點(diǎn)。

覓食是蟻群最重要且有趣的社會(huì)活動(dòng)之一

[3]。據(jù)昆蟲學(xué)家的觀察和研究，發(fā)現(xiàn)螞蟻食性甚雜，各種螞蟻喜歡不同的食物和取食方式。比如，當(dāng)弓背蟻屬(學(xué)名：Camponotus，又名巨山蟻屬、木匠蟻屬，俗稱木匠蟻、木蟻)的一只工蟻發(fā)現(xiàn)食物時(shí)，它在食物的周圍釋放一種分泌物作標(biāo)記，然后回巢，并一路釋放分泌物作為示蹤標(biāo)記。在巢內(nèi)，它以“搖擺表演”的方式告知同伴它發(fā)現(xiàn)了食物。隨即，巢穴內(nèi)的工蟻跟隨它或沿著分泌物的氣味來到食物源。如果食物源有足夠多的食物，就會(huì)吸引大批的工蟻一起涌向食物源，于是成百上千的工蟻在螞蟻巢穴和食物源之間來回忙碌，將食物搬運(yùn)回螞蟻巢穴。在蟻群取食一段時(shí)間后，人們發(fā)現(xiàn)，螞蟻竟然找到一條從螞蟻巢穴到食物源之間最短的路徑，并沿著這條路徑搬運(yùn)食物。當(dāng)人為地在上述路徑上設(shè)置一障礙物時(shí)，經(jīng)一段時(shí)間后，蟻群又能找到一條從螞蟻巢穴到食物源之間最短的搬運(yùn)食物路徑。圖7.1所示實(shí)驗(yàn)展示了螞蟻這一覓食行為。圖7.1(a)為螞蟻已經(jīng)在螞蟻巢穴與食物之間建立了最短的取食路徑AE(或EA)。圖7.1(b)為研究人員在圖7.1(a)所示的螞蟻取食路徑上設(shè)置一障礙物HC，從而使螞蟻的可取食路徑為AHE(或EHA)或ACE(或ECA)，螞蟻只能選其一。顯然，AHE路徑較ACE路徑長。圖7.1(c)為螞蟻經(jīng)過一段時(shí)間的探索、尋找，找到了食物源到螞蟻巢穴之間最短的取食路徑ACE(或ECA)。

小小的爬行螞蟻靠什么總能夠準(zhǔn)確尋找到最短的取食路徑？圖7.1在螞蟻取食路徑設(shè)置障礙的實(shí)驗(yàn)7.2.2蟻群的信息系統(tǒng)及使用機(jī)制

蟻群有著令人稱奇的信息系統(tǒng)，其中包括視覺、聲音、無聲語言及其有效的信息機(jī)制，特別是螞蟻獨(dú)門絕技的無聲語言及相應(yīng)的使用機(jī)制。研究發(fā)現(xiàn)，當(dāng)螞蟻外出覓食或在回巢穴的途中，它們都會(huì)釋放一種特殊的信息素(pheromone)氣味(通常稱信息素)來標(biāo)示行進(jìn)的軌跡，螞蟻用這種獨(dú)有的無聲語言來設(shè)置類似人類路標(biāo)的蟻蹤。有了示蹤的信息素，螞蟻就能順利回“家”。進(jìn)一步的研究發(fā)現(xiàn)，螞蟻在尋找食物過程中，在它們經(jīng)過的地方所留下的信息素，不僅能被同一蟻群中的其他螞蟻感知到，而且其強(qiáng)度也能被感知，螞蟻會(huì)傾向于沿信息素濃度較高的方向移動(dòng)，而移動(dòng)過程又會(huì)留下新的信息素，對(duì)原有的信息素進(jìn)行加強(qiáng)。如此，越多螞蟻經(jīng)過的路徑，信息素會(huì)越強(qiáng)，而后續(xù)的螞蟻選擇走該路徑的可能性也越大。最后，幾乎所有的螞蟻都走信息素最強(qiáng)的路徑?；谛畔⑺丶靶畔⑺氐氖褂脵C(jī)制，螞蟻就能在食物源和螞蟻巢穴之間建立一條最短的取食路徑。下面通過圖7.2，結(jié)合具體示例數(shù)據(jù)來說明蟻群在食物源和螞蟻巢穴之間建立一條最短的取食路徑的原理。圖7.2蟻群取食最短路徑產(chǎn)生示意圖在圖7.1(b)中，A是螞蟻巢穴，E是食物源，HC是障礙物。圖中有兩條路徑從螞蟻巢穴通向食物源，抽象其如圖7.2(a)所示，稱圖中的A-C-E(或E-C-A)為路徑Ⅰ；稱A-H-E(或E-H-A)為路徑Ⅱ。為方便說明，我們假定路徑Ⅱ的長度是路徑Ⅰ長度的兩倍，分別為2和1個(gè)單位長度?，F(xiàn)假設(shè)所有螞蟻在一個(gè)單位時(shí)間可移動(dòng)的距離為1單位長度。任何螞蟻在行走時(shí)，都會(huì)在1個(gè)單位長度上均勻留下濃度為1個(gè)單位的信息素。在t=0時(shí)刻前，上述兩條路徑上均無信息素，信息素量為0(也可以設(shè)為不為0的初始值)。

設(shè)t=0時(shí)刻，有20只螞蟻從A點(diǎn)出發(fā)，由于此時(shí)兩條路徑上的信息素相同均為0，所以20只螞蟻選擇兩條路徑的概率相等。不妨假設(shè)有10只螞蟻選擇了路徑Ⅰ，另外10只螞蟻選擇了路徑Ⅱ。在t=1時(shí)刻，第二批20只螞蟻從A點(diǎn)準(zhǔn)備出發(fā)，由于此時(shí)路徑Ⅱ上AH段和路徑Ⅰ上AC段的信息素相同，所以第二批20只準(zhǔn)備出發(fā)的螞蟻選擇兩條路徑的概率相等。不妨再假設(shè)有10只螞蟻選擇了路徑Ⅰ，另外10只螞蟻選擇了路徑Ⅱ。而此時(shí)，選擇路徑Ⅰ的第一批10只螞蟻已到達(dá)了食物源E，選擇路徑Ⅱ的第一批10只螞蟻也行進(jìn)1個(gè)單位的距離，到達(dá)H點(diǎn)。此時(shí)，路徑Ⅰ和路徑Ⅱ上面的信息素積累情況見圖7.2(b)。

在t=2時(shí)刻，第一批選擇路徑Ⅰ的10只螞蟻帶著食物以很大概率沿原路返回到A點(diǎn)，這些螞蟻在返回時(shí)每只螞蟻在路徑Ⅰ上又留下1個(gè)單位的信息素。而選擇路徑Ⅱ的第一批10只螞蟻也行進(jìn)1個(gè)單位的距離，到達(dá)E點(diǎn)即食物源處。同時(shí)，選擇路徑Ⅱ的第二批10只螞蟻也行進(jìn)1個(gè)單位的距離，到達(dá)H點(diǎn)。此時(shí)，路徑Ⅱ上AH段上累積20個(gè)單位的信息素，HE段上有10個(gè)單位的信息素。選擇路徑Ⅰ的第二批十只螞蟻到達(dá)食物源E點(diǎn)。此時(shí)，路徑Ⅰ上的信息素累積到30個(gè)單位。路徑Ⅰ和路徑Ⅱ上面的信息素積累情況見圖7.2(c)。當(dāng)?shù)谌?0只螞蟻從A點(diǎn)準(zhǔn)備出發(fā)，由于此時(shí)兩條路徑上的信息素不同，所以第三批20只螞蟻選擇兩條路徑的概率不相等。不妨假設(shè)有多于10只螞蟻選擇了路徑Ⅰ，剩余的螞蟻選擇了路徑Ⅱ。同時(shí)，第二批選擇路徑Ⅱ的十只螞蟻從食物源準(zhǔn)備返回蟻群巢穴，由于路徑Ⅰ上的信息素量大于路徑Ⅱ上的信息素量，故這批螞蟻中的大部分會(huì)選擇路徑Ⅰ返回巢穴。隨著時(shí)間推移，后續(xù)的螞蟻會(huì)以越來越大的概率選擇路徑Ⅰ，前往食物源E或攜帶食物返回蟻群巢穴。最終所有螞蟻以很大概率選擇路徑Ⅰ，前往食物源E或攜帶食物返回蟻群巢穴。蟻群從而在食物源和螞蟻巢穴之間建立起一條最短的取食路徑。注意，在這里我們假設(shè)信息素沒有揮發(fā)，每只螞蟻留下信息素的能力相同、方式相同。

7.3基本人工蟻群算法

7.3.1人工蟻群與真實(shí)蟻群

蟻群算法(ACO，AntColonyOptimization)是模擬螞蟻群體覓食行為的仿生優(yōu)化算法，由意大利學(xué)者M(jìn).Dorigo于1991年在他的博士論文中首次提出來。在蟻群算法中，需要建立與真實(shí)螞蟻對(duì)應(yīng)的人工蟻群概念。人工蟻群與真實(shí)蟻群有許多相同之處，也有一些不同之處。一方面，人工蟻群是真實(shí)蟻群行為特征的抽象，這種抽象體現(xiàn)在將真實(shí)蟻群覓食行為中最重要的信息機(jī)制賦予人工蟻群；另一方面，因人工蟻群是需要解決實(shí)際問題中的復(fù)雜優(yōu)化問題，為了能使蟻群算法更加有效，人工蟻群具備真實(shí)蟻群所不具備的一些特征。

1.真實(shí)蟻群和人工蟻群的異同

人工蟻群主要的行為特征都是源于真實(shí)蟻群的，故兩者具有下面的共性：

(1)人工蟻群和真實(shí)蟻群有相同的任務(wù)，就是尋找起點(diǎn)(蟻穴)和終點(diǎn)(食物源)之間的最優(yōu)解(最短路徑)。

(2)人工蟻群和真實(shí)蟻群都是相互合作的群體，最優(yōu)解(最短路徑)是整個(gè)蟻群中每個(gè)螞蟻個(gè)體相互協(xié)作，共同不斷探索的結(jié)果。

(3)人工蟻群和真實(shí)蟻群都是通過信息素進(jìn)行間接通信。

(4)人工蟻群還應(yīng)用了真實(shí)蟻群覓食過程中的正反饋機(jī)制。蟻群的正反饋機(jī)制使得問題的解向著全局最優(yōu)的方向不斷進(jìn)化，最終能夠有效地獲得相對(duì)較優(yōu)的解。

(5)人工蟻群和真實(shí)蟻群都存在著信息素?fù)]發(fā)機(jī)制。這種機(jī)制可以使螞蟻逐漸忘記過去，不會(huì)受過去經(jīng)驗(yàn)的過分約束，這有利于指引螞蟻向著新的方向進(jìn)行搜索，避免算法過早收斂。

(6)人工蟻群和真實(shí)蟻群都是基于概率轉(zhuǎn)移的局部搜索策略，即螞蟻在節(jié)點(diǎn)i基于概率轉(zhuǎn)移到節(jié)點(diǎn)j。螞蟻轉(zhuǎn)移時(shí)，所應(yīng)用的策略在時(shí)間和空間上是完全局部的。

2.人工蟻群的特征

人工蟻群主要的行為特征都是源于真實(shí)蟻群的，但是不完全等同于真實(shí)蟻群。從算法模型的角度出發(fā)，人工蟻群具有真實(shí)蟻群不具備的下列特性：

(1)人工蟻群生活在一個(gè)離散的空間中。它們的移動(dòng)，本質(zhì)上是從一個(gè)離散狀態(tài)向另一個(gè)離散狀態(tài)的變化。

(2)人工蟻群具有記憶它們過去行為的特征。

(3)人工螞蟻釋放信息素的量，是由蟻群所建立的問題解決方案優(yōu)劣程度的函數(shù)來決定。

(4)人工蟻群信息素更新的時(shí)間，隨問題的不同而變化，不反映真實(shí)蟻群的行為。如：有的人工蟻群算法模型中，人工蟻群算法在產(chǎn)生一個(gè)解后，才去改變解所對(duì)應(yīng)的路徑上信息素的量；在有的人工蟻群算法模型中，則是螞蟻只要做出一步選擇(即從當(dāng)前城市i選擇去城市j，在到達(dá)城市j)的同時(shí)就更新所選路段(ij)上信息素的量。

(5)為了改善算法的性能，對(duì)人工蟻群可以賦予一些特殊本領(lǐng)，如前瞻性、局部優(yōu)化、原路返回等。在一些應(yīng)用中，人工蟻群算法可以有局部更新能力。7.3.2基本人工蟻群算法原理

旅行商問題是數(shù)學(xué)領(lǐng)域中著名的問題之一。它假設(shè)有一個(gè)旅行商人要去n個(gè)城市，他需要規(guī)劃所要走的路徑，路徑規(guī)劃的目標(biāo)是必須經(jīng)歷所有n個(gè)城市，且所規(guī)劃路徑對(duì)應(yīng)的路程為最短。規(guī)劃路徑的限制是每個(gè)城市只能去一次，而且最后要回到原來出發(fā)的城市。顯然，TSP問題的本質(zhì)是一個(gè)組合優(yōu)化問題，該問題已經(jīng)被證明具有NP計(jì)算復(fù)雜性。所以，任何能使該問題求解且方法簡單的算法，都受到高度的評(píng)價(jià)和關(guān)注。本節(jié)結(jié)合求解TSP問題來介紹基本的人工蟻群算法的原理。基本蟻群算法求解旅行商問題的原理是：首先將m個(gè)人工螞蟻隨機(jī)地分布于多個(gè)城市，且每個(gè)螞蟻從所在城市出發(fā)，n步(螞蟻從當(dāng)前所在城市轉(zhuǎn)移到任何另一城市為一步)后，每個(gè)人工螞蟻回到出發(fā)的城市(也稱走出一條路徑)。如果m個(gè)人工螞蟻所走出的m條路徑對(duì)應(yīng)的路程中最短者不是TSP問題的最短路程，則重復(fù)這一過程，直至尋找到滿意的TSP問題的最短路程為止。在此迭代過程的一次循環(huán)中，任何一只螞蟻不僅要遵循約束即每個(gè)城市只能訪問一次，而且從當(dāng)前所在城市i以概率確定將要去訪問的下一個(gè)城市j。這個(gè)概率是它所在城市i與下一個(gè)要去城市j之間的距離dij以及城市i與城市j之間道路(這里把兩個(gè)城市i與j抽象為平面上兩個(gè)點(diǎn)，城市i與j之間的道路抽象為這兩個(gè)點(diǎn)之間的連線，稱其為邊，記為eij)上信息素量的函數(shù)。當(dāng)螞蟻確定好下一個(gè)要訪問的城市j，且到達(dá)這個(gè)城市j時(shí)，會(huì)以某種方式在這兩個(gè)城市之間的路段上釋放(貢獻(xiàn))信息素。7.3.3基本人工蟻群算法模型

為了說明算法，首先定義如下符號(hào)：

m：蟻群中螞蟻數(shù)量；

bi(t)：在t時(shí)刻位于城市i的螞蟻個(gè)數(shù)，

dij：城市i和城市j之間的距離；

ηij：城市i、j之間的能見度，反映由城市i轉(zhuǎn)移到城市j的啟發(fā)程度，這個(gè)量在蟻群算法運(yùn)行中保持不變；

τij：城市i和城市j之間邊eij上的信息素殘留強(qiáng)度；

Δτij：一次循環(huán)后邊eij上信息素的增量；

Δτkij：螞蟻k在一次循環(huán)中在邊eij上貢獻(xiàn)信息素的增量；

pkij：螞蟻k從當(dāng)前所在城市i前去訪問城市j的概率。

基本蟻群算法的流程如圖7.3所示。

初始化主要將m只人工螞蟻隨機(jī)分布在多個(gè)城市(當(dāng)m≥n時(shí)，有螞蟻的城市數(shù)最多為n；當(dāng)m<n時(shí)，有螞蟻的城市數(shù)最多為m。換句話說，初始化后有部分城市中是沒有螞蟻的)。

在t時(shí)刻(也可以視為一次循環(huán)中的第t步，t=0，1，2，…，n－1)，位于城市i中的螞蟻k選擇要轉(zhuǎn)移去城市j的概率pkij為(7.1)圖7.3基本蟻群算法流程圖在t時(shí)刻，位于城市i中的螞蟻k決定要轉(zhuǎn)移到城市j，在t+1時(shí)刻，螞蟻k轉(zhuǎn)移來到了城市j，則在邊eij上可貢獻(xiàn)的信息素量為Δτkij(t，t+1)，螞蟻k對(duì)邊eij上所貢獻(xiàn)信息素增量在t到t+1期間完成(螞蟻k對(duì)邊eij上所貢獻(xiàn)信息素增量也可以不在t到t+1期間完成，而是在一次循環(huán)結(jié)束后進(jìn)行。貢獻(xiàn)信息素增量的具體實(shí)現(xiàn)見后面內(nèi)容)，螞蟻轉(zhuǎn)移的同時(shí)，完成對(duì)邊eij上所貢獻(xiàn)信息素的添加。對(duì)任意兩個(gè)城市i，j之間道路對(duì)應(yīng)的邊eij信息素增量按照下式進(jìn)行：(7.2)螞蟻對(duì)本次循環(huán)所走過的邊eij上所貢獻(xiàn)信息素增量的實(shí)現(xiàn)也可以在本次循環(huán)結(jié)束時(shí)完成，即經(jīng)過n步，m個(gè)螞蟻同時(shí)各自完成一次循環(huán)，每個(gè)螞蟻給出了一個(gè)解決方案，每只螞蟻對(duì)所經(jīng)過的邊上信息素的貢獻(xiàn)量，是走出的解決方案即路徑對(duì)應(yīng)的路程長度的函數(shù)，每只螞蟻只要參照其對(duì)應(yīng)的禁忌表就知道本次循環(huán)的路徑，對(duì)該路徑對(duì)應(yīng)的每段邊上的信息素進(jìn)行調(diào)整，具體見公式(7.5)。

每完成一次循環(huán)，對(duì)截至當(dāng)前的結(jié)果進(jìn)行評(píng)估，如果滿足條件，則算法結(jié)束，否則，m個(gè)螞蟻再次進(jìn)入一次新的循環(huán)。在蟻群算法中，對(duì)Δτkij可以用不同的方式實(shí)現(xiàn)，對(duì)

Δτkij用不同的方式實(shí)現(xiàn)就產(chǎn)生不同的蟻群算法。M.Dorigo給出三種不同的模型，分別稱之為蟻密模型、蟻量模型和蟻周模型。7.3.4蟻群算法的蟻密模型、蟻量模型和蟻周模型

蟻群算法的蟻密模型、蟻量模型和蟻周模型的區(qū)別主要在于對(duì)Δτkij(t，t+1)調(diào)整方式的不同。在蟻密模型中，一只螞蟻k在經(jīng)過城市i、j之間邊eij時(shí)，對(duì)該邊eij所貢獻(xiàn)的信息素增量為常量，即每單位長度上為Q：(7.3)在蟻量模型中，一只螞蟻k在經(jīng)過城市i、j之間邊eij時(shí)，對(duì)該邊eij所貢獻(xiàn)的信息素增量為變量，即每單位長度上為Q/dij，它與城市i和城市j之間路段的長度dij有關(guān)，dij越小，則貢獻(xiàn)的信息素越多，具體為(7.4)以上兩種模型中，一只螞蟻k若從城市i選擇到達(dá)城市j，對(duì)兩城市之間邊eij上信息素貢獻(xiàn)的增量在螞蟻k經(jīng)過邊eij的同時(shí)完成。

在蟻群算法的蟻周模型中，一只螞蟻k在經(jīng)過城市i、j之間邊eij時(shí)，對(duì)邊eij上貢獻(xiàn)的信息素增量為每單位長度Q/Lk，Lk為螞蟻k在本次循環(huán)中所走出路徑對(duì)應(yīng)路程的長度，(7.5)在蟻周模型中，一只螞蟻k在一次循環(huán)中，若從城市i到達(dá)過城市j，對(duì)城市i、j之間邊eij上信息素貢獻(xiàn)的增量在本次循環(huán)結(jié)束時(shí)才進(jìn)行更新調(diào)整。顯然，螞蟻k表現(xiàn)越優(yōu)秀，Lk會(huì)越小，對(duì)所經(jīng)過路徑上信息素增量的貢獻(xiàn)會(huì)越大。以上幾個(gè)模型的主要區(qū)別在于信息素的更新策略，蟻周模型用的是全局信息，即完成一次循環(huán)后對(duì)所經(jīng)過整條路徑上的信息素進(jìn)行更新，整體性較強(qiáng)；而蟻量和蟻密兩種模型用的是局部信息，即螞蟻每完成一步后就對(duì)剛經(jīng)過路徑上的信息素進(jìn)行更新。由于蟻周模型中信息增量Δτkij(t+1)考慮了全局變化，因而很好地保證了殘留信息不至于無限積累，非最優(yōu)路徑會(huì)逐漸隨時(shí)間推移被忘記。

上述蟻量和蟻密模型的實(shí)現(xiàn)過程可以用偽碼表示如下：

(1)初始化。

置循環(huán)次數(shù)計(jì)數(shù)器Nc=0；

城市i與城市j之間邊eij上信息素初始值τij(t)=c;

城市i與城市j之間邊eij上信息素增量Δτij(t)=0;城市i與城市j之間的能見度ηij=l;

每一次循環(huán)始，置步數(shù)計(jì)數(shù)器t=0；

置禁忌表tabuk=，該表記錄一次循環(huán)過程螞蟻k(k=1，2，…，m)訪問過的城市，用它保障每個(gè)城市只訪問一次的約束；

設(shè)置禁忌表的索引s=1。

將m個(gè)人工螞蟻隨機(jī)分布在n個(gè)城市中(或這n個(gè)城市的一部分中)，并將分布的情況記錄在禁忌表中，具體如下：

fori=1tondo

fork=1tobi(t)do

tabuk(s)=i

(2)每只螞蟻建立一個(gè)解決方案即完成一次循環(huán)。

s=0

fori=1tondo

s=s+1

fork=1tobi(t)do

螞蟻k以概率pkij選擇城市j；

將螞蟻k轉(zhuǎn)移到城市j；

將螞蟻k到達(dá)的城市j加到螞蟻k的禁忌表，tabuk(s)=j；

計(jì)算螞蟻k對(duì)經(jīng)過的邊eij上信息素貢獻(xiàn)的增量，蟻密模型按式

(7.3)Δτkij(t，t+1)=Q計(jì)算，蟻量模型按式(7.4)Δτkij(t，t+1)=Q/dij計(jì)算；

按式τij(t，t+1)=ρτij(t)+Δτkij(t，t+1)更新螞蟻k經(jīng)過邊(ij)的信息素。

(3)依據(jù)禁忌表計(jì)算每只螞蟻k在本次循環(huán)所走出解決方案的路徑長度Lk。

(4)計(jì)算本次循環(huán)后所有螞蟻?zhàn)叱龅淖疃搪窂讲⑴c歷史上的最短路徑Ls比較，且將短路徑賦予Ls。

(5)評(píng)估最新計(jì)算結(jié)果。

如果循環(huán)次數(shù)大于算法運(yùn)行時(shí)設(shè)定的最大循環(huán)次數(shù)或最短路徑長度滿足預(yù)期，則算法運(yùn)行結(jié)束。

對(duì)于蟻周模型，由于螞蟻采用一次循環(huán)后對(duì)它所經(jīng)過的路徑上的信息素進(jìn)行更新。故螞蟻對(duì)所經(jīng)過路徑上信息素的更新按照下面進(jìn)行，其他同蟻量、蟻密模型。計(jì)算一次循環(huán)中螞蟻k所走出解決方案的路徑對(duì)應(yīng)路程長度Lk，

fork=1tomdo

Lk=0

fors=1tondo

Lk=Lk+L[tabuk(s－1)，tabuk(s)]{L(x，y)求城市x和城市y距離函數(shù)}

每次循環(huán)后每兩個(gè)城市之間邊上信息素增量為Δτij,且Δτij初始值置為0(i,j=1,2,…，n):

fork=1tomdo

fors=1tondo

蟻群算法在解決一些小規(guī)模的組合優(yōu)化比如TSP問題時(shí)，表現(xiàn)令人滿意，但是隨著問題規(guī)模的增加，蟻群算法很難在可接受的循環(huán)次數(shù)內(nèi)找出最優(yōu)解。為此，研究者針對(duì)蟻群算法的不足，進(jìn)行了大量的改進(jìn)研究工作。之后幾節(jié)中，將詳細(xì)介紹一些改進(jìn)的蟻群算法。7.3.5蟻群算法的參數(shù)

蟻群算法在其實(shí)現(xiàn)過程之中，有幾個(gè)參數(shù)(這些參數(shù)有α、β、m、Q、ρ)[4]需要設(shè)定其初值，這些參數(shù)初值的設(shè)定對(duì)算法的性能影響較大。

1.信息啟發(fā)因子α

信息啟發(fā)因子α反映了螞蟻在從城市i向城市j轉(zhuǎn)移時(shí)，這兩個(gè)城市之間道路(邊)上所累積的信息素在指導(dǎo)蟻群搜索中選擇從城市i向城市j轉(zhuǎn)移時(shí)的相對(duì)重要程度，反映了蟻群在路徑搜索中隨機(jī)性因素作用的強(qiáng)度。α值越大，螞蟻選擇以前走過的路徑的可能性越大，搜索的隨機(jī)性越弱。α值過大也可能使蟻群的搜索過早陷于局部最優(yōu)。

2.期望值啟發(fā)式因子β

期望值啟發(fā)式因子β反映螞蟻在搜索過程中啟發(fā)信息(即期望值ηij)在指導(dǎo)蟻群搜索中的相對(duì)重要程度。期望值啟發(fā)式因子β的大小反映了蟻群在道路搜索中先驗(yàn)性、確定性因素作用的強(qiáng)度，其值越大，螞蟻在某個(gè)局部點(diǎn)上選擇局部最短路徑的可能性越大。雖然它使搜索的收斂速度得以加快，但蟻群在最優(yōu)路徑的搜索過程中隨機(jī)性減弱，易于陷入局部最優(yōu)。

蟻群算法的全局尋優(yōu)性能首先要求蟻群的搜索過程必須有很強(qiáng)的隨機(jī)性，而蟻群算法的快速收斂性能又要求蟻群的搜索過程必須要有較高的確定性。因此，必須對(duì)與此密切相關(guān)的α、β兩者在隨機(jī)性和確定性進(jìn)行平衡。

3.螞蟻數(shù)m

蟻群算法是一種隨機(jī)搜索算法，它通過多個(gè)候選解組成群體的進(jìn)化過程來尋求最優(yōu)解，在這個(gè)進(jìn)化過程中，既需要每個(gè)個(gè)體的自適應(yīng)能力，更需要群體的相互協(xié)作，這個(gè)相互協(xié)作，通過個(gè)體之間的信息交流來完成。在TSP中，單個(gè)螞蟻在一次循環(huán)中所經(jīng)過的路徑為TSP問題的一個(gè)候選解，m個(gè)螞蟻在一次循環(huán)中所經(jīng)過的路徑，則為TSP問題的一個(gè)解子集。顯然，子集越大(即蟻群數(shù)量多)可以提高蟻群算法的全局搜索能力以及算法的穩(wěn)定性。然而，螞蟻數(shù)目較大時(shí)，會(huì)使大量的曾被搜索過的解(路徑)上的信息量的變化比較平均，信息正反饋的作用不明顯，搜索的隨機(jī)性雖然得到了加強(qiáng)，但收斂速度減慢。反之，子集較小(即蟻群數(shù)量少)，特別是當(dāng)要處理的問題規(guī)模比較大時(shí)，會(huì)使那些很少被搜索到的路段(或解)上的信息素量減小到接近于0，搜索的隨機(jī)性減弱，雖然收斂速度加快，但會(huì)使算法的全局性能降低，算法的穩(wěn)定性差，容易出現(xiàn)過早停滯現(xiàn)象。

4.信息素總量Q

在蟻群算法的蟻周模型中，信息素總信息量Q為螞蟻循環(huán)一周后向所經(jīng)過的路徑上釋放信息素的總量。Q越大，則螞蟻在已經(jīng)走過的路徑上信息素的累積加快，可以加強(qiáng)蟻群搜索時(shí)的正反饋性能，有助于算法的快速收斂。

5.信息素殘留系數(shù)ρ

在蟻群算法中，隨著時(shí)間的推移，螞蟻在道路上留下的信息素氣味將會(huì)逐漸消逝，用參數(shù)ρ表示信息素氣味消逝快慢程度(或稱信息素?fù)]發(fā)度)。信息素殘留系數(shù)ρ的大小直接關(guān)系到蟻群算法的全局搜索能力及其收斂速度。當(dāng)信息素殘留系數(shù)ρ過小，而要處理的問題規(guī)模比較大時(shí)，會(huì)使那些很少被搜索到的路段(或路徑)上的信息素量快速減小到接近于0，從而會(huì)降低算法的全局搜索能力；當(dāng)信息素殘留系數(shù)ρ過大時(shí)，以前搜索過的路徑被再次選擇的可能性過大，也會(huì)影響到算法的隨機(jī)性能和全局搜索能力。7.3.6用蟻群算法求解TSP問題仿真示例

1.20城市TSP問題的坐標(biāo)

20城市TSP問題的坐標(biāo)如下：

5.326，2.558;4.276，3.452;4.819，2.624;3.165，2.457;

0.915，3.921;4.637，6.026;1.524，2.261;3.447，2.111;

3.548，3.665;2.649，2.556;4.399，1.194;4.660，2.949;

1.479，4.440;5.036，0.244;2.830，3.140;1.072，3.454;

5.845，6.203;0.194，1.767;1.660，2.395;2.682，6.072

2.20城市TSP問題的仿真結(jié)果

取α=1，β=2，ρ=0.4，Q=80，m=20，循環(huán)次數(shù)設(shè)為4000次，實(shí)驗(yàn)共進(jìn)行10次，采用蟻密模型、蟻量模型、蟻周模型的仿真結(jié)果見表7.1。7.3.7基本蟻群算法的收斂性

蟻群算法在求解復(fù)雜優(yōu)化問題(尤其是離散優(yōu)化問題)方面具有優(yōu)越性，并得到廣泛應(yīng)用。但蟻群算法是一種仿生算法，對(duì)其收斂性的理論研究較薄弱。迄今為止，有關(guān)蟻群算法收斂性分析、證明的文獻(xiàn)[5，6，7，8，9，10，11，12]有限。本節(jié)引用文獻(xiàn)[10]，從解TSP問題的蟻群算法入手，對(duì)其收斂性進(jìn)行分析。

假設(shè)螞蟻都是從城市A出發(fā)，走遍其他城市后又回到城市A，且產(chǎn)生s個(gè)解決方案，也僅有s個(gè)解決方案，分別表示為l1，l2，…，ls，其對(duì)應(yīng)的路程長度分別為d1，d2，…，ds。為便于理解，假設(shè)從A出發(fā)又回到A的s條路徑為Al1A，Al2A,…，AlsA，如圖7.4所示。圖7.4從A出發(fā)最終回到A共s條路徑最優(yōu)路徑的數(shù)目分為下列兩種情況：

情況1：d1<d2≤d3≤…≤ds，即只有一條最優(yōu)路徑。

情況2：d1=d2=…=dr<dr+1≤dr+2≤…≤ds，即有r(r≤s)條最優(yōu)路徑。

m只螞蟻在s條路徑上往返爬行。依照蟻群算法，隨著時(shí)間的推移，大多數(shù)螞蟻選擇最短路徑。以下分析推導(dǎo)，證明隨著迭代次數(shù)的增加，求解TSP的蟻群算法選擇最短路徑的概率趨于1。

假設(shè)τik表示螞蟻爬行第k趟后，留在路徑li(1≤i≤s)上的平均信息素，pik表示螞蟻爬行第k趟后選擇路徑li(1≤i≤s)的平均概率。初始時(shí)刻，各條路徑上的信息素量均相等為常數(shù)C(C>0)。

定理1

當(dāng)α≥0，β≥0時(shí)，對(duì)于情況1，有τ1k>τ2k≥

…≥τsk，則p1k>p2k≥…≥psk；對(duì)于情況2，有τ1k=τ2k=

…=τrk>τr+1k≥…≥τsk，則p1k=p2k=…=prk>pr+1k≥…≥psk。

(1)情況1的證明：

由于有故可知又由于從而有

故以此類推，可以得到由數(shù)學(xué)歸納法可知，當(dāng)α≥0，β≥0時(shí)，有

(2)情況2的證明，與情況1的證明類似。

定理1說明，若有多條最短路，則這些最短路上的平均信息素量相等。因此，選擇這些最短路的平均概率也相等，并且每趟運(yùn)行完成后，最短路上的平均信息素量最多，選擇最短路的平均概率最大。

定理2

當(dāng)α≥1，β≥0時(shí),對(duì)于情況1，有p1,k>p1,k－1;

而對(duì)于情況2，則有p1,k+p2,k+…+pr,k>p1,k－1+p2,k－1+…+pr,k－1。

(1)情況1的證明：

因?yàn)橛?/p>

(2)情況2的證明,與情況1證明類似。

定理2說明，隨著時(shí)間的推移，選擇最短路徑的概率越來越大。

定理3

當(dāng)α≥1，β≥0時(shí)，

對(duì)于情況1，i>1，有而對(duì)于情況2，i>r，有(1)情況1的證明:由定理2可得且又由定理1，可知τ1,k－1>τi,k－1,所以有由d1<d2≤d3≤…≤ds，可知?jiǎng)t有又由定理2，可知p1,k－1>p1,0，所以有因?yàn)橛杏搔选?0,1),p1,i<1(i=1,2,…，k－2)，可知所以有令θ為常數(shù)且θ∈(0,1)，則有所以，當(dāng)i>1時(shí)可得即

(2)情況2的證明，與情況1證明類似。

定理4

當(dāng)α≥1，β≥0時(shí)，對(duì)于情況1，對(duì)于情況2，

(1)情況1證明：由定理3可知，當(dāng)i>1時(shí)，有所以有

(2)情況2的證明,與情況1證明類似。

7.4改進(jìn)的蟻群優(yōu)化算法

7.4.1帶精英策略的蟻群算法

對(duì)蟻群算法最早的一種改進(jìn)是帶精英策略(ElitistStrategy)的蟻群算法。其改進(jìn)的思想是在算法每次循環(huán)后，對(duì)目前為止已找出的最佳路徑給予額外的信息素增量，這將在接下去的下一次循環(huán)中對(duì)螞蟻更有吸引力。并將該路徑記為L*(全局最優(yōu)行程)，同時(shí)將經(jīng)過這些行程(或找出該路徑)的螞蟻記為“精英”。每次循環(huán)結(jié)束后，各路徑上的信息素按照下式進(jìn)行更新：(7.6)其中，δ是精英螞蟻的個(gè)數(shù)，L*是目前為止所找出的最優(yōu)路徑的長度。這種改進(jìn)型算法能夠以更快的速度獲得更好的解。但是，若選擇的精英螞蟻過多，對(duì)路徑的搜索可能會(huì)很快集中在極優(yōu)值附近，從而導(dǎo)致算法較早地收斂于局部次優(yōu)解，即所有螞蟻都沿著同一條路徑移動(dòng)，重復(fù)地建立相同的解決方案，導(dǎo)致搜索過早停滯，不能找出更好的方案。因此，需要確定適當(dāng)?shù)木⑽浵伒臄?shù)量。7.4.2基于優(yōu)化排序的蟻群算法

基于優(yōu)化排序的蟻群算法[13]原理是每次循環(huán)后，對(duì)每只螞蟻所走出的路徑按其長度進(jìn)行排序，,螞蟻對(duì)所走路徑上信息素增量的更新根據(jù)該螞蟻的排名位次進(jìn)行加權(quán)調(diào)整，其量正比于該螞蟻的排名次序。

而且只考慮路徑長度小的δ只優(yōu)秀螞蟻。此外，找出到目前為止最優(yōu)路徑螞蟻所經(jīng)過的邊，這些邊也將獲得額外的增量(這相當(dāng)于帶精英策略的蟻群算法中精英螞蟻的信息素更新)。在這樣一個(gè)帶精英和排序混合策略的設(shè)置中，軌跡上的信息素量根據(jù)下式進(jìn)行更新：

(7.7)其中，一次循環(huán)后排名前δ只優(yōu)秀螞蟻，其序號(hào)為k(k=1，2，…，δ)，Lk為序號(hào)為k的螞蟻?zhàn)哌^路徑的對(duì)應(yīng)的長度，δ為本次循環(huán)中的精英螞蟻個(gè)數(shù)，L*是最優(yōu)解對(duì)應(yīng)的長度，μ(0<μ<1)是加權(quán)系數(shù)。7.4.3最大—最小蟻群算法

1.最大—最小值蟻群算法

基本的蟻群算法，尤其是帶精英策略的蟻群算法，會(huì)將螞蟻搜索行為集中到最優(yōu)解附近，從而更容易發(fā)生早熟收斂行為。Thomas等人提出的最大—最小蟻群算法[14](MMAS，MAX-MINAntSystem)，在解決早熟收斂問題中取得了較好的效果。MMAS算法對(duì)蟻群算法的信息素更新方式進(jìn)行了改進(jìn)，它在每次循環(huán)之后，并不是所有螞蟻都進(jìn)行信息素更新，只構(gòu)造了最佳解的那只螞蟻(這只螞蟻可以是找出當(dāng)前循環(huán)中最優(yōu)解的螞蟻，也可以是找出自算法開始運(yùn)行以來最優(yōu)解的螞蟻)，有資格進(jìn)行信息素更新。為了進(jìn)一步避免出現(xiàn)早熟停滯現(xiàn)象，MMAS算法中對(duì)每條路徑的信息素濃度規(guī)定了最大最小值，取值范圍被限制在[τmin，τmax]，并在初始化每條路徑上，規(guī)定信息素值為上限值，從而提高了初始階段算法的搜索能力。MMAS蟻群算法對(duì)信息素的更新方法如下：(7.8)不管采用選擇螞蟻kibbest方案或選擇螞蟻kgbbest方案，都有可能導(dǎo)致搜索停滯。以TSP問題為例，當(dāng)兩個(gè)城市i，j之間的邊eij上的信息素明顯高于其他邊時(shí)，螞蟻會(huì)更傾向于選擇這個(gè)解元素。正反饋機(jī)制使得該解元素上的信息素會(huì)更進(jìn)一步增強(qiáng)，從而螞蟻將會(huì)重復(fù)建立同一個(gè)解，空間搜索將會(huì)停止。這一問題的根源在于某解上信息素與其他解上信息素的差異過大，且螞蟻趨向選擇信息素量大的邊。為此，MMAS算法對(duì)任意解上信息素量規(guī)定了最大τmax和最小τmin的限制，在算法運(yùn)行始終都有τmin≤τij(t)≤τmax，即在算法運(yùn)行中，若τij(t)>τmax則設(shè)置τij(t)=τmax，若τij(t)<τmin則設(shè)置τij(t)=τmin。前面提到，每條路徑上信息素值初始化為上限值τmax，從而提高初始階段算法的搜索能力。當(dāng)每條路徑上信息素值初始化為上限值τmax時(shí)，在第一次循環(huán)后，至多差(1－ρ)τmax(ρ為信息素殘留系數(shù))。第二次循環(huán)后，最優(yōu)解元素與其他邊上信息素至多差(1－ρ2)τmax。以此類推，由于ρ較大，故最優(yōu)解元素與其他邊上信息素差異不是很大。進(jìn)一步知道，螞蟻按照方程(7.1)的選擇概率將增加得更加緩慢，從而有利于螞蟻傾向于探索新的解。

2.最大—最小值蟻群算法仿真

對(duì)7.3.6節(jié)20城市TSP問題，采用最大—最小模型，每隔500次采樣，路徑上信息素的變化和最優(yōu)路徑的變化情況見圖7.5。

該20城市TSP問題，采用最大—最小模型，實(shí)驗(yàn)仿真結(jié)果見圖7.6。

3.蟻密、蟻量、蟻周和最大—最小值蟻群算法仿真對(duì)比

對(duì)7.3.6節(jié)20城市TSP問題，采用蟻密、蟻量、蟻周和最大—最小模型蟻群算法進(jìn)行仿真對(duì)比。α、β、ρ、Q和m取兩組不同值，循環(huán)次數(shù)仍設(shè)為4000次，實(shí)驗(yàn)共進(jìn)行10次，仿真結(jié)果見表7.2和表7.3。圖7.5每隔500次采樣路徑上信息素的變化和最優(yōu)路徑的變化情況圖7.620城市TSP問題采用最大—最小模型最短路徑示意圖

7.5用蟻群算法求解JobShop問題

7.5.1經(jīng)典JobShop問題的描述

1.經(jīng)典JobShop問題

JobShopSchedulingProblem(JSSP,JobShop調(diào)度問題)是車間生產(chǎn)調(diào)度[15，16]中最經(jīng)典的問題之一。一個(gè)n×m的JobShop問題可以描述為n個(gè)工件在m臺(tái)機(jī)器上進(jìn)行加工，且每個(gè)工件都有其明確的加工順序(稱其為工序)。

JobShop調(diào)度最基本約束條件如下：

(1)順序約束，工件的每道工序必須在它前面的工序加工完成后才能開始加工；

(2)在同一時(shí)刻，每個(gè)工件僅能在一臺(tái)機(jī)器上進(jìn)行加工；

(3)在同一時(shí)刻，每臺(tái)機(jī)器僅能對(duì)一個(gè)工件進(jìn)行加工。

JobShop調(diào)度目標(biāo)是找到最小化最大流程時(shí)間的工序處理序列，即設(shè)計(jì)的目標(biāo)函數(shù)是使完成所有工件工序加工的總時(shí)間最小。

JobShop問題的變量：

J：工件集合，J={j1，j2，…，jn}；

I：加工機(jī)器集合，I={i1，i2，…，im}；

o：加工工序集合，o={oxy｜x∈J，y∈I}，即某工件jx(1≤x≤n)在機(jī)器上iy(1≤y≤m)完成工藝加工；

Sj：工件加工順序向量，Sj=[ojp1，ojp2，…，ojpk]，j∈J，pi∈I(1≤i≤m)，且不違背順序約束。

tj：完成工件j各工序加工所需時(shí)間向量，tj={Δtjp1，Δtjp2,…,Δtjpk}，Δtjpi為完成工件j第pi(1≤i≤k≤m)工序所需要的時(shí)間。

2.JobShop調(diào)度問題析取圖描述

用基本蟻群算法求解JobShop調(diào)度問題的關(guān)鍵是將JobShop調(diào)度問題轉(zhuǎn)化為適合于蟻群算法的一個(gè)自然表達(dá)，TSP問題應(yīng)用蟻群算法求解的直觀形式是圖模式。可以考慮用類似圖的形式來建立JobShop調(diào)度問題的圖模型。

參照TSP問題圖模式，構(gòu)造JobShop調(diào)度問題的圖模型為

G=(N，A∪E)

其中N是圖中節(jié)點(diǎn)集合，每個(gè)節(jié)點(diǎn)代表工序集中的一個(gè)工序oxy;A為合取弧，表示同一工件各工序的加工順序方向，按照加工順序方向，合取弧均為單向箭頭(用單向弧表示);E是可以先后進(jìn)行加工的工序間的連接，構(gòu)成析取弧集(用連線表示)。G中每一合取弧的權(quán)值為所對(duì)應(yīng)起點(diǎn)工序的加工時(shí)間。

例如表7.4所示一個(gè)規(guī)模為3×3的JobShop問題。表7.4中元素可表示為t/Mi(o)形式，這里t表示工序o在機(jī)器上Mt的加工時(shí)間，比如，1/M1(1)表示工件1的工序1在1號(hào)機(jī)器上加工，并且它的加工時(shí)間為1個(gè)時(shí)間單位。該表給出3個(gè)工件共9個(gè)加工工序，統(tǒng)一編號(hào)為1，2，…，9，工序的集合為{1，2，3，4，5，6，7，8，9}。同時(shí)，每行自左至右也給出每個(gè)工件的加工順序，1/M1(