基于自適應遺傳算法的連續時空最優搜索路徑規劃研究

張獻，任耀峰，王潤芃（海軍工程大學理學院，湖北武漢430033）

基于自適應遺傳算法的連續時空最優搜索路徑規劃研究

張獻，任耀峰，王潤芃
（海軍工程大學理學院，湖北武漢430033）

針對連續時空最優搜索者路徑問題，利用隨機微分方程描述Markov運動目標，建立了同時優化搜索者方向和速度的規劃模型，并考慮了搜索速度對探測能力的影響。設計了一種新穎的自適應變異遺傳算法，算法采用較高的變異概率作用于父代精英個體組，通過引入3種控制因子對變異方向和幅度進行自適應控制，動態調節局部搜索和全局搜索的平衡。在對方向未知的逃離目標搜索算例中，得到了近似對數螺旋曲線的搜索路徑；在直升機搜索多目標的路徑規劃中，提供了合理有效的搜索方案。算法對比表明所給出的算法在全局優化能力和穩定性上有明顯的優勢，適用于求解連續搜索路徑規劃問題。

運籌學；最優搜索；連續時空；Markovian目標；自適應變異遺傳算法；反潛搜索

0　引言

最優搜索者路徑問題（OSPP）是搜索論中搜索者運動受到約束的一類復雜優化問題，要求搜索者在有限資源約束下，構造一個搜索路徑使得搜索效益最大，目前在海上救援、無人機偵查、反潛搜索[1-3]等諸多領域有廣泛的應用。

根據是否對時間和空間進行了離散化處理，OSPP可大致分為離散時空OSPP和連續時空OSPP兩類[4]。1986年Trummel和Weisinger已經證明了在離散時間和空間下，對于靜止目標OSPP的復雜度至少是NP-hard[5].目前無論對于哪類問題，許多學者都將算法的設計與優化作為問題研究的一個重要方向?！?br>