《人工智能07蟻群算法及其應用.ppt》由會員分享，可在線閱讀，更多相關《人工智能07蟻群算法及其應用.ppt（51頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第七章 蟻群算法及其應用,蟻群算法的背景,20世紀50年代中期創(chuàng)立了仿生學，人們從生物進化的機理中受到啟發(fā)。提出了許多用以解決復雜優(yōu)化問題的新方法，如進化規(guī)劃、進化策略、遺傳算法等，這些算法成功地解決了一些實際問題。 蟻群算法從螞蟻覓食得到啟發(fā)。,蟻群算法的背景,仿生算法 集群智能算法 概率型算法 遺傳算法、進化算法 粒子群算法（課程論文2）、蟻群算法 用來解決眾多NP-hard問題,蟻群算法的背景,自然蟻群的自組織行為特征 高度結構化的組織雖然螞蟻的個體行為極其簡單，但由個體組成的蟻群卻構成高度結構化的社會組織，螞蟻社會的成員有分工，有相互的通信和信息傳遞。 自然優(yōu)化蟻群在覓食過程中，在沒有

2、任何提示下總能找到從蟻巢到食物源之間的最短路徑；當經(jīng)過的路線上出現(xiàn)障礙物時，還能迅速找到新的最優(yōu)路徑。 信息正反饋螞蟻在尋找食物時，在其經(jīng)過的路徑上釋放信息素（外激素）。螞蟻基本沒有視覺，但能在小范圍內(nèi)察覺同類散發(fā)的信息素的軌跡，由此來決定何去何從，并傾向于朝著信息素強度高的方向移動。 自催化行為某條路徑上走過的螞蟻越多，留下的信息素也越多（隨時間蒸發(fā)一部分），后來螞蟻選擇該路徑的概率也越高。,蟻群算法的背景,概念原型 各個螞蟻在沒有事先告訴他們食物在什么地方的前提下開始尋找食物。 當一只找到食物以后，它會向環(huán)境釋放一種揮發(fā)性分泌物pheromone (稱為信息素,該物質(zhì)隨著時間的推移會逐漸揮

3、發(fā)消失，信息素濃度的大小表征路徑的遠近)來實現(xiàn)的，吸引其他的螞蟻過來，這樣越來越多的螞蟻會找到食物。 有些螞蟻并沒有像其它螞蟻一樣總重復同樣的路，他們會另辟蹊徑，如果另開辟的道路比原來的其他道路更短，那么，漸漸地，更多的螞蟻被吸引到這條較短的路上來。 最后，經(jīng)過一段時間運行，就可能會出現(xiàn)一條最短的路徑被大多數(shù)螞蟻重復著。,蟻群算法的提出,算法的提出 蟻群算法（Ant Colony Optimization, ACO），又稱螞蟻算法一種用來在圖中尋找優(yōu)化路徑的機率型算法。 它由Marco Dorigo于1992年在他的博士論文“Ant system: optimization by a colo

4、ny of cooperating agents”中提出，其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。最早用于解決著名的旅行商問題(TSP , traveling salesman problem)。,蟻群算法的提出,基本原理 蟻群算法是對自然界螞蟻的尋徑方式進行模似而得出的一種仿生算法。 螞蟻在運動過程中，能夠在它所經(jīng)過的路徑上留下一種稱之為信息素(pheromone)的物質(zhì)進行信息傳遞，而且螞蟻在運動過程中能夠感知這種物質(zhì)，并以此指導自己的運動方向，因此由大量螞蟻組成的蟻群集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。,蟻群算法的提出

5、,簡化的螞蟻尋食正反饋過程 螞蟻從A點出發(fā)，速度相同，食物在D點，可能隨機選擇路線ABD或ACD。假設初始時每條路線分配一只螞蟻，每個時間單位行走一步，本圖為經(jīng)過9個時間單位時的情形：走ABD的螞蟻到達終點，而走ACD的螞蟻剛好走到C點，為一半路程。,蟻群算法的提出,本圖為從開始算起，經(jīng)過18個時間單位時的情形：走ABD的螞蟻到達終點后得到食物又返回了起點A，而走ACD的螞蟻剛好走到D點。,蟻群算法的提出,假設螞蟻每經(jīng)過一處所留下的信息素為一個單位，則經(jīng)過36個時間單位后，所有開始一起出發(fā)的螞蟻都經(jīng)過不同路徑從D點取得了食物，此時ABD的路線往返了2趟，每一處的信息素為4個單位，而 ACD

6、的路線往返了一趟，每一處的信息素為2個單位，其比值為2：1。 尋找食物的過程繼續(xù)進行，則按信息素的指導，蟻群在ABD路線上增派一只螞蟻（共2只），而ACD路線上仍然為一只螞蟻。再經(jīng)過36個時間單位后，兩條線路上的信息素單位積累為12和4，比值為3：1。 若按以上規(guī)則繼續(xù)，蟻群在ABD路線上再增派一只螞蟻（共3只），而ACD路線上仍然為一只螞蟻。再經(jīng)過36個時間單位后，兩條線路上的信息素單位積累為24和6，比值為4：1。 若繼續(xù)進行，則按信息素的指導，最終所有的螞蟻會放棄ACD路線，而都選擇ABD路線。這也就是前面所提到的正反饋效應。,蟻群算法的提出,人工蟻群算法 基于以上蟻群尋找食

7、物時的最優(yōu)路徑選擇問題，可以構造人工蟻群，來解決最優(yōu)化問題，如TSP問題。 人工蟻群中把具有簡單功能的工作單元看作螞蟻。二者的相似之處在于都是優(yōu)先選擇信息素濃度大的路徑。較短路徑的信息素濃度高，所以能夠最終被所有螞蟻選擇，也就是最終的優(yōu)化結果。 兩者的區(qū)別在于人工蟻群有一定的記憶能力，能夠記憶已經(jīng)訪問過的節(jié)點。同時，人工蟻群在選擇下一條路徑的時候是按一定算法規(guī)律有意識地尋找最短路徑，而不是盲目的。例如在TSP問題中，可以預先知道當前城市到下一個目的地的距離。 人工蟻群 VS 自然蟻群,蟻群算法的特征,蟻群算法采用了分布式正反饋并行計算機制, 易于與其他方法結合, 并具有較強的魯棒性。 （1）其

8、原理是一種正反饋機制或稱增強型學習系統(tǒng)；它通過信息素的不斷更新達到最終收斂于近似最優(yōu)路徑上； （2）它是一種通用型隨機優(yōu)化方法；但人工螞蟻決不是對實際螞蟻的一種簡單模擬，它融進了人類的智能； （3）它是一種分布式的優(yōu)化方法；不僅適合目前的串行計算機，而且適合未來的并行計算機； （4）它是一種全局優(yōu)化的方法；不僅可用于求解單目標優(yōu)化問題，而且可用于求解多目標優(yōu)化問題； （5）它是一種啟發(fā)式算法；計算復雜性為 O(NC*m*n2)，其中NC 是迭代次數(shù)，m 是螞蟻數(shù)目，n 是目的節(jié)點數(shù)目。,蟻群算法的特征,算法優(yōu)點： （1）求解問題的快速性由正反饋機制決定 （2）全局優(yōu)化性由分布式計算決定，避免蟻

9、群在尋優(yōu)空間中過早收斂 （3）有限時間內(nèi)答案的合理性由貪婪式搜索模式?jīng)Q定，使能在搜索過程的早期就找到可以接受的較好解,蟻群算法的基本思想,算法流程圖：,蟻群算法的基本思想,以TSP問題為例： 1、根據(jù)具體問題設置多只螞蟻，分頭并行搜索。 2、每只螞蟻完成一次周游后，在行進的路上釋放信息素，信息素量與解的質(zhì)量成正比。 3、螞蟻路徑的選擇根據(jù)信息素強度大小（初始信息素量設為相等），同時考慮兩點之間的距離，采用隨機的局部搜索策略。這使得距離較短的邊，其上的信息素量較大，后來的螞蟻選擇該邊的概率也較大。,蟻群算法的基本思想,4、每只螞蟻只能走合法路線（經(jīng)過每個城市1次且僅1次），為此設置禁忌表來控制。

10、 5、所有螞蟻都搜索完一次就是迭代一次，每迭代一次就對所有的邊做一次信息素更新，原來的螞蟻死掉，新的螞蟻進行新一輪搜索。 6、更新信息素包括原有信息素的蒸發(fā)和經(jīng)過的路徑上信息素的增加。 7、達到預定的迭代步數(shù)，或出現(xiàn)停滯現(xiàn)象（所有螞蟻都選擇同樣的路徑，解不再變化），則算法結束，以當前最優(yōu)解作為問題的解輸出。,蟻群算法的數(shù)學模型,TSP算例分析,旅行商問題（TSP）,給定n個城市和兩個兩個城市之間的距離，要求確定一條經(jīng)過所有城市僅一次的最短路徑。,第一步:初始化 將m只螞蟻隨機放到n個城市，每只螞蟻的禁忌表為螞蟻當前所在城市，各邊信息素初始化為c。 禁忌表體現(xiàn)了人工螞蟻的記憶性，使得螞蟻不會走重

11、復道路，提高了效率。,蟻群算法的數(shù)學模型,,,第二步:選擇路徑路徑 在t時刻，螞蟻k從城市i轉(zhuǎn)移到城市j的概率為：,,,,蟻群算法的數(shù)學模型,,,蟻群算法的數(shù)學模型,蟻群的規(guī)模和停止規(guī)則 蟻群大小: 一般情況下蟻群中螞蟻的個數(shù)不超過TSP圖中節(jié)點的個數(shù)。 終止條件: 1 給定一個外循環(huán)的最大數(shù)目，表明已經(jīng)有足夠的螞蟻工作； 2 當前最優(yōu)解連續(xù)K次相同而停止，其中K是一個給定的整數(shù)，表示算法已經(jīng)收斂，不再需要繼續(xù)； 3 目標值控制規(guī)則，給定優(yōu)化問題（目標最小化）的一個下界和一個誤差值，當算法得到的目標值同下界之差小于給定的誤差值時，算法終止。,第四步：輸出結果 若未達到終止條件則轉(zhuǎn)步驟二，

12、否則，輸出目前的最優(yōu)解。,TSP應用舉例,TSP應用舉例,TSP應用舉例,TSP應用舉例,TSP應用舉例,TSP應用舉例,改進的蟻群優(yōu)化算法,,一般蟻群算法的框架主要有三個組成部分： 蟻群的活動； 信息素的揮發(fā)； 信息素的增強； 主要體現(xiàn)在轉(zhuǎn)移概率公式和信息素更新公式。,（一）帶精英策略的螞蟻系統(tǒng),特點在信息素更新時給予當前最優(yōu)解以額外的信息素量，使最優(yōu)解得到更好的利用。找到全局最優(yōu)解的螞蟻稱為“精英螞蟻”。,（二）蟻群系統(tǒng),規(guī)則和都是為了使搜索過程更具有指導性，即使螞蟻的搜索主要集中在當前找出的最好解鄰域內(nèi)。規(guī)則則是為了使已選的邊對后來的螞蟻具有較小的影響力，以避免螞蟻收斂到同一路徑。,（三

13、）最大最小螞蟻系統(tǒng),關于 的取值，沒有確定的方法，有的 書例子中取為0.01，10；有的書提出一個在最大 值給定的情況下計算最小值的公式。,（四）基于優(yōu)化排序的螞蟻系統(tǒng),特點：每次迭代完成后，螞蟻所經(jīng)路徑由小到大排序， 并根據(jù)路徑長度賦予不同的權重，路徑越短權重越大。 信息素更新時對 考慮權重的影響。,（六）一種新的自適應蟻群算法,特點：將ACS中的狀態(tài)轉(zhuǎn)移規(guī)則改為自適應偽隨機 比率規(guī)則，動態(tài)調(diào)整轉(zhuǎn)移概率，以避免出現(xiàn) 停滯現(xiàn)象。,,說明：在ACS的狀態(tài)轉(zhuǎn)移公式中， 是給定的常數(shù)；在AACA中， 是隨平均節(jié)點分支數(shù)ANB而變 化的變量。ANB較大，意味著下一步可選的城市較多， 也

14、變大，表示選擇信息素和距離最好的邊的可能性增大；反之減小。,（七）基于混合行為的蟻群算法,特點：按螞蟻的行為特征將螞蟻分成4類，稱為4個子蟻群，各子蟻群按各自的轉(zhuǎn)移規(guī)則行動，搜索路徑，每迭代一次，更新當前最優(yōu)解，按最優(yōu)路徑長度更新各條邊上的信息素，如此直至算法結束。,螞蟻行為螞蟻在前進過程中，用以決定其下一步移動到哪個狀態(tài)的規(guī)則集合。,蟻群算法與遺傳、模擬退火算法的比較,實驗結果表明： 1、蟻群算法所找出的解的質(zhì)量最高，遺傳算法次之，模擬退火算法最低。 2、蟻群算法的收斂速度最快，遺傳算法次之，模擬退火算法最慢。蟻群算法之所以能夠快速收斂到全局最優(yōu)解，是因為該算法的個體之間不斷進行信息交流和傳

15、遞。單個個體容易收斂于局部最優(yōu)，多個個體通過合作可以很快地收斂于解空間的最優(yōu)解的附近。,蟻群算法的應用,應用領域 蟻群算法能夠被用于解決大多數(shù)優(yōu)化問題或者能夠轉(zhuǎn)化為優(yōu)化求解的問題。 現(xiàn)在其應用領域已擴展到多目標優(yōu)化、數(shù)據(jù)分類、數(shù)據(jù)聚類、模式識別、電信QoS管理、生物系統(tǒng)建模、流程規(guī)劃、信號處理、機器人控制、決策支持以及仿真和系統(tǒng)辯識等方面，群智能理論和方法為解決這類應用問題提供了新的途徑。,蟻群算法的應用,蟻群算法在電信路由優(yōu)化中已取得了一定的應用成果。HP公司和英國電信公司在90年代中后期都開展了這方面的研究，設計了蟻群路由算法（Ant Colony Routing, ACR）。 每只螞蟻

16、就像蟻群優(yōu)化算法中一樣，根據(jù)它在網(wǎng)絡上的經(jīng)驗與性能，動態(tài)更新路由表項。如果一只螞蟻因為經(jīng)過了網(wǎng)絡中堵塞的路由而導致了比較大的延遲，那么就對該表項做較大的增強。同時根據(jù)信息素揮發(fā)機制實現(xiàn)系統(tǒng)的信息更新，從而拋棄過期的路由信息。這樣，在當前最優(yōu)路由出現(xiàn)擁堵現(xiàn)象時，ACR算法就能迅速的搜尋另一條可替代的最優(yōu)路徑，從而提高網(wǎng)絡的均衡性、負荷量和利用率。目前這方面的應用研究仍在升溫，因為通信網(wǎng)絡的分布式信息結構、非穩(wěn)定隨機動態(tài)特性以及網(wǎng)絡狀態(tài)的異步演化與ACO的算法本質(zhì)和特性非常相似。,蟻群算法的應用,基于群智能的聚類算法起源于對蟻群蟻卵的分類研究。Lumer和Faieta將Deneubourg提出將蟻

17、巢分類模型應用于數(shù)據(jù)聚類分析。其基本思想是將待聚類數(shù)據(jù)隨機地散布到一個二維平面內(nèi)，然后將虛擬螞蟻分布到這個空間內(nèi)，并以隨機方式移動，當一只螞蟻遇到一個待聚類數(shù)據(jù)時即將之拾起并繼續(xù)隨機運動，若運動路徑附近的數(shù)據(jù)與背負的數(shù)據(jù)相似性高于設置的標準則將其放置在該位置，然后繼續(xù)移動，重復上述數(shù)據(jù)搬運過程。按照這樣的方法可實現(xiàn)對相似數(shù)據(jù)的聚類。,蟻群算法的應用,ACO還在許多經(jīng)典組合優(yōu)化問題中獲得了成功的應用，如二次規(guī)劃問題（QAP）、機器人路徑規(guī)劃、作業(yè)流程規(guī)劃、圖著色（Graph Coloring）等問題。 經(jīng)過多年的發(fā)展，ACO已成為能夠有效解決實際二次規(guī)劃問題的幾種重要算法之一。AS在作業(yè)流程計

18、劃（Job-shop Scheduling）問題中的應用實例已經(jīng)出現(xiàn)，這說明了AS在此領域的應用潛力。利用MAX-MIN AS解決PAQ也取得了比較理想的效果，并通過實驗中的計算數(shù)據(jù)證明采用該方法處理PAQ比較早的SA算法更好，且與禁忌搜索算法性能相當。利用ACO實現(xiàn)對生產(chǎn)流程和特料管理的綜合優(yōu)化，并通過與遺傳、模擬退火和禁忌搜索算法的比較證明了ACO的工程應用價值。,蟻群算法的應用,許多研究者將ACO用于了武器攻擊目標分配和優(yōu)化問題、車輛運行路徑規(guī)劃、區(qū)域性無線電頻率自動分配、Bayesian networks的訓練和集合覆蓋等應用優(yōu)化問題。Costa和Herz還提出了一種AS在規(guī)劃問題方面

19、的擴展應用圖著色問題，并取得了可與其他啟發(fā)式算法相比的效果。,應用舉例：基于實時流媒體框架的用戶接入問題,,,問題描述,（1）類似于傳統(tǒng)結構，視頻源依舊首先根據(jù)其到NVS的延時、帶寬以及NVS負載情況選擇接入某個NVS。 （2）然后，用戶請求該NVS所接入的視頻源并計算得出合適的proxy接入選擇（也可能直接接入該NVS）。 （3）隨后，視頻內(nèi)容由該NVS通過proxy傳輸轉(zhuǎn)發(fā)交付用戶（或直接傳輸，對應于用戶直連NVS情形）。,問題描述,,,適應函數(shù),應用舉例：以減排為目標的發(fā)電調(diào)度問題,2020/9/3,47,污染物排放,除硫、除硝、除塵設備,,排放到大氣中,二氧化硫（SO2）,氮氧化物（NOx）,煙塵,,,解決方案,2020/9/3,48,,,,,調(diào)度控制中心,電廠1,電廠n,,調(diào)度算法,本文算法：,蟻群算法,優(yōu)化目標：,路徑構造：,將調(diào)度任務 生成分配序列,,調(diào)度算法,選擇概率：,信息素更新規(guī)則：,算法偽代碼,