1、基于群智能的優(yōu)化算法蟻群算法研究綜述目 錄1234蟻群算法的應(yīng)用研究趨勢群智能概述2蟻群算法簡述1.群智能概述v 人工智能涉及許多仿生學(xué)的內(nèi)容v 群智能： 一類分散自組織個體的集體智能行為的總稱 受到自然界群居動物行為的啟發(fā) 群：蟻群、鳥群、魚群、細(xì)菌群、蜂群等等1.群智能概述v 群居動物的特點： 群中個體的功能簡單 個體功能加在一起表現(xiàn)出復(fù)雜行為智能行為v 螞蟻覓食行為1.群智能概述v 以蟻群為例 單個螞蟻的能力有限，無法獨立存活 蟻群具有強大的生存和適應(yīng)能力 螞蟻間通過信息素實現(xiàn)交流，保證信息的傳播 個體通過聚集成群后的交流，使得群內(nèi)涌現(xiàn)出智能v 經(jīng)典的群智能算法： 蟻群算法（螞蟻覓食）

2、粒子群算法（鳥覓食） 人工蜂群算法（蜜蜂覓食）2.蟻群算法簡述v 蟻群算法： 1992年由意大利學(xué)者多里戈提出 模擬螞蟻覓食過程中找到最佳路徑的行為 一種新型的優(yōu)化算法，可用于求解NP難問題2.蟻群算法簡述v 雙橋?qū)嶒灒貉芯课浵伒囊捠承袨関 分時段記錄各路徑上的螞蟻數(shù)量 4分鐘時：螞蟻均勻的分布在橋上 8分鐘時：大多數(shù)螞蟻從短的路徑上通過2.蟻群算法簡述v 螞蟻覓食過程： 初始螞蟻隨機移動 遇到食物分泌信息素（揮發(fā)性物質(zhì)） 螞蟻在搬運食物回家的路上留下信息素 其他螞蟻選擇信息素濃度高的路移動 信息素會隨著時間慢慢揮發(fā)，但關(guān)鍵路徑上的信息素相對濃度高v 結(jié)果： 蟻群找到一條覓食的最短路徑2.蟻群

3、算法簡述v 蟻群覓食分析： 基于螞蟻尋找食物時的最短路徑選擇問題，可以構(gòu)造人工蟻群，解決優(yōu)化問題v 人工螞蟻 VS 自然螞蟻v 相似： 都優(yōu)先選擇信息素濃度大的路徑v 不同： 人工螞蟻有記憶能力，記錄訪問過的位置 人工螞蟻按預(yù)先設(shè)定的順序選擇下一條路徑2.蟻群算法簡述v 例：旅行商問題（TSP）: 有一個推銷員，要到n個城市推銷商品。要求是從某個城市出發(fā)，在訪問過所有n個城市后回到出發(fā)地，求整個過程的最短路徑是哪條？v 屬于組合優(yōu)化問題v 被證明具有NPC計算復(fù)雜性2.蟻群算法簡述v 蟻群算法步驟：初始化確定行走方向更新禁忌表求信息素增量將m只螞蟻隨機放置。設(shè)定信息素初始值將訪問過的城市添加到

4、禁忌表。根據(jù)轉(zhuǎn)移概率公式選擇下一訪問地點。判斷終止條件每只螞蟻周游玩一周之后，計算每條邊上信息素增量。當(dāng)算法滿足終止條件時，算法結(jié)束。2.蟻群算法簡述v 蟻群算法步驟： 設(shè)置時間t=0 設(shè)置迭代次數(shù)NC=1，設(shè)置最大迭代次數(shù) 設(shè)置螞蟻數(shù)k=1 每條邊上信息素濃度相同 將m只螞蟻隨機放到n個城市初始化更新禁忌表確定行走方向求信息素增量判斷終止條件0)0(ijmaxNC2.蟻群算法簡述v 蟻群算法步驟： 轉(zhuǎn)移概率公式：初始化更新禁忌表確定行走方向求信息素增量判斷終止準(zhǔn)則)(tij2.蟻群算法簡述v 蟻群算法步驟： 將訪問過的城市加入禁忌表 禁忌表：作用是防止螞蟻走重復(fù)的路徑，走過一個城市，就把它的

5、編號加入到禁忌表。初始化更新禁忌表確定行走方向求信息素增量判斷終止準(zhǔn)則2.蟻群算法簡述v 蟻群算法步驟： 更新每條支路上信息素初始化更新禁忌表確定行走方向求信息素增量判斷終止準(zhǔn)則每條邊的信息素增量2.蟻群算法簡述v 蟻群算法步驟：判斷迭代次數(shù)是否是達(dá)到預(yù)先設(shè)置的NCmax，若沒有則繼續(xù)迭代，否則輸出結(jié)果。初始化更新禁忌表確定行走方向求信息素增量判斷終止準(zhǔn)則2.蟻群算法簡述v MATLAB仿真: 使用德國海德堡大學(xué)的TSPLIB95數(shù)據(jù)庫 算法的參數(shù)設(shè)置為： 迭代次數(shù)：40、螞蟻數(shù)：5、期望因子：10 信息素?fù)]發(fā)因子：0.5、信息素強度：1002.蟻群算法簡述v MATLAB仿真：Eil51數(shù)據(jù)

6、庫3.蟻群算法的應(yīng)用蟻群算法主要用來解決路徑規(guī)劃等離散優(yōu)化問題，比如旅行商問題、指派問題、調(diào)度問題等。其后，許多研究者進(jìn)一步發(fā)展了這一算法，并將他們的研究成果應(yīng)用到許多領(lǐng)域。蟻群算法的應(yīng)用主要表現(xiàn)在以下幾個方面v 組合優(yōu)化問題中的應(yīng)用聚類問題路由算法設(shè)計圖著色問題車輛調(diào)度路徑規(guī)劃3.蟻群算法的應(yīng)用v 聚類問題：起源于對蟻群蟻卵分類的研究v 算法基本思想 將待聚類物體隨機地分散在一個二維平面上 虛擬螞蟻分布在空間內(nèi)，并以隨機方式移動 當(dāng)螞蟻遇到一個待聚類物體時，將物體拾起并繼續(xù)隨機移動 若運動路徑附近的物體與背負(fù)的物體相似時，將其放到該位置，然后繼續(xù)移動。 重復(fù)上述過程3.蟻群算法的應(yīng)用v 聚類問題：四色聚類實驗3.蟻群算法的應(yīng)用v 聚類問題：八色聚類實驗3.蟻群算法的應(yīng)用v 路由問題： HP公司和英國電信公司在90年代中后期都開展了這方面的研究 設(shè)計了蟻群路由算法（ANT COLONY ROUTING） 目前的研究熱點在WSN的路由優(yōu)化問題4.蟻群算法研究趨勢 蟻群算法也存在一些缺陷，如：算法需要較長的搜索時間，而且該方法容易出現(xiàn)停滯現(xiàn)象，即搜索進(jìn)行到一定程度，所有個體發(fā)現(xiàn)的解完全一致，不能對解空間進(jìn)一步的搜索，它的改進(jìn)主要集中在以下三個方面