蟻群算法1.概述2.基本蟻群算法3.蟻群算法的參數選擇4.改進的蟻群算法5.蟻群算法的應用實例什么是群？指的是蜂群、鳥群、蟻群、魚群等等，具有社會群居行為的動物。群的特征：1.相互作用的相鄰個體的集合2.個體的行為簡單，只能完成一般工作3.智能化的集體行為1.概述a.個體間不僅能夠交互信息，還能夠處理信息，根據信息改變自身行為。b.沒有一個集中控制中心，分布式、自組織c.作為群體協同工作時，能夠實現出非常復雜的行為特征——智能螞蟻的覓食過程1.隨機移動2.遇到食物分泌信息素3.在搬運食物回家的路上留下信息素4.其他螞蟻發(fā)現留有信息素的路徑結束漫游，沿該路徑移動，遇到食物同樣開始分泌信息素。5.信息素會隨時間揮發(fā)，短路徑上的信息素相對濃度高。1.概述什么是蟻群算法蟻群算法的特點1.能覺察小范圍區(qū)域內狀況，并判斷出是否有食物或其他同類的信息激素軌跡；2.能釋放自己的信息激素；3所遺留的信息激素數量會隨時間而逐步減少。螞蟻系統(tǒng)：模擬蟻群突現聚集行為的蟻群算法，是作為一類新的計算模式引入的。螞蟻系統(tǒng)的提出1.概述它是一種通用的啟發(fā)式算法，可用來解決各種不同的組合優(yōu)化問題。1.螞蟻之間通過環(huán)境進行通信。2.螞蟻對環(huán)境的反應由其內部模式決定。3.在個體水平上，每只螞蟻僅根據環(huán)境做出獨立選擇。2.1蟻群算法的原理蟻群算法的思想：用螞蟻的行走路線表示待求解問題的可行解，每只螞蟻在解空間中獨立的搜索可行解，解的質量越高，在“行走路線”上留下的信息激素也就越多，隨著算法的推進，代表較好解的路線上的信息激素逐漸增多，選擇它的螞蟻也逐漸增多，最終整個蟻群在正反饋的作用下集中到代表最優(yōu)解的路線上，也就找到了最優(yōu)解。人工蟻群與自然蟻群的異同點：相似處：優(yōu)先選擇信息素濃度大的路徑區(qū)別：1.人工蟻群有一定的記憶能力，能夠記憶已經訪問過的節(jié)點。2.人工蟻群在選擇下一條路徑的時候，是按一定算法規(guī)律有意識的尋找最短路徑，而不是盲目的。2.基本蟻群算法2.2蟻群算法的實現各路徑上信息激素物質的濃度為τij(t+n)=(1-ρ)?τij(t)+Δτijτij(t)表示時刻t在路徑edge(i,j)上釋放的信息素量；ρ表示在時間t到t+n之間所經過路徑上信息激素的蒸發(fā)系數；（1-ρ）為信息激素殘留因子本次迭代中第k只螞蟻釋放在路徑上的信息激素量其中，2.基本蟻群算法Q為宜常量，用來表示螞蟻釋放的信息激素量，

Lk是第k只螞蟻完成一次旅行時所走過的路徑總長度。2.基本蟻群算法Pkij(t)表示第k只螞蟻由城市i向城市j轉移的概率式中allowedk表示第k只螞蟻下一步允許選擇的城市集合；

α為信息啟發(fā)式因子，表示軌跡的相對重要性；

β為期望啟發(fā)式因子，表示能見度的相對重要性；

ηij(t)為啟發(fā)函數，表示螞蟻從城市i轉移到城市j期望程度，

ηij(t)通常取城市i與城市j之間距離的倒數。

pkij(t)是關于信息激素量τij(t)和啟發(fā)式因子ηij的函數。τij(t)給出了在過去有多少只螞蟻選擇走同一條路徑的信息，而ηij則表明一個城市越近，螞蟻就越有可能向該城市移動。2.基本蟻群算法蟻群算法求解TSP的流程圖如圖8-1所示：M.Dorigo提出了三種蟻群算法模型，本節(jié)所給出的算法稱為Ant-Cycle;另外兩個算法分別稱為Ant-Quantity和Ant-Density,其差別主要是Δτkij表示方式的區(qū)別。在Ant-Quantity模型中，

在Ant-Density模型中2.基本蟻群算法蟻群算法的本質：蟻群算法實際上是正反饋原理和啟發(fā)式算法向結合的一種算法。在選擇路徑時，螞蟻不僅利用了路徑上的信息激素，而且用到了城市間距離的倒數作為啟發(fā)式因子。實驗結果表明，Ant-Cycle算法比Ant-Quantity和Ant-Density有更好的性能。原因是Ant-Cycle利用的是全局信息來更新路徑上的信息激素量，而后兩種算法使用的是局部信息。蟻群算法優(yōu)化過程的本質：①選擇機制，信息量越大的路徑，被選中的概率越大；②更新機制，路徑上面的信息量會隨螞蟻的經過而增長，同時也隨著時間的推移逐漸減??；③協調機制，螞蟻之間實際上是通過信息量來相互通信、協同工作的。2.基本蟻群算法3.1蟻群算法參數對其性能的影響蟻群算法中的參數主要包括信息激素殘留因子1-ρ、信息啟發(fā)式因子α、期望啟發(fā)式因子β、螞蟻數目m、信息激素強度Q。信息激素揮發(fā)因子ρ的大小直接關系到蟻群算法的全局搜索能力及其收斂速度；而信息激素殘留因子1-ρ反映了螞蟻之間個體相互影響的強弱。啟發(fā)式因子α反映螞蟻在運動過程中所積累的信息量在指導蟻群搜索中的相對重要程度，其值越大，螞蟻選擇以前走過路徑的可能性就越大，搜索的隨機性減弱；而當啟發(fā)式因子α值過小時，則易使蟻群的搜索過早陷于最優(yōu)。3.蟻群算法參數選擇期望啟發(fā)式因子β反映了啟發(fā)式信息在指導蟻群搜索過程中的相對重要程度，其大小反映了蟻群尋優(yōu)過程中先驗性、確定性因素的作用強度。其值越大，則螞蟻在某個局部點上選擇局部最短路徑的可能性越大，雖然這時算法的收斂速度得以加快，但蟻群搜索最優(yōu)路徑的隨機性減弱，易陷于局部最優(yōu)。在Ant-Cycle模型中，信息激素強度Q為螞蟻循環(huán)一周時釋放在所經路徑上的信息激素總量，其作用是為了充分利用有向圖上的全局信息反饋量，使得算法在正反饋機制作用下以合理的演化速度搜索到所求問題的全局最優(yōu)解。Q越大，則在螞蟻已遍歷路徑上的信息激素的累積加快，可以加強蟻群搜索時的正反饋性能，有助于算法的快速收斂。3.蟻群算法參數選擇3.2蟻群算法參數選擇方法用蟻群算法求解問題，都存在算法有關參數的選擇問題，較好的參數組合將會使得算法具有全局搜索能力和較快的收斂速度；相反，不好的參數組合則會使得算法收斂速度過快或過慢，并且容易陷入局部最優(yōu)解。由于缺乏理論指導，算法參數一般采用試探法來確定，造成工作量大，并且很難得到最優(yōu)的參數選擇，從而影響了算法的使用性能。文獻【5】對基本蟻群算法的4個參數作了對比實驗，即假定螞蟻數目m等于城市的數目n；信息激素強度Q?{0.3,0.5,0.7,0.9,0.999}；參數α?{0,0.5,1,2,5}和β?{0,1,2,5}，分別表示信息激素水平和城市間的距離對轉移概率的貢獻程度。

3.蟻群算法參數選擇為了分析這些參數組合對算法性能的影響，固定前兩個參數，而對α與β各種組合進行分析，總共需要20組實驗；但是若考慮Q的影響，想做徹底的分析需要做100組實驗，在加上螞蟻數目m，則實驗的組數難以承受。更重要的是，這些參數實際上相互耦合，相互聯系，具有復雜的關系，僅取這些粗糙的值進行組合，難以找到參數的最優(yōu)組合。段海濱在對蟻群算法參數選擇規(guī)律實驗分析的基礎上，總結出一種“三步走”選擇蟻群算法最優(yōu)組合參數的有效方法，具體步驟如下：⑴確定螞蟻數目，按城市規(guī)模/螞蟻數目≈1.5的選擇策略來確定螞蟻的總數目；⑵參數粗調，即調整取值范圍較大的信息啟發(fā)式因子α、期望啟發(fā)式因子β以及信息激素強度Q等參數，以得到較理想的解；⑶參數微調，即調整取值范圍較小的信息激素揮發(fā)因子ρ。3.蟻群算法參數選擇以上步驟反復進行，直到最終確定出一組較為理想的組合參數為止。蟻群算法的參數是影響蟻群算法求解性能和效率的關鍵因素，到目前為止蟻群算法還沒像其他的啟發(fā)式算法那樣已形成系統(tǒng)的分析方法和具有堅實的數學基礎，其參數的選擇更多的是依靠實驗和經驗，沒有定理來確定。3.蟻群算法參數選擇蟻群算法的優(yōu)點：⑴具有較強的魯棒性。⑵采用分布式計算機制。⑶具有良好的啟發(fā)性。⑷易與其他方法結合。改進的蟻群算法包括①Ant-Q蟻群算法②ACS算法③最大-最小螞蟻系統(tǒng)④自適應蟻群算法4.改進的蟻群算法4.1Ant-Q蟻群算法Dorigo等人在基本蟻群算法的基礎上提出了Ant-Q蟻群算法，Ant-Q算法中用來指引螞蟻初始尋優(yōu)的一個狀態(tài)傳遞方程，也稱行為選擇機制為式中δ為AQ值相對重要性系數；q為[0,1]上的隨機數；

q0是初始設定的參數，

q≤q0≤1,q0值越大，螞蟻在轉移時隨機選擇節(jié)點的概率就越??；J是式（8-4）式中計算出的概率；HE的作用同ηij；AQ為學習因子，用來指導螞蟻的運動，4.改進的蟻群算法也按照式(8-8)更新，即式(8-7)式(8-8)進一步揭示了Ant-Q算法與強化學習算法的聯系。實驗結果表明，與基本蟻群算法相比，Ant-Q算法更具有一般性，而且更有利于全局搜索。4.2ACS算法ACS算法繼承了Ant-Q算法的優(yōu)點并對基本蟻群算法模型做出了幾點重要改進：⑴ACS算法中，螞蟻在尋找最佳路徑的過程中只使用局部信息，即采用局部信息對外信息激素濃度進行調整。⑵在螞蟻所有尋優(yōu)過程結束后，再一次調整信息激素濃度，而這次采用全局信息，只對過程中發(fā)現的路徑上的信息激素濃度進行加強。4.改進的蟻群算法1.ACS算法的狀態(tài)轉移策略位于城市i的螞蟻k在t時刻選擇下一城市j的策略如下：其中0<q0<1是初始設定的參數；q?(0,1)為一隨機數；S是根據式(8-10)決定的隨機變量，即4.改進的蟻群算法如果隨機數q小于初始值q0，則根據啟發(fā)信息選擇最大的一個；如果q﹥q0，則根據式(8-10),根據概率的大小來選擇下一個城市。這樣既保證了搜索的收斂性性能好，又增強了搜索策略的多樣性，以避免過早的陷于搜索停滯狀態(tài)。信息激素局部更新策略信息激素局部更新的作用是使已選擇的邊對后來的螞蟻具有較小的影響力，從而使螞蟻對沒有選中的邊有更強的探索能力。當螞蟻從城市i轉移到城市j后，edge(i,j)上的信息激素量可按式(8-11)進行更新，即τij(t+1)=(1-ξ)*τij(t)+ξ?τ0(8-11)其中ξ為(0,1)區(qū)間上的可調參數；τ0為常數。4.改進的蟻群算法信息激素全局更新策略當所有螞蟻走完全部城市后，只有經過那些路徑邊上的螞蟻才允許釋放信息激素，按照式(8-12)進行更新。其中ρ為信息激素蒸發(fā)系數；Lk為最優(yōu)路徑的長度。這種策略的目的是為了增強那些屬于最優(yōu)路徑上的邊的信息激素，可以大大增加這些邊上的信息激素。4.改進的蟻群算法4.3最大-最小螞蟻系統(tǒng)為了克服在Ant-Q算法中可能出現的停滯現象，Thomas等提出了最大-最小螞蟻系統(tǒng)，該算法主要做了如下改進：①每次迭代結束后，只有最優(yōu)解所屬路徑上的信息被更新，從而更好地利用了歷史信息；②為了避免算法過早收斂于并非全局最優(yōu)的解，將各條路徑可能的外激素濃度限制于[τmin,τmax]，超出這個范圍的值被強制設為τmin或τmax，一方面避免了某條路徑上的信息激素遠大于其他路徑的信息激素濃度，從而有效降低了過早停滯的可能。另一方面，不會因為某路徑的信息激素濃度過低而喪失發(fā)現新路徑的可能。各路徑上外激素的起始濃度設為τmax，在算法的初始時刻，

ρ取較小的值時，算法有更好的發(fā)現較好解的能力。所有螞蟻完成一次迭代后，按式(8-13)4.改進的蟻群算法對路徑上的信息作全局更新。允許更新的路徑可以是全局最優(yōu)解，或本次迭代的最優(yōu)解。實踐證明，逐漸增加全局最優(yōu)解的使用頻率，會使該算法獲得較好的性能。需要說明的是，僅采用最大-最小信息激素濃度的限制還不足以在較長的時間里持續(xù)消除停滯現象，因此，可以對其進一步改進，比如在該算法中引入信息激素的平滑機制等。4.改進的蟻群算法4.4自適應蟻群算法蟻群算法的主要依據是信息正反饋原理和某種啟發(fā)式算法的有機結合。這種算法在構造解的過程中，利用隨機選擇策略，這種選擇策略使得進化速度較慢，正反饋原理旨在強化性能較好的解，卻容易出現停滯現象，這是造成蟻群算法不足之處的根本原因。針對蟻群算法加速收斂和早熟、停滯現象的矛盾，因此提出了一種基于分布均勻度的自適應蟻群算法。該算法根據優(yōu)化過程中解的分布均勻度，動態(tài)地調整信息量更新策略和選擇路徑概率，這樣，可以在加速收斂和防止早熟、停滯現象之間取得很好的平衡。為此基于常規(guī)數學模型引入“聚度”的概念來衡量解的均勻程度，從而決定每次選擇路徑的概率以及信息量更新的策略。具體方法如下：4.改進的蟻群算法定義8.1設從城市i共有r條路到達另外r個城市i1,i2,…,ir,另設上一次迭代中，經過這r條路徑上的螞蟻分別為a1,a2,…,ar,令城市i的聚度為若在上一次迭代中，m只螞蟻遍歷時經過以城市i為起點的r條路徑的s條，設經過他們的螞蟻個數分別a1,a2,…,ar,這些值均不為0，而其余路徑上的螞蟻個數均為0。城市的聚度i隨s的減小而增大。為使聚度的大小達到有效的平衡，以在改善螞蟻搜索速度的同時避免局部優(yōu)化，可考慮根據城市i的聚度sta(i)來4.改進的蟻群算法確定螞蟻在該城市時下一步可選擇的路徑數ω，ω可取為

在路徑選擇過程中，螞蟻僅考慮信息量最高的ω條路徑。顯然，當城市的聚度越大時，ω越大，螞蟻下一步的分布范圍越來越廣；反之，聚度越小，螞蟻搜索時分布范圍就越小。

為了調整各個路徑被選中的概率，引入“信息權重”這個量來限制信息量和期望程度，其總體原則是要使信息量大的和當前局部最優(yōu)的路徑被選擇的概率較大。4.改進的蟻群算法定義8.2以城市i為起點的r條路徑按其信息量由高到低排序，序號依次存于數組rank中，即數組元素rank[j]的值為路徑(i,j)的序號。下一步可供選擇的路徑條數為w，取q=w/r，計算則ξij為路徑(i,j)的信息權重。應用信息權重ξij，螞蟻由城市i按式(8-18)的概率選擇城市j,即4.改進的蟻群算法式中對各路徑上的信息量及期望程度都乘上了信息權重ξij。路徑(i,j)的信息權重ξij反映了螞蟻從城市i選擇下一個城市j時，路徑(i,j)上的信息量ξij(t)以及可訪問度ηij(t)對螞蟻選擇概率的影響程度。對于信息量較大的路徑，其信息權重較大，螞蟻選擇該路徑的概率也較大。自適應更新信息量的過程如下：根據信息量的均勻度自適應的進行信息量的更新，以動態(tài)調整各條路徑上的信息量的分布，使其不至于過分集中或者分散，避免在加速收斂的同時成熟。信息量局部更新可根據以下策略：4.改進的蟻群算法由于螞蟻常常選擇信息量較大的路徑，當多只螞蟻選中同一路徑后，信息量增加的幅度太大就容易使多只螞蟻集中到該路徑，因此取1/dij為增加的信息量。若選擇該路徑的螞蟻達到一定數量或多數螞蟻選擇該路徑后因當前距離超過上一次的最優(yōu)路徑長度終止遍歷(這里分別設定為m/3和m/5),信息量則取-10/d0ij,這時可大幅度削減其信息量使其趨于各條路徑信息量的平均值，從而使螞蟻選擇其他路徑的可能性增加，讓搜索到的解趨于多樣化。信息量的整體更新可根據以下策略：4.改進的蟻群算法式中Ll(t)為本次迭代過程中第l只螞蟻遍歷的路徑全長；Ψl為第l只螞蟻所對應的解對該路徑上的信息量更新的影響程度。

Ψl的計算方法為：設經過路徑(i,j)的螞蟻總數為K，對他們在本次迭代中遍歷的路徑全長由小到大進行排序，所得序號存放于數組rank中，即rank[l]表示第l只螞蟻對應的序號。算法的具體步驟為算法1自適應螞蟻算法。(1)初始化。隨機產生m個初始解，設其中經過路徑(i,j)的初始解有s個，他們的總長度分別為L1,L2,…LS,則路徑(i,j)上的初始信息量為其中Q為常數4.改進的蟻群算法(2)迭代過程4.改進的蟻群算法算法二選