蟻群算法研究綜述(附視頻)課件

基于群智能的優(yōu)化算法蟻群算法研究綜述基于群智能的優(yōu)化算法蟻群算法研究綜述1目錄1234蟻群算法的應(yīng)用研究趨勢(shì)群智能概述2蟻群算法簡(jiǎn)述目錄1234蟻群算法的應(yīng)用研究趨勢(shì)群智能概述2蟻群算21.群智能概述人工智能涉及許多仿生學(xué)的內(nèi)容群智能：一類分散自組織個(gè)體的集體智能行為的總稱受到自然界群居動(dòng)物行為的啟發(fā)群：蟻群、鳥群、魚群、細(xì)菌群、蜂群等等1.群智能概述人工智能涉及許多仿生學(xué)的內(nèi)容31.群智能概述群居動(dòng)物的特點(diǎn)：群中個(gè)體的功能簡(jiǎn)單個(gè)體功能加在一起表現(xiàn)出復(fù)雜行為——智能行為螞蟻覓食行為1.群智能概述群居動(dòng)物的特點(diǎn)：41.群智能概述以蟻群為例單個(gè)螞蟻的能力有限，無法獨(dú)立存活蟻群具有強(qiáng)大的生存和適應(yīng)能力螞蟻間通過信息素實(shí)現(xiàn)交流，保證信息的傳播個(gè)體通過聚集成群后的交流，使得群內(nèi)涌現(xiàn)出智能經(jīng)典的群智能算法：蟻群算法（螞蟻覓食）粒子群算法（鳥覓食）人工蜂群算法（蜜蜂覓食）1.群智能概述以蟻群為例52.蟻群算法簡(jiǎn)述蟻群算法：1992年由意大利學(xué)者多里戈提出模擬螞蟻覓食過程中找到最佳路徑的行為一種新型的優(yōu)化算法，可用于求解NP難問題2.蟻群算法簡(jiǎn)述蟻群算法：62.蟻群算法簡(jiǎn)述雙橋?qū)嶒?yàn)：研究螞蟻的覓食行為分時(shí)段記錄各路徑上的螞蟻數(shù)量4分鐘時(shí)：螞蟻均勻的分布在橋上8分鐘時(shí)：大多數(shù)螞蟻從短的路徑上通過2.蟻群算法簡(jiǎn)述雙橋?qū)嶒?yàn)：研究螞蟻的覓食行為72.蟻群算法簡(jiǎn)述螞蟻覓食過程：初始螞蟻隨機(jī)移動(dòng)遇到食物分泌信息素（揮發(fā)性物質(zhì)）螞蟻在搬運(yùn)食物回家的路上留下信息素其他螞蟻選擇信息素濃度高的路移動(dòng)信息素會(huì)隨著時(shí)間慢慢揮發(fā)，但關(guān)鍵路徑上的信息素相對(duì)濃度高結(jié)果：蟻群找到一條覓食的最短路徑2.蟻群算法簡(jiǎn)述螞蟻覓食過程：82.蟻群算法簡(jiǎn)述蟻群覓食分析：基于螞蟻尋找食物時(shí)的最短路徑選擇問題，可以構(gòu)造人工蟻群，解決優(yōu)化問題人工螞蟻VS自然螞蟻相似：都優(yōu)先選擇信息素濃度大的路徑不同：人工螞蟻有記憶能力，記錄訪問過的位置人工螞蟻按預(yù)先設(shè)定的順序選擇下一條路徑2.蟻群算法簡(jiǎn)述蟻群覓食分析：92.蟻群算法簡(jiǎn)述例：旅行商問題（TSP）:有一個(gè)推銷員，要到n個(gè)城市推銷商品。要求是從某個(gè)城市出發(fā)，在訪問過所有n個(gè)城市后回到出發(fā)地，求整個(gè)過程的最短路徑是哪條？屬于組合優(yōu)化問題被證明具有NPC計(jì)算復(fù)雜性2.蟻群算法簡(jiǎn)述例：旅行商問題（TSP）:102.蟻群算法簡(jiǎn)述蟻群算法步驟：初始化確定行走方向更新禁忌表求信息素增量將m只螞蟻隨機(jī)放置。設(shè)定信息素初始值將訪問過的城市添加到禁忌表。根據(jù)轉(zhuǎn)移概率公式選擇下一訪問地點(diǎn)。判斷終止條件每只螞蟻周游玩一周之后，計(jì)算每條邊上信息素增量。當(dāng)算法滿足終止條件時(shí)，算法結(jié)束。2.蟻群算法簡(jiǎn)述蟻群算法步驟：初始化確定行走方向更新禁忌表求112.蟻群算法簡(jiǎn)述蟻群算法步驟：設(shè)置時(shí)間t=0設(shè)置迭代次數(shù)NC=1，設(shè)置最大迭代次數(shù)設(shè)置螞蟻數(shù)k=1每條邊上信息素濃度相同將m只螞蟻隨機(jī)放到n個(gè)城市初始化更新禁忌表確定行走方向求信息素增量判斷終止條件2.蟻群算法簡(jiǎn)述蟻群算法步驟：初始化更新禁忌表確定行走方向求122.蟻群算法簡(jiǎn)述蟻群算法步驟：轉(zhuǎn)移概率公式：初始化更新禁忌表確定行走方向求信息素增量判斷終止準(zhǔn)則2.蟻群算法簡(jiǎn)述蟻群算法步驟：初始化更新禁忌表確定行走方向求132.蟻群算法簡(jiǎn)述蟻群算法步驟：將訪問過的城市加入禁忌表禁忌表：作用是防止螞蟻?zhàn)咧貜?fù)的路徑，走過一個(gè)城市，就把它的編號(hào)加入到禁忌表。初始化更新禁忌表確定行走方向求信息素增量判斷終止準(zhǔn)則2.蟻群算法簡(jiǎn)述蟻群算法步驟：初始化更新禁忌表確定行走方向求142.蟻群算法簡(jiǎn)述蟻群算法步驟：更新每條支路上信息素初始化更新禁忌表確定行走方向求信息素增量判斷終止準(zhǔn)則每條邊的信息素增量2.蟻群算法簡(jiǎn)述蟻群算法步驟：初始化更新禁忌表確定行走方向求152.蟻群算法簡(jiǎn)述蟻群算法步驟： 判斷迭代次數(shù)是否是達(dá)到預(yù)先設(shè)置的NCmax，若沒有則繼續(xù)迭代，否則輸出結(jié)果。初始化更新禁忌表確定行走方向求信息素增量判斷終止準(zhǔn)則2.蟻群算法簡(jiǎn)述蟻群算法步驟：初始化更新禁忌表確定行走方向求162.蟻群算法簡(jiǎn)述MATLAB仿真:使用德國(guó)海德堡大學(xué)的TSPLIB95數(shù)據(jù)庫算法的參數(shù)設(shè)置為：迭代次數(shù)：40、螞蟻數(shù)：5、期望因子：10信息素?fù)]發(fā)因子：0.5、信息素強(qiáng)度：1002.蟻群算法簡(jiǎn)述MATLAB仿真:172.蟻群算法簡(jiǎn)述MATLAB仿真：Eil51數(shù)據(jù)庫2.蟻群算法簡(jiǎn)述MATLAB仿真：Eil51數(shù)據(jù)庫183.蟻群算法的應(yīng)用

蟻群算法主要用來解決路徑規(guī)劃等離散優(yōu)化問題，比如旅行商問題、指派問題、調(diào)度問題等。其后，許多研究者進(jìn)一步發(fā)展了這一算法，并將他們的研究成果應(yīng)用到許多領(lǐng)域。蟻群算法的應(yīng)用主要表現(xiàn)在以下幾個(gè)方面組合優(yōu)化問題中的應(yīng)用聚類問題路由算法設(shè)計(jì)圖著色問題車輛調(diào)度路徑規(guī)劃3.蟻群算法的應(yīng)用 蟻群算法主要用來解決路徑規(guī)劃等離散優(yōu)化193.蟻群算法的應(yīng)用聚類問題：起源于對(duì)蟻群蟻卵分類的研究算法基本思想將待聚類物體隨機(jī)地分散在一個(gè)二維平面上虛擬螞蟻分布在空間內(nèi)，并以隨機(jī)方式移動(dòng)當(dāng)螞蟻遇到一個(gè)待聚類物體時(shí)，將物體拾起并繼續(xù)隨機(jī)移動(dòng)若運(yùn)動(dòng)路徑附近的物體與背負(fù)的物體相似時(shí)，將其放到該位置，然后繼續(xù)移動(dòng)。重復(fù)上述過程3.蟻群算法的應(yīng)用聚類問題：起源于對(duì)蟻群蟻卵分類的研究203.蟻群算法的應(yīng)用聚類問題：四色聚類實(shí)驗(yàn)3.蟻群算法的應(yīng)用聚類問題：四色聚類實(shí)驗(yàn)213.蟻群算法的應(yīng)用聚類問題：八色聚類實(shí)驗(yàn)3.蟻群算法的應(yīng)用聚類問題：八色聚類實(shí)驗(yàn)223.蟻群算法的應(yīng)用路由問題：HP公司和英國(guó)電信公司在90年代中后期都開展了這方面的研究設(shè)計(jì)了蟻群路由算法（ANTCOLONYROUTING）目前的研究熱點(diǎn)在WSN的路由優(yōu)化問題3.蟻群算法的應(yīng)用路由問題：234.蟻群算法研究趨勢(shì) 蟻群算法也存在一些缺陷，如：算法需要較長(zhǎng)的搜索時(shí)間，而且該方法容易出現(xiàn)停滯現(xiàn)象，即搜索進(jìn)行到一定程度，所有個(gè)體發(fā)現(xiàn)的解完全一致，不能對(duì)解空間進(jìn)一步的搜索，它的改進(jìn)主要集中在以下三個(gè)方面：信息素的調(diào)整如開始搜索前所有信息素水平設(shè)為最大值，擴(kuò)大搜索范圍，采用最值蟻群算法減少停滯。搜索速度的改進(jìn)：引入偵察蟻、搜索蟻、工蟻。搜索策略的改善：加入擾動(dòng)、添加牽引力引導(dǎo)螞蟻朝全局最優(yōu)搜索。4.蟻群算法研究趨勢(shì) 蟻群算法也存在一些缺陷，如：算法需24基于群智能的優(yōu)化算法蟻群算法研究綜述基于群智能的優(yōu)化算法蟻群算法研究綜述25目錄1234蟻群算法的應(yīng)用研究趨勢(shì)群智能概述2蟻群算法簡(jiǎn)述目錄1234蟻群算法的應(yīng)用研究趨勢(shì)群智能概述2蟻群算261.群智能概述人工智能涉及許多仿生學(xué)的內(nèi)容群智能：一類分散自組織個(gè)體的集體智能行為的總稱受到自然界群居動(dòng)物行為的啟發(fā)群：蟻群、鳥群、魚群、細(xì)菌群、蜂群等等1.群智能概述人工智能涉及許多仿生學(xué)的內(nèi)容271.群智能概述群居動(dòng)物的特點(diǎn)：群中個(gè)體的功能簡(jiǎn)單個(gè)體功能加在一起表現(xiàn)出復(fù)雜行為——智能行為螞蟻覓食行為1.群智能概述群居動(dòng)物的特點(diǎn)：281.群智能概述以蟻群為例單個(gè)螞蟻的能力有限，無法獨(dú)立存活蟻群具有強(qiáng)大的生存和適應(yīng)能力螞蟻間通過信息素實(shí)現(xiàn)交流，保證信息的傳播個(gè)體通過聚集成群后的交流，使得群內(nèi)涌現(xiàn)出智能經(jīng)典的群智能算法：蟻群算法（螞蟻覓食）粒子群算法（鳥覓食）人工蜂群算法（蜜蜂覓食）1.群智能概述以蟻群為例292.蟻群算法簡(jiǎn)述蟻群算法：1992年由意大利學(xué)者多里戈提出模擬螞蟻覓食過程中找到最佳路徑的行為一種新型的優(yōu)化算法，可用于求解NP難問題2.蟻群算法簡(jiǎn)述蟻群算法：302.蟻群算法簡(jiǎn)述雙橋?qū)嶒?yàn)：研究螞蟻的覓食行為分時(shí)段記錄各路徑上的螞蟻數(shù)量4分鐘時(shí)：螞蟻均勻的分布在橋上8分鐘時(shí)：大多數(shù)螞蟻從短的路徑上通過2.蟻群算法簡(jiǎn)述雙橋?qū)嶒?yàn)：研究螞蟻的覓食行為312.蟻群算法簡(jiǎn)述螞蟻覓食過程：初始螞蟻隨機(jī)移動(dòng)遇到食物分泌信息素（揮發(fā)性物質(zhì)）螞蟻在搬運(yùn)食物回家的路上留下信息素其他螞蟻選擇信息素濃度高的路移動(dòng)信息素會(huì)隨著時(shí)間慢慢揮發(fā)，但關(guān)鍵路徑上的信息素相對(duì)濃度高結(jié)果：蟻群找到一條覓食的最短路徑2.蟻群算法簡(jiǎn)述螞蟻覓食過程：322.蟻群算法簡(jiǎn)述蟻群覓食分析：基于螞蟻尋找食物時(shí)的最短路徑選擇問題，可以構(gòu)造人工蟻群，解決優(yōu)化問題人工螞蟻VS自然螞蟻相似：都優(yōu)先選擇信息素濃度大的路徑不同：人工螞蟻有記憶能力，記錄訪問過的位置人工螞蟻按預(yù)先設(shè)定的順序選擇下一條路徑2.蟻群算法簡(jiǎn)述蟻群覓食分析：332.蟻群算法簡(jiǎn)述例：旅行商問題（TSP）:有一個(gè)推銷員，要到n個(gè)城市推銷商品。要求是從某個(gè)城市出發(fā)，在訪問過所有n個(gè)城市后回到出發(fā)地，求整個(gè)過程的最短路徑是哪條？屬于組合優(yōu)化問題被證明具有NPC計(jì)算復(fù)雜性2.蟻群算法簡(jiǎn)述例：旅行商問題（TSP）:342.蟻群算法簡(jiǎn)述蟻群算法步驟：初始化確定行走方向更新禁忌表求信息素增量將m只螞蟻隨機(jī)放置。設(shè)定信息素初始值將訪問過的城市添加到禁忌表。根據(jù)轉(zhuǎn)移概率公式選擇下一訪問地點(diǎn)。判斷終止條件每只螞蟻周游玩一周之后，計(jì)算每條邊上信息素增量。當(dāng)算法滿足終止條件時(shí)，算法結(jié)束。2.蟻群算法簡(jiǎn)述蟻群算法步驟：初始化確定行走方向更新禁忌表求352.蟻群算法簡(jiǎn)述蟻群算法步驟：設(shè)置時(shí)間t=0設(shè)置迭代次數(shù)NC=1，設(shè)置最大迭代次數(shù)設(shè)置螞蟻數(shù)k=1每條邊上信息素濃度相同將m只螞蟻隨機(jī)放到n個(gè)城市初始化更新禁忌表確定行走方向求信息素增量判斷終止條件2.蟻群算法簡(jiǎn)述蟻群算法步驟：初始化更新禁忌表確定行走方向求362.蟻群算法簡(jiǎn)述蟻群算法步驟：轉(zhuǎn)移概率公式：初始化更新禁忌表確定行走方向求信息素增量判斷終止準(zhǔn)則2.蟻群算法簡(jiǎn)述蟻群算法步驟：初始化更新禁忌表確定行走方向求372.蟻群算法簡(jiǎn)述蟻群算法步驟：將訪問過的城市加入禁忌表禁忌表：作用是防止螞蟻?zhàn)咧貜?fù)的路徑，走過一個(gè)城市，就把它的編號(hào)加入到禁忌表。初始化更新禁忌表確定行走方向求信息素增量判斷終止準(zhǔn)則2.蟻群算法簡(jiǎn)述蟻群算法步驟：初始化更新禁忌表確定行走方向求382.蟻群算法簡(jiǎn)述蟻群算法步驟：更新每條支路上信息素初始化更新禁忌表確定行走方向求信息素增量判斷終止準(zhǔn)則每條邊的信息素增量2.蟻群算法簡(jiǎn)述蟻群算法步驟：初始化更新禁忌表確定行走方向求392.蟻群算法簡(jiǎn)述蟻群算法步驟： 判斷迭代次數(shù)是否是達(dá)到預(yù)先設(shè)置的NCmax，若沒有則繼續(xù)迭代，否則輸出結(jié)果。初始化更新禁忌表確定行走方向求信息素增量判斷終止準(zhǔn)則2.蟻群算法簡(jiǎn)述蟻群算法步驟：初始化更新禁忌表確定行走方向求402.蟻群算法簡(jiǎn)述MATLAB仿真:使用德國(guó)海德堡大學(xué)的TSPLIB95數(shù)據(jù)庫算法的參數(shù)設(shè)置為：迭代次數(shù)：40、螞蟻數(shù)：5、期望因子：10信息素?fù)]發(fā)因子：0.5、信息素強(qiáng)度：1002.蟻群算法簡(jiǎn)述MATLAB仿真:412.蟻群算法簡(jiǎn)述MATLAB仿真：Eil51數(shù)據(jù)庫2.蟻群算法簡(jiǎn)述MATLAB仿真：Eil51數(shù)據(jù)庫423.蟻群算法的應(yīng)用

蟻群算法主要用來解決路徑規(guī)劃等離散優(yōu)化問題，比如旅行商問題、指派問題、調(diào)度問題等。其后，許多研究者進(jìn)一步發(fā)展了這一算法，并將他們的研究成果應(yīng)用到許多領(lǐng)域。蟻群算法的應(yīng)用主要表現(xiàn)在以下幾個(gè)方面組合優(yōu)化問題中的應(yīng)用聚類問題路由算法設(shè)計(jì)圖著色問題車輛調(diào)度路徑規(guī)劃3.蟻群算法的應(yīng)用 蟻群算法主要用來解決路徑規(guī)劃等離散優(yōu)化433.蟻群算法的應(yīng)用聚類問題：起源于對(duì)蟻群蟻卵分類的研究算法基本思想將待聚類物體隨機(jī)地分散在一個(gè)二維平面上虛擬螞蟻分布在空間內(nèi)，并以隨機(jī)方式移動(dòng)當(dāng)螞蟻遇到一個(gè)待聚類物體時(shí)，將物體拾起并繼續(xù)隨機(jī)移動(dòng)若運(yùn)動(dòng)路徑附近的物體與背負(fù)的物體相似時(shí)，將其放到該位置，然后繼續(xù)移動(dòng)。重復(fù)上述過程3.蟻群算法的應(yīng)用聚類問題：起源于對(duì)蟻群蟻卵分類的研究443.蟻群算法的應(yīng)用聚類問題：四色聚類實(shí)驗(yàn)3.蟻群算法的應(yīng)用聚類問題：四色聚類實(shí)驗(yàn)453.蟻群算法的應(yīng)用聚類問題：八色聚類實(shí)驗(yàn)3.蟻群算法的應(yīng)用聚類問題：八色聚類實(shí)驗(yàn)463.蟻群算法的應(yīng)用路由問題：HP公司和英國(guó)電信公司在90年代中后期都開展了這方面的研究設(shè)計(jì)了蟻群路由算法（ANTCOLONYROUTING