群智能優化算法在路徑規劃中的應用

張文輝，王晨宇

(1.2.桂林電子科技大學 計算機與信息安全學院，廣西 桂林 541004)

0引言

在移動機器人相關技術研究中，導航技術是其核心，而路徑規劃是導航技術研究的一個重要環節和組成部分。傳統的路徑規劃方法主要有人工勢場法，柵格法，自由空間法等，這些傳統的路徑規劃方法或是為局部極小值問題無法求出最優路徑，或是在復雜環境下求解速度過慢。此外，某些傳統算法在多障礙或動態的環境下可能無法獲得可行路徑。群智能算法因為具有較強的全局搜索能力和并行處理能力，能夠較好的適應復雜的環境，可以用來解決傳統的路徑規劃算法存在的問題。本文主要介紹了三種群智能算法以及它們在路徑規劃中最近的相關研究，并對算法的實驗結果進行了對比。最后，總結了群智能算法應用在路徑規劃中存在的問題，提出了今后主要的研究方向。

1路徑規劃中的群智能算法

群智能(Swarm Intelligence)這一表述最早在1989年由Gerardo Beni在分子自動機系統中提出。群智能算法是模仿自然界的生物群體的自治行為來構造和優化算法[1]。在SI系統中，每個成員個體根據其他成員及其環境的信息調整自己的行為，不斷地進行簡單自組織的局部行為，再通過不同個體之間的信息交流，進而實現群體智能。群智能算法由于其分布性、自組織性、較強的魯棒性等優點，已經成功應用在函數優化等領域。因為群智能算法具有較好的魯棒性，以及并行搜索等特點，近年來許多學者將其應用到優化路徑規劃的算法之中。許多研究者借助群智能算法的這些特點和優勢，對傳統的路徑規劃方法進行優化，取得了顯著的效果。許多研究人員的相關實驗表明，將群智能算法與傳統路徑規劃方法結合，能夠有效提高算法的性能和效率。

1.1人工魚群算法

1.1.1 人工魚群算法簡介

人工魚群算法(Artificial Fish Swarm Algorithm, AFSA)是模擬魚群在自然環境中尋找食物的群智能算法，是由我國學者李曉磊[2]提出的。在人工魚系統中，每條人工魚個體根據周圍環境的食物濃度以及周圍同伴數量來決定將要進行的行為，主要有覓食行為、追尾行為、聚群行為。其中，覓食行為是個體向更優解的方向前進的個體尋優過程，追尾行為和聚群行為是個體與周圍環境相互交互的過程。經過多次迭代操作之后，大部分人工魚將會聚集在食物濃度最好的區域，即尋找到最優解。借助人工魚群算法的較強的并行搜索能力和快速的全局尋優能力，能較好地提高路徑規劃的結果。人工魚群算法的流程圖如圖1所示。

圖1 人工魚群算法流程圖

使用人工魚群算法進行路徑規劃的實驗中，將要進行路徑規劃的區域通過建模方法(柵格法，自由空間法，鏈路圖法)轉化為解空間。其中，目標點代表著食物濃度最高的點，距離目標點越遠的點食物濃度越低，多條人工魚在解空間中進行并行搜索，通過同伴之間的相互影響，不斷向著食物濃度更高的方向前進，從到達目標點的人工魚所經過的路徑中選擇最優的路徑作為路徑尋優結果。但是傳統的人工魚群算法存在著后期收斂速度慢，尋優精度不高的問題，許多研究者提出了相關的改進方法。

1.1.2 人工魚群算法改進路徑規劃方法

黃宜慶等[3]提出基于多策略混合人工魚群算法。處于局部極值周圍的人工魚個體由于視野原因無法尋找到全局極值，引入加權平均距離策略為人工魚選擇合適的視野，保證收斂速度并且防止陷入局部最優。采用對數遞增函數作為移動因子，能更好的定位前進方向，保證全局收斂速度和收斂精度。在算法中增加高斯變異策略，增加了種群多樣性，能夠提高全局搜索能力。

在原始人工魚群算法中，人工魚的視野，步長等參數都是固定的，固定參數會導致算法的適應能力較弱。比如，步長不變可能會導致在算法前期因為步長過小而收斂速度慢，或是在算法后期因為步長過大而產生振蕩現象。與采用固定參數的原始人工魚群算法相比，加入了自適應策略的人工魚群算法能夠根據當前搜索環境的差異，自適應地選取適合的參數，進而能夠提高算法的搜索性能。

由于在人工魚群算法中，最優解會保留在公告牌中，個體間不會分享最優解信息，這意味著它缺乏自上而下的信息交互，這會降低算法的搜索效率。Li等[4]采用混合策略，將差分進化引入到人工魚群算法中。通過變異，交叉和選擇操作，使人工魚個體擺脫局部最優，提高收斂速度。李君等[5]利用最速下降法替代部分覓食行為，保證后期的人工魚每次行為之后都是向適應度較優的方向前進，減少了人工魚行為的隨機性，提高了算法的收斂速度。鄧濤等[6]提出了一種免疫人工魚群網絡算法，引入精英魚策略，簡化聚群行為和追尾行為，構造免疫人工魚群網絡。在減少了計算時間的同時，能有效加快跳出局部極值的速度。姚凌波等[7]借鑒反向學習中反向解的原理，將反向解作為新的引導點，調整人工魚的狀態，提高了發掘潛在較優解的機率，避免其陷入局部最優。

在算法后期，人工魚個體大部分集中在環境中的極值點附近，同伴之間的相互影響會越來越弱，所以算法的后期收斂速度變慢。以上改進算法通過減少算法的隨機性，增加較優個體的影響力，從而提高算法的收斂速度。

針對人工魚群算法收斂精度不高以及不容易跳出局部極值的問題，許多學者采用將傳統人工魚群算法與其他智能算法相結合得到新的混合算法。周金治等[8]提出了基于差分進化與模擬退火的人工魚群算法，采用模擬退火算法對適應度最高的狀態進行細化搜索，解決陷入局部最優解的情況，引入差分策略提高搜索后期的尋優精度，逼近最優解。張淦[9]向傳統人工魚群算法中引入了螢火蟲算法中的吸引度概念，在每次迭代過程中，最低濃度的個體會在行動時會受到最高濃度個體的吸引，處在局部最優解附近的人工魚個體會向著全局最優個體所在方向前進，能夠加快收斂速度。實驗表明，算法的收斂速度得到了較大提升，并且具備一定的跳出局部極值的能力。

人工魚群算法的優點是具有較好的并行搜索能力，并且對初始值要求不高，魯棒性較強，在應用于路徑該規劃問題中時可以在較短的時間內尋找到接近最優路徑的可行解。缺點是算后期收斂速度慢，收斂精度低的。現有的研究主要對算法的參數調整，個體更新提出了改進策略，或是將人工魚群算法與其他算法融合，彌補算法的不足。改進后算法與原始人工魚群算法相比，算法性能在各方面都有較大提升。

1.2蟻群算法

1.2.1 蟻群算法簡介

蟻群算法(Ant Colony Algorithm,ACA)是20世紀90年代由意大利學者Marco Dorigo等人[10]首先提出來的一種基于種群的模擬進化算法，是受自然界中螞蟻尋找食物過程中發現路徑的行為啟發而來的最早是用于解決旅行商(TSP)問題。在蟻群系統中，每一個螞蟻個體在尋找食物的過程中，都會在走過的路徑留下一定濃度的信息素，而螞蟻在選擇路徑時候會更傾向于選擇信息素強度更大的路徑，因此人工蟻群是一種基于正反饋的分布式協作系統。算法流程如圖2所示。

圖2 人工蟻群算法流程圖

1.2.2 蟻群算法改進路徑規劃方法

蟻群算法目前主要有兩種改進方向，一種是改進信息素的更新方式、路徑尋優狀態選擇策略、參數調整，另一種是將蟻群算法與其他算法進行融合。

尚曉磊[11]對信息素更新公式行改進，結合最大—最小值螞蟻算法，將信息素的濃度劃分在一定范圍之間，當一個種群的所有螞蟻都到達目標柵格后，在更新信息素時，派出反向螞蟻對路徑進行全局信息素更新，避免局部最優，從而改善算法的執行效率。為了提高算法的全局搜索能力，使其盡快找到最優路徑，Yu等[12]采用信息素自適應衰減規則，在選擇下一步時考慮信息素和距離，而不僅僅考慮信息素濃度。在蟻群算法中，信息素的更新規則影響著算法的全局搜索能力和局部搜索能力。

以上改進算法對信息素的更新公式進行了改進，避免了信息素平均分配導致蟻群算法收斂速度下降的問題。同時解決了螞蟻容易陷入局部最優和滯后搜索的問題，使得蟻群可以根據實際情況在原有路徑和新路徑之間得到更好的選擇。

針對在復雜環境中，蟻群搜索路徑效率慢，劣質解影響算法的運行速度的問題，王欽釗[13]等結合人工勢場法對蟻群算法改進，通過人工勢場計算路徑點的適應值，初始化信息素矩陣來獲得高質量的初始解，并在算法尋優階段引入勢場力導向算子，改算法能有效降低路徑搜索時候的盲目性和隨機性，保證蟻群搜索的全局性。趙峰等[14]設計了一種實時性的，能夠動態調整的自適應搜索半徑蟻群算法。該算法將路徑規劃的區域劃分為若干個子區域，根據環境的復雜程度自適應地調整搜索半徑，尋找到所有最優局部目標點，之后再尋找全局最優目標點。傳統的蟻群算法中，螞蟻搜索路徑只與信息素有關，目標方向與路徑選擇沒有直接影響，算法的搜索效率比較低。柳長安[15]等提出根據目標點吸引機制，自適應調整啟發函數，提高算法的收斂速度，機器人可以快速地避開障礙物安全到達目標點。

蟻群算法的路徑選擇是基于信息素的濃度的，在復雜環境中，蟻群算法在初始搜索時由于缺少信息素的參與會產生許多劣質解，影響算法的運行效率，加入初始化信息能夠提高初始解的質量。在算法搜索時，增加目標點對路徑的影響使路徑的選擇更具方向性，降低算法搜索時的隨機性和盲目性，能夠有效減少劣質解的產生。實驗表明改進后的算法的收斂速度比傳統蟻群算法有了較大提升，能夠較好地適應復雜的動態環境。

于樹科等[16]提出了融合了蟻群算法和遺傳算法的方法，蟻群算法的反饋機制使其能夠利用系統中的反饋信息，進行全局尋優能力。而遺傳算法搜搜速度快，適合大范圍搜索。算法前期，用遺傳算法產生的最優解來初始化蟻群算法的信息素。算法后期利用蟻群算法的收斂速度快來尋找最優路徑。

個人認為蟻群算法具有較強的自適應能力和魯棒性，是一種全局搜索算法，利用信息素正反饋和信息共享機制來尋找最優路徑是蟻群算法最大的特點，能夠很好地應用于路徑規劃的問題中。但是蟻群算法的計算量大，易陷入局部最優解。現有的改進算法主要是對蟻群算法的信息素更新方式，路徑選擇方式改進，或是融合蟻群算法與其它群智能算法。

2.3粒子群算法

2.3.1 粒子群算法簡介

算法(Particle Swarm Optimization, PSO)是Kennedy和Eberhart于1995年提出的群智能優化算法[17]，已經被廣泛應用于訓練神經網絡、功能優化和各類基于過程的分析應用。其基本思想是所有粒子通過適應度函數確定飛行速度，并由速度決定粒子在解空間中的搜索行為。每個粒子都有一個由目標函數決定的適應值，并知道給粒子本身發現的適應值最好的位置以及整個群體的粒子發現的最好位置。粒子通過自身經驗和群體經驗來決定下一步的行為。

在路徑尋優算法中，每個粒子的位置代表一個可行解即有效路徑，通過不斷更新迭代最終找到評價最優的函數值即最優解。與其他算法相比，粒子群算法具有簡單易實現、收斂速度快、控制參數少等優點，并適用于復雜非線性問題及離散優化問題。但PSO算法也是一種隨機啟發式算法，其自身存在一些不足，初始化粒子的隨機性較強，影響粒子群的尋優效率和可靠性，依賴歷史最優導致算法后期的局部搜索能力較差。粒子群算法的流程圖如圖3所示。

圖3 粒子群的速度和位置更新

1.3.2 粒子群算法改進路徑規劃方法

粒子群算法由于粒子搜索的隨機性，存在著收斂速度差、局部尋優能力弱的缺點，方昕[18]結合A星搜索算法的思想，初始化種群生成含有啟發信息的粒子群，引入平滑度調整粒子搜索方向，使用慣性權重來控制算法的局部搜索能力和全局搜索能力，提高了算法的收斂精度。楊景明等[19]提出一種多目標自適應混沌粒子群優化算法，該算法對全局最優粒子采用了一種新型動態加權方法，并引入了自適應變異策略，算法在不同時期能夠自適應地調整參數，不僅提高了最優解的質量，而且提高了最優解的均勻性。

粒子群算法依賴全局歷史最優解和個體歷史最優解，可以很好地利用群體信息，收斂性強。但是依賴歷史信息容易導致算法在搜索后期的種群多樣性較差，局部搜索能力不足。針對多目標問題要求得到的非劣解能夠盡可能分布均勻且覆蓋廣泛，張超[20]提出了混合粒子群算法與人工蜂群算法的混合算法，兼顧了收斂性能和多樣性。為了減弱個體對歷史最優解的依賴，自適應的調整每個個體歷史最優解的加速因子，使個體歷史最優解的影響逐漸降低，讓更加優秀的全局歷史最優解發揮更大的作用。

針對粒子群算法過早收斂問題文獻，劉潔[21]提出了自適應權重策略。在粒子群算法中，慣性權重較大時會提高算法的全局搜索能力，慣性權重較小的時候算法偏向于局部搜索。將利用個體粒子的速度和群體粒子的離散度來動態地調整慣性權重，能夠避免陷入局部最優解。為了提高算法的準確性和穩定性，在位置更新中引入了自然選擇方法，保持種群多樣性。實驗證明，改進后的算法有效地提升了收斂速度、加強了算法的全局搜索能力。

Guo等[22]根據移動機器人路徑規劃問題的總體設計，提出了模糊神經網絡的控制方法，該方法結合了模糊控制和神經網絡。改進的粒子群算法用于調整模糊神經網絡的參數，以更好地實現移動機器人的路徑規劃。神經網絡具有較強的容錯性和自適應學習的能力，能夠有效地分析和融合環境中的信息。模糊控制具有邏輯推理的能力，在處理結構化知識方面更為有效。該算法結合了神經網絡與模糊控制的優點，融合神經網絡的自學習能力和模糊控制的模糊推理能力，并利用粒子群算法對模糊神經網絡的參數進行優化，增加了算法的搜索精度。

粒子群算法具有簡單易實現，收斂速度快，適應性強等優點。但是粒子群算法同其他群智能算法一樣，存在著易陷入局部最優的問題。目前的改進放方法對粒子群的更新策略、參數調整進行了改進，或者是利用粒子群算法的優勢將粒子群算法與神經網絡或者其他智能算法相融合。

2群智能算法性能比較

每種群智能算法在應用到路徑規劃的時候都有其優點，但也會存在不足。存在的比較大問題是結果易陷入局部最優，收斂速度慢，收斂精度低等問題。總結結果如表1所示。

表1 各群智能算法優化路徑規劃存在的優缺點比較

人工魚群算法在應用到路徑規劃時，具有收斂速度快，對初始參數不敏感，魯棒性高，較強的全局搜索能力等優點。但是算法后期的搜索速度慢，而且人工魚容易在局部最優解附近徘徊，導致收斂精度下降。目前已應用于組合優化、神經網絡訓練、約束優化、電力系統負荷預測、參數估計、多目標優化等題，并且取得了良好的效果。

人工蟻群算法本身就是模仿螞蟻尋找路徑而來，在進行路徑的時候具有正反饋，分布式協作和信息共享的特點。但是蟻群算法的計算時間比較長，而且依賴于信息素的影響，可能當出現較優路徑的時候由于信息素含量的影響出現停滯現象。蟻群算法最初用于解決旅行商問題。已經陸續滲透到其他領域中，如二次分配問題、大規模集成電路設計、通訊網絡中的路由問題以及負載平衡問題、車輛調度問題、數據聚類問題、區域性無線電頻率自動分配問題等。

粒子群算法的參數較少，易于實現，收斂精度高，算法早期的收斂速度快，但是局部搜索能力差，后期搜索速度慢。粒子群算法最早應用于訓練人工神經網絡，隨后，粒子群算法被廣泛地應用于函數優化、 約束優化、 模式分類、機器人路徑規劃、 信號處理、模式識別等工程領域。

3結束語

本文主要從群智能算法對路徑規劃研究成果進行了論述。傳統的路規劃方法由于計算時間長，處理復雜環境能力弱等問題并不能很好的得到一條最優路徑。群智能優化算法因為普遍具有分布性，自組織性，較強的魯棒性的優點，被廣泛地應用在路徑規劃領域，并取得了一定的成果，但是仍有一些問題需要解決。比如，改進后算法雖然在一定條件下避免了陷入局部最優，或是增強了跳出局部極值的能力，但是依然存在著陷入局部最優的可能性。有的算法收斂速度較快，但是會發生早熟現象，影響收斂精度。

對參數的調整能夠改變算法的性能，如何設置最優參數適應不同的環境也是一種優化問題。路徑規劃算法應用場景不斷拓展，為了滿足多約束條件的目標優化，將多種算法進行融合是一種主要的方法。目前的路徑規劃研究多是在已知靜態的二維環境下進行實驗，隨著技術領域的不斷拓展，復雜三維環境下的動態路徑規劃是未來研究的趨勢。