第-6-章-蟻群算法

人工智能ArtificialIntelligence群智能

SwarmIntelligence

源于生物（動物）行為的啟發(fā)

群(Swarm)群在自然界中廣泛存在。根據(jù)劍橋高級學(xué)生詞典的釋義，Swarm被定義為alargegroupofinsectsallmovingtogether.也即：一大群一起運動的昆蟲。然而，群的概念并不僅僅局限于昆蟲，例如：魚群，鳥群，也都表現(xiàn)出一定的群集性。

群的每個成員，稱為一個個體。每個個體，其運動只遵循簡單的規(guī)則。并且群成員之間是平等關(guān)系，而沒有主從關(guān)系。由這些平等的、相互間能夠協(xié)調(diào)運動的個體的集合，稱之為“群”。群智能(SwarmIntelligence)通過觀察鳥群和魚群，科學(xué)家發(fā)現(xiàn)，由這些生物群體所表現(xiàn)出的集體行為以及群成員之間的相互作用是如此的協(xié)調(diào)，以致于我們從主觀的觀感上認(rèn)為群的運動一定是由一個或若干個“與眾不同”的群成員所指揮。

然而事實并非如此。

因此，一個問題產(chǎn)生了：Howcouldaswarmperformlikethat？答案只有一個：群智能。

實際上，群成員的集體運動以及它們之間的相互作用是從每個群成員個體所遵循的一些簡單行為規(guī)則自底向上的一種“突現(xiàn)（emergence）”。個體僅具有簡單智能，但群體行為卻表現(xiàn)出比較高級的智能。

5

preyfoodanobstacleislaidinthepath

choosingpaththeshortestpath觀察發(fā)現(xiàn)，螞蟻可以在沒有任何可見提示的情況下，找出從巢穴到食物源的最短路徑，并且能隨環(huán)境的變化而變化。(1)螞蟻的覓食行為螞蟻是如何在食物源和巢穴之間找到最短路徑的？

在螞蟻的體內(nèi)存有一種化學(xué)物質(zhì)，稱為信息素（pheromone），當(dāng)它們移動時通過釋放信息素，以產(chǎn)生一條返回巢穴的路徑。

在尋找食物時，螞蟻先隨意地對其巢穴周圍的區(qū)域進(jìn)行搜尋，并在走過的路上留下信息素。一旦一只螞蟻找到了食物源，它會對食物做出評估并將一部分帶回巢穴。在返回的途中，螞蟻會根據(jù)食物的數(shù)量和質(zhì)量留下不同量的信息素，信息素的濃度痕跡會引導(dǎo)其他螞蟻找到食物源。蟻群算法原理7

螞蟻行為的機制

螞蟻個體之間的信息交換是一個正反饋過程，其覓食的協(xié)作本質(zhì)可以概括為：路徑概率選擇機制：信息素濃度越高的路線，被選中的概率越大。信息素更新機制：路徑越短，信息素的濃度增長得越快。協(xié)同工作機制：螞蟻個體之間通過信息素進(jìn)行信息傳遞。

由此，創(chuàng)造了蟻群優(yōu)化算法（AntColonyOptimization，ACO）

（2）鳥群行為9人們觀察鳥群的群體行為發(fā)現(xiàn)：當(dāng)一群鳥在隨機搜尋食物時，發(fā)現(xiàn)某個區(qū)域內(nèi)有一塊食物，鳥會先后飛向食物，以及在食物最近的鳥的周圍區(qū)域繼續(xù)搜尋食物。數(shù)目龐大的鳥群在飛行中可以有形的改變方向，散開，或者隊形的重組。

科學(xué)家認(rèn)為，上述行為是基于鳥類的社會行為中的兩個要素：個體經(jīng)驗和社會學(xué)習(xí)。由此，創(chuàng)造了粒子群優(yōu)化算法

（ParticleSwarmoptimization，PSO）

(3)魚群行為11

魚在一片水域的游動，可以歸納為四種行為：

a.覓食行為

當(dāng)魚群發(fā)現(xiàn)食物時，會向著食物的方向快速游去；

b.追尾行為

一條魚向其視野內(nèi)的另一條游向食物的魚游去；

c.聚群行為

為了避免被其他動物捕食，游向伙伴多的地方；d.隨機游動

無目的的游動。由此，創(chuàng)造了人工魚群算法（ArtificialFishSwarmAlgorithm，AFSA）

外國學(xué)者Reynolds使用計算機圖形動畫對復(fù)雜的群體行為進(jìn)行仿真，仿真中采用三個簡單規(guī)則，成功地模擬了飛行的鳥群。這三個規(guī)則是：1.避免碰撞2.飛向目標(biāo)3.飛向群體的中心在計算智能領(lǐng)域已經(jīng)取得成功的兩個典型的基于Swarmintelligence的優(yōu)化算法分別是蟻群算法和粒子群算法。除此之外，魚群算法、蜂群算法、蛙跳算法、螢火蟲算法、細(xì)菌覓食算法等基于群智能的優(yōu)化算法也受到了廣泛的關(guān)注。群智能算法蟻群算法

(AntColonyOptimization,ACO)

在非洲的大草原上，如果你發(fā)現(xiàn)羚羊在奔逃，那一定是獅子來了；如果見到獅子在躲避，那一定是象群在發(fā)怒了；如果見到成百上千的獅子和大象集體逃命的壯觀景象，那是什么來了呢？

——螞蟻軍團來了背景2001年至今1996年-2001年意大利學(xué)者Dorigo1991年啟發(fā)各種改進(jìn)算法的提出，應(yīng)用領(lǐng)域更廣引起學(xué)者關(guān)注，在應(yīng)用領(lǐng)域得到拓寬ACO首次被系統(tǒng)的提出自然界中真實蟻群集體行為MacroDorigo從自然界中蟻群的的覓食行為中受啟發(fā)，于1991年，由意大利學(xué)者M(jìn).Dorigo在其博士論文中提出，并成功的解決了旅行商(TSP)問題。針對該算法的不足，一些學(xué)者提出了許多改進(jìn)的蟻群優(yōu)化算法，如蟻群系統(tǒng)，最大-最小螞蟻系統(tǒng)，最優(yōu)保留蟻群系統(tǒng)等。一些學(xué)者提出了蟻群優(yōu)化元啟發(fā)式這一求解復(fù)雜問題的統(tǒng)一框架，這一框架為蟻群優(yōu)化算法的理論研究和設(shè)計提供了技術(shù)上的保障。我國最早研究蟻群算法的是東北大學(xué)的張紀(jì)會博士和徐心和教授。背景蟻群算法(antcolonyoptimization,ACO)，又稱螞蟻算法，是一種用來在圖中尋找優(yōu)化路徑的機率型算法。它由MarcoDorigo于1991年在他的博士論文中提出，其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。什么是蟻群算法信息素：信息素多的地方顯然經(jīng)過這里的螞蟻多，因而會有更多的螞蟻聚集過來。正反饋現(xiàn)象：某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。螞蟻如何找到最短路徑當(dāng)螞蟻沿著一條路到達(dá)終點以后會馬上返回來，這樣，短的路螞蟻來回一次的時間就短，這也意味著重復(fù)的頻率就快，因而在單位時間里走過的螞蟻數(shù)目就多，灑下的信息素自然也會多，自然會有更多的螞蟻被吸引過來，從而灑下更多的信息素……；而長的路正相反，因此，越來越多地螞蟻聚集到較短的路徑上來，最短的路徑就近似找到了。蟻群算法的基本思想蟻群算法的提出簡化的螞蟻尋食正反饋過程

螞蟻從A點出發(fā)，速度相同，食物在D點，可能隨機選擇路線ABD或ACD。假設(shè)初始時每條路線分配一只螞蟻，每個時間單位行走一步，本圖為經(jīng)過9個時間單位時的情形：走ABD的螞蟻到達(dá)終點，而走ACD的螞蟻剛好走到C點，為一半路程。蟻群算法的提出

本圖為從開始算起，經(jīng)過18個時間單位時的情形：走ABD的螞蟻到達(dá)終點后得到食物又返回了起點A，而走ACD的螞蟻剛好走到D點。蟻群算法的提出

假設(shè)螞蟻每經(jīng)過一處所留下的信息素為一個單位，則經(jīng)過36個時間單位后，所有開始一起出發(fā)的螞蟻都經(jīng)過不同路徑從D點取得了食物，此時ABD的路線往返了2趟，每一處的信息素為4個單位，而ACD的路線往返了一趟，每一處的信息素為2個單位，其比值為2：1。尋找食物的過程繼續(xù)進(jìn)行，則按信息素的指導(dǎo)，蟻群在ABD路線上增派一只螞蟻（共2只），而ACD路線上仍然為一只螞蟻。再經(jīng)過36個時間單位后，兩條線路上的信息素單位積累為12和4，比值為3：1。若按以上規(guī)則繼續(xù)，蟻群在ABD路線上再增派一只螞蟻（共3只），而ACD路線上仍然為一只螞蟻。再經(jīng)過36個時間單位后，兩條線路上的信息素單位積累為24和6，比值為4：1。若繼續(xù)進(jìn)行，則按信息素的指導(dǎo)，最終所有的螞蟻會放棄ACD路線，而都選擇ABD路線。這也就是前面所提到的正反饋效應(yīng)。蟻群算法的提出人工蟻群算法 基于以上蟻群尋找食物時的最優(yōu)路徑選擇問題，可以構(gòu)造人工蟻群，來解決最優(yōu)化問題，如TSP問題。 人工蟻群中把具有簡單功能的工作單元看作螞蟻。二者的相似之處在于都是優(yōu)先選擇信息素濃度大的路徑。較短路徑的信息素濃度高，所以能夠最終被所有螞蟻選擇，也就是最終的優(yōu)化結(jié)果。 兩者的區(qū)別在于人工蟻群有一定的記憶能力，能夠記憶已經(jīng)訪問過的節(jié)點。同時，人工蟻群在選擇下一條路徑的時候是按一定算法規(guī)律有意識地尋找最短路徑，而不是盲目的。例如在TSP問題中，可以預(yù)先知道當(dāng)前城市到下一個目的地的距離。人工蟻群VS自然蟻群蟻群算法的特征

蟻群算法采用了分布式正反饋并行計算機制,易于與其他方法結(jié)合,并具有較強的魯棒性。（1）其原理是一種正反饋機制或稱增強型學(xué)習(xí)系統(tǒng)；它通過信息素的不斷更新達(dá)到最終收斂于近似最優(yōu)路徑上；（2）它是一種通用型隨機優(yōu)化方法；但人工螞蟻決不是對實際螞蟻的一種簡單模擬，它融進(jìn)了人類的智能；（3）它是一種分布式的優(yōu)化方法；不僅適合目前的串行計算機，而且適合未來的并行計算機；（4）它是一種全局優(yōu)化的方法；不僅可用于求解單目標(biāo)優(yōu)化問題，而且可用于求解多目標(biāo)優(yōu)化問題；（5）它是一種啟發(fā)式算法；計算復(fù)雜性為O(NC*m*n2)，其中NC是迭代次數(shù)，m是螞蟻數(shù)目，n是目的節(jié)點數(shù)目。蟻群算法的基本思想算法流程圖：開始初始化迭代次數(shù)Nc=Nc+1螞蟻k=1螞蟻k=k+1按照狀態(tài)轉(zhuǎn)移概率公式選擇下一個元素修改禁忌表K>=螞蟻總數(shù)m？按照公式進(jìn)行信息量更新滿足結(jié)束條件？輸出程序計算結(jié)果結(jié)束YYNN蟻群系統(tǒng)在TSP問題中的應(yīng)用10城市TSP問題20城市TSP問題蟻群系統(tǒng)在TSP問題中的應(yīng)用30城市TSP問題48城市TSP問題蟻群算法的數(shù)學(xué)模型TSP算例分析旅行商問題（TSP）給定n個城市和兩個兩個城市之間的距離，要求確定一條經(jīng)過所有城市僅一次的最短路徑。第一步:初始化將m只螞蟻隨機放到n個城市，每只螞蟻的禁忌表為螞蟻當(dāng)前所在城市，各邊信息素初始化為c。禁忌表體現(xiàn)了人工螞蟻的記憶性，使得螞蟻不會走重復(fù)道路，提高了效率。蟻群算法的數(shù)學(xué)模型

第二步:選擇路徑路徑在t時刻，螞蟻k從城市i轉(zhuǎn)移到城市j的概率為：蟻群算法的數(shù)學(xué)模型

蟻群算法的數(shù)學(xué)模型蟻群的規(guī)模和停止規(guī)則蟻群大小:

一般情況下蟻群中螞蟻的個數(shù)不超過TSP圖中節(jié)點的個數(shù)。終止條件:1給定一個外循環(huán)的最大數(shù)目，表明已經(jīng)有足夠的螞蟻工作；

2當(dāng)前最優(yōu)解連續(xù)K次相同而停止，其中K是一個給定的整數(shù)，表示算法已經(jīng)收斂，不再需要繼續(xù)；

3目標(biāo)值控制規(guī)則，給定優(yōu)化問題（目標(biāo)最小化）的一個下界和一個誤差值，當(dāng)算法得到的目標(biāo)值同下界之差小于給定的誤差值時，算法終止。第四步：輸出結(jié)果若未達(dá)到終止條件則轉(zhuǎn)步驟二，否則，輸出目前的最優(yōu)解。TSP應(yīng)用舉例TSP應(yīng)用舉例TSP應(yīng)用舉例TSP應(yīng)用舉例TSP應(yīng)用舉例TSP應(yīng)用舉例總結(jié)：蟻群算法的基本思想以TSP問題為例：1、根據(jù)具體問題設(shè)置多只螞蟻，分頭并行搜索。

2、每只螞蟻完成一次周游后，在行進(jìn)的路上釋放信息素，信息素量與解的質(zhì)量成正比。

3、螞蟻路徑的選擇根據(jù)信息素強度大小（初始信息素量設(shè)為相等），同時考慮兩點之間的距離，采用隨機的局部搜索策略。這使得距離較短的邊，其上的信息素量較大，后來的螞蟻選擇該邊的概率也較大?？偨Y(jié)：蟻群算法的基本思想4、每只螞蟻只能走合法路線（經(jīng)過每個城市1次且僅1次），為此設(shè)置禁忌表來控制。

5、所有螞蟻都搜索完一次就是迭代一次，每迭代一次就對所有的邊做一次信息素更新，原來的螞蟻死掉，新的螞蟻進(jìn)行新一輪搜索。

6、更新信息素包括原有信息素的蒸發(fā)和經(jīng)過的路徑上信息素的增加。

7、達(dá)到預(yù)定的迭代步數(shù)，或出現(xiàn)停滯現(xiàn)象（所有螞蟻都選擇同樣的路徑，解不再變化），則算法結(jié)束，以當(dāng)前最優(yōu)解作為問題的解輸出。改進(jìn)的蟻群優(yōu)化算法▲最優(yōu)解保留策略螞蟻系統(tǒng)（帶精英策略的螞蟻系統(tǒng)ASelite）▲蟻群系統(tǒng)（ACS）▲最大-最小螞蟻系統(tǒng)（MMAS）▲基于優(yōu)化排序的螞蟻系統(tǒng)（ASrank）▲最優(yōu)最差螞蟻系統(tǒng)（BWAS）▲一種新的自適應(yīng)蟻群算法（AACA）▲基于混合行為的蟻群算法（HBACA）改進(jìn)的蟻群算法一般蟻群算法的框架主要有三個組成部分：蟻群的活動；信息素的揮發(fā)；信息素的增強；主要體現(xiàn)在轉(zhuǎn)移概率公式和信息素更新公式。（一）帶精英策略的螞蟻系統(tǒng)特點——在信息素更新時給予當(dāng)前最優(yōu)解以額外的信息素量，使最優(yōu)解得到更好的利用。找到全局最優(yōu)解的螞蟻稱為“精英螞蟻”?！⑽浵佋谶吷显黾拥男畔⑺亓浚弧⑽浵亗€數(shù)；——當(dāng)前全局最優(yōu)解路徑長度。特點１、狀態(tài)轉(zhuǎn)移規(guī)則——偽隨機比率規(guī)則

設(shè)為常數(shù)，為隨機數(shù)，如果，則螞蟻轉(zhuǎn)移的下一座城市是使取最大值的城市；若，仍按轉(zhuǎn)移概率確定。２、全局更新規(guī)則——只有精英螞蟻才允許釋放信息素，即只有全局最優(yōu)解所屬的邊才增加信息素。３、局部更新規(guī)則——螞蟻每次從城市轉(zhuǎn)移到城市后，邊上的信息素適當(dāng)減少。一般，取值較大。（二）蟻群系統(tǒng)

規(guī)則１和２都是為了使搜索過程更具有指導(dǎo)性，即使螞蟻的搜索主要集中在當(dāng)前找出的最好解鄰域內(nèi)。規(guī)則３則是為了使已選的邊對后來的螞蟻具有較小的影響力，以避免螞蟻收斂到同一路徑。（三）最大最小螞蟻系統(tǒng)

關(guān)于的取值，沒有確定的方法，有的書例子中取為0.01，10；有的書提出一個在最大值給定的情況下計算最小值的公式。1、每次迭代后，只對最優(yōu)解所屬路徑上的信息素更新。特點2、對每條邊的信息素量限制在范圍內(nèi)，目的是防止某一條路徑上的信息素量遠(yuǎn)大于其余路徑，避免過早收斂于局部最優(yōu)解。（四）基于優(yōu)化排序的螞蟻系統(tǒng)特點：每次迭代完成后，螞蟻所經(jīng)路徑由小到大排序，并根據(jù)路徑長度賦予不同的權(quán)重，路徑越短權(quán)重越大。信息素更新時對考慮權(quán)重的影響。特點：主要是修改了ACS中的全局更新公式，增加對最差螞蟻路徑信息素的更新，對最差解進(jìn)行削弱，使信息素差異進(jìn)一步增大。（五）最優(yōu)最差螞蟻系統(tǒng)（六）一種新的自適應(yīng)蟻群算法特點：將ACS中的狀態(tài)轉(zhuǎn)移規(guī)則改為自適應(yīng)偽隨機比率規(guī)則，動態(tài)調(diào)整轉(zhuǎn)移概率，以避免出現(xiàn)停滯現(xiàn)象。說明：在ACS的狀態(tài)轉(zhuǎn)移公式中，是給定的常數(shù)；在AACA中，是隨平均節(jié)點分支數(shù)ANB而變化的變量。ANB較大，意味著下一步可選的城市較多，也變大，表示選擇信息素和距離最好的邊的可能性增大；反之減小。（七）基于混合行為的蟻群算法特點：按螞蟻的行為特征將螞蟻分成4類，稱為4個子蟻群，各子蟻群按各自的轉(zhuǎn)移規(guī)則行動，搜索路徑，每迭代一次，更新當(dāng)前最優(yōu)解，按最優(yōu)路徑長度更新各條邊上的信息素，如此直至算法結(jié)束。螞蟻行為——螞蟻在前進(jìn)過程中，用以決定其下一步移動到哪個狀態(tài)的規(guī)則集合。1、螞蟻以隨機方式選擇下一步要到達(dá)的狀態(tài)。2、螞蟻以貪婪方式選擇下一步要到達(dá)的狀態(tài)。3、螞蟻按信息素強度選擇下一步要到達(dá)的狀態(tài)。4、螞蟻按信息素強度和城市間距離選擇下一步要到達(dá)的狀態(tài)。螞蟻行為蟻群算法的應(yīng)用蟻群算法的應(yīng)用舉例網(wǎng)絡(luò)路由問題將蟻群算法應(yīng)用于解決受限路由問題，目前可以解決包括帶寬、延時、丟包率和最小花費等約束條件在內(nèi)的QoS組播路由問題，比現(xiàn)有的鏈路狀態(tài)路由算法有明顯的優(yōu)越性蟻群算法的應(yīng)用舉例電力系統(tǒng)領(lǐng)域電力系統(tǒng)的許多優(yōu)化問題本質(zhì)上是屬于組合優(yōu)化問題。蟻群算法的應(yīng)用舉例航跡規(guī)劃問題

航跡規(guī)劃是指在特定的約束條件下，尋找運動體從初始點到目標(biāo)點滿足某種性能指標(biāo)最優(yōu)的運動軌跡。

混流裝配線調(diào)度混流裝配線(sequencingmixedmodelsonanassemblyline,SMMAL)是指一定時間內(nèi)，在一條生產(chǎn)線上生產(chǎn)出多種不同型號的產(chǎn)品，產(chǎn)品的品種可以隨顧客需求的變化而變化。SMMAL是車間作業(yè)調(diào)度問題(job-shopschedulingproblem,JSP)的具體應(yīng)用之一。SMMAL問題描述以汽車組裝為例，即在組裝所有車輛的過程中，所確定的組裝順序應(yīng)使各零部件的使用速率均勻化。如果不同型號的汽車消耗零部件的種類大致相同，那么原問題可簡化為單級SMMAL調(diào)度問題。SMMAL問題描述i表示車型數(shù)的標(biāo)號n表示需要裝配的車型數(shù)m表示裝配線上需要的零部件種類總數(shù)p表示生產(chǎn)調(diào)度中子裝配的標(biāo)號表示零部件p的理想使用速率j表示車型調(diào)度結(jié)果(即排序位置)的標(biāo)號D表示在一個生產(chǎn)循環(huán)中需要組裝的各種車型的總和SMMAL問題描述di表示在一個生產(chǎn)循環(huán)中車型i的數(shù)量bip表示生產(chǎn)每輛i車型需要零部件p的數(shù)量表示在組裝線調(diào)度中前j-1臺車消耗零部件p的數(shù)量和假設(shè)有3種車型A、B、C排序，每個生產(chǎn)循環(huán)需A型車3輛，B型車2輛，C型車1輛，則每個循環(huán)共需生產(chǎn)6輛車。采用下圖的搜索空間定義，列表示6個排序階段，行表示有3種車型可以選擇。蟻群算法就是不斷改變圓圈的大小，最終尋找到滿意的可行解。搜索的初始狀態(tài)

簡單SMMAL排序的搜索空間舉例經(jīng)過若干次迭代之后，搜索空間變化，此時最可能的可行解為B-A-C-A-B-A若干次迭代后的狀態(tài)局部搜索(