蟻群優(yōu)化算法

第一頁，共二十九頁，2022年，8月28日螞蟻的生活習(xí)性第二頁，共二十九頁，2022年，8月28日蟻群優(yōu)化的起源蟻群優(yōu)化

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

信息素增量

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

第十一頁，共二十九頁，2022年，8月28日概率分配的實現(xiàn)方法一等獎二等獎三等獎輪盤賭00.150.4510.150.300.55概率1概率2概率3概率積累概率第十二頁，共二十九頁，2022年，8月28日蟻群優(yōu)化的流程第十三頁，共二十九頁，2022年，8月28日

帶精英策略的螞蟻系統(tǒng)當(dāng)前最優(yōu)解精英螞蟻第十四頁，共二十九頁，2022年，8月28日

帶精英策略的螞蟻系統(tǒng)帶精英策略的螞蟻系統(tǒng)（AntSystemwithelitiststrategy）是最早的改進(jìn)螞蟻系統(tǒng)。精英策略的思想是保留住一代中的最適應(yīng)個體。螞蟻系統(tǒng)中的精英策略：每次循環(huán)之后給予最優(yōu)解以額外的信息素量。這樣的解被稱為全局最優(yōu)解（global-bestsolution）。找出這個解的螞蟻被稱為精英螞蟻(elitistants)。第十五頁，共二十九頁，2022年，8月28日

帶精英策略的螞蟻系統(tǒng)信息素根據(jù)下式進(jìn)行更新其中第十六頁，共二十九頁，2022年，8月28日

帶精英策略的螞蟻系統(tǒng)表示精英螞蟻引起的路徑(i,j)上的信息素量的增加。是精英螞蟻的個數(shù)。是所找出的最優(yōu)解的路徑長度。第十七頁，共二十九頁，2022年，8月28日

帶精英策略的螞蟻系統(tǒng)的特征可以使螞蟻系統(tǒng)找出更優(yōu)的解。找到這些解的時間更短。精英螞蟻過多會導(dǎo)致搜索早熟收斂。第十八頁，共二十九頁，2022年，8月28日

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

0.020.100.020.700.030.030.080.02ABCDEFGH第二組概率：

0.150.130.100.120.100.150.110.14ABCDEFGH較優(yōu)的解，取不到怎么辦？第十九頁，共二十九頁，2022年，8月28日

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

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

0.020.100.020.700.030.030.080.02ABCDEFGH第二組概率：

0.150.130.100.120.100.150.110.14ABCDEFGH總是取到該較優(yōu)的解，怎么辦？第二十三頁，共二十九頁，2022年，8月28日局部最優(yōu)全局最優(yōu)0AB

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