基于NSGA-Ⅱ算法的傳感器目標分配*

吳建剛　詹廣平　張代國

(海軍駐武漢三江航天集團軍事代表室　孝感　432000)

?

基于NSGA-Ⅱ算法的傳感器目標分配*

吳建剛詹廣平張代國

(海軍駐武漢三江航天集團軍事代表室孝感432000)

摘要將傳統的傳感器目標分配問題轉化為了基于跟蹤效能最大和傳感器使用率最小的多目標優化模型。利用非劣分層遺傳算法處理傳感器目標分配多目標優化問題。非劣分層遺傳算法通過對種群內的所有個體的多個目標函數進行非劣分層排序來度量個體的適應能力,通過遺傳算法能夠獲取Pareto最優解集。仿真試驗表明該方法能夠獲得滿意效果。

關鍵詞多目標優化; 遺傳算法; 傳感器目標分配; 非劣分層; Pareto集

Sensor-target Assignment with Multi-objective NSGA-Ⅱ Algorithm

WU JiangangZHAN GuangpingZHANG Daiguo

(Navy Representative Office in Wuhan Sanjiang Aerospace Group, Xiaogan432000)

AbstractThe sensor-target assignment problem is transformed into a multi-objective optimization model, which is based on maximum detection efficiency and minimum the used sensor resource. The non-dominated set ranking genetic algorithm(NSGA-Ⅱ) is presented to solve the multi-objective optimization sensor-target assignment problem. The population’s fitness is evaluated by the non-dominated set rank, the diversity evolution operation is evaluated by genetic algorithm(GA). The proposed NSGA-Ⅱ algorithm can provide Pareto-optimal front. The simulation experiment gives good assignment result.

Key Wordsmulti-objective optimization, genetic algorithm, sensor-target assignment, non-dominated set ranking, Pareto set

Class NumberTP301.6; TP202

1引言

隨著科技的發展,各種面向復雜應用背景的多傳感器系統大量涌現,已廣泛應用于工業、農業、交通、氣象預報、環境監測、地球科學觀測等各個領域。為了充分發揮多傳感器系統的協同探測性能,必須對傳感器資源進行科學合理的分配,因此產生了信息融合領域傳感器管理的概念[1~2]。傳感器管理是指利用多個傳感器收集關于目標與環境的信息,以任務為導向,在一定的約束條件下,合理分配參與執行任務的傳感器,通過使傳感器信息在網絡中實現共享,恰當分配或驅動多傳感器協同工作完成相應的任務,以使一定的任務性能最優。其中,傳感器目標分配是傳感器管理的一項重要內容,即對多傳感器多目標跟蹤任務進行分配調度,在滿足跟蹤精度的條件下不至于過度浪費資源,從而發揮多傳感器協同探測的能力[3]。

多傳感器多目標分配問題是典型的最優化問題,傳統的求解方法是根據傳感器目標感知概率建立目標跟蹤效能函數,然后采用傳統規劃類或新興智能優化方法進行求解。這種方法求解屬于單目標優化問題,往往能夠獲取全局最優解,且跟蹤的效能實現最大化,但往往分配結果會過多的使用傳感器資源,造成一定程度的資源浪費[4~6]。因此,本文增加一個傳感器使用率函數,即在跟蹤效能函數最大化的基礎上,使傳感器使用率最小。這樣就可以將傳感器目標分配問題轉化為多目標優化問題。多目標優化問題是指多個目標函數在解的可行域上的優化問題,在科學研究和工程實踐中許多優化問題均可歸結為多目標優化問題,包括目標分配、城市運輸、能量分配、網絡優化、資本預算、工業制造等。傳統的多目標優化方法是將多個目標函數通過偏好加權轉化為單目標優化問題,而現實工程應用中決策者不易獲取偏好權值,使得決策造成困難。近年來基于Pareto集多目標優化策略的求解方法能夠避免傳統方法的偏好權值選取,且能獲得一系列前端解集合,供決策者參考,因此被廣泛應用于多目標優化決策。

本文根據遺傳算法和Pareto集多目標優化原理,研究了非劣分層的多目標優化遺傳算法,采用Pareto集非劣分層原理,根據種群中個體的多個目標函數值進行非劣分層,得到非劣解集,從而為決策者提供多種決策方案。文中首先介紹了傳感器目標分配問題的多目標優化數學模型,接著研究了非劣分層的多目標優化遺傳算法(NSGA-Ⅱ)及其在傳感器目標分配中的應用,最后進行了傳感器目標分配仿真試驗,從而實現了NSGA-Ⅱ求解傳感器目標分配問題。

2理論模型

(1)

(2)

用第i個傳感器監測第j個目標的探測概率可表示為

pij=1-(1-eij)xij

(3)

則所有m個傳感器對目標j的探測概率pj為

(4)

監測效能為

(5)

決策方案中,使用的傳感器跟蹤目標數目為

(6)

則傳感器使用率為

(7)

從而可建立標準的約束優化問題為

(8)

其中,i=1,2,…,n;j=1,2,…,m。

3模型求解

3.1NSGA-Ⅱ算法

NSGA-Ⅱ算法是將標準遺傳算法應用于多目標優化問題時提出的,其思想是將Pareto集非劣分層的方法應用到遺傳算法中,具體做法為:通過對多目標解群體基于個體的秩進行分類,得到具有優劣關系的不同非劣層,而第一非劣層構成Pareto前端,Pareto前端代表了最優解集,與傳統優化問題不同的是,Pareto解給出的是一個最優解的集合,可供決策者針對不同的情形進行選擇[7~10]。

用于多目標優化求解的NSGA-Ⅱ算法要關注的幾個重要概念如下:

· 種群個體秩

個體的秩的定義是種群中Pareto占優個體的數目。

· Pareto集非劣分層

種群中相同秩的個體分為一層;具體分層方式根據個體的秩進行分層,個體秩越小則該層優勢越大,最優非劣層是秩為1的分層,通常稱為Pareto前端。

3.2NSGA-Ⅱ應用

本文采用NSGA-Ⅱ算法進行傳感器目標分配優化,其流程圖如圖1所示。具體實現步驟如下:

圖1　NSGA-Ⅱ算法傳感器目標分配流程圖

1) 問題解編碼:由于每個傳感器對特定目標的探測只有兩種狀態,因此本文采用二進制0-1編碼。

假定有m個目標,傳感器系統中有n個可用器。采用二進制0-1編碼,每個染色體由按目標順序排列的傳感器編號組成,表示一種可能的分配方案,其中每個基因表示一批目標的分配結果,染色體的長度為m*n。編碼基因的取值為0或者1,不同的基因可取相同的編碼值。例如:m取4,n取3,如圖2所示,種群的1個染色體001011001001表示一個目標分配方案,即第1個傳感器只分配給第三個目標,第2個傳感器分配給目標1和2,第3種武器分配給目標1和4。

圖2　染色體編碼方案示意圖

2) 初始化目標分配解種群。結合約束條件生成一個比所需群體規模要大很多的初始群體,從該群體中再隨機選取適合所要的群體規模的個體,選擇以后對所選的初始群體進行評價,如果它的最好個體的適應度達到了理論適應度的0.8左右,則選擇,否則重新生成大規模的初始群體進行選擇。

3) Pareto集非劣分層:種群中每個解與該種群中所有的其它解進行比較,看是否劣于種群中的其它任意一個解,并記錄個數,根據個數進行分層。

4) 遺傳算子操作:遺傳算子操作與標準遺傳算法一樣,交叉過程中采用基因重組的形式產生兩個子個體,選擇過程采用Pareto占優的概念,在所產生的兩個個體和父本個體中選擇最優的個體,如果兩個個個體無差別,則在兩個子個體中隨機選擇一個個體。

5) 種群合并與篩選。對整個親代和子代種群執行非劣分層,然后再進行種群篩選,選出初始種群規模大小的種群,具體篩選策略是:從最優非劣解開始,接收每層的個體直到填滿所有的種群位置。

6) 迭代次數加1,返回步驟3),直至達到最大迭代次數為止,種群中的所有第一非劣層解即構成Pareto最優解集。

3.3仿真分析

為了驗證本文算法的有效性,將設計仿真試驗進行傳感器目標分配優化,假設傳感器系統具有三種不同的傳感器,需要探跟蹤四個目標,第1個傳感器最多可跟蹤8個目標,第2個傳感器最多可跟蹤8個目標,第3個傳感器最多可跟蹤8個目標,則傳感器最大可跟蹤目標矩陣為C=[8,8,8]。目標的重要程度系數和每種傳感器對每個目標的概率見重要程度系數矩陣和探測概率矩陣,重要程度矩陣W=[0.7,0.8,0.9,0.85],探測概率矩陣

對于優化模型本文采用罰函數法處理其中的約束條件,然后進行求解。

圖3　NSGA-Ⅱ算法求解傳感器目標分配結果Pareto前端分布圖

圖3為200次迭代后的種群,串聯曲線連接的8個點為Pareto前端,即最優非劣解集,其中的每一個解代表一種分配方案。圖3中所示的用改進的NSGA-Ⅱ算法求解的傳感器目標分配多目標優化模型得到的非劣解集構成的Pareto前沿,較好地維護了Pareto解的分布性與收斂性,體現了增加傳感器使用率對探測效能的影響,便于決策者進行決策。例如,如果決策者要求探測效能0.7

4結語

本文結合遺傳算法和Pareto集多目標優化方法,將非劣分層多目標優化遺傳算法NSGA-Ⅱ應用到了傳感器目標分配問題,利用多目標優化遺傳算法搜索能力強、考慮問題全面等特點進行目標分配。仿真實驗表明,NSGA-Ⅱ算法結構簡單,易于實現,且搜索能力強,可適用于解決較復雜的或規模較大的傳感器目標分配問題。

參 考 文 獻

[1] Bar-Shalom Y, Willet P, Tian X. Tracking and data fusion: a handbook of algorithms[J]. Control Systems,2012,32(5):114-116.

[2] Kruger A B. Itegrated tracking and sensor management based on expected information gain[C]//Proc. of SPIE Signal Processing, Sensor Fusion, and Target Recogniton,2007,6567:65670C1-C11.

[3] Kolba M P, Collins L M. Sensor management using a new framework for observation modeling[C]//Proc. of SPIE Signal Processing and Statistical Classification,2009,7303:1-26.

[4] Nash J M. Optimal allocation of tracking resources[C]//Proc. of the IEEE Conference on Decision and Control,2000:1177-1180.

[5] Avasarala V A. Market-based approach to sensor management[J]. Journal of Advances in Information Fusion,2009,4:1-27.

[6] Chavali P, Nehorai A. Managing multi-modal sensor networks using price theory[J]. IEEE Trans. on Signal Processing,2012,60(9):4874-4886.

[7] Kalyanmoy D. Muilti-objective optimization using evolutionary algorithms[M]. New York: John Wiley & Sons,2001:245-253.

[8] Kundu D, Suresh K, Ghosh S, et al. Muilti-objective optimization with artificial weed colonies[J]. Information Science,2011(181):2441-2454.

[9] Srinivas N, Deb K. Muilti-objective optimization using nondominated sorting in genetic algorithms[J]. Evolutionary Computation,1994,2(3):221-248.

[10] Deb K, Pratap A, Agarwal S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-Ⅱ[J]. Evolutionary Computation, IEEE Transactions on,2002,6(2):182-197.

中圖分類號TP301.6; TP202

DOI:10.3969/j.issn.1672-9730.2016.03.009

作者簡介:吳建剛,男,碩士,工程師,研究方向:項目管理。

收稿日期:2015年9月10日,修回日期:2015年10月27日