人工智能07蟻群算法及其應(yīng)用

章蟻群算法及其應(yīng)用2021/6/271蟻群算法的背景20世紀(jì)50年代中期創(chuàng)立了仿生學(xué)，人們從生物進(jìn)化的機(jī)理中受到啟發(fā)。提出了許多用以解決復(fù)雜優(yōu)化問題的新方法，如進(jìn)化規(guī)劃、進(jìn)化策略、遺傳算法等，這些算法成功地解決了一些實(shí)際問題。蟻群算法從螞蟻覓食得到啟發(fā)。2021/6/272蟻群算法的背景仿生算法集群智能算法概率型算法遺傳算法、進(jìn)化算法粒子群算法（課程論文2）、蟻群算法用來(lái)解決眾多NP-hard問題2021/6/273蟻群算法的背景自然蟻群的自組織行為特征高度結(jié)構(gòu)化的組織——雖然螞蟻的個(gè)體行為極其簡(jiǎn)單，但由個(gè)體組成的蟻群卻構(gòu)成高度結(jié)構(gòu)化的社會(huì)組織，螞蟻社會(huì)的成員有分工，有相互的通信和信息傳遞。自然優(yōu)化——蟻群在覓食過程中，在沒有任何提示下總能找到從蟻巢到食物源之間的最短路徑；當(dāng)經(jīng)過的路線上出現(xiàn)障礙物時(shí)，還能迅速找到新的最優(yōu)路徑。信息正反饋——螞蟻在尋找食物時(shí)，在其經(jīng)過的路徑上釋放信息素（外激素）。螞蟻基本沒有視覺，但能在小范圍內(nèi)察覺同類散發(fā)的信息素的軌跡，由此來(lái)決定何去何從，并傾向于朝著信息素強(qiáng)度高的方向移動(dòng)。自催化行為——某條路徑上走過的螞蟻越多，留下的信息素也越多（隨時(shí)間蒸發(fā)一部分），后來(lái)螞蟻選擇該路徑的概率也越高。2021/6/274蟻群算法的背景概念原型 各個(gè)螞蟻在沒有事先告訴他們食物在什么地方的前提下開始尋找食物。 當(dāng)一只找到食物以后，它會(huì)向環(huán)境釋放一種揮發(fā)性分泌物pheromone(稱為信息素,該物質(zhì)隨著時(shí)間的推移會(huì)逐漸揮發(fā)消失，信息素濃度的大小表征路徑的遠(yuǎn)近)來(lái)實(shí)現(xiàn)的，吸引其他的螞蟻過來(lái)，這樣越來(lái)越多的螞蟻會(huì)找到食物。 有些螞蟻并沒有像其它螞蟻一樣總重復(fù)同樣的路，他們會(huì)另辟蹊徑，如果另開辟的道路比原來(lái)的其他道路更短，那么，漸漸地，更多的螞蟻被吸引到這條較短的路上來(lái)。

最后，經(jīng)過一段時(shí)間運(yùn)行，就可能會(huì)出現(xiàn)一條最短的路徑被大多數(shù)螞蟻重復(fù)著。2021/6/275蟻群算法的提出算法的提出 蟻群算法（AntColonyOptimization,ACO），又稱螞蟻算法——一種用來(lái)在圖中尋找優(yōu)化路徑的機(jī)率型算法。 它由MarcoDorigo于1992年在他的博士論文“Antsystem:optimizationbyacolonyofcooperatingagents”中提出，其靈感來(lái)源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。最早用于解決著名的旅行商問題(TSP,travelingsalesmanproblem)。2021/6/276蟻群算法的提出基本原理

蟻群算法是對(duì)自然界螞蟻的尋徑方式進(jìn)行模似而得出的一種仿生算法。螞蟻在運(yùn)動(dòng)過程中，能夠在它所經(jīng)過的路徑上留下一種稱之為信息素(pheromone)的物質(zhì)進(jìn)行信息傳遞，而且螞蟻在運(yùn)動(dòng)過程中能夠感知這種物質(zhì)，并以此指導(dǎo)自己的運(yùn)動(dòng)方向，因此由大量螞蟻組成的蟻群集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過的螞蟻越多，則后來(lái)者選擇該路徑的概率就越大。2021/6/277蟻群算法的提出簡(jiǎn)化的螞蟻尋食正反饋過程

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

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

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

蟻群算法采用了分布式正反饋并行計(jì)算機(jī)制,易于與其他方法結(jié)合,并具有較強(qiáng)的魯棒性。（1）其原理是一種正反饋機(jī)制或稱增強(qiáng)型學(xué)習(xí)系統(tǒng)；它通過信息素的不斷更新達(dá)到最終收斂于近似最優(yōu)路徑上；（2）它是一種通用型隨機(jī)優(yōu)化方法；但人工螞蟻決不是對(duì)實(shí)際螞蟻的一種簡(jiǎn)單模擬，它融進(jìn)了人類的智能；（3）它是一種分布式的優(yōu)化方法；不僅適合目前的串行計(jì)算機(jī)，而且適合未來(lái)的并行計(jì)算機(jī)；（4）它是一種全局優(yōu)化的方法；不僅可用于求解單目標(biāo)優(yōu)化問題，而且可用于求解多目標(biāo)優(yōu)化問題；（5）它是一種啟發(fā)式算法；計(jì)算復(fù)雜性為O(NC*m*n2)，其中NC是迭代次數(shù)，m是螞蟻數(shù)目，n是目的節(jié)點(diǎn)數(shù)目。2021/6/2712蟻群算法的特征算法優(yōu)點(diǎn)：（1）求解問題的快速性——由正反饋機(jī)制決定（2）全局優(yōu)化性——由分布式計(jì)算決定，避免蟻群在尋優(yōu)空間中過早收斂（3）有限時(shí)間內(nèi)答案的合理性——由貪婪式搜索模式?jīng)Q定，使能在搜索過程的早期就找到可以接受的較好解2021/6/2713蟻群算法的基本思想算法流程圖：開始初始化迭代次數(shù)Nc=Nc+1螞蟻k=1螞蟻k=k+1按照狀態(tài)轉(zhuǎn)移概率公式選擇下一個(gè)元素修改禁忌表K>=螞蟻總數(shù)m？按照公式進(jìn)行信息量更新滿足結(jié)束條件？輸出程序計(jì)算結(jié)果結(jié)束YYNN2021/6/2714蟻群算法的基本思想以TSP問題為例：1、根據(jù)具體問題設(shè)置多只螞蟻，分頭并行搜索。

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

3、螞蟻路徑的選擇根據(jù)信息素強(qiáng)度大?。ǔ跏夹畔⑺亓吭O(shè)為相等），同時(shí)考慮兩點(diǎn)之間的距離，采用隨機(jī)的局部搜索策略。這使得距離較短的邊，其上的信息素量較大，后來(lái)的螞蟻選擇該邊的概率也較大。2021/6/2715蟻群算法的基本思想4、每只螞蟻只能走合法路線（經(jīng)過每個(gè)城市1次且僅1次），為此設(shè)置禁忌表來(lái)控制。

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

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

7、達(dá)到預(yù)定的迭代步數(shù)，或出現(xiàn)停滯現(xiàn)象（所有螞蟻都選擇同樣的路徑，解不再變化），則算法結(jié)束，以當(dāng)前最優(yōu)解作為問題的解輸出。2021/6/2716蟻群算法的數(shù)學(xué)模型TSP算例分析旅行商問題（TSP）給定n個(gè)城市和兩個(gè)兩個(gè)城市之間的距離，要求確定一條經(jīng)過所有城市僅一次的最短路徑。第一步:初始化將m只螞蟻隨機(jī)放到n個(gè)城市，每只螞蟻的禁忌表為螞蟻當(dāng)前所在城市，各邊信息素初始化為c。禁忌表體現(xiàn)了人工螞蟻的記憶性，使得螞蟻不會(huì)走重復(fù)道路，提高了效率。2021/6/2717蟻群算法的數(shù)學(xué)模型

第二步:選擇路徑路徑在t時(shí)刻，螞蟻k從城市i轉(zhuǎn)移到城市j的概率為：2021/6/2718蟻群算法的數(shù)學(xué)模型2021/6/2719蟻群算法的數(shù)學(xué)模型蟻群的規(guī)模和停止規(guī)則蟻群大小:

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

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

3目標(biāo)值控制規(guī)則，給定優(yōu)化問題（目標(biāo)最小化）的一個(gè)下界和一個(gè)誤差值，當(dāng)算法得到的目標(biāo)值同下界之差小于給定的誤差值時(shí)，算法終止。第四步：輸出結(jié)果若未達(dá)到終止條件則轉(zhuǎn)步驟二，否則，輸出目前的最優(yōu)解。2021/6/2720TSP應(yīng)用舉例2021/6/2721TSP應(yīng)用舉例2021/6/2722TSP應(yīng)用舉例2021/6/2723TSP應(yīng)用舉例2021/6/2724TSP應(yīng)用舉例2021/6/2725TSP應(yīng)用舉例2021/6/2726改進(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)的蟻群算法2021/6/2727一般蟻群算法的框架主要有三個(gè)組成部分：蟻群的活動(dòng)；信息素的揮發(fā)；信息素的增強(qiáng)；主要體現(xiàn)在轉(zhuǎn)移概率公式和信息素更新公式。2021/6/2728（一）帶精英策略的螞蟻系統(tǒng)特點(diǎn)——在信息素更新時(shí)給予當(dāng)前最優(yōu)解以額外的信息素量，使最優(yōu)解得到更好的利用。找到全局最優(yōu)解的螞蟻稱為“精英螞蟻”。——精英螞蟻在邊上增加的信息素量；——精英螞蟻個(gè)數(shù)；——當(dāng)前全局最優(yōu)解路徑長(zhǎng)度。2021/6/2729特點(diǎn)１、狀態(tài)轉(zhuǎn)移規(guī)則——偽隨機(jī)比率規(guī)則

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

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

關(guān)于的取值，沒有確定的方法，有的書例子中取為0.01，10；有的書提出一個(gè)在最大值給定的情況下計(jì)算最小值的公式。1、每次迭代后，只對(duì)最優(yōu)解所屬路徑上的信息素更新。特點(diǎn)2、對(duì)每條邊的信息素量限制在范圍內(nèi)，目的是防止某一條路徑上的信息素量遠(yuǎn)大于其余路徑，避免過早收斂于局部最優(yōu)解。（四）基于優(yōu)化排序的螞蟻系統(tǒng)特點(diǎn)：每次迭代完成后，螞蟻所經(jīng)路徑由小到大排序，并根據(jù)路徑長(zhǎng)度賦予不同的權(quán)重，路徑越短權(quán)重越大。信息素更新時(shí)對(duì)考慮權(quán)重的影響。2021/6/2731特點(diǎn)：主要是修改了ACS中的全局更新公式，增加對(duì)最差螞蟻路徑信息素的更新，對(duì)最差解進(jìn)行削弱，使信息素差異進(jìn)一步增大。（五）最優(yōu)最差螞蟻系統(tǒng)（六）一種新的自適應(yīng)蟻群算法特點(diǎn)：將ACS中的狀態(tài)轉(zhuǎn)移規(guī)則改為自適應(yīng)偽隨機(jī)比率規(guī)則，動(dòng)態(tài)調(diào)整轉(zhuǎn)移概率，以避免出現(xiàn)停滯現(xiàn)象。說(shuō)明：在ACS的狀態(tài)轉(zhuǎn)移公式中，是給定的常數(shù)；在AACA中，是隨平均節(jié)點(diǎn)分支數(shù)ANB而變化的變量。ANB較大，意味著下一步可選的城市較多，也變大，表示選擇信息素和距離最好的邊的可能性增大；反之減小。2021/6/2732（七）基于混合行為的蟻群算法特點(diǎn)：按螞蟻的行為特征將螞蟻分成4類，稱為4個(gè)子蟻群，各子蟻群按各自的轉(zhuǎn)移規(guī)則行動(dòng)，搜索路徑，每迭代一次，更新當(dāng)前最優(yōu)解，按最優(yōu)路徑長(zhǎng)度更新各條邊上的信息素，如此直至算法結(jié)束。螞蟻行為——螞蟻在前進(jìn)過程中，用以決定其下一步移動(dòng)到哪個(gè)狀態(tài)的規(guī)則集合。1、螞蟻以隨機(jī)方式選擇下一步要到達(dá)的狀態(tài)。2、螞蟻以貪婪方式選擇下一步要到達(dá)的狀態(tài)。3、螞蟻按信息素強(qiáng)度選擇下一步要到達(dá)的狀態(tài)。4、螞蟻按信息素強(qiáng)度和城市間距離選擇下一步要到達(dá)的狀態(tài)。螞蟻行為2021/6/2733蟻群算法與遺傳、模擬退火算法的比較實(shí)驗(yàn)結(jié)果表明：1、蟻群算法所找出的解的質(zhì)量最高，遺傳算法次之，模擬退火算法最低。2、蟻群算法的收斂速度最快，遺傳算法次之，模擬退火算法最慢。蟻群算法之所以能夠快速收斂到全局最優(yōu)解，是因?yàn)樵撍惴ǖ膫€(gè)體之間不斷進(jìn)行信息交流和傳遞。單個(gè)個(gè)體容易收斂于局部最優(yōu)，多個(gè)個(gè)體通過合作可以很快地收斂于解空間的最優(yōu)解的附近。2021/6/2734蟻群算法的應(yīng)用應(yīng)用領(lǐng)域 蟻群算法能夠被用于解決大多數(shù)優(yōu)化問題或者能夠轉(zhuǎn)化為優(yōu)化求解的問題。 現(xiàn)在其應(yīng)用領(lǐng)域已擴(kuò)展到多目標(biāo)優(yōu)化、數(shù)據(jù)分類、數(shù)據(jù)聚類、模式識(shí)別、電信QoS管理、生物系統(tǒng)建模、流程規(guī)劃、信號(hào)處理、機(jī)器人控制、決策支持以及仿真和系統(tǒng)辯識(shí)等方面，群智能理論和方法為解決這類應(yīng)用問題提供了新的途徑。2021/6/2735蟻群算法的應(yīng)用

蟻群算法在電信路由優(yōu)化中已取得了一定的應(yīng)用成果。HP公司和英國(guó)電信公司在90年代中后期都開展了這方面的研究，設(shè)計(jì)了蟻群路由算法（AntColonyRouting,ACR）。每只螞蟻就像蟻群優(yōu)化算法中一樣，根據(jù)它在網(wǎng)絡(luò)上的經(jīng)驗(yàn)與性能，動(dòng)態(tài)更新路由表項(xiàng)。如果一只螞蟻因?yàn)榻?jīng)過了網(wǎng)絡(luò)中堵塞的路由而導(dǎo)致了比較大的延遲，那么就對(duì)該表項(xiàng)做較大的增強(qiáng)。同時(shí)根據(jù)信息素?fù)]發(fā)機(jī)制實(shí)現(xiàn)系統(tǒng)的信息更新，從而拋棄過期的路由信息。這樣，在當(dāng)前最優(yōu)路由出現(xiàn)擁堵現(xiàn)象時(shí)，ACR算法就能迅速的搜尋另一條可替代的最優(yōu)路徑，從而提高網(wǎng)絡(luò)的均衡性、負(fù)荷量和利用率。目前這方面的應(yīng)用研究仍在升溫，因?yàn)橥ㄐ啪W(wǎng)絡(luò)的分布式信息結(jié)構(gòu)、非穩(wěn)定隨機(jī)動(dòng)態(tài)特性以及網(wǎng)絡(luò)狀態(tài)的異步演化與ACO的算法本質(zhì)和特性非常相似。2021/6/2736蟻群算法的應(yīng)用

基于群智能的聚類算法起源于對(duì)蟻群蟻卵的分類研究。Lumer和Faieta將Deneubourg提出將蟻巢分類模型應(yīng)用于數(shù)據(jù)聚類分析。其基本思想是將待聚類數(shù)據(jù)隨機(jī)地散布到一個(gè)二維平面內(nèi)，然后將虛擬螞蟻分布到這個(gè)空間內(nèi)，并以隨機(jī)方式移動(dòng)，當(dāng)一只螞蟻遇到一個(gè)待聚類數(shù)據(jù)時(shí)即將之拾起并繼續(xù)隨機(jī)運(yùn)動(dòng)，若運(yùn)動(dòng)路徑附近的數(shù)據(jù)與背負(fù)的數(shù)據(jù)相似性高于設(shè)置的標(biāo)準(zhǔn)則將其放置在該位置，然后繼續(xù)移動(dòng)，重復(fù)上述數(shù)據(jù)搬運(yùn)過程。按照這樣的方法可實(shí)現(xiàn)對(duì)相似數(shù)據(jù)的聚類。2021/6/2737蟻群算法的應(yīng)用 ACO還在許多經(jīng)典組合優(yōu)化問題中獲得了成功的應(yīng)用，如二次規(guī)劃問題（QAP）、機(jī)器人路徑規(guī)劃、作業(yè)流程規(guī)劃、圖著色（GraphColoring）等問題。 經(jīng)過多年的發(fā)展，ACO已成為能夠有效解決實(shí)際二次規(guī)劃問題的幾種重要算法之一。AS在作業(yè)流程計(jì)劃（Job-shopScheduling）問題中的應(yīng)用實(shí)例已經(jīng)出現(xiàn)，這說(shuō)明了AS在此領(lǐng)域的應(yīng)用潛力。利用MAX-MINAS解決PAQ也取得了比較理想的效果，并通過實(shí)驗(yàn)中的計(jì)算數(shù)據(jù)證明采用該方法處理PAQ比較早的SA算法更好，且與禁忌搜索算法