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

1、現(xiàn)代智能優(yōu)化算法 顏學(xué)峰實(shí)驗(yàn)十六樓415房間Email：華東理工大學(xué)信息學(xué)院自動化研究所二八年 十 月現(xiàn)代智能優(yōu)化算法模擬退火遺傳算法蟻群優(yōu)化算法蟻群優(yōu)化算法螞蟻生物行為螞蟻搬家，天要下雨。螞蟻群體行為。相互協(xié)作的一群螞蟻可以戰(zhàn)勝比自己強(qiáng)壯的昆蟲，并把它搬回巢；而單個螞蟻則不能。相互協(xié)作的一群螞蟻可以很容易找到從蟻巢到食物源的最短路徑，而單個螞蟻則不能。此外，螞蟻還能夠適應(yīng)環(huán)境的變化，例如在蟻群的運(yùn)動路線上突然出現(xiàn)障礙物時，它們能夠很快地重新找到最優(yōu)路徑。不但引起昆蟲學(xué)家，而且也引起數(shù)學(xué)及計算機(jī)方面的專家和工程師的興趣。蟻群優(yōu)化算法螞蟻生物行為昆蟲學(xué)家通過大量的研究發(fā)現(xiàn)：螞蟻個體之間是通過信息

2、交流達(dá)到找到從蟻巢到食物源的最短路徑的目的。螞蟻個體通過在其所經(jīng)過的路上留下一種稱之為“信息素”（pheromone）或“跡”的物質(zhì)來實(shí)現(xiàn)與同伴之間的信息傳遞。隨后的螞蟻遇到信息素時，不僅能檢測出該物質(zhì)的存在以及量的多少，而且可根據(jù)信息素的濃度來指導(dǎo)自己對前進(jìn)方向的選擇。蟻群優(yōu)化算法螞蟻生物行為信息素隨著時間的推移會逐漸揮發(fā)掉，于是路徑的長短及其螞蟻的多少就對殘余信息素的強(qiáng)度產(chǎn)生影響，反過來信息素的強(qiáng)弱又指導(dǎo)著其它螞蟻的行動方向。因此，某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。這就構(gòu)成了螞蟻群體行為表現(xiàn)出的一種信息正反饋現(xiàn)象，并實(shí)現(xiàn)找到蟻巢到食物源的最短路徑。蟻群優(yōu)化算法螞蟻生

3、物行為蟻群實(shí)現(xiàn)找到蟻巢到食物源的最短路徑示意圖障礙物ABCDEHd=1d=1d=0.5d=0.5圖1圖1中設(shè)A是蟻巢，E是食物源，H、C為障礙物，由于障礙物的存在，由A外出覓食或由E返回巢穴的螞蟻只能經(jīng)由H或C到達(dá)目的地。BH和HD距離為1單位，BC和DC距離為0.5單位。假設(shè)螞蟻以“1單位長度/單位時間”的速度往返于A和E，每經(jīng)過一個單位時間各有30只螞蟻離開A和E到達(dá)B和D。 蟻群優(yōu)化算法螞蟻生物行為蟻群實(shí)現(xiàn)找到蟻巢到食物源的最短路徑示意圖障礙物ABCDEH15151515初始時，各有30只螞蟻在B和D點(diǎn)遇到障礙物，開始選擇路徑。由于此時路徑上無跡，螞蟻便以相同的概率隨機(jī)地走兩條路中的任意

4、一條，因而15只選往H，15只選往C（圖2）。經(jīng)過一個單位時間以后，路徑BHD被15只螞蟻爬過，而路徑BCD上則被30只螞蟻爬過，BCD上的信息量是BHD上信息量的兩倍。 圖2蟻群優(yōu)化算法螞蟻生物行為蟻群實(shí)現(xiàn)找到蟻巢到食物源的最短路徑示意圖障礙物ABCDEH10102020圖3此時，又有30只螞蟻離開B和D，于是20只選擇往C方向，而另外10只則選往H（圖3）。這樣，更多的信息量被留在更短的路徑BCD上。隨著時間的推移和上述過程的重復(fù)，短路徑上的信息量便以更快的速度增長，于是會有越來越多的螞蟻選擇這條短路徑，以致最終完全選擇這條短路徑BCD。 相對弱小，功能并不強(qiáng)大的個體是完成復(fù)雜的工作。蟻群

5、優(yōu)化算法算法提出一個著名的組合優(yōu)化問題：旅行商問題（TSP, traveling salesman problem），一個商人欲到 n 個城市推銷商品，每個兩個城市 i 和 j 之間的距離為 dij ，如何選擇一條道路使得商人每個城市走一遍后回到起點(diǎn)且所走路徑最短。蟻群優(yōu)化算法算法提出一般旅行商問題TSP，數(shù)學(xué)模型描述：選擇 ij 路線為1，否則為0避免產(chǎn)生回路走入城市j只有一次從城市i出發(fā)只有一次蟻群優(yōu)化算法算法提出例子，一般旅行商TSP問題的解。ABDEC如圖所示，從A城市出發(fā)回到A城市一個TSP問題的解是ABCEDA，即圖中紅色線條路徑。這個解滿足以上四個約束條件。蟻群優(yōu)化算法算法提出N

6、P問題：至今為止，還沒有一個有能求得最優(yōu)解的多項(xiàng)式時間算法的組合優(yōu)化問題稱為NP問題。TSP問題就是一個著名的NP問題。在如何解決這個問題方面已經(jīng)有了大量的研究。這其中包括遺傳算法，退火算法，動態(tài)規(guī)劃等等。蟻群優(yōu)化算法算法提出TSP問題與蟻群尋徑行為比較：TSP問題蟻群尋徑行為解路徑尋優(yōu)過程選擇路徑最短路徑（最優(yōu)解）最短路徑蟻群優(yōu)化算法算法提出在20世紀(jì)90年代，意大利學(xué)者Dorigo等人從生物進(jìn)化的機(jī)理中受到啟發(fā)，通過模擬自然界螞蟻尋徑的行為，提出了一種全新的模擬進(jìn)化算法，蟻群優(yōu)化算法。并用該方法求解TSP問題（及其他組合優(yōu)化問題，如分配問題、Job-shop 調(diào)度問題等），取得了一系列較好

7、的實(shí)驗(yàn)結(jié)果。 蟻群優(yōu)化算法算法提出蟻群優(yōu)化算法的核心思想有三條：第一，選擇機(jī)制：跡越多的路徑，被選中的概率越大；第二，跡更新機(jī)制：路徑越短，跡增加越快；第三，協(xié)作機(jī)制：個體之間通過跡進(jìn)行信息交流。蟻群優(yōu)化算法算法流程蟻群優(yōu)化算法實(shí)現(xiàn)（以TSP問題為例）：第一步，初始化，將m只螞蟻放入到n個隨機(jī)選擇的城市中。第二步，選擇機(jī)制：每一只螞蟻每一步的行動是，根據(jù)一定的依據(jù)選擇下一個它還沒有訪問的城市；第三步，跡更新機(jī)制：在完成一步（從一個城市到達(dá)另外一個城市）或者一個循環(huán)（完成對所有n個城市的訪問）后，更新所有路徑上的殘留信息濃度。 第四步，判斷是否停止算法，停止則輸出最優(yōu)結(jié)果；否則，返回第二步。蟻群

8、優(yōu)化算法算法流程選擇機(jī)制，選擇下一個城市的依據(jù)主要是兩點(diǎn)：1）t 時刻連接城市 i 和 j 的路徑上殘留信息（跡）的濃度 。2）由城市 i 轉(zhuǎn)移到城市 j 的啟發(fā)信息，該啟發(fā)信息是由要解決的問題給出的 ，在TSP問題中一般取 ，其中， 表示城市 i，j 間的距離， 在這里可以稱為先驗(yàn)知識。 蟻群優(yōu)化算法算法流程選擇機(jī)制，那么，t 時刻位于城市 i 的螞蟻 k 選擇城市 j 為目標(biāo)城市的概率是： ：殘留信息的相對重要程度；：啟發(fā)信息的相對重要程度；：所有可能的目標(biāo)城市，即還沒有訪問的城市。為了避免對同一個城市的多次訪問，每一只螞蟻都保存一個列表tabu(k)，用于記錄到目前為止已經(jīng)訪問的城市；：

9、t時刻螞蟻由 i 城市到 j 城市的概率。 蟻群優(yōu)化算法算法流程跡更新機(jī)制，為了避免殘留信息過多引起的殘留信息淹沒啟發(fā)信息的問題，在每一只螞蟻完成對所有n個城市的訪問后（也即一個循環(huán)結(jié)束后）或每走一步（從一個城市到下一個城市后），必須對殘留信息進(jìn)行更新處理， Morigo介紹三種跡更新機(jī)制：1）ant-cycle算法2）ant-density算法3）ant-quantity算法蟻群優(yōu)化算法算法流程跡更新機(jī)制ant-cycle算法，在每一只螞蟻完成對所有n個城市的訪問后，對舊的信息進(jìn)行削弱，將最新的螞蟻訪問路徑的信息加入 。 ：殘留信息的保留部分； ：殘留信息被削弱的部分，小于1； ：螞蟻k在時

10、間段t到t+n內(nèi)的訪問過程中，在i到j(luò)的路徑上留下的殘留信息濃度；Q ：為常量；Lk ：螞蟻k在本次循環(huán)中所選擇路徑的總長度。 蟻群優(yōu)化算法算法流程跡更新機(jī)制ant-cycle算法， ：螞蟻k在時間段t到t+n內(nèi)的訪問過程中，在i到j(luò)的路徑上留下的殘留信息濃度；Q ：為常量；Lk ：螞蟻k在本次循環(huán)中所選擇路徑的總長度；如果沒有選擇i到j(luò)的路徑，則 蟻群優(yōu)化算法算法流程跡更新機(jī)制ant-density算法，在每一只螞蟻完成下一個個城市的訪問后，對舊的信息進(jìn)行削弱，將最新的螞蟻訪問路徑的信息加入 。 螞蟻k選擇i到j(luò)的路徑螞蟻k沒有選擇i到j(luò)的路徑蟻群優(yōu)化算法算法流程跡更新機(jī)制ant-quant

11、ity算法，在每一只螞蟻完成下一個個城市的訪問后，對舊的信息進(jìn)行削弱，將最新的螞蟻訪問路徑的信息加入 。 螞蟻k選擇i到j(luò)的路徑螞蟻k沒有選擇i到j(luò)的路徑蟻群優(yōu)化算法算法流程跡更新機(jī)制三種算法的比較，ant-cycle算法的效果最好，這是因?yàn)樗玫氖侨中畔/Lk；ant-density、ant-quantity算法用的是局部信息Q、Q/dij。 蟻群優(yōu)化算法算法流程跡更新機(jī)制優(yōu)點(diǎn)：1）保證了殘留信息不至于無限累積，如果路徑?jīng)]有被選中，那么上面的殘留信息會隨時間的推移而逐漸減弱，這使算法能“忘記”不好的路徑；2）即使路徑經(jīng)常被訪問也不至于因?yàn)?的累積，而產(chǎn)生 使啟發(fā)信息的作用無法體現(xiàn)。 蟻群

12、優(yōu)化算法算法流程N(yùn)C=0，將m只螞蟻放到n個節(jié)點(diǎn)上開始對所有螞蟻置初始城市到tabu（k）NC=MAX嗎？對所有螞蟻計算概率，選擇下一個城市并將螞蟻移到下一個城市j，將j加入到tabu（k）tabu（k）滿嗎？更新最佳路徑，清空tabu（k），NC=NC+1得到最佳路徑，結(jié)束算法流程框圖ant-cycle蟻群優(yōu)化算法算法流程算法復(fù)雜度：如果程序終止于NC次循環(huán)后，這個算法的復(fù)雜度為O（NC*n2*m）。一般情況下，m一般取值與n為同一數(shù)量級，因此整個算法的復(fù)雜度O（NC*n3） 蟻群優(yōu)化算法優(yōu)缺點(diǎn)優(yōu)點(diǎn)：1）正反饋，能迅速找到較好的解；2）分布式計算，可以避免過早地收斂；3）強(qiáng)啟發(fā)，能在早期的尋

13、優(yōu)中迅速找到合適（可行）的解；4）強(qiáng)魯棒性，對基本蟻群優(yōu)化算法稍加修改，便可以應(yīng)用于其他問題；5）易于與其他優(yōu)化算法結(jié)合，以改善其優(yōu)化性能。蟻群優(yōu)化算法優(yōu)缺點(diǎn)缺點(diǎn)：1）算法有眾多參數(shù)（如殘留信息的相對重要程度、啟發(fā)信息的相對重要程度、Q常數(shù)、殘留信息的保留部分）需要確定，并且算法對參數(shù)敏感；2）求解時間較長，蟻群算法的復(fù)雜度可以反映這一點(diǎn)；3）易出現(xiàn)停滯現(xiàn)象，即算法搜索進(jìn)行到一定程度后，所有個體發(fā)現(xiàn)的解都完全一致，不能對解空間進(jìn)一步進(jìn)行搜索。蟻群優(yōu)化算法改進(jìn)蟻群算法的各種改進(jìn)：1）MAX-MIN ANT SYSTEM （MMAS）算法2）自適應(yīng)蟻群優(yōu)化算法3）自適應(yīng)調(diào)整信息素的蟻群算法4）自適

14、應(yīng)調(diào)整 （殘留信息的保留部分）的蟻群算法5）帶雜交算子的蟻群算法6）在解決TSP問題分段算法Section_MMMAS7）在解決TSP問題相遇算法MMMAS蟻群優(yōu)化算法改進(jìn)1）MAX-MIN ANT SYSTEM （MMAS）算法只對最佳路徑增加跡的濃度，從而更好地利用了歷史信息；為了避免算法過早收斂于并非全局最優(yōu)的解，將各條路徑可能的跡濃度限制于 ，超出這個范圍的值被強(qiáng)制設(shè)為 或者為 ，可以有效地避免某條路徑上的信息量遠(yuǎn)大于其余路徑，使得所有的螞蟻都集中到同一條路徑上；將各條路徑上跡的初始濃度設(shè)為 ，這樣便可以更加充分地進(jìn)行尋優(yōu)。 蟻群優(yōu)化算法改進(jìn)2）自適應(yīng)蟻群優(yōu)化算法問題：蟻群算法的主要依

15、據(jù)是信息正反饋原理和某種啟發(fā)式算法的有機(jī)結(jié)合。在構(gòu)造解的過程中，利用隨機(jī)選擇策略，這種選擇策略使得進(jìn)化速度慢；正反饋原理旨在強(qiáng)化性能較好的解，卻容易出現(xiàn)停滯現(xiàn)象。解決：從選擇策略方面進(jìn)行修改，采用確定性選擇和隨機(jī)選擇相結(jié)合的選擇策略，并在搜索過程中動態(tài)地調(diào)整確定性選擇的概率。進(jìn)化到一定代數(shù)后，進(jìn)化方向已經(jīng)基本確定，這時對路徑上信息量作動態(tài)調(diào)整，縮小最好和最差路徑上的信息兩的差距，并適當(dāng)增大隨機(jī)選擇的概率，以利于對解空間的更完全搜索。蟻群優(yōu)化算法改進(jìn)2）自適應(yīng)蟻群優(yōu)化算法該算法由下式確定螞蟻 k 從 i 城市轉(zhuǎn)移到 s 城市：蟻群優(yōu)化算法改進(jìn)3）自適應(yīng)調(diào)整信息素的蟻群算法問題：蟻群算法的主要依據(jù)

16、是信息正反饋原理和某種啟發(fā)式算法的有機(jī)結(jié)合。在構(gòu)造解的過程中，利用隨機(jī)選擇策略，這種選擇策略使得進(jìn)化速度慢；正反饋原理旨在強(qiáng)化性能較好的解，卻容易出現(xiàn)停滯現(xiàn)象。解決：根據(jù)搜索進(jìn)展情況，動態(tài)修改需要增加的信息素的方法。算法采用時變函數(shù)Q（t）來替代調(diào)整信息素 中常量Q，即 ， Q（t）隨著人工螞蟻搜索過程做實(shí)時的調(diào)整和變化蟻群優(yōu)化算法改進(jìn)3）自適應(yīng)調(diào)整信息素的蟻群算法自適應(yīng)調(diào)整策略：通過對算法的監(jiān)控，實(shí)時判斷算法的搜索狀態(tài)，如果一段時間內(nèi)獲得的最優(yōu)解沒有變化，則減少要添加的信息素，即減少 中的Q（t）。Q（t）時變函數(shù)幾個例子，針對不同情況使用蟻群優(yōu)化算法改進(jìn)4）自適應(yīng)調(diào)整 （殘留信息的保留部分）的蟻群算法問題：當(dāng)問題規(guī)模比較大時，由于信息素的揮發(fā)系數(shù) 1- 的存在，使那些從未被搜索到的解上信息素會減少到接近于0，降低