無人機航跡規(guī)劃群智能優(yōu)化算法綜述

劉雨坤，侯捷

(1.天津市寶坻區(qū)第一中學，天津，301800；2.北京科技大學自動化學院，北京，100083)

1 常見的無人機航跡規(guī)劃群智能優(yōu)化算法

1.1 粒子群算法

鳥群在大自然中飛行時，每只鳥都有自己的飛行位置和速度，都可以感受到周圍其他鳥類的信息并依據(jù)周圍其他鳥類的飛行狀態(tài)調整自身當前的位置和速度。而在鳥群遷移，朝著食物資源豐富的地方飛行中，遷徙期初，鳥類的飛行屬于漫無目的的飛行，直到有一只鳥發(fā)現(xiàn)了食物源比較理想的棲息地，此時，它傳遞的信息給一只鳥，一只鳥往這個棲息地飛行，逐漸其他鳥類都開始朝這個棲息地飛行，如圖1所示。鳥類飛行過程中的群體行為為人們在優(yōu)化決策中提供了思想：通過自身經驗和他人經驗進行決策以及群集效應，分工合作。

圖1 鳥群飛行示意圖

粒子群算法相對于其他智能優(yōu)化算法具算法通用性強、收斂速度較快、迭代公式簡單易于仿真實現(xiàn)等優(yōu)點。但是，標準粒子群算法也存在一些缺點，主要包含：（1）由于受到全局影響，個體很容易放棄當前搜索而進入另一個空間，導致局部搜索能力差，搜索精度不高。（2）由于迭代公式簡單，收斂過程很大程度依賴參數(shù)選取，而對于參數(shù)的選擇，目前尚缺乏很強的指導性原則，優(yōu)化結果的好壞主要依賴算法中各種參數(shù)的選取。

1.2 蟻群算法

蟻群算法（ACO）是一種群智能進化算法，簡稱為螞蟻算法。1992年，Marco Dorigo第一次在他的學術論文中提出了這種智能仿生算法。其基本思想可以描述為：大自然中，螞蟻的覓食行為是蟻群的總體搜索行為，每只螞蟻在覓食過程中，相互之間都會傳遞信息激素。如果每個螞蟻在沒有被事前告知食物來源的情況，蟻群中的任意單只螞蟻發(fā)現(xiàn)食物源后，這只螞蟻會在食物環(huán)境周圍釋放出一種特殊的分泌物，以此來通知種群中其他螞蟻向食物源靠近，經過一段時間的累積，多數(shù)螞蟻會聚集到這條道路上，最終所有的螞蟻會沿著這條路徑找到食物。但是，并不是每次螞蟻覓食都遵循這一規(guī)律，另外一些螞蟻并不會按照路徑上的分泌物進行行走，他們會另辟蹊徑，找出其他的路徑到達同一食物源，并分泌信息素，經過一段的時間累積，如果新路徑長度比原路徑長度更短，就會有更多的螞蟻，根據(jù)此路徑上的信息素搜索到食物源，最終，整個蟻群中絕大多數(shù)螞蟻會通過最短路徑完成覓食，這樣的一個完整過程就是蟻群正反饋過程。

螞蟻覓食的過程如圖2所示。當蟻巢和食物源之間無障礙物時，路徑類似于直線，如圖(a)所示。在蟻巢和食物源之間有障礙物阻隔的時候，螞蟻會自動繞過障礙物，找出路線走向食物源，如圖(b)所示。而多數(shù)情況是圖(c)所示的情形：由于螞蟻在走過的路線上會釋放出一種特有的信息素，這種物質會在環(huán)境中慢慢揮發(fā)消散，后代螞蟻在覓食過程中會受到信息素作用的引導，從而隨著蟻群覓食行為的進行，路徑較短的覓食路線上信息素濃度累積量會越來越多，后代螞蟻選擇這條道路的可能性就會越大，通過螞蟻這種特有的覓食習慣，最終蟻群可以找到一條在蟻巢和食物源之間最短的路徑，這一過程也是蟻群算法尋徑的主要過程。

圖2 螞蟻覓食示意圖

蟻群算法具有魯棒性好、計算并行性、正反饋機制、易于與其它方法融合等優(yōu)點。但是蟻群算法也存在著許多問題，在一定程度上造成了算法在航跡規(guī)劃過程中存在缺陷，主要包括如下幾點：（1）蟻群算法是一種啟發(fā)式仿生算法，通過螞蟻當前所在位置及下一步要到達的位置間距作為算法的啟發(fā)信息進行尋徑，在對障礙物的預先規(guī)避方面存在一定問題；（2）蟻群算法在搜索初期由于沒有指導信息，導致算法在尋徑初期具有很強的隨機性，且環(huán)境規(guī)模越大，其性能也越差；（3）算法中的禁忌表有時會使螞蟻在尋徑過程中無法走到終點陷入死胡同，出現(xiàn)非完整路徑。以上三點使蟻群算法存在收斂過快、路徑搜索效率低及收斂速度慢的缺點。

1.3 蜂群算法

蜜蜂是一類會飛的聚居類型的生物，雖然每一個蜜蜂的活動很簡單，可群體的統(tǒng)一性行為十分復雜，是該種群在自然界生存的關鍵。蜂群中的每個個體的角色都有很大的差別，但都可以進行一系列的復雜工作，如筑巢、采蜜、繁殖培育后代等，整個蜂群的最大一個特點就是各種蜜蜂可以根據(jù)不同的情況互相轉換彼此的角色。在現(xiàn)實的采蜜過程中，蜜蜂并不是單獨行動的，整個蜂群協(xié)同工作，能夠快速準確地找到花蜜，如圖3所示。整個蜂群對周圍環(huán)境的變化適應度也是非常高的。

圖3 蜜蜂交流信息示意圖

Karaboga在2005年提出人工蜂群算法。它是一種具有群體統(tǒng)一性、智能規(guī)劃性質的算法，其思想來源于模擬現(xiàn)實中的蜜蜂的各種行為。通常，食物源所在的位置表征待優(yōu)化問題的一個可行解，待采蜜源的豐富程度與解的質量是相對的，豐富程度越高的蜜源所對應的解的質量也越好。如圖4所示，蜜蜂去一個食物源開采花蜜，每個采蜜蜂（引領蜂）攜帶它采蜜過程中獲得的各種信息飛回蜂巢，它將在外面采蜜儲存的所有信息傳遞給其它等待的觀察蜂（跟隨蜂）。等待中的蜜蜂接收這些有用的信息，以蜜蜂之間特有的方式選擇好的蜜源開采。蜜蜂的行為可分為：招募行為和放棄食物源行為。招募行為是指采蜜蜂通過“搖擺舞”來傳遞所得到的食物源的各種信息，等待的觀察蜂接收信息，開采豐富程度高的食物源。放棄食物源行為是指一個蜜源在開采一定次數(shù)之后質量下降或達到開采上限，這時采蜜蜂會放棄該食物源轉變形態(tài)成為偵查蜂搜索新的目標或成為觀察蜂。人工蜂群算法巧妙地統(tǒng)籌種群內部各種單一個體，使所有個體都有明確的分工，各種蜜蜂各司其職，非常適合解決群體復雜優(yōu)化問題。

圖4 蜜蜂采蜜過程圖

相較其他智能算法，人工蜂群算法的操作比較簡單，需要控制的參數(shù)較少，并且魯棒性比較強。但是在傳統(tǒng)的人工蜂群算法中，存在一些缺點：（1）引領蜂搜索是一個隨機的過程，局部搜索能力較弱，算法從開始階段收斂速度就較慢；（2）存在“早熟”的收斂性缺陷。如何增強人工蜂群算法鄰域搜索的開發(fā)能力，對算法本身以及將算法應用于無人機航跡規(guī)劃中都顯得十分重要。

2 展望

2.1 應用環(huán)境展望

21世紀是信息爆炸的時代，現(xiàn)代戰(zhàn)爭也進入高技術信息化的時代，立體和多維是現(xiàn)代戰(zhàn)爭的重要特點。而無人機由于其重量輕、機動性高、造價低和不必冒生命危險等優(yōu)點將在軍事戰(zhàn)爭中扮演越來越重要的角色。另一方面，隨著雷達技術的發(fā)展，相控陣雷達技術的逐漸完善以及廣泛應用，導彈制導精度的不斷提高，無人機在執(zhí)行任務時需要面對的環(huán)境更加惡劣，需要承擔的風險日益增大。因此，很多情況下，單架無人機無法滿足任務要求。當考慮到單架無人機執(zhí)行任務還涉及工作空間小、視角范圍小以及載重量小等系列問題時，人們?yōu)榱藨獙ξ磥硇畔⒒瘧?zhàn)爭的需要，開始研究多無人機協(xié)同編隊飛行（Coordinated Formation Flight，簡稱CFF）。無人機協(xié)同編隊飛行可以實現(xiàn)冗余配置，提高任務的完成概率，就算編隊中有一兩架無人機出現(xiàn)問題的時候，其他無人機也可以繼續(xù)完成任務。此外，多架無人機通過任務分配可以大大縮短完成任務的時間，從而增強執(zhí)行任務的能力。另外，多無人機系統(tǒng)還有對目標的協(xié)同定位、協(xié)同感應和協(xié)同干擾能力等，可以大大提高任務的執(zhí)行效率。因此，使用多無人機協(xié)同執(zhí)行任務已成為未來無人機發(fā)展的必然趨勢。

2.2 群智能優(yōu)化算法展望

隨著優(yōu)化理論的發(fā)展，一些新穎的群智能優(yōu)化算法不斷被提出并得到了長足的發(fā)展，成為解決優(yōu)化問題的新方法，如狼群算法、果蠅算法、魚群算法等。這些算法不但豐富了現(xiàn)代優(yōu)化技術，為具有非線性、多目標等特點的組合優(yōu)化問題提供了新的解決方案，而且為其他優(yōu)化算法提供了新的改進思路。雖然針對群智能優(yōu)化算法已經開展了大量的研究，但是具體到每個算法，都還存在一些不足之處，未來對優(yōu)化算法的研究依然還是混合算法。所謂混合算法就是指將兩個已經存在的算法按照一定的規(guī)則搭配起來組成一個新的算法，這個新的算法能夠繼承這兩種算法的優(yōu)點并克服缺點，從而獲得較好的算法性能。通常情況下有三種混合方式。其一，將兩種算法串行混合，首先利用一種算法進行優(yōu)化快速收斂到較優(yōu)解集，然后使用另外一種算法得出最優(yōu)解；其二，將兩種算法并行混合，用兩種算法同時進行優(yōu)化，在優(yōu)化過程中進行部分信息交互也可以在優(yōu)化結束后對兩種優(yōu)化結果進行篩選；其三，將全局算法與局部算法進行混合，用全局算法的大框架在全局范圍內進行尋優(yōu)，在局部用局部搜索方法較快較好得到局部最優(yōu)解。

3 結束語

在無人機航跡規(guī)劃的研究中，針對已知環(huán)境下靜態(tài)航跡預規(guī)劃已開展了大量的研究，對該問題的探究已經相對成熟。而隨著無人機要執(zhí)行的任務越來越復雜，加上環(huán)境的不確定，未知威脅信息環(huán)境下的實時無人機航跡規(guī)劃將是未來研究的重點和難點，該問題要求在規(guī)定的時間內得到代價盡可能小的航跡。

[1]辛貴州.無人飛行器航跡規(guī)劃算法研究[D].黑龍江：哈爾濱工程大學，2010.

[2]程曉明.無人機雙機協(xié)同航跡規(guī)劃技術研究[D].江蘇：南京航空航天大學，2015.

[3]繆永飛.軍用飛行器航跡規(guī)劃與顯示技術研究[D].湖南：國防科學技術大學，2006.