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

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

實(shí)驗(yàn)十六樓415房間Email：Tel:64253254(o)、

二○○八年十月現(xiàn)代智能優(yōu)化算法模擬退火遺傳算法蟻群優(yōu)化算法蟻群優(yōu)化算法—螞蟻生物行為螞蟻搬家，天要下雨。螞蟻群體行為。相互協(xié)作的一群螞蟻可以戰(zhàn)勝比自己強(qiáng)壯的昆蟲，并把它搬回巢；而單個(gè)螞蟻則不能。相互協(xié)作的一群螞蟻可以很容易找到從蟻巢到食物源的最短路徑，而單個(gè)螞蟻則不能。此外，螞蟻還能夠適應(yīng)環(huán)境的變化，例如在蟻群的運(yùn)動(dòng)路線上突然出現(xiàn)障礙物時(shí)，它們能夠很快地重新找到最優(yōu)路徑?！坏鹄ハx學(xué)家，而且也引起數(shù)學(xué)及計(jì)算機(jī)方面的專家和工程師的興趣。蟻群優(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)找到蟻巢到食物源的最短路徑。蟻群優(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。蟻群優(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蟻群優(yōu)化算法—算法提出一個(gè)著名的組合優(yōu)化問(wèn)題：旅行商問(wèn)題（TSP,travelingsalesmanproblem），一個(gè)商人欲到n個(gè)城市推銷商品，每個(gè)兩個(gè)城市i和j之間的距離為dij，如何選擇一條道路使得商人每個(gè)城市走一遍后回到起點(diǎn)且所走路徑最短。蟻群優(yōu)化算法—算法提出一般旅行商問(wèn)題TSP，數(shù)學(xué)模型描述：選擇ij路線為1，否則為0避免產(chǎn)生回路走入城市j只有一次從城市i出發(fā)只有一次蟻群優(yōu)化算法—算法提出例子，一般旅行商TSP問(wèn)題的解。ABDEC如圖所示，從A城市出發(fā)回到A城市一個(gè)TSP問(wèn)題的解是ABCEDA，即圖中紅色線條路徑。這個(gè)解滿足以上四個(gè)約束條件。蟻群優(yōu)化算法—算法提出TSP問(wèn)題與蟻群尋徑行為比較：TSP問(wèn)題蟻群尋徑行為解路徑尋優(yōu)過(guò)程選擇路徑最短路徑（最優(yōu)解）最短路徑蟻群優(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é)果。蟻群優(yōu)化算法—算法提出蟻群優(yōu)化算法的核心思想有三條：第一，選擇機(jī)制：跡越多的路徑，被選中的概率越大；第二，跡更新機(jī)制：路徑越短，跡增加越快；第三，協(xié)作機(jī)制：個(gè)體之間通過(guò)跡進(jìn)行信息交流。蟻群優(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í)。蟻群優(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ò)城市的概率。蟻群優(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算法蟻群優(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ò)的路徑，則蟻群優(yōu)化算法—算法流程跡更新機(jī)制——ant-density算法，在每一只螞蟻完成下一個(gè)個(gè)城市的訪問(wèn)后，對(duì)舊的信息進(jìn)行削弱，將最新的螞蟻訪問(wèn)路徑的信息加入。螞蟻k選擇i到j(luò)的路徑螞蟻k沒有選擇i到j(luò)的路徑蟻群優(yōu)化算法—算法流程跡更新機(jī)制——ant-quantity算法，在每一只螞蟻完成下一個(gè)個(gè)城市的訪問(wèn)后，對(duì)舊的信息進(jìn)行削弱，將最新的螞蟻訪問(wèn)路徑的信息加入。螞蟻k選擇i到j(luò)的路徑螞蟻k沒有選擇i到j(luò)的路徑蟻群優(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)。蟻群優(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蟻群優(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)行搜索。蟻群優(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蟻群優(yōu)化算法—改進(jìn)1）MAX-MINANTSYSTEM（MMAS）算法只對(duì)最佳路徑增加跡的濃度，從而更好地利用了歷史信息；為了避免算法過(guò)早收斂于并非全局最優(yōu)的解，將各條路徑可能的跡濃度限制于，超出這個(gè)范圍的值被強(qiáng)制設(shè)為或者為，可以有效地避免某條路徑上的信息量遠(yuǎn)大于其余路徑，使得所有的螞蟻都集中到同一條路徑上；將各條路徑上跡的初始濃度設(shè)為，這樣便可以更加充分地進(jìn)行尋優(yōu)。蟻群優(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ì)解空間的更完全搜索。蟻群優(yōu)化算法—改進(jìn)2）自適應(yīng)蟻群優(yōu)化算法該算法由下式確定螞蟻k從i城市轉(zhuǎn)移到s城市：蟻群優(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)整和變化蟻群優(yōu)化算法—改進(jìn)3）自適應(yīng)調(diào)整信息素的蟻群算法自適應(yīng)調(diào)整策略：通過(guò)對(duì)算法的監(jiān)控，實(shí)時(shí)判斷算法的搜索狀態(tài)，如果一段時(shí)間內(nèi)獲得的最優(yōu)解沒有變化，則減少要添加的信息素，即減少中的Q（t）。Q（t）時(shí)變函數(shù)幾個(gè)例子，針對(duì)不同情況使用蟻群優(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ò)減少，雖然可以提高算法的全局搜索能力，但