為解決障礙空間中的k近鄰查詢問題,提出一種基于改進的并行蟻群算法的k近鄰查詢方法（PAQ）。首先,利用不同信息素種類的蟻群實現(xiàn)并行查詢k近鄰;其次,增加時間因素作為路徑長短的判斷條件,以最直接地呈現(xiàn)螞蟻的搜索時間;然后,重新定義初始信息素濃度,以避免螞蟻的盲目搜索;最后,引入可視點將障礙路徑分割為多段歐氏路徑,選擇可視點進行概率轉(zhuǎn)移,并改進啟發(fā)函數(shù),以促使螞蟻朝著更為正確的方向搜索,避免算法過早陷入局部最優(yōu)。與WithGrids相比,當(dāng)數(shù)據(jù)點個數(shù)小于300時,對于線段障礙,算法運行時間平均縮短約91.5%;對于多邊形障礙平均縮短約78.5%。實驗結(jié)果表明,該方法在數(shù)據(jù)規(guī)模較小時的運行時間具有明顯的優(yōu)勢,且可以處理多邊形障礙。 

【文章來源】：計算機應(yīng)用. 2019,39(03)北大核心CSCD

【文章頁數(shù)】：6 頁

【部分圖文】：

近鄰查詢的框架Fig．2Frameworkofknearestneighborquery表1各變量的含義

ρ值的選取Fig．3Selectionofρvalue

?對螞蟻的搜索方向加以修正，從而縮短了搜索時間。PAQ方法的運行時間增長的原因是參與障礙距離計算的障礙物個數(shù)的增加使計算開銷增大。而PAQ方法在處理多邊形障礙時的運行時間增長速度比處理線段障礙的快，原因是處理多邊形障礙物所需的可視點要多于處理線段障礙物的，這使障礙路徑的分段數(shù)增加，障礙距離的計算量增大。經(jīng)計算，在障礙物個數(shù)小于60時，在處理線段障礙時，PAQ運行效率較WithGrids平均提高94．2%;在處理多邊形障礙時，PAQ運行效率較WithGrids平均提高72．0%。圖5k對運行時間的影響Fig．5Effectsofkonrunningtime圖6數(shù)據(jù)點個數(shù)對運行時間的影響Fig．6Effectsofnumberofdatapointsonrunningtime圖7障礙物個數(shù)對運行時間的影響Fig．7EffectsofnumberofobstaclesonrunningtimePAQ方法中的并行部分是各蟻群同時從各自巢穴出發(fā)，獨立搜索到食物源的最短路徑。從圖8中可以看出，隨著數(shù)據(jù)點個數(shù)的增多，加速比在緩慢降低，主要原因是隨著數(shù)據(jù)點個數(shù)的增多，螞蟻的數(shù)量也在增加，并且蟻群中各螞蟻仍是串行實現(xiàn)的，運行時間也就隨之延長了。圖8PAQ的加速比Fig．8AccelerationratioofPAQ5結(jié)語本文提出了一種改進的并行蟻群算法來實現(xiàn)障礙空間中的k近鄰查詢。該方法用不同信息素種類的蟻群來實現(xiàn)蟻群算法的并行化，提高算法的效率。它加入時間因素作為最短路徑的判斷條件，選擇障礙空間中的可視點進行概率轉(zhuǎn)移，并利用重新定義的初始信息素濃度和改進的啟發(fā)函數(shù)來引導(dǎo)和修正螞蟻的搜索方向，改善蟻群算法的性能。實驗結(jié)果表明，在小規(guī)模數(shù)據(jù)下，改進的并行蟻群算法對障礙空間中的k近鄰查詢較WithGrids方法有更短的運行時間

【參考文獻】：
期刊論文
[1]基于蟻群算法的面向服務(wù)軟件的部署優(yōu)化方法[J]. 李琳,應(yīng)時,趙翀,董波.  電子學(xué)報. 2016(01)
[2]利用蟻群算法生成覆蓋表:探索與挖掘[J]. 曾夢凡,陳思洋,張文茜,聶長海.  軟件學(xué)報. 2016(04)
[3]基于蟻群算法的分布式衛(wèi)星光網(wǎng)絡(luò)波長路由分配技術(shù)研究[J]. 董毅,趙尚弘,李勇軍,趙靜,鄧博于.  電子與信息學(xué)報. 2015(11)
[4]一種基于蟻群優(yōu)化的顯著邊緣檢測算法[J]. 張志龍,楊衛(wèi)平,李吉成.  電子與信息學(xué)報. 2014(09)
[5]基于改進蟻群算法的服務(wù)組合優(yōu)化[J]. 夏亞梅,程渤,陳俊亮,孟祥武,劉棟.  計算機學(xué)報. 2012(02)



本文編號：3236382