應用捕食搜索策略的改進多態(tài)蟻群算法
發(fā)布時間：2021-09-08 15:37
結合捕食搜索策略對多態(tài)蟻群算法進行改良。該算法引入以下機制:在人工蟻選擇路徑階段,設置偵查素路徑為優(yōu)先,為非偵查素路徑設置懲罰因子;利用權值在偵查素和非偵查素路徑都施加信息素,通過該機制避免多態(tài)蟻群算法陷入停滯;在每輪人工蟻最優(yōu)結果的鄰域應用捕食搜索策略,并通過競爭機制選擇最優(yōu)解更新信息素。通過TSP的仿真實驗結果表明,提出的融合算法可以有目的地指導信息素分布,加快算法向最優(yōu)解的收斂速度及提高最優(yōu)解質(zhì)量,克服傳統(tǒng)多態(tài)蟻群算法的缺陷。
【文章來源】：計算機工程與應用. 2019,55(14)北大核心CSCD
【文章頁數(shù)】：7 頁
【部分圖文】：
多態(tài)蟻群算法的停滯示意
2019，55（14）4偵查素指導信息素分布的機制針對上述停滯問題，本文提出的PS-PACA采取如下策略：（1）合理設置nMAXPC，均勻化各路徑的信息素分布；（2）為信息素設置最大最小閾值，防止各路徑信息素差別過大；（3）優(yōu)化搜索蟻搜索路徑的方式；（4）優(yōu)化信息素揮發(fā)策略的方式對多態(tài)蟻群算法進行改良。對PACA停滯發(fā)生時螞蟻已走過的城市數(shù)進行統(tǒng)計，得出nMAXPC,TSP問題規(guī)模與已走過的城市數(shù)的關系如圖2所示，可見，nMAXPC設置得越小，停滯發(fā)生得越早；按照原PACA設置的nMAXPC顯然過小，這也是該算法很快陷入停滯的原因。此外，隨著TSP問題規(guī)模的擴大，PACA的停滯問題并沒有得到好轉。由圖2可知，隨著nMAXPC值的擴大，每輪螞蟻停滯前走過的城市增多。當nMAXPC=0時，螞蟻無法選擇城市。即算法剛開始就陷入停滯；當nMAXPC=n（n為城市數(shù)）時，停滯現(xiàn)象消失，nMAXPC值喪失減小搜索空間的意義；結合下面的優(yōu)化步驟，本文將nMAXPC選為n/2較為合理。Stutzle等[3]提出的最大-最小螞蟻系統(tǒng)（MAX-MINAntSystem，MMAS），通過為信息素設置上下限閾值的方法，改良了信息素濃度相差過大的情況。對于PACA，信息素的上下限閾值設置需滿足既可避免各路徑信息素相差過大，又能使最優(yōu)路徑有足夠的信息素留存。當偵查蟻在城市周圍留下偵察素后，搜索蟻首先按照式（6）從鄰近的nMAXPC個城市中選擇，當鄰近的nMAXPC個城市已被選盡時，則依據(jù)基本蟻群算法概率選擇公式進行選擇，并且設置懲罰因子λ，提高偵察素在尋優(yōu)過程中起到的作用。這樣兼顧了多態(tài)蟻群算法快速收斂的特點，又使算法避免了停滯的問題。Pkij=ìí
平均最優(yōu)值429.11428.877544.447898.60556.20578.2021763.1524393.90實驗設定代數(shù)10001000100010002000200020002000平均收斂代數(shù)6764796>1000681362550>2000σ/%0.730.6700.482.016.062.2514.60表1TSP問題測試結果050100150200250300Iterationtimes560540520500480460440420LengthMMASPS-PACA10203040506070706050403020100YX（a）最優(yōu)解隨迭代次數(shù)的收斂情況（b）經(jīng)PS-PACA優(yōu)化的最優(yōu)路徑圖4eil51問題測試結果050100150200250300Iterationtimes1000095009000850080007500LengthMMASPS-PACA12001000800600400200020040060080010001200140016001800YX（a）最優(yōu)解隨迭代次數(shù)的收斂情況（b）經(jīng)PS-PACA優(yōu)化的最優(yōu)路徑圖5berlin52問題測試結果趙亞文，等：應用捕食搜索策略的改進多態(tài)蟻群算法119
【參考文獻】：
期刊論文
[1]基于加工操作單元的多態(tài)蟻群裝夾規(guī)劃方法[J]. 黃風立,左春檉,顧金梅,王海燕,張禮兵. 機械工程學報. 2017(07)
[2]CCN中基于鄰居協(xié)作的多態(tài)蟻群路由算法[J]. 劉期烈,夏遠鵬,秦慶偉,馮志宇,吳鳳陽. 計算機工程與應用. 2017(24)
[3]多態(tài)蟻群算法的認知無線電頻譜分配[J]. 張婧怡,向新,王鋒,孫曄,魯陽,李斌. 空軍工程大學學報(自然科學版). 2016(02)
[4]基于多態(tài)蟻群算法的高光譜遙感影像最優(yōu)波段選擇[J]. 丁小輝,李華朋,張樹清. 遙感技術與應用. 2016(02)
[5]加權值多態(tài)蟻群算法[J]. 鮑文杰,朱信忠,趙建民,徐慧英. 軟件工程. 2016(04)
[6]基于信息素的自適應連續(xù)域混合蟻群算法[J]. 周裊,葛洪偉,蘇樹智. 計算機工程與應用. 2017(06)
[7]基于二次退火機制的改進多態(tài)蟻群算法[J]. 杜振鑫,王兆青,王枝楠,秦偉,段云濤. 中南大學學報(自然科學版). 2011(10)
[8]基于自適應多態(tài)免疫蟻群算法的TSP求解[J]. 吳建輝,章兢,劉朝華. 計算機應用研究. 2010(05)
[9]Linux集群下基于改進多態(tài)蟻群負載均衡算法研究[J]. 師淳,李志蜀. 四川大學學報(自然科學版). 2009(05)
[10]多態(tài)蟻群算法[J]. 徐精明,曹先彬,王煦法. 中國科學技術大學學報. 2005(01)
碩士論文
[1]多態(tài)蟻群算法在TSP問題應用中的改進與優(yōu)化[D]. 鮑文杰.浙江師范大學 2016
[2]多態(tài)蟻群算法研究及其應用[D]. 岳鳳.山東師范大學 2009
本文編號：3391042
【文章來源】：計算機工程與應用. 2019,55(14)北大核心CSCD
【文章頁數(shù)】：7 頁
【部分圖文】：
多態(tài)蟻群算法的停滯示意
2019，55（14）4偵查素指導信息素分布的機制針對上述停滯問題，本文提出的PS-PACA采取如下策略：（1）合理設置nMAXPC，均勻化各路徑的信息素分布；（2）為信息素設置最大最小閾值，防止各路徑信息素差別過大；（3）優(yōu)化搜索蟻搜索路徑的方式；（4）優(yōu)化信息素揮發(fā)策略的方式對多態(tài)蟻群算法進行改良。對PACA停滯發(fā)生時螞蟻已走過的城市數(shù)進行統(tǒng)計，得出nMAXPC,TSP問題規(guī)模與已走過的城市數(shù)的關系如圖2所示，可見，nMAXPC設置得越小，停滯發(fā)生得越早；按照原PACA設置的nMAXPC顯然過小，這也是該算法很快陷入停滯的原因。此外，隨著TSP問題規(guī)模的擴大，PACA的停滯問題并沒有得到好轉。由圖2可知，隨著nMAXPC值的擴大，每輪螞蟻停滯前走過的城市增多。當nMAXPC=0時，螞蟻無法選擇城市。即算法剛開始就陷入停滯；當nMAXPC=n（n為城市數(shù)）時，停滯現(xiàn)象消失，nMAXPC值喪失減小搜索空間的意義；結合下面的優(yōu)化步驟，本文將nMAXPC選為n/2較為合理。Stutzle等[3]提出的最大-最小螞蟻系統(tǒng)（MAX-MINAntSystem，MMAS），通過為信息素設置上下限閾值的方法，改良了信息素濃度相差過大的情況。對于PACA，信息素的上下限閾值設置需滿足既可避免各路徑信息素相差過大，又能使最優(yōu)路徑有足夠的信息素留存。當偵查蟻在城市周圍留下偵察素后，搜索蟻首先按照式（6）從鄰近的nMAXPC個城市中選擇，當鄰近的nMAXPC個城市已被選盡時，則依據(jù)基本蟻群算法概率選擇公式進行選擇，并且設置懲罰因子λ，提高偵察素在尋優(yōu)過程中起到的作用。這樣兼顧了多態(tài)蟻群算法快速收斂的特點，又使算法避免了停滯的問題。Pkij=ìí
平均最優(yōu)值429.11428.877544.447898.60556.20578.2021763.1524393.90實驗設定代數(shù)10001000100010002000200020002000平均收斂代數(shù)6764796>1000681362550>2000σ/%0.730.6700.482.016.062.2514.60表1TSP問題測試結果050100150200250300Iterationtimes560540520500480460440420LengthMMASPS-PACA10203040506070706050403020100YX（a）最優(yōu)解隨迭代次數(shù)的收斂情況（b）經(jīng)PS-PACA優(yōu)化的最優(yōu)路徑圖4eil51問題測試結果050100150200250300Iterationtimes1000095009000850080007500LengthMMASPS-PACA12001000800600400200020040060080010001200140016001800YX（a）最優(yōu)解隨迭代次數(shù)的收斂情況（b）經(jīng)PS-PACA優(yōu)化的最優(yōu)路徑圖5berlin52問題測試結果趙亞文，等：應用捕食搜索策略的改進多態(tài)蟻群算法119
【參考文獻】：
期刊論文
[1]基于加工操作單元的多態(tài)蟻群裝夾規(guī)劃方法[J]. 黃風立,左春檉,顧金梅,王海燕,張禮兵. 機械工程學報. 2017(07)
[2]CCN中基于鄰居協(xié)作的多態(tài)蟻群路由算法[J]. 劉期烈,夏遠鵬,秦慶偉,馮志宇,吳鳳陽. 計算機工程與應用. 2017(24)
[3]多態(tài)蟻群算法的認知無線電頻譜分配[J]. 張婧怡,向新,王鋒,孫曄,魯陽,李斌. 空軍工程大學學報(自然科學版). 2016(02)
[4]基于多態(tài)蟻群算法的高光譜遙感影像最優(yōu)波段選擇[J]. 丁小輝,李華朋,張樹清. 遙感技術與應用. 2016(02)
[5]加權值多態(tài)蟻群算法[J]. 鮑文杰,朱信忠,趙建民,徐慧英. 軟件工程. 2016(04)
[6]基于信息素的自適應連續(xù)域混合蟻群算法[J]. 周裊,葛洪偉,蘇樹智. 計算機工程與應用. 2017(06)
[7]基于二次退火機制的改進多態(tài)蟻群算法[J]. 杜振鑫,王兆青,王枝楠,秦偉,段云濤. 中南大學學報(自然科學版). 2011(10)
[8]基于自適應多態(tài)免疫蟻群算法的TSP求解[J]. 吳建輝,章兢,劉朝華. 計算機應用研究. 2010(05)
[9]Linux集群下基于改進多態(tài)蟻群負載均衡算法研究[J]. 師淳,李志蜀. 四川大學學報(自然科學版). 2009(05)
[10]多態(tài)蟻群算法[J]. 徐精明,曹先彬,王煦法. 中國科學技術大學學報. 2005(01)
碩士論文
[1]多態(tài)蟻群算法在TSP問題應用中的改進與優(yōu)化[D]. 鮑文杰.浙江師范大學 2016
[2]多態(tài)蟻群算法研究及其應用[D]. 岳鳳.山東師范大學 2009
本文編號：3391042
本文鏈接：http://sikaile.net/kejilunwen/sousuoyinqinglunwen/3391042.html
最近更新
教材專著
