賀井然，何廣軍，于學(xué)生

（1.空軍工程大學(xué)防空反導(dǎo)學(xué)院，西安 710043；2.解放軍95607 部隊(duì)，成都 610066）

0 引言

在解決無人機(jī)的路徑規(guī)劃問題方面，學(xué)者提出了如人工勢(shì)場(chǎng)法、模擬退火法、模糊邏輯法等算法［1］。肖玉婷等［2］提出了一種基于分塊優(yōu)化思想的覆蓋路徑規(guī)劃方法，將大規(guī)模環(huán)境分塊優(yōu)化，減小了計(jì)算量，能適應(yīng)多種形狀區(qū)域；劉暢等［3］人提出了一種基于模糊推理機(jī)制的邏輯架構(gòu)設(shè)計(jì)，運(yùn)用可變自主OOADA 循環(huán)動(dòng)態(tài)分配人機(jī)權(quán)限，實(shí)現(xiàn)了復(fù)雜威脅環(huán)境下實(shí)時(shí)航跡規(guī)劃。近年來，蟻群算法、粒子群算法等群智能算法也被用于解決無人機(jī)路徑規(guī)劃的問題［4-5］。夏瑞等［6］提出一種基于人工蜂群算法的非確定性雙向規(guī)劃?rùn)C(jī)制搜索算法，大大提高了產(chǎn)生航跡的質(zhì)量；王慶海［7］引入動(dòng)態(tài)評(píng)價(jià)策略、模擬退火準(zhǔn)則和復(fù)合型優(yōu)化算法結(jié)構(gòu)，對(duì)人工蜂群算法進(jìn)行改進(jìn)，提高了算法的優(yōu)化效率；本文采用改進(jìn)蜂群算法研究無人機(jī)路徑規(guī)劃問題。

1 相關(guān)算法簡(jiǎn)介

1.1 人工蜂群算法

人工蜂群算法（ABC）是一種仿生群智能算法，通過模擬蜜蜂尋找花蜜的方式來尋找最優(yōu)解，以蜜源表示可能存在的解，以蜂蜜量表示解的適應(yīng)度。初始化階段，確定種群數(shù)量N，蜜源維數(shù)D，隨機(jī)生成初始蜜源，并計(jì)算適應(yīng)度fiti的值。公式如下：

式中，xij表示第i 個(gè)蜜源的第j 維，i=1，2，3…，N，j=1，2，3…，D，xu表示蜜源允許的最大值，xl表示蜜源允許的最小值，fi表示解對(duì)應(yīng)的函數(shù)值。

采蜜蜂階段，在初始蜜源附近尋找新的蜜源，根據(jù)適應(yīng)度大小選擇是否替換蜜源。

觀察蜂階段，根據(jù)更新后蜜源的適應(yīng)度，觀察蜂按照輪盤賭規(guī)則選擇跟隨的采蜜蜂，pi表示選取第i 個(gè)蜜源的概率。

偵察蜂階段，如果一個(gè)蜜源開采次數(shù)達(dá)到上限仍然沒有更新，則放棄該蜜源，并在解空間中重新尋找蜜源。

1.2 K 均值聚類算法

對(duì)于一樣本x={xi∈R，i=1，2，…，n}，x 為一個(gè)d維向量?？梢詫颖緞澐譃閗 個(gè)不同的類別C={C1，C2，…，Ck}，其中，每一個(gè)類都有一個(gè)聚類中心，聚類中心計(jì)算公式如下：

式中，d（xi，Cj）表示聚類中心Cj與類中元素xi的距離，J 表示各類內(nèi)距的和。

2 改進(jìn)人工蜂群算法

盡管人工蜂群算法具有良好的全局搜索能力和高魯棒性等優(yōu)點(diǎn)，但是該算法容易早熟，后期收斂速度低，針對(duì)這些問題，本文使用K 均值聚類算法（KMC）對(duì)原始人工蜂群算法進(jìn)行改進(jìn)［8］。原始蜂群算法初始種群全部隨機(jī)生成，因此，需要采用最大最小距離積法對(duì)初始種群分散，克服初始種群的隨機(jī)性。KMC 算法根據(jù)樣本之間的相似度將樣本分為多個(gè)類，相同類的樣本具有盡可能高的相似度，不同類的樣本具有盡可能低的相似度，該算法具有聚類快速，局部搜索能力強(qiáng)的特點(diǎn)，能有效地解決蜂群算法后期收斂速度低的問題。

2.1 最大最小距離積法初始化

原始蜂群算法中，初始種群隨機(jī)產(chǎn)生，具有很強(qiáng)的隨機(jī)性，如果初始種群過于密集，會(huì)影響算法的全局搜索能力，容易陷入局部最優(yōu)。本文采用最大最小距離積法對(duì)隨機(jī)種群進(jìn)行初始化，降低初始種群的隨機(jī)性。

設(shè)需要選取k 個(gè)初始點(diǎn)，第1 步在初始種群C中隨機(jī)選擇一個(gè)元素x1作為第1 個(gè)初始點(diǎn)，然后將x1移動(dòng)到集合D 中。第2 步計(jì)算更新后C 中元素到x1的距離，選取其中距離最大的元素x2移動(dòng)到D中。第3 步分別計(jì)算更新后C 中剩余元素到集合D中每一個(gè)元素的距離d，計(jì)算C 中元素對(duì)應(yīng)d 的最大值和最小值的乘積，選取其中乘積最大的一個(gè)元素移動(dòng)到D 中，重復(fù)此步驟直到選取足夠的初始點(diǎn)。第4 步輸出集合D。

通過以上步驟，將隨機(jī)生成地初始種群分散處理，避免了隨機(jī)生成種群過于密集的問題。

2.2 K 均值聚類改進(jìn)蜂群算法

K 均值聚類改進(jìn)蜂群算法（KMC 改進(jìn)蜂群算法）的基本思想是，將每次人工蜂群算法迭代得到的蜜源作為KMC 算法的初始點(diǎn)，對(duì)蜜源進(jìn)行聚類，聚類完成后再將更新后的中心更新蜜源。將KMC和ABC 兩種算法交替執(zhí)行，直到算法結(jié)束。

KMC 改進(jìn)蜂群算法的步驟如下：

第1 步：設(shè)置初始種群數(shù)量、采蜜蜂和觀察蜂的數(shù)量，蜜源最大開采數(shù)量、最大循環(huán)次數(shù)、聚類類別數(shù)，其中采蜜蜂和觀察蜂各占種群數(shù)量的一半，聚類類別數(shù)和根據(jù)式（1）隨機(jī)生成初始種群，并運(yùn)用最大最小距離積法對(duì)生成的初始種群進(jìn)行初始化。

第2 步：對(duì)初始化后的種群進(jìn)行聚類劃分，并計(jì)算種群的適應(yīng)度，按照適應(yīng)度排序，適應(yīng)度大的一半種群設(shè)置為采蜜蜂，另一半設(shè)置為觀察蜂。

第3 步：按照式（3）在采蜜蜂現(xiàn)有蜜源的領(lǐng)域進(jìn)行搜索，用適應(yīng)度高的蜜源更新現(xiàn)有蜜源，觀察蜂按照輪盤賭規(guī)則跟隨采蜜蜂。

第4 步：再次對(duì)蜜源進(jìn)行聚類劃分，用新的聚類中心更新蜜源。如果一個(gè)蜜源開采次數(shù)達(dá)到最大次數(shù)還沒有更新，則放棄該蜜源，對(duì)應(yīng)的蜜蜂轉(zhuǎn)化為偵察蜂。

第5 步：判斷是否達(dá)到最大循環(huán)次數(shù)，如果沒有則返回第2 步，如果達(dá)到則輸出適應(yīng)度最高的蜜源，算法結(jié)束。

圖1 KMC 改進(jìn)蜂群算法流程圖

3 問題描述

3.1 建立環(huán)境模型

無人機(jī)在實(shí)際執(zhí)行任務(wù)中，往往會(huì)遇到非常復(fù)雜的環(huán)境情況，如樓房、樹木等障礙，雷達(dá)、敵機(jī)等威脅，不適宜飛行的區(qū)域等。在模型建立中往往難以準(zhǔn)確地表達(dá)出不同的環(huán)境因素，本文將所有不可飛行區(qū)域等效為障礙物表示，這樣無人機(jī)在復(fù)雜環(huán)境下的航跡規(guī)劃問題就簡(jiǎn)化成了避障路線的問題。

3.2 代價(jià)函數(shù)

無人機(jī)航跡規(guī)劃就是要找出一條由起點(diǎn)到終點(diǎn)的最優(yōu)航跡，即無人機(jī)按照這一條航跡行動(dòng)代價(jià)最低。無人機(jī)的航跡可以看作是多段折線，為了方便建模，將無人機(jī)的航跡簡(jiǎn)化為多個(gè)矢量的和。設(shè)無人機(jī)航跡通過M 個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)對(duì)應(yīng)矢量XM，則無人機(jī)航跡可以用一組矢量來表示：

式中，X 表示無人機(jī)的航跡，Xm表示無人機(jī)到達(dá)第m 個(gè)節(jié)點(diǎn)的矢量，（am，bm）表示節(jié)點(diǎn)坐標(biāo)。

無人機(jī)在實(shí)際執(zhí)行任務(wù)時(shí)，受限于攜帶燃料，作業(yè)時(shí)間有限。因此，在航跡規(guī)劃中要求航跡長(zhǎng)度盡可能短，以保證無人機(jī)有足夠的燃料和時(shí)間執(zhí)行相關(guān)任務(wù)。無人機(jī)在節(jié)點(diǎn)處需要轉(zhuǎn)向調(diào)整，在轉(zhuǎn)向中同樣需要耗費(fèi)燃料，我們希望無人機(jī)總體的轉(zhuǎn)向角度較小。由上述可以得出無人機(jī)的代價(jià)函數(shù)如下：

式中，P1表示無人機(jī)的距離代價(jià)，P2表示無人機(jī)的轉(zhuǎn)向代價(jià)。|θm|表示無人機(jī)在第m 個(gè)節(jié)點(diǎn)的轉(zhuǎn)向角度的絕對(duì)值，cost1表示無人機(jī)前進(jìn)產(chǎn)生的能耗，cost2表示無人機(jī)旋轉(zhuǎn)所產(chǎn)生的能耗，ω1，ω2為距離代價(jià)和轉(zhuǎn)向代價(jià)的能耗系數(shù)，取值按文獻(xiàn)［9］中由實(shí)驗(yàn)方法得到：ω1=0.107 2，ω2=0.010 4。無人機(jī)的總代價(jià)為：

無人機(jī)的總代價(jià)為：

4 仿真實(shí)例

設(shè)種群數(shù)量為20，采蜜蜂和觀察蜂的數(shù)量均為10，最大循環(huán)次數(shù)為2 000，蜜源開采上限為100，節(jié)點(diǎn)數(shù)設(shè)置為10，在100*100 范圍內(nèi)進(jìn)行路徑規(guī)劃，起點(diǎn)和終點(diǎn)坐標(biāo)分別為（0，0）和（100，100）。障礙物數(shù)量為8，位置和半徑由程序隨機(jī)給出。仿真結(jié)果如圖2、圖3 所示。

圖2 原始蜂群算法最優(yōu)路徑

圖3 KMC 改進(jìn)蜂群算法最優(yōu)路徑

單次尋優(yōu)的代價(jià)函數(shù)值如表1 所示。

表1 ABC 算法代價(jià)函數(shù)值

由表1 結(jié)果可知，原始蜂群算法在循環(huán)500 次時(shí)代價(jià)函數(shù)值達(dá)到最小值16.079 5，其后代價(jià)函數(shù)沒有繼續(xù)降低。KMC 改進(jìn)蜂群算法代價(jià)函數(shù)值在1 700 次循環(huán)時(shí)達(dá)到最小值15.709 6，由于蜂群算法具有隨機(jī)性，對(duì)兩種算法分別運(yùn)行10 次，計(jì)算兩種算法得出的最優(yōu)解的平均值。運(yùn)行結(jié)果如表2所示。

表2 多次尋優(yōu)結(jié)果

經(jīng)過10 次運(yùn)行，原始蜂群算法得到的代價(jià)函數(shù)值的平均值為：16.097 56，KMC 改進(jìn)蜂群算法得到的代價(jià)函數(shù)值的平均值為：15.890 97。

5 結(jié)論

在原本的蜂群算法中嵌入KMC 聚類算法，使種群更新后分布更加分散，降低了隨機(jī)性對(duì)算法的影響，并提高了算法后期的收斂速度。將該算法應(yīng)用到無人機(jī)路徑規(guī)劃問題上，仿真結(jié)果表明該算法能有效地解決無人機(jī)路徑規(guī)劃問題，求解過程中改進(jìn)算法收斂速度更快，后期局部搜索能力更強(qiáng)，求出的路徑相比原始蜂群算法路徑長(zhǎng)度更短，轉(zhuǎn)角總和更低，花費(fèi)代價(jià)更小，并且在多次尋優(yōu)中得到的解的平均質(zhì)量更好。