《蟻群優(yōu)化算法》

1、螞蟻的生活習(xí)性蟻群優(yōu)化的起源蟻群優(yōu)化 (ant colony optimization, ACO)，又名蟻群算法。1991年意大利學(xué)者M(jìn).Dorigo在其博士學(xué)位論文中首先提出。通過模擬自然界中螞蟻集體尋徑的行為而提出的一種基于種群的啟發(fā)式仿生進(jìn)化算法。蟻群優(yōu)化的特征一種典型的群體智能模式。充分利用蟻群能通過個(gè)體間簡(jiǎn)單的信息傳遞來進(jìn)行尋優(yōu)。通過正反饋、分布式協(xié)作進(jìn)行路徑尋優(yōu)。正反饋原理：螞蟻釋放信息素(pheromone)。蟻群優(yōu)化的正反饋機(jī)制旅行商問題（TSP）旅行商問題（traveling salesman problem, TSP）。一名商人要遍歷多個(gè)城市，各個(gè)城市之間可達(dá)且距離已知，如

2、何找到在訪問每個(gè)城市一次后再回到起點(diǎn)的最短路徑。 TSP問題舉例TSP問題的解BCDEFGHIJABCDEFGHIJA路徑 1路徑2：信息素強(qiáng)度：?jiǎn)l(fā)程度螞蟻 k 由位置 i 移動(dòng) j 到的概率蟻群優(yōu)化描述蟻群優(yōu)化描述廣州南寧長(zhǎng)沙福州:信息素強(qiáng)度:啟發(fā)因子蟻群優(yōu)化描述信息素殘留系數(shù)，(0, 1) 信息素增量 啟發(fā)程度與距離成反比 概率分配的實(shí)現(xiàn)方法一等獎(jiǎng)二等獎(jiǎng)三等獎(jiǎng)輪盤賭0 0.15 0.45 10.15 0.30 0.55概率1概率2概率3概率積累概率蟻群優(yōu)化的流程帶精英策略的螞蟻系統(tǒng)當(dāng)前最優(yōu)解精英螞蟻帶精英策略的螞蟻系統(tǒng)帶精英策略的螞蟻系統(tǒng)（Ant System with elitist

3、strategy）是最早的改進(jìn)螞蟻系統(tǒng)。精英策略的思想是保留住一代中的最適應(yīng)個(gè)體。螞蟻系統(tǒng)中的精英策略：每次循環(huán)之后給予最優(yōu)解以額外的信息素量。這樣的解被稱為全局最優(yōu)解（global-best solution）。找出這個(gè)解的螞蟻被稱為精英螞蟻(elitist ants)。帶精英策略的螞蟻系統(tǒng)信息素根據(jù)下式進(jìn)行更新其中帶精英策略的螞蟻系統(tǒng) 表示精英螞蟻引起的路徑(i, j)上的信息素量的增加。 是精英螞蟻的個(gè)數(shù)。 是所找出的最優(yōu)解的路徑長(zhǎng)度。帶精英策略的螞蟻系統(tǒng)的特征可以使螞蟻系統(tǒng)找出更優(yōu)的解。找到這些解的時(shí)間更短。精英螞蟻過多會(huì)導(dǎo)致搜索早熟收斂。比較兩組概率第一組概率： 0.02 0.10

4、0.02 0.70 0.03 0.03 0.08 0.02 A B C D E F G H第二組概率： 0.15 0.13 0.10 0.12 0.10 0.15 0.11 0.14 A B C D E F G H較優(yōu)的解，取不到怎么辦？蟻群系統(tǒng)蟻群系統(tǒng)(Ant Colony System, ACS)是由Dorigo和Gambardella在1996年提出的。蟻群系統(tǒng)做了三個(gè)方面的改進(jìn)：狀態(tài)轉(zhuǎn)移規(guī)則為更好更合理地利用新路徑和利用關(guān)于問題的先驗(yàn)知識(shí)提供了方法。全局更新規(guī)則只應(yīng)用于最優(yōu)的螞蟻路徑上。在建立問題解決方案的過程中，應(yīng)用局部信息素更新規(guī)則。蟻群系統(tǒng)狀態(tài)轉(zhuǎn)移規(guī)則一只位于節(jié)點(diǎn)r的螞蟻通過應(yīng)用

5、下式給出的規(guī)則選擇下一個(gè)將要移動(dòng)到的城市s其中，S根據(jù)下列公式得到蟻群系統(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)方向。比較兩組概率第一組概率： 0.02 0.10 0.02 0.70 0.03 0.03 0.08 0.02 A B C D E F G H第二組概率： 0.15 0.13 0.10 0.12 0.10 0.15 0.11 0.14 A B C D E F G H總是取到該較優(yōu)的解，怎么辦？局部最優(yōu)全局最優(yōu)0 A B xy局部最

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