現(xiàn)代智能優(yōu)化算法

顏學(xué)峰實(shí)驗(yàn)十六樓415房間Email：xfyan@Tel:64253254(o)東理工大學(xué)信息學(xué)院自動(dòng)化研究所

二○○八年十月現(xiàn)代優(yōu)化算法-蟻群算法共39頁(yè)，您現(xiàn)在瀏覽的是第1頁(yè)!現(xiàn)代智能優(yōu)化算法模擬退火遺傳算法蟻群優(yōu)化算法現(xiàn)代優(yōu)化算法-蟻群算法共39頁(yè)，您現(xiàn)在瀏覽的是第2頁(yè)!蟻群優(yōu)化算法—螞蟻生物行為螞蟻搬家，天要下雨。螞蟻群體行為。相互協(xié)作的一群螞蟻可以戰(zhàn)勝比自己強(qiáng)壯的昆蟲，并把它搬回巢；而單個(gè)螞蟻則不能。相互協(xié)作的一群螞蟻可以很容易找到從蟻巢到食物源的最短路徑，而單個(gè)螞蟻則不能。此外，螞蟻還能夠適應(yīng)環(huán)境的變化，例如在蟻群的運(yùn)動(dòng)路線上突然出現(xiàn)障礙物時(shí)，它們能夠很快地重新找到最優(yōu)路徑。——不但引起昆蟲學(xué)家，而且也引起數(shù)學(xué)及計(jì)算機(jī)方面的專家和工程師的興趣?，F(xiàn)代優(yōu)化算法-蟻群算法共39頁(yè)，您現(xiàn)在瀏覽的是第3頁(yè)!蟻群優(yōu)化算法—螞蟻生物行為昆蟲學(xué)家通過(guò)大量的研究發(fā)現(xiàn)：螞蟻個(gè)體之間是通過(guò)信息交流達(dá)到找到從蟻巢到食物源的最短路徑的目的。螞蟻個(gè)體通過(guò)在其所經(jīng)過(guò)的路上留下一種稱之為“信息素”（pheromone）或“跡”的物質(zhì)來(lái)實(shí)現(xiàn)與同伴之間的信息傳遞。隨后的螞蟻遇到信息素時(shí)，不僅能檢測(cè)出該物質(zhì)的存在以及量的多少，而且可根據(jù)信息素的濃度來(lái)指導(dǎo)自己對(duì)前進(jìn)方向的選擇?，F(xiàn)代優(yōu)化算法-蟻群算法共39頁(yè)，您現(xiàn)在瀏覽的是第4頁(yè)!蟻群優(yōu)化算法—螞蟻生物行為蟻群實(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單位長(zhǎng)度/單位時(shí)間”的速度往返于A和E，每經(jīng)過(guò)一個(gè)單位時(shí)間各有30只螞蟻離開A和E到達(dá)B和D?，F(xiàn)代優(yōu)化算法-蟻群算法共39頁(yè)，您現(xiàn)在瀏覽的是第5頁(yè)!蟻群優(yōu)化算法—螞蟻生物行為蟻群實(shí)現(xiàn)找到蟻巢到食物源的最短路徑示意圖障礙物ABCDEH10102020圖3此時(shí)，又有30只螞蟻離開B和D，于是20只選擇往C方向，而另外10只則選往H（圖3）。這樣，更多的信息量被留在更短的路徑BCD上。隨著時(shí)間的推移和上述過(guò)程的重復(fù)，短路徑上的信息量便以更快的速度增長(zhǎng)，于是會(huì)有越來(lái)越多的螞蟻選擇這條短路徑，以致最終完全選擇這條短路徑BCD。相對(duì)弱小，功能并不強(qiáng)大的個(gè)體是完成復(fù)雜的工作?，F(xiàn)代優(yōu)化算法-蟻群算法共39頁(yè)，您現(xiàn)在瀏覽的是第6頁(yè)!蟻群優(yōu)化算法—算法提出一般旅行商問(wèn)題TSP，數(shù)學(xué)模型描述：選擇ij路線為1，否則為0避免產(chǎn)生回路走入城市j只有一次從城市i出發(fā)只有一次現(xiàn)代優(yōu)化算法-蟻群算法共39頁(yè)，您現(xiàn)在瀏覽的是第7頁(yè)!蟻群優(yōu)化算法—算法提出NP問(wèn)題：至今為止，還沒有一個(gè)有能求得最優(yōu)解的多項(xiàng)式時(shí)間算法的組合優(yōu)化問(wèn)題稱為NP問(wèn)題。TSP問(wèn)題就是一個(gè)著名的NP問(wèn)題。在如何解決這個(gè)問(wèn)題方面已經(jīng)有了大量的研究。這其中包括遺傳算法，退火算法，動(dòng)態(tài)規(guī)劃等等?，F(xiàn)代優(yōu)化算法-蟻群算法共39頁(yè)，您現(xiàn)在瀏覽的是第8頁(yè)!蟻群優(yōu)化算法—算法提出在20世紀(jì)90年代，意大利學(xué)者Dorigo等人從生物進(jìn)化的機(jī)理中受到啟發(fā)，通過(guò)模擬自然界螞蟻尋徑的行為，提出了一種全新的模擬進(jìn)化算法，蟻群優(yōu)化算法。并用該方法求解TSP問(wèn)題（及其他組合優(yōu)化問(wèn)題，如分配問(wèn)題、Job-shop調(diào)度問(wèn)題等），取得了一系列較好的實(shí)驗(yàn)結(jié)果?，F(xiàn)代優(yōu)化算法-蟻群算法共39頁(yè)，您現(xiàn)在瀏覽的是第9頁(yè)!蟻群優(yōu)化算法—算法流程蟻群優(yōu)化算法實(shí)現(xiàn)（以TSP問(wèn)題為例）：步，初始化，將m只螞蟻放入到n個(gè)隨機(jī)選擇的城市中。第二步，選擇機(jī)制：每一只螞蟻每一步的行動(dòng)是，根據(jù)一定的依據(jù)選擇下一個(gè)它還沒有訪問(wèn)的城市；第三步，跡更新機(jī)制：在完成一步（從一個(gè)城市到達(dá)另外一個(gè)城市）或者一個(gè)循環(huán)（完成對(duì)所有n個(gè)城市的訪問(wèn)）后，更新所有路徑上的殘留信息濃度。第四步，判斷是否停止算法，停止則輸出最優(yōu)結(jié)果；否則，返回第二步?，F(xiàn)代優(yōu)化算法-蟻群算法共39頁(yè)，您現(xiàn)在瀏覽的是第10頁(yè)!蟻群優(yōu)化算法—算法流程選擇機(jī)制，那么，t時(shí)刻位于城市i的螞蟻k選擇城市j為目標(biāo)城市的概率是：：殘留信息的相對(duì)重要程度；：?jiǎn)l(fā)信息的相對(duì)重要程度；：所有可能的目標(biāo)城市，即還沒有訪問(wèn)的城市。為了避免對(duì)同一個(gè)城市的多次訪問(wèn)，每一只螞蟻都保存一個(gè)列表tabu(k)，用于記錄到目前為止已經(jīng)訪問(wèn)的城市；：t時(shí)刻螞蟻由i城市到j(luò)城市的概率。現(xiàn)代優(yōu)化算法-蟻群算法共39頁(yè)，您現(xiàn)在瀏覽的是第11頁(yè)!蟻群優(yōu)化算法—算法流程跡更新機(jī)制——ant-cycle算法，在每一只螞蟻完成對(duì)所有n個(gè)城市的訪問(wèn)后，對(duì)舊的信息進(jìn)行削弱，將最新的螞蟻訪問(wèn)路徑的信息加入。：殘留信息的保留部分；：殘留信息被削弱的部分，小于1；：螞蟻k在時(shí)間段t到t+n內(nèi)的訪問(wèn)過(guò)程中，在i到j(luò)的路徑上留下的殘留信息濃度；Q：為常量；Lk：螞蟻k在本次循環(huán)中所選擇路徑的總長(zhǎng)度?，F(xiàn)代優(yōu)化算法-蟻群算法共39頁(yè)，您現(xiàn)在瀏覽的是第12頁(yè)!蟻群優(yōu)化算法—算法流程跡更新機(jī)制——ant-density算法，在每一只螞蟻完成下一個(gè)個(gè)城市的訪問(wèn)后，對(duì)舊的信息進(jìn)行削弱，將最新的螞蟻訪問(wèn)路徑的信息加入。螞蟻k選擇i到j(luò)的路徑螞蟻k沒有選擇i到j(luò)的路徑現(xiàn)代優(yōu)化算法-蟻群算法共39頁(yè)，您現(xiàn)在瀏覽的是第13頁(yè)!蟻群優(yōu)化算法—算法流程跡更新機(jī)制——三種算法的比較，ant-cycle算法的效果最好，這是因?yàn)樗玫氖侨中畔ⅰ猀/Lk；ant-density、ant-quantity算法用的是局部信息——Q、Q/dij?，F(xiàn)代優(yōu)化算法-蟻群算法共39頁(yè)，您現(xiàn)在瀏覽的是第14頁(yè)!蟻群優(yōu)化算法—算法流程N(yùn)C=0，將m只螞蟻放到n個(gè)節(jié)點(diǎn)上開始對(duì)所有螞蟻置初始城市到tabu（k）NC=MAX嗎？對(duì)所有螞蟻計(jì)算概率，選擇下一個(gè)城市并將螞蟻移到下一個(gè)城市j，將j加入到tabu（k）tabu（k）滿嗎？更新最佳路徑，清空tabu（k），NC=NC+1得到最佳路徑，結(jié)束算法流程框圖ant-cycle現(xiàn)代優(yōu)化算法-蟻群算法共39頁(yè)，您現(xiàn)在瀏覽的是第15頁(yè)!蟻群優(yōu)化算法—優(yōu)缺點(diǎn)優(yōu)點(diǎn)：1）正反饋，能迅速找到較好的解；2）分布式計(jì)算，可以避免過(guò)早地收斂；3）強(qiáng)啟發(fā)，能在早期的尋優(yōu)中迅速找到合適（可行）的解；4）強(qiáng)魯棒性，對(duì)基本蟻群優(yōu)化算法稍加修改，便可以應(yīng)用于其他問(wèn)題；5）易于與其他優(yōu)化算法結(jié)合，以改善其優(yōu)化性能?，F(xiàn)代優(yōu)化算法-蟻群算法共39頁(yè)，您現(xiàn)在瀏覽的是第16頁(yè)!蟻群優(yōu)化算法—改進(jìn)蟻群算法的各種改進(jìn)：1）MAX-MINANTSYSTEM（MMAS）算法2）自適應(yīng)蟻群優(yōu)化算法3）自適應(yīng)調(diào)整信息素的蟻群算法4）自適應(yīng)調(diào)整（殘留信息的保留部分）的蟻群算法5）帶雜交算子的蟻群算法6）在解決TSP問(wèn)題——分段算法Section_MMMAS7）在解決TSP問(wèn)題——相遇算法MMMAS現(xiàn)代優(yōu)化算法-蟻群算法共39頁(yè)，您現(xiàn)在瀏覽的是第17頁(yè)!蟻群優(yōu)化算法—改進(jìn)2）自適應(yīng)蟻群優(yōu)化算法問(wèn)題：蟻群算法的主要依據(jù)是信息正反饋原理和某種啟發(fā)式算法的有機(jī)結(jié)合。在構(gòu)造解的過(guò)程中，利用隨機(jī)選擇策略，這種選擇策略使得進(jìn)化速度慢；正反饋原理旨在強(qiáng)化性能較好的解，卻容易出現(xiàn)停滯現(xiàn)象。解決：從選擇策略方面進(jìn)行修改，采用確定性選擇和隨機(jī)選擇相結(jié)合的選擇策略，并在搜索過(guò)程中動(dòng)態(tài)地調(diào)整確定性選擇的概率。進(jìn)化到一定代數(shù)后，進(jìn)化方向已經(jīng)基本確定，這時(shí)對(duì)路徑上信息量作動(dòng)態(tài)調(diào)整，縮小最好和最差路徑上的信息兩的差距，并適當(dāng)增大隨機(jī)選擇的概率，以利于對(duì)解空間的更完全搜索。現(xiàn)代優(yōu)化算法-蟻群算法共39頁(yè)，您現(xiàn)在瀏覽的是第18頁(yè)!蟻群優(yōu)化算法—改進(jìn)3）自適應(yīng)調(diào)整信息素的蟻群算法問(wèn)題：蟻群算法的主要依據(jù)是信息正反饋原理和某種啟發(fā)式算法的有機(jī)結(jié)合。在構(gòu)造解的過(guò)程中，利用隨機(jī)選擇策略，這種選擇策略使得進(jìn)化速度慢；正反饋原理旨在強(qiáng)化性能較好的解，卻容易出現(xiàn)停滯現(xiàn)象。解決：根據(jù)搜索進(jìn)展情況，動(dòng)態(tài)修改需要增加的信息素的方法。算法采用時(shí)變函數(shù)Q（t）來(lái)替代調(diào)整信息素中常量Q，即，Q（t）隨著人工螞蟻搜索過(guò)程做實(shí)時(shí)的調(diào)整和變化現(xiàn)代優(yōu)化算法-蟻群算法共39頁(yè)，您現(xiàn)在瀏覽的是第19頁(yè)!蟻群優(yōu)化算法—改進(jìn)4）自適應(yīng)調(diào)整（殘留信息的保留部分）的蟻群算法問(wèn)題：當(dāng)問(wèn)題規(guī)模比較大時(shí)，由于信息素的揮發(fā)系數(shù)1-的存在，使那些從未被搜索到的解上信息素會(huì)減少到接近于0，降低了算法的全局搜索能力，而且過(guò)大時(shí)，以前搜索過(guò)冊(cè)解被選擇的可能性過(guò)大，也會(huì)影響到算法全局搜索能力；通過(guò)減少，雖然可以提高算法的全局搜索能力，但又會(huì)使算法的收斂速度降低。解決：自適應(yīng)調(diào)整的值，的初始值為=1；當(dāng)算法求得的最優(yōu)值在N次循環(huán)內(nèi)沒有明顯改進(jìn)時(shí)，減為：現(xiàn)代優(yōu)化算法-蟻群算法共39頁(yè)，您現(xiàn)在瀏覽的是第20頁(yè)!蟻群優(yōu)化算法—連續(xù)問(wèn)題第二，強(qiáng)度更新方程

尋優(yōu)過(guò)程：

現(xiàn)代優(yōu)化算法-蟻群算法共39頁(yè)，您現(xiàn)在瀏覽的是第21頁(yè)!蟻群優(yōu)化算法—螞蟻生物行為信息素隨著時(shí)間的推移會(huì)逐漸揮發(fā)掉，于是路徑的長(zhǎng)短及其螞蟻的多少就對(duì)殘余信息素的強(qiáng)度產(chǎn)生影響，反過(guò)來(lái)信息素的強(qiáng)弱又指導(dǎo)著其它螞蟻的行動(dòng)方向。因此，某一路徑上走過(guò)的螞蟻越多，則后來(lái)者選擇該路徑的概率就越大。這就構(gòu)成了螞蟻群體行為表現(xiàn)出的一種信息正反饋現(xiàn)象，并實(shí)現(xiàn)找到蟻巢到食物源的最短路徑?，F(xiàn)代優(yōu)化算法-蟻群算法共39頁(yè)，您現(xiàn)在瀏覽的是第22頁(yè)!蟻群優(yōu)化算法—螞蟻生物行為蟻群實(shí)現(xiàn)找到蟻巢到食物源的最短路徑示意圖障礙物ABCDEH15151515初始時(shí)，各有30只螞蟻在B和D點(diǎn)遇到障礙物，開始選擇路徑。由于此時(shí)路徑上無(wú)跡，螞蟻便以相同的概率隨機(jī)地走兩條路中的任意一條，因而15只選往H，15只選往C（圖2）。經(jīng)過(guò)一個(gè)單位時(shí)間以后，路徑BHD被15只螞蟻爬過(guò)，而路徑BCD上則被30只螞蟻爬過(guò)，BCD上的信息量是BHD上信息量的兩倍。圖2現(xiàn)代優(yōu)化算法-蟻群算法共39頁(yè)，您現(xiàn)在瀏覽的是第23頁(yè)!蟻群優(yōu)化算法—算法提出一個(gè)著名的組合優(yōu)化問(wèn)題：旅行商問(wèn)題（TSP,travelingsalesmanproblem），一個(gè)商人欲到n個(gè)城市推銷商品，每個(gè)兩個(gè)城市i和j之間的距離為dij，如何選擇一條道路使得商人每個(gè)城市走一遍后回到起點(diǎn)且所走路徑最短?，F(xiàn)代優(yōu)化算法-蟻群算法共39頁(yè)，您現(xiàn)在瀏覽的是第24頁(yè)!蟻群優(yōu)化算法—算法提出例子，一般旅行商TSP問(wèn)題的解。ABDEC如圖所示，從A城市出發(fā)回到A城市一個(gè)TSP問(wèn)題的解是ABCEDA，即圖中紅色線條路徑。這個(gè)解滿足以上四個(gè)約束條件?，F(xiàn)代優(yōu)化算法-蟻群算法共39頁(yè)，您現(xiàn)在瀏覽的是第25頁(yè)!蟻群優(yōu)化算法—算法提出TSP問(wèn)題與蟻群尋徑行為比較：TSP問(wèn)題蟻群尋徑行為解路徑尋優(yōu)過(guò)程選擇路徑最短路徑（最優(yōu)解）最短路徑現(xiàn)代優(yōu)化算法-蟻群算法共39頁(yè)，您現(xiàn)在瀏覽的是第26頁(yè)!蟻群優(yōu)化算法—算法提出蟻群優(yōu)化算法的核心思想有三條：，選擇機(jī)制：跡越多的路徑，被選中的概率越大；第二，跡更新機(jī)制：路徑越短，跡增加越快；第三，協(xié)作機(jī)制：個(gè)體之間通過(guò)跡進(jìn)行信息交流。現(xiàn)代優(yōu)化算法-蟻群算法共39頁(yè)，您現(xiàn)在瀏覽的是第27頁(yè)!蟻群優(yōu)化算法—算法流程選擇機(jī)制，選擇下一個(gè)城市的依據(jù)主要是兩點(diǎn)：1）t時(shí)刻連接城市i和j的路徑上殘留信息（跡）的濃度——。2）由城市i轉(zhuǎn)移到城市j的啟發(fā)信息，該啟發(fā)信息是由要解決的問(wèn)題給出的——，在TSP問(wèn)題中一般取，其中，表示城市i，j間的距離，在這里可以稱為先驗(yàn)知識(shí)?，F(xiàn)代優(yōu)化算法-蟻群算法共39頁(yè)，您現(xiàn)在瀏覽的是第28頁(yè)!蟻群優(yōu)化算法—算法流程跡更新機(jī)制，為了避免殘留信息過(guò)多引起的殘留信息淹沒啟發(fā)信息的問(wèn)題，在每一只螞蟻完成對(duì)所有n個(gè)城市的訪問(wèn)后（也即一個(gè)循環(huán)結(jié)束后）或每走一步（從一個(gè)城市到下一個(gè)城市后），必須對(duì)殘留信息進(jìn)行更新處理，Morigo介紹三種跡更新機(jī)制：1）ant-cycle算法2）ant-density算法3）ant-quantity算法現(xiàn)代優(yōu)化算法-蟻群算法共39頁(yè)，您現(xiàn)在瀏覽的是第29頁(yè)!蟻群優(yōu)化算法—算法流程跡更新機(jī)制——ant-cycle算法，：螞蟻k在時(shí)間段t到t+n內(nèi)的訪問(wèn)過(guò)程中，在i到j(luò)的路徑上留下的殘留信息濃度；Q：為常量；Lk：螞蟻k在本次循環(huán)中所選擇路徑的總長(zhǎng)度；如果沒有選擇i到j(luò)的路徑，則現(xiàn)代優(yōu)化算法-蟻群算法共39頁(yè)，您現(xiàn)在瀏覽的是第30頁(yè)!蟻群優(yōu)化算法—算法流程跡更新機(jī)制——ant-quantity算法，在每一只螞蟻完成下一個(gè)個(gè)城市的訪問(wèn)后，對(duì)舊的信息進(jìn)行削弱，將最新的螞蟻訪問(wèn)路徑的信息加入。螞蟻k選擇i到j(luò)的路徑螞蟻k沒有選擇i到j(luò)的路徑現(xiàn)代優(yōu)化算法-蟻群算法共39頁(yè)，您現(xiàn)在瀏覽的是第31頁(yè)!蟻群優(yōu)化算法—算法流程跡更新機(jī)制——優(yōu)點(diǎn)：1）保證了殘留信息不至于無(wú)限累積，如果路徑?jīng)]有被選中，那么上面的殘留信息會(huì)隨時(shí)間的推移而逐漸減弱，這使算法能“忘記”不好的路徑；2）即使路徑經(jīng)常被訪問(wèn)也不至于因?yàn)榈睦鄯e，而產(chǎn)生使啟發(fā)信息的作用無(wú)法體現(xiàn)。現(xiàn)代優(yōu)化算法-蟻群算法共39頁(yè)，您現(xiàn)在瀏覽的是第32頁(yè)!蟻群優(yōu)化算法—算法流程算法復(fù)雜度：如果程序終止于NC次循環(huán)后，這個(gè)算法的復(fù)雜度為O（NC*n2*m）。一般情況下，m一般取值與n為同一數(shù)量級(jí)，因此整個(gè)算法的復(fù)雜度O（NC*n3）

現(xiàn)代優(yōu)化算法-蟻群算法共39頁(yè)，您現(xiàn)在瀏覽的是第33頁(yè)!蟻群優(yōu)化算法—優(yōu)缺點(diǎn)缺點(diǎn)：1）算法有眾多參數(shù)（如殘留信息的相對(duì)重要程度、啟發(fā)信息的相對(duì)重要程度、Q常數(shù)、殘留信息的保留部分）需要確定，并且算法對(duì)參數(shù)敏感；2）求解時(shí)間較長(zhǎng)，蟻群算法的復(fù)雜度可以反映這一點(diǎn)；3）易出現(xiàn)停滯現(xiàn)象，即算法搜索進(jìn)行到一定程度后，所有個(gè)體發(fā)現(xiàn)的解都完全一致，不能對(duì)解空間進(jìn)一步進(jìn)行搜索?，F(xiàn)代優(yōu)化算法-蟻群算法共39頁(yè)，您