障礙空間中基于并行蟻群算法的k近鄰查詢

郭良敏 朱瑩 孫麗萍

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

關(guān)鍵詞：障礙空間;k近鄰;蟻群算法;并行化;可視點(diǎn)

中圖分類號(hào)： TP311

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-9081（2019）03-0790-06

Abstract： To solve the problem of k nearest neighbor query in obstacle space， a k nearest neighbor Query method based on improved Parallel Ant colony algorithm （PAQ） was proposed. Firstly， ant colonies with different kinds of pheromones were utilized to search k nearest neighbors in parallel. Secondly， a time factor was added as a condition of judging path length to directly show the searching time of ants. Thirdly， the concentration of initial pheromone was redefined to avoid the blind searching of ants. Finally， visible points were introduced to divide the obstacle path into multiple Euclidean paths， meawhile the heuristic function was improved and the visible points were selected by ants to conduct probability transfer making ants search in more proper direction and prevent the algorithm from falling into local optimum early. Compared to WithGrids method， with number of data points less than 300， the running time for line segment obstacle is averagely reduced by about 91.5%， and the running time for polygonal obstacle is averagely reduced by about 78.5%. The experimental results show that the running time of the proposed method has obvious advantage on small-scale data， and the method can process polygonal obstacles.

Key words： obstacle space; k nearest neighbors; ant colony algorithm; parallelization; visible point

0 引言

近年來，智能設(shè)備快速發(fā)展，基于位置的服務(wù)（Location Based Service， LBS）被人們廣泛關(guān)注，在生活中也得到了很好的應(yīng)用。LBS根據(jù)用戶的位置為用戶提供有效的服務(wù)，例如：為用戶查找最近的電影院、附近的餐廳等。為了高效地從大量數(shù)據(jù)中挖掘出有用的信息，研究者們?cè)O(shè)計(jì)了許多查詢算法，如：最近鄰、k近鄰、反k近鄰、Skyline查詢等。由于k近鄰的應(yīng)用范圍很廣，研究者們對(duì)其進(jìn)行了較多研究，特別是在隱私保護(hù)和路網(wǎng)方面[1-2]。Jing等[1]提出了一種有效的路網(wǎng)k近鄰查詢驗(yàn)證技術(shù)，利用網(wǎng)絡(luò)Voronoi圖和鄰居來證明查詢結(jié)果的完整性。Ni等[2]設(shè)計(jì)了一個(gè)新的（s，ε）模型，通過改變s和ε參數(shù)來滿足用戶的查詢偏好，能更方便地呈現(xiàn)用戶對(duì)查詢效率的要求。然而，已有的近鄰查詢研究往往只考慮理想的歐氏空間，而實(shí)際地面上移動(dòng)的物體通常會(huì)受到一些地理環(huán)境的影響，如：建筑物、河流等。因此，若要準(zhǔn)確計(jì)算近鄰查詢中涉及的最短路徑，則必須要考慮障礙物因素，從而獲得較為準(zhǔn)確的k近鄰。

經(jīng)典的求解最短路徑的算法有Dijkstra算法、Floyd算法、A*算法等，但它們的搜索效率并不高。近年來，出現(xiàn)了一些新的啟發(fā)式算法，如遺傳算法、粒子群算法和蟻群算法等，提高了搜索效率。蟻群算法[3-8]是繼遺傳算法之后的又一種全局優(yōu)化算法，概念簡(jiǎn)單，優(yōu)化結(jié)果好，已被成功應(yīng)用于多種NP難組合優(yōu)化問題：路徑優(yōu)化、信息檢索等。目前，人們對(duì)蟻群算法收斂速度慢、易于停滯、容易陷入局部最優(yōu)等不足也作了很多改進(jìn)，如：夏亞梅等[3]提出了一種多信息素動(dòng)態(tài)更新的蟻群算法，對(duì)基本蟻群算法進(jìn)行了局部?jī)?yōu)化和全局優(yōu)化，并將其應(yīng)用在服務(wù)組合優(yōu)化中。Cao[4]提出一種改進(jìn)的機(jī)器人全局路徑規(guī)劃蟻群算法，從信息素?fù)]發(fā)因子、啟發(fā)函數(shù)和信息素更新策略三方面進(jìn)行優(yōu)化。Liu等[5]針對(duì)蟻群算法的收斂速度，將信息素?cái)U(kuò)散和幾何局部最優(yōu)化結(jié)合，尋找全局最優(yōu)路徑。張志龍等[6]對(duì)蟻群算法的啟發(fā)函數(shù)、信息素增量的計(jì)算和轉(zhuǎn)移概率進(jìn)行改進(jìn)，并將其應(yīng)用到圖像的邊緣檢測(cè)中。上述研究確實(shí)優(yōu)化克服了蟻群算法的諸多不足，但仍有研究者嘗試從不同角度對(duì)蟻群算法作改進(jìn)，如并行蟻群算法[8]，解決了算法的可擴(kuò)展性問題。

本文從一個(gè)新的角度對(duì)并行蟻群算法作改進(jìn)，并將改進(jìn)的并行蟻群算法應(yīng)用于解決障礙空間中的k近鄰查詢問題。主要工作如下：

1）通過賦予每個(gè)蟻群不同的信息素種類，讓多個(gè)蟻群同時(shí)工作，從而實(shí)現(xiàn)蟻群算法的并行化。

2）提出一種改進(jìn)的并行蟻群算法，用于解決障礙空間中的k近鄰查詢問題。它通過添加時(shí)間因素作為判斷路徑長(zhǎng)度的條件，以更直接地體現(xiàn)路徑長(zhǎng)度;重新定義初始信息素濃度，并改進(jìn)轉(zhuǎn)移概率和啟發(fā)函數(shù)，以使螞蟻朝著更為正確的方向搜索，避免算法過早陷入局部最優(yōu)。

3）引入可視點(diǎn)[9]作為分割點(diǎn)，將障礙路徑分段，無論將障礙物視為線段還是多邊形，都可分段計(jì)算出障礙距離。

1 相關(guān)工作

1.1 障礙距離及障礙空間中的近鄰查詢

障礙空間中近鄰查詢的關(guān)鍵是計(jì)算障礙距離以獲得最短路徑。給定一組障礙物，可以通過構(gòu)建可見圖來找源點(diǎn)和目的地點(diǎn)之間的最短路徑。Lozano-Pérez等[10]證明了最短路徑可以通過任何傳統(tǒng)的最短路徑算法在可見圖中求解。Zhang等[11]提出了計(jì)算障礙距離的新方法，查詢過程中如有遇到障礙，則LBS服務(wù)器將會(huì)重復(fù)查詢最短路徑。

關(guān)于障礙空間中的近鄰查詢工作有：Zhang等[12]提出了第一個(gè)全面的方法來處理障礙空間中的查詢，它首先利用歐氏距離確定最近鄰點(diǎn)，然后計(jì)算出歐氏最近鄰點(diǎn)與查詢點(diǎn)之間的障礙距離dol，根據(jù)歐氏距離的性質(zhì)可知，只有障礙距離小于dol的點(diǎn)才可能成為障礙最近鄰點(diǎn)，最后作障礙距離dol范圍內(nèi)的障礙最近鄰查詢，直到求出一個(gè)最小的障礙距離點(diǎn)。Xia等[13]提出一種高效的障礙最近鄰算法，它只以增量方式處理與查詢有關(guān)的數(shù)據(jù)點(diǎn)和障礙物，從而過濾掉大量的點(diǎn)和障礙物，該算法基于R樹和最佳優(yōu)先搜索算法，提高了查詢算法的效率。本文研究的障礙空間中的k近鄰查詢是獲取在障礙空間中k個(gè)距離查詢點(diǎn)q最近的數(shù)據(jù)點(diǎn)。Gu等[14]提出了一種有效處理障礙空間中k近鄰查詢的方法，它結(jié)合障礙Voronoi圖進(jìn)行離線預(yù)處理，并設(shè)計(jì)了幾種剪枝方法來有效查詢最近鄰。目前已有的障礙空間中的k近鄰查詢研究還較少，而已有的近鄰查詢方法大多只考慮線段障礙。本文引入可視點(diǎn)，分段計(jì)算障礙距離，并根據(jù)求解的障礙距離進(jìn)行k近鄰選取，在面對(duì)線段障礙和多邊形障礙時(shí)，均可以獲得較高的查詢效率。

1.2 并行蟻群算法

蟻群算法并行化有兩種策略：一種是并行獨(dú)立運(yùn)行（Parallel Independent Runs， PIR）[15]，每個(gè)子蟻群獨(dú)立搜索路徑而不相互通信;另一種是部分異步并行實(shí)現(xiàn)（Partial Asynchronous Parallel Implementation， PAPI）[15-18]，每個(gè)子蟻群經(jīng)過一定次數(shù)的迭代后，與其他子蟻群周期性交換最佳解，并更新其本地信息。由于PAPI能提高收斂速度，提高和效率，因此，大部分研究工作采用PAPI模型。例如，Manfrin等[16]提出了基于完全連通的拓?fù)浣Y(jié)構(gòu)的并行策略。在該模型中，一個(gè)蟻群作為Master，收集其他k-1個(gè)子蟻群發(fā)現(xiàn)的最優(yōu)解決方案，并廣播給所有子蟻群。該方法隨著問題規(guī)模的增大，巡回路徑的規(guī)模越來越大，成本會(huì)越來越高。Randall等[17]提出了一種蟻群算法的通信策略，每個(gè)子蟻群間相互通信，這有助于生成多樣化的解決方案，從而提高找到高質(zhì)量解決方案的可能性。但在策略中，主處理器必須負(fù)責(zé)收集、分類和比較所有子蟻群的解決方案，極大地影響了處理速度。Koshimizu等[18]提出劃分子蟻群的搜索空間的方法，讓搜索區(qū)域只被子蟻群使用。但其生成的多樣化解決方案不具有傳導(dǎo)性，且由于其固定的交換周期而降低了全局搜索能力。由已有研究可知，影響并行蟻群算法性能的主要因素有連接拓?fù)浣Y(jié)構(gòu)、通信策略和交換周期。針對(duì)這些因素，Yang等[19]提出了一種基于MPI（Message Passing Interface）的隨機(jī)匹配并行蟻群優(yōu)化算法，它設(shè)計(jì)了一種新的互連通信拓?fù)浣Y(jié)構(gòu)，處理器采用隨機(jī)匹配的方法進(jìn)行通信，并提出了一個(gè)非固定的交換周期，該算法縮短了執(zhí)行時(shí)間，效率較高。

本文用不同信息素種類區(qū)分蟻群以實(shí)現(xiàn)并行化，以多信息素的方式代替復(fù)雜的拓?fù)浣Y(jié)構(gòu)，用更簡(jiǎn)單的方法縮短算法的運(yùn)行時(shí)間，提高性能。

2 相關(guān)概念及符號(hào)描述

定義1 可視點(diǎn)[9]。若兩點(diǎn)間沒有被任何障礙物隔開，能直接可達(dá)，則稱這樣的點(diǎn)互為可視點(diǎn)。

如圖1所示，在矩形區(qū)域中包含三個(gè)障礙物{O1，O2，O3}，q為查詢點(diǎn)，矩形區(qū)域中的實(shí)心黑點(diǎn)即為q的可視點(diǎn)，q與其可視點(diǎn)之間用虛線連接。其他空心點(diǎn)和q之間被障礙物隔開，不能直接可達(dá)，因此它們不是q的可視點(diǎn)。

定義2 障礙距離[10]。兩個(gè)不可視的點(diǎn)p1和p2之間的障礙距離為p1繞過障礙物到達(dá)p2的最短路徑長(zhǎng)度。

為了便于描述，表1列出了本文中用到的符號(hào)。

3 障礙空間中基于并行蟻群算法的k近鄰查詢

3.1 k近鄰查詢的總體框架

障礙空間中基于并行蟻群算法的k近鄰查詢分為3個(gè)步驟：1）查詢用戶q給LBS服務(wù)器發(fā)送帶有位置信息的k近鄰查詢請(qǐng)求;2）LBS服務(wù)器接收到查詢請(qǐng)求后，根據(jù)查詢用戶q的位置，采用改進(jìn)的并行蟻群算法進(jìn)行k近鄰的選取;3）服務(wù)器完成k近鄰選取之后，將k個(gè)近鄰數(shù)據(jù)點(diǎn)返回給查詢用戶q。其框架如圖2所示。

3.2 基于改進(jìn)的并行蟻群算法的k近鄰選取

本文將查詢用戶的位置作為食物源，其余數(shù)據(jù)點(diǎn)為螞蟻的巢穴，不同巢穴中的蟻群種類不同，在路徑上釋放的信息素種類也不同。讓多個(gè)蟻群同時(shí)出發(fā)，用釋放的信息素種類進(jìn)行區(qū)分，實(shí)現(xiàn)蟻群算法的并行化，以提高算法的執(zhí)行速度。螞蟻移動(dòng)過程中，假設(shè)所有螞蟻的移動(dòng)速度相同，在螞蟻出發(fā)的同時(shí)開始計(jì)時(shí)，螞蟻每經(jīng)過一個(gè)節(jié)點(diǎn)，系統(tǒng)都會(huì)記錄此時(shí)的時(shí)間。本文主要從如下4個(gè)方面改進(jìn)基本蟻群算法：

1）增加時(shí)間因素作為判斷條件。當(dāng)每個(gè)蟻群都完成從巢穴到食物源的搜索之后，查看在食物源點(diǎn)記錄下的時(shí)間，用時(shí)最短的螞蟻即是走的最短路徑。

2）信息素初始化。基本蟻群算法中，由于初始信息素濃度相等，導(dǎo)致螞蟻在剛開始時(shí)盲目搜索，致使搜索大量無關(guān)路徑，對(duì)信息素濃度局部更新產(chǎn)生誤導(dǎo)。該問題不僅會(huì)導(dǎo)致初始搜索時(shí)間偏長(zhǎng)，并且由于無關(guān)路徑信息素濃度被加強(qiáng)，還可能影響最短路徑搜索，將算法引入局部最優(yōu)。因此，本文通過初步判斷點(diǎn)i與螞蟻巢穴和食物源之間的距離，對(duì)初始信息素濃度給出新的定義，作為螞蟻開始時(shí)搜索的方向性引導(dǎo)，初始信息素的計(jì)算如式（1）所示：

3）啟發(fā)函數(shù)?；鞠伻核惴ǖ膯l(fā)函數(shù)是以鄰近節(jié)點(diǎn)路徑最短的原理選取下一節(jié)點(diǎn)，但若當(dāng)前點(diǎn)與鄰近節(jié)點(diǎn)之間的路徑差值并不明顯，則得到的結(jié)果不一定是最優(yōu)的，并且通過正反饋機(jī)制該誤差值會(huì)進(jìn)一步放大，導(dǎo)致螞蟻向錯(cuò)誤的方向?qū)ふ?，影響了整個(gè)算法的性能。因此，本文定義的啟發(fā)函數(shù)為：

4）信息素濃度的更新。為了使算法能更快地收斂于最優(yōu)解，每只螞蟻完成從點(diǎn)i到點(diǎn)j的移動(dòng)后，都對(duì)分段ij上的信息素作局部信息素濃度更新，所有螞蟻都完成從蟻群巢穴到食物源的移動(dòng)之后，對(duì)每一分段ij上的信息素作全局信息素濃度更新。對(duì)局部信息素濃度和全局信息素濃度的更新方法分別如式（3）和式（4）所示：

障礙空間中基于改進(jìn)的并行蟻群算法的k近鄰選取算法如算法1所示。

把每個(gè)巢穴中的所有螞蟻看作是一個(gè)蟻群，每個(gè)蟻群攜帶的信息素種類不同，基于此進(jìn)行并行搜索。此處，并行實(shí)現(xiàn)是利用多線程讓多個(gè)蟻群同時(shí)搜索最優(yōu)解（一個(gè)蟻群對(duì)應(yīng)一個(gè)線程）。算法2描述了單個(gè)蟻群的搜索過程，具體如下。

算法2 單個(gè)蟻群的搜索過程。

3.3 時(shí)間復(fù)雜度分析

本文方法提出一種基于改進(jìn)的并行蟻群算法的k近鄰查詢方法（k nearest neighbor Query method based on improved Parallel Ant colony algorithm， PAQ），在根據(jù)概率轉(zhuǎn)移公式選擇下一節(jié)點(diǎn)時(shí)要遍歷所有節(jié)點(diǎn)，因此時(shí)間復(fù)雜度較高，為O（Nc*a*（n+m）2+n log n），其中a為各蟻群中的螞蟻數(shù)，Nc為迭代次數(shù)，n為數(shù)據(jù)點(diǎn)個(gè)數(shù)，m為障礙物的數(shù)目。文獻(xiàn)[14]方法（WithGrids）的時(shí)間復(fù)雜度為O（n2+2m2+n log（n+m）+4n log n）。在問題規(guī)模較小時(shí)，PAQ的運(yùn)行效率會(huì)明顯優(yōu)高于WithGrids;但隨著問題規(guī)模的增大，PAQ的效率會(huì)逐漸降低，會(huì)低于WithGrids。

4 實(shí)驗(yàn)與結(jié)果分析

4.1 實(shí)驗(yàn)環(huán)境及數(shù)據(jù)集

由于文獻(xiàn)[14]和本文均是解決障礙空間中的k近鄰查詢問題，因此，為了驗(yàn)證本文方法的有效性，與文獻(xiàn)[14]的WithGrids方法進(jìn)行了算法運(yùn)行時(shí)間的對(duì)比。實(shí)驗(yàn)的硬件環(huán)境：CPU為Intel Core 2.83GHz，內(nèi)存為4096MB RAM，操作系統(tǒng)為Windows 7旗艦版32位，利用Java進(jìn)行編程。對(duì)于PAQ方法，本文利用多線程模擬多處理機(jī)進(jìn)行仿真。本文利用兩個(gè)數(shù)據(jù)集來進(jìn)行實(shí)驗(yàn)：一個(gè)數(shù)據(jù)集是“Greece”[14]，其包含了希臘河流“rivers”和道路“roads”的地理位置;另一個(gè)數(shù)據(jù)集是“Germany”[14]，其包含了德國(guó)鐵路線“rrlines”的地理位置和地形圖數(shù)據(jù)“hypsogr”。文中用“hypsogr”作為數(shù)據(jù)點(diǎn)集合，“rrlines”“rivers”和“roads”分別作為障礙物集合，實(shí)驗(yàn)中的查詢范圍是一個(gè)自定義的動(dòng)態(tài)矩形。本文所有的實(shí)驗(yàn)結(jié)果均是程序運(yùn)行50次取的平均值。

4.2 主要參數(shù)值的選取

本文的主要參數(shù)值是通過改變因變量進(jìn)行多次實(shí)驗(yàn)選取的經(jīng)驗(yàn)值[20-22]。參數(shù)ρ∈（0，1），在區(qū)間（0， 1）內(nèi)任意取值觀察實(shí)驗(yàn)的最終結(jié)果（如圖3），發(fā)現(xiàn)在處理線段障礙物時(shí)，設(shè)置ρ=0.3時(shí)，PAQ方法的運(yùn)行時(shí)間最短;在處理多邊形障礙物時(shí)，設(shè)置ρ=0.7時(shí)，PAQ方法的運(yùn)行時(shí)間最短。參數(shù)α、 β的取值范圍設(shè)為[0， 5]，同樣地，在區(qū)間[0， 5]中任意取值測(cè)試實(shí)驗(yàn)結(jié)果，如圖4所示。從圖4中可以看出，α的取值對(duì)PAQ方法運(yùn)行時(shí)間的影響并不太明顯，但當(dāng)β=2時(shí)，實(shí)驗(yàn)結(jié)果相對(duì)較好，為使得PAQ的效果最優(yōu)，設(shè)置α=β=2。

為不失一般性，且要體現(xiàn)PAQ方法的優(yōu)越性，本文對(duì)數(shù)據(jù)點(diǎn)個(gè)數(shù)、障礙物個(gè)數(shù)和k采用折中取值的方法，若無特別說明將設(shè)置蟻群中螞蟻數(shù)a=5，數(shù)據(jù)點(diǎn)個(gè)數(shù)n=100，障礙物個(gè)數(shù)m=3，k=3[14]。

4.3 結(jié)果分析

圖5給出了三種不同障礙物下k值對(duì)算法運(yùn)行時(shí)間的影響。對(duì)于WithGrids方法，它基于網(wǎng)格分區(qū)索引對(duì)數(shù)據(jù)點(diǎn)和線段障礙物的信息作預(yù)處理，節(jié)約了算法搜索信息后再計(jì)算障礙距離的時(shí)間。而PAQ方法通過設(shè)置多個(gè)蟻群并行尋找最短路徑，另外，給蟻群的初始信息素濃度，讓螞蟻在一開始搜索最短路徑時(shí)就有導(dǎo)向性，從一定程度上優(yōu)化了蟻群算法，再利用改進(jìn)的啟發(fā)函數(shù)，也避免了蟻群算法過早陷入局部最優(yōu)，及時(shí)更新局部信息素濃度和全局信息素濃度也都提高了PAQ方法的正確性，縮短了PAQ方法的運(yùn)行時(shí)間，因此PAQ方法的時(shí)間效率更高。從圖5中還可看出，PAQ方法的運(yùn)行時(shí)間隨著k值的增大也在增長(zhǎng)，原因是較高的k值需要較大的搜索空間，因此需要更多的計(jì)算時(shí)間。而PAQ方法在處理多邊形障礙時(shí)的運(yùn)行時(shí)間較處理線段障礙的長(zhǎng)，原因是多邊形障礙頂點(diǎn)個(gè)數(shù)多，障礙路徑的數(shù)量增多。經(jīng)計(jì)算，在k值小于15時(shí)，在處理線段障礙時(shí)，PAQ運(yùn)行效率較WithGrids平均提高88.9%;在處理多邊形障礙時(shí)，PAQ運(yùn)行效率較WithGrids平均提高72.5%。

圖6顯示了三種不同障礙物下數(shù)據(jù)點(diǎn)個(gè)數(shù)對(duì)算法運(yùn)行時(shí)間的影響。從圖6可以看出，隨數(shù)據(jù)點(diǎn)個(gè)數(shù)的增加，WithGrids方法的運(yùn)行時(shí)間先減少后趨于平穩(wěn)，原因是它根據(jù)需要在構(gòu)建網(wǎng)格分區(qū)索引的成本和搜索成本之間作權(quán)衡，在找到一個(gè)平衡點(diǎn)之后運(yùn)行時(shí)間就會(huì)保持相對(duì)穩(wěn)定。同樣由于多個(gè)蟻群的同時(shí)搜索以及對(duì)搜索方向的引導(dǎo)，PAQ方法的運(yùn)行時(shí)間仍優(yōu)于WithGrids方法。而PAQ方法在處理多邊形障礙時(shí)的運(yùn)行時(shí)間仍然比處理線段障礙的長(zhǎng)，原因是障礙物頂點(diǎn)個(gè)數(shù)越多，路徑數(shù)量就越多，障礙距離的計(jì)算量也就越大;但二者的運(yùn)行時(shí)間都會(huì)隨數(shù)據(jù)點(diǎn)個(gè)數(shù)的增加會(huì)延長(zhǎng)。延長(zhǎng)的原因是數(shù)據(jù)點(diǎn)個(gè)數(shù)的增加意味著搜索空間的增大，計(jì)算量也隨之變大，但同時(shí)空間中障礙物的比例也會(huì)降低。經(jīng)計(jì)算，在數(shù)據(jù)點(diǎn)個(gè)數(shù)小于300時(shí)，在處理線段障礙時(shí)，PAQ運(yùn)行效率較WithGrids平均提高91.5%;在處理多邊形障礙時(shí)，PAQ運(yùn)行效率較WithGrids平均提高78.5%。

圖7顯示了三種不同障礙物下障礙物個(gè)數(shù)對(duì)算法運(yùn)行時(shí)間的影響。從圖7可以看出，隨障礙物數(shù)量的增加，PAQ方法的運(yùn)行時(shí)間在增長(zhǎng)，但仍明顯比WithGrids方法的運(yùn)行時(shí)間短。PAQ方法性能更優(yōu)的主要原因還是實(shí)現(xiàn)了并行，并通過對(duì)螞蟻的搜索方向加以修正，從而縮短了搜索時(shí)間。PAQ方法的運(yùn)行時(shí)間增長(zhǎng)的原因是參與障礙距離計(jì)算的障礙物個(gè)數(shù)的增加使計(jì)算開銷增大。而PAQ方法在處理多邊形障礙時(shí)的運(yùn)行時(shí)間增長(zhǎng)速度比處理線段障礙的快，原因是處理多邊形障礙物所需的可視點(diǎn)要多于處理線段障礙物的，這使障礙路徑的分段數(shù)增加，障礙距離的計(jì)算量增大。經(jīng)計(jì)算，在障礙物個(gè)數(shù)小于60時(shí)，在處理線段障礙時(shí)，PAQ運(yùn)行效率較WithGrids平均提高94.2%;在處理多邊形障礙時(shí)，PAQ運(yùn)行效率較WithGrids平均提高72.0%。

PAQ方法中的并行部分是各蟻群同時(shí)從各自巢穴出發(fā)，獨(dú)立搜索到食物源的最短路徑。從圖8中可以看出，隨著數(shù)據(jù)點(diǎn)個(gè)數(shù)的增多，加速比在緩慢降低，主要原因是隨著數(shù)據(jù)點(diǎn)個(gè)數(shù)的增多，螞蟻的數(shù)量也在增加，并且蟻群中各螞蟻仍是串行實(shí)現(xiàn)的，運(yùn)行時(shí)間也就隨之延長(zhǎng)了。

5 結(jié)語

本文提出了一種改進(jìn)的并行蟻群算法來實(shí)現(xiàn)障礙空間中的k近鄰查詢。該方法用不同信息素種類的蟻群來實(shí)現(xiàn)蟻群算法的并行化，提高算法的效率。它加入時(shí)間因素作為最短路徑的判斷條件，選擇障礙空間中的可視點(diǎn)進(jìn)行概率轉(zhuǎn)移，并利用重新定義的初始信息素濃度和改進(jìn)的啟發(fā)函數(shù)來引導(dǎo)和修正螞蟻的搜索方向，改善蟻群算法的性能。實(shí)驗(yàn)結(jié)果表明，在小規(guī)模數(shù)據(jù)下，改進(jìn)的并行蟻群算法對(duì)障礙空間中的k近鄰查詢較WithGrids方法有更短的運(yùn)行時(shí)間，且能處理多邊形障礙。下一步，將進(jìn)一步改進(jìn)本文算法，以適應(yīng)k值、數(shù)據(jù)點(diǎn)個(gè)數(shù)和障礙物個(gè)數(shù)較大的情況。

參考文獻(xiàn) （References）

[1] JING Y， HU L， KU W-S， et al. Authentication of k nearest neighbor query on road networks [J]. IEEE Transactions on Knowledge and Data Engineering， 2014， 26（6）： 1494-1506.

[2] NI W， GU M， CHEN X. Location privacy-preserving k nearest neighbor query under user's preference [J]. Knowledge-based Systems， 2016， 103（C）： 19-27.

[3] 夏亞梅，程渤，陳俊亮，等.基于改進(jìn)蟻群算法的服務(wù)組合優(yōu)化[J].計(jì)算機(jī)學(xué)報(bào)，2012，35（2）：270-281.（XIA Y M， CHENG B， CHEN J L， et al. Optimizing services composition based on improved ant colony algorithm [J]. Chinese Journal of Computers， 2012， 35（2）： 270-281.）

[4] CAO J. Robot global path planning based on an improved ant colony algorithm [J]. Journal of Computer and Communications， 2016， 4（2）： 11-19.

[5] LIU J， YANG J， LIU H， et al. An improved ant colony algorithm for robot path planning [J]. Soft Computing， 2017， 21（19）： 5829-5839.

[6] 張志龍，楊衛(wèi)平，李吉成.一種基于蟻群優(yōu)化的顯著邊緣檢測(cè)算法[J].電子與信息學(xué)報(bào)，2014，36（9）：2061-2067.（ZHANG Z L， YANG W P， LI J C. A novel salient image edge detection algorithm based on ant colony optimization [J]. Journal of Electronics and Information Technology， 2014， 36（9）： 2061-2067.）

[7] 董毅，趙尚弘，李勇軍，等.基于蟻群算法的分布式衛(wèi)星光網(wǎng)絡(luò)波長(zhǎng)路由分配技術(shù)研究[J].電子與信息學(xué)報(bào)， 2015，37（11）：2650-2656.（DONG Y， ZHAO S H， LI Y J， et al. Research on routing and wavelength assignment based on ant colony optimization in distributed satellite optical network [J]. Journal of Electronics and Information Technology， 2015， 37（11）： 2650-2656.）

[8] DORIGO M， BIRATTARI M， STUTZLE T. Ant colony optimization： artificial ants as a computational intelligence technique [J]. IEEE Computational Intelligence Magazine， 2006， 1（4）： 28-39.

[9] XU J， GTING R H. Querying visible points in large obstructed space [J]. GeoInformatica， 2015， 19（3）： 435-461.

[10] LOZANO-PREZ T， WESLEY M A. An algorithm for planning collision-free paths among polyhedral obstacles [J]. Communications of the ACM， 1979， 22（10）： 560-570.

[11] ZHANG L， LI J， YANG S， et al. Privacy preserving in cloud environment for obstructed shortest path query [J]. Wireless Personal Communications， 2017， 96（2）： 2305-2322.

[12] ZHANG J， PAPADIAS D， MOURATIDIS K， et al. Spatial queries in the presence of obstacles [C]// Proceedings of the 2004 International Conference on Extending Database Technology， LNCS 2992. Berlin： Springer， 2004：366-384.

[13] XIA C， HSU D， TUNG A K H. A fast filter for obstructed nearest neighbor queries [C]// Proceedings of the 2004 British National Conference on Databases， LNCS 3112. Berlin： Springer， 2004： 203-215.

[14] GU Y， YU G， YU X. An efficient method for k nearest neighbor searching in obstructed spatial databases [J]. Journal of Information Science and Engineering， 2014， 30（5）： 1569-1583.

[15] STTZLE T. Parallelization strategies for ant colony optimization [C]// Proceedings of the 1998 International Conference on Parallel Problem Solving from Nature， LNCS 1498. Berlin： Springer， 1998： 722-731.

[16] MANFRIN M， BIRATTARI M， STTZLE T， et al. Parallel ant colony optimization for the traveling salesman problem [C]// Proceedings of the 2006 International Workshop on Ant Colony Optimization and Swarm Intelligence， LNCS 4150. Berlin： Springer， 2006： 224-234.

[17] RANDALL M， LEWIS A. A parallel implementation of ant colony optimization [J]. Journal of Parallel and Distributed Computing， 2002， 62（9）： 1421-1432.

[18] KOSHIMIZU H， SAITO T. Parallel ant colony optimizers with local and global ants [C]// Proceedings of the 2009 International Joint Conference on Neural Networks. Piscataway， NJ： IEEE， 2009： 2707-2711.

[19] YANG Q， FANG L， DUAN X. RMACO： a randomly matched parallel ant colony optimization [J]. World Wide Web， 2016， 19（6）： 1009-1022.

[20] MERKLE D， MIDDENDORF M， SCHMECK H. Ant colony optimization for resource-constrained project scheduling [J]. IEEE Transactions on Evolutionary Computation， 2002， 6（4）： 333-346.

[21] 李琳，應(yīng)時(shí)，趙翀，等.基于蟻群算法的面向服務(wù)軟件的部署優(yōu)化方法[J].電子學(xué)報(bào)，2016，44（1）：123-129.（LI L， YING S， ZHAO C， et al. Deployment optimization of service-oriented software based on ant colony algorithm [J]. Acta Electronica Sinica， 2016， 44（1）： 123-129.）

[22] 曾夢(mèng)凡，陳思洋，張文茜，等.利用蟻群算法生成覆蓋表：探索與挖掘[J].軟件學(xué)報(bào)，2016，27（4）：855-878.（ZENG M F， CHEN S Y， ZHANG W Q， et al. Generating covering arrays using ant colony optimization： exploration and mining [J]. Journal of Software， 2016， 27（4）： 855-878.）