無人機航跡規劃群智能優化算法綜述

劉雨坤，侯捷

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

1 常見的無人機航跡規劃群智能優化算法

1.1 粒子群算法

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

圖1 鳥群飛行示意圖

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

1.2 蟻群算法

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

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

圖2 螞蟻覓食示意圖

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

1.3 蜂群算法

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

圖3 蜜蜂交流信息示意圖

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

圖4 蜜蜂采蜜過程圖

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

2 展望

2.1 應用環境展望

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

2.2 群智能優化算法展望

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

3 結束語

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

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

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

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