灰狼優化算法的改進及其應用

鄧 飛，魏祎璇，劉奕巧，王統照

（1.華北科技學院 經濟管理學院，河北 廊坊 065201；2.北京科技大學 大安全科學研究院，北京 100083；3.馬來亞大學 機械工程學院，馬來西亞 吉隆坡50603；4.寧波諾丁漢大學 流體與熱工程研究中心，浙江 寧波 315100）

0 引言

求解復雜問題的經典群體智能優化算法有遺傳算法（Genetic Algorithm,GA）[1]、模擬退火算法（Simulated Annealing,SA）[2]、粒子群優化算法（Particle Swarm Optimization,PSO）[3]、蟻群優化算法（Ant Colony Optimization,ACO）[4]等。Mirjalili 等（2014）[5]提出的灰狼優化算法（Grey Wolf Optimization，GWO）雖然較其他群體智能算法具有調節參數少、結構簡化易于程序實現、求解精度高等優點,但也存在一定的缺陷，例如：不能直接對離散組合問題進行求解[5]；存在著群體進化迭代中全局尋優能力欠缺，容易陷入局部最優的問題；不能直接用于解決多目標優化復雜問題。針對上述問題，本文在GWO算法的基礎上進行改進，提出離散編碼、解碼策略以適配優化離散組合問題；引入GA 算法中的交叉操作和大規模鄰域搜索算法（Large Neighborhood Search，LNS）中的破壞修復操作，在彌補全局搜索能力不足的同時，進一步提高局部搜索能力；融入NSGA-Ⅱ框架，實現多目標優化復雜問題的求解。

1 問題描述

旅行商問題（Travelling Salesman Problem,TSP）和多旅行商問題（Multiple Traveling Salesman Problem，MTSP）屬于典型的離散組合優化問題[6]，在TSP和MTSP的基礎上添加不同約束條件后可以得到不同形式的泛化多旅行商問題（General Multiple Traveling Salesman Problem，GMTSP）[7]。本文以洪澇災害中的無人機應急救援任務為應用場景來驗證所提出的改進的GWO算法的有效性。為盡快了解整體災情，單架無人機在執行空中巡航任務時從中心出發，訪問受災需求點后再返回中心，僅需在TSP中考慮整個飛行距離最短，因此屬于單目標優化問題。……