蟻群優(yōu)化算法

第1頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月螞蟻的生活習(xí)性第2頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月蟻群優(yōu)化的起源蟻群優(yōu)化

(antcolonyoptimization,ACO)，又名蟻群算法。1991年意大利學(xué)者M(jìn).Dorigo在其博士學(xué)位論文中首先提出。通過(guò)模擬自然界中螞蟻集體尋徑的行為而提出的一種基于種群的啟發(fā)式仿生進(jìn)化算法。第3頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月蟻群優(yōu)化的特征一種典型的群體智能模式。充分利用蟻群能通過(guò)個(gè)體間簡(jiǎn)單的信息傳遞來(lái)進(jìn)行尋優(yōu)。通過(guò)正反饋、分布式協(xié)作進(jìn)行路徑尋優(yōu)。第4頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月正反饋原理：螞蟻釋放信息素(pheromone)。蟻群優(yōu)化的正反饋機(jī)制第5頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月旅行商問(wèn)題（TSP）旅行商問(wèn)題（travelingsalesmanproblem,TSP）。一名商人要遍歷多個(gè)城市，各個(gè)城市之間可達(dá)且距離已知，如何找到在訪問(wèn)每個(gè)城市一次后再回到起點(diǎn)的最短路徑。第6頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月TSP問(wèn)題舉例第7頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月TSP問(wèn)題的解BCDEFGHIJABCDEFGHIJA路徑1路徑2第8頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月：信息素強(qiáng)度：?jiǎn)l(fā)程度螞蟻k由位置i移動(dòng)j到的概率蟻群優(yōu)化描述第9頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月蟻群優(yōu)化描述廣州南寧長(zhǎng)沙福州:信息素強(qiáng)度:啟發(fā)因子第10頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月蟻群優(yōu)化描述信息素殘留系數(shù)，(0,1)

信息素增量

啟發(fā)程度與距離成反比

第11頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月概率分配的實(shí)現(xiàn)方法一等獎(jiǎng)二等獎(jiǎng)三等獎(jiǎng)輪盤賭00.150.4510.150.300.55概率1概率2概率3概率積累概率第12頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月蟻群優(yōu)化的流程第13頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月

帶精英策略的螞蟻系統(tǒng)當(dāng)前最優(yōu)解精英螞蟻第14頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月

帶精英策略的螞蟻系統(tǒng)帶精英策略的螞蟻系統(tǒng)（AntSystemwithelitiststrategy）是最早的改進(jìn)螞蟻系統(tǒng)。精英策略的思想是保留住一代中的最適應(yīng)個(gè)體。螞蟻系統(tǒng)中的精英策略：每次循環(huán)之后給予最優(yōu)解以額外的信息素量。這樣的解被稱為全局最優(yōu)解（global-bestsolution）。找出這個(gè)解的螞蟻被稱為精英螞蟻(elitistants)。第15頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月

帶精英策略的螞蟻系統(tǒng)信息素根據(jù)下式進(jìn)行更新其中第16頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月

帶精英策略的螞蟻系統(tǒng)表示精英螞蟻引起的路徑(i,j)上的信息素量的增加。是精英螞蟻的個(gè)數(shù)。是所找出的最優(yōu)解的路徑長(zhǎng)度。第17頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月

帶精英策略的螞蟻系統(tǒng)的特征可以使螞蟻系統(tǒng)找出更優(yōu)的解。找到這些解的時(shí)間更短。精英螞蟻過(guò)多會(huì)導(dǎo)致搜索早熟收斂。第18頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月

比較兩組概率第一組概率：

0.020.100.020.700.030.030.080.02ABCDEFGH第二組概率：

0.150.130.100.120.100.150.110.14ABCDEFGH較優(yōu)的解，取不到怎么辦？第19頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月

蟻群系統(tǒng)蟻群系統(tǒng)(AntColonySystem,ACS)是由Dorigo和Gambardella在1996年提出的。蟻群系統(tǒng)做了三個(gè)方面的改進(jìn)：狀態(tài)轉(zhuǎn)移規(guī)則為更好更合理地利用新路徑和利用關(guān)于問(wèn)題的先驗(yàn)知識(shí)提供了方法。全局更新規(guī)則只應(yīng)用于最優(yōu)的螞蟻路徑上。在建立問(wèn)題解決方案的過(guò)程中，應(yīng)用局部信息素更新規(guī)則。第20頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月蟻群系統(tǒng)狀態(tài)轉(zhuǎn)移規(guī)則一只位于節(jié)點(diǎn)r的螞蟻通過(guò)應(yīng)用下式給出的規(guī)則選擇下一個(gè)將要移動(dòng)到的城市s其中，S根據(jù)下列公式得到第21頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月蟻群系統(tǒng)狀態(tài)轉(zhuǎn)移規(guī)則q是在[0,1]區(qū)間均勻分布的隨機(jī)數(shù)。q0的大小決定了利用先驗(yàn)知識(shí)與探索新路徑之間的相對(duì)重要性。上述狀態(tài)轉(zhuǎn)移規(guī)則被稱為偽隨機(jī)比例規(guī)則。特點(diǎn)是算法傾向于選擇短的且有著大量信息素的邊作為移動(dòng)方向。第22頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月

比較兩組概率第一組概率：

0.020.100.020.700.030.030.080.02ABCDEFGH第二組概率：

0.150.130.100.120.100.150.110.14ABCDEFGH總是取到該較優(yōu)的解，怎么辦？第23頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月局部最優(yōu)全局最優(yōu)0AB

xy局部最優(yōu)與全局最優(yōu)第24頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月最大-最小螞蟻系統(tǒng)蟻群算法將螞蟻的搜索行為集中到最優(yōu)解的附近可以提高解的質(zhì)量和收斂速度，從而改進(jìn)算法的性能。但這種搜索方式會(huì)使早熟收斂行為更容易發(fā)生。最大-最小螞蟻系統(tǒng)(Max-MinAntSystem,MMAS)能將這種搜索方式和一種能夠有效避免早熟收斂的機(jī)制結(jié)合在一起，從而使算法獲得最優(yōu)的性能。第25頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月最大-最小螞蟻系統(tǒng)為了充分利用循環(huán)最優(yōu)解和到目前為止找出的最優(yōu)解，在每次循環(huán)之后，只有一只螞蟻進(jìn)行信息素更新。這只螞蟻可能是找出當(dāng)前循環(huán)中最優(yōu)解的螞蟻，也可能是找出從實(shí)驗(yàn)開(kāi)始以來(lái)最優(yōu)解的螞蟻。為避免搜索的停滯，在每個(gè)解的元素上的的信息素軌跡量的值域范圍被限制在區(qū)間內(nèi)。第26頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月信息素軌跡更新在MMAS中，只有一只螞蟻用于在每次循環(huán)后更新信息軌跡。經(jīng)修改的軌跡更新規(guī)則如下：表示迭代最優(yōu)解或全局最優(yōu)解的值。第27頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月信息素軌跡的限制的原因不管是選擇迭代最優(yōu)還是全局最優(yōu)螞蟻來(lái)進(jìn)行信息素更新，都可能導(dǎo)致搜索的停滯。停滯現(xiàn)象發(fā)生的原因：