基于NSGA-Ⅱ算法的傳感器目標(biāo)分配*

吳建剛　詹廣平　張代國

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

?

基于NSGA-Ⅱ算法的傳感器目標(biāo)分配*

吳建剛詹廣平張代國

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

摘要將傳統(tǒng)的傳感器目標(biāo)分配問題轉(zhuǎn)化為了基于跟蹤效能最大和傳感器使用率最小的多目標(biāo)優(yōu)化模型。利用非劣分層遺傳算法處理傳感器目標(biāo)分配多目標(biāo)優(yōu)化問題。非劣分層遺傳算法通過對種群內(nèi)的所有個(gè)體的多個(gè)目標(biāo)函數(shù)進(jìn)行非劣分層排序來度量個(gè)體的適應(yīng)能力,通過遺傳算法能夠獲取Pareto最優(yōu)解集。仿真試驗(yàn)表明該方法能夠獲得滿意效果。

關(guān)鍵詞多目標(biāo)優(yōu)化; 遺傳算法; 傳感器目標(biāo)分配; 非劣分層; 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引言

隨著科技的發(fā)展,各種面向復(fù)雜應(yīng)用背景的多傳感器系統(tǒng)大量涌現(xiàn),已廣泛應(yīng)用于工業(yè)、農(nóng)業(yè)、交通、氣象預(yù)報(bào)、環(huán)境監(jiān)測、地球科學(xué)觀測等各個(gè)領(lǐng)域。為了充分發(fā)揮多傳感器系統(tǒng)的協(xié)同探測性能,必須對傳感器資源進(jìn)行科學(xué)合理的分配,因此產(chǎn)生了信息融合領(lǐng)域傳感器管理的概念[1~2]。傳感器管理是指利用多個(gè)傳感器收集關(guān)于目標(biāo)與環(huán)境的信息,以任務(wù)為導(dǎo)向,在一定的約束條件下,合理分配參與執(zhí)行任務(wù)的傳感器,通過使傳感器信息在網(wǎng)絡(luò)中實(shí)現(xiàn)共享,恰當(dāng)分配或驅(qū)動多傳感器協(xié)同工作完成相應(yīng)的任務(wù),以使一定的任務(wù)性能最優(yōu)。其中,傳感器目標(biāo)分配是傳感器管理的一項(xiàng)重要內(nèi)容,即對多傳感器多目標(biāo)跟蹤任務(wù)進(jìn)行分配調(diào)度,在滿足跟蹤精度的條件下不至于過度浪費(fèi)資源,從而發(fā)揮多傳感器協(xié)同探測的能力[3]。

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

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

2理論模型

(1)

(2)

用第i個(gè)傳感器監(jiān)測第j個(gè)目標(biāo)的探測概率可表示為

pij=1-(1-eij)xij

(3)

則所有m個(gè)傳感器對目標(biāo)j的探測概率pj為

(4)

監(jiān)測效能為

(5)

決策方案中,使用的傳感器跟蹤目標(biāo)數(shù)目為

(6)

則傳感器使用率為

(7)

從而可建立標(biāo)準(zhǔn)的約束優(yōu)化問題為

(8)

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

3模型求解

3.1NSGA-Ⅱ算法

NSGA-Ⅱ算法是將標(biāo)準(zhǔn)遺傳算法應(yīng)用于多目標(biāo)優(yōu)化問題時(shí)提出的,其思想是將Pareto集非劣分層的方法應(yīng)用到遺傳算法中,具體做法為:通過對多目標(biāo)解群體基于個(gè)體的秩進(jìn)行分類,得到具有優(yōu)劣關(guān)系的不同非劣層,而第一非劣層構(gòu)成Pareto前端,Pareto前端代表了最優(yōu)解集,與傳統(tǒng)優(yōu)化問題不同的是,Pareto解給出的是一個(gè)最優(yōu)解的集合,可供決策者針對不同的情形進(jìn)行選擇[7~10]。

用于多目標(biāo)優(yōu)化求解的NSGA-Ⅱ算法要關(guān)注的幾個(gè)重要概念如下:

· 種群個(gè)體秩

個(gè)體的秩的定義是種群中Pareto占優(yōu)個(gè)體的數(shù)目。

· Pareto集非劣分層

種群中相同秩的個(gè)體分為一層;具體分層方式根據(jù)個(gè)體的秩進(jìn)行分層,個(gè)體秩越小則該層優(yōu)勢越大,最優(yōu)非劣層是秩為1的分層,通常稱為Pareto前端。

3.2NSGA-Ⅱ應(yīng)用

本文采用NSGA-Ⅱ算法進(jìn)行傳感器目標(biāo)分配優(yōu)化,其流程圖如圖1所示。具體實(shí)現(xiàn)步驟如下:

圖1　NSGA-Ⅱ算法傳感器目標(biāo)分配流程圖

1) 問題解編碼:由于每個(gè)傳感器對特定目標(biāo)的探測只有兩種狀態(tài),因此本文采用二進(jìn)制0-1編碼。

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

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

2) 初始化目標(biāo)分配解種群。結(jié)合約束條件生成一個(gè)比所需群體規(guī)模要大很多的初始群體,從該群體中再隨機(jī)選取適合所要的群體規(guī)模的個(gè)體,選擇以后對所選的初始群體進(jìn)行評價(jià),如果它的最好個(gè)體的適應(yīng)度達(dá)到了理論適應(yīng)度的0.8左右,則選擇,否則重新生成大規(guī)模的初始群體進(jìn)行選擇。

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

4) 遺傳算子操作:遺傳算子操作與標(biāo)準(zhǔn)遺傳算法一樣,交叉過程中采用基因重組的形式產(chǎn)生兩個(gè)子個(gè)體,選擇過程采用Pareto占優(yōu)的概念,在所產(chǎn)生的兩個(gè)個(gè)體和父本個(gè)體中選擇最優(yōu)的個(gè)體,如果兩個(gè)個(gè)個(gè)體無差別,則在兩個(gè)子個(gè)體中隨機(jī)選擇一個(gè)個(gè)體。

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

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

3.3仿真分析

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

對于優(yōu)化模型本文采用罰函數(shù)法處理其中的約束條件,然后進(jìn)行求解。

圖3　NSGA-Ⅱ算法求解傳感器目標(biāo)分配結(jié)果Pareto前端分布圖

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

4結(jié)語

本文結(jié)合遺傳算法和Pareto集多目標(biāo)優(yōu)化方法,將非劣分層多目標(biāo)優(yōu)化遺傳算法NSGA-Ⅱ應(yīng)用到了傳感器目標(biāo)分配問題,利用多目標(biāo)優(yōu)化遺傳算法搜索能力強(qiáng)、考慮問題全面等特點(diǎn)進(jìn)行目標(biāo)分配。仿真實(shí)驗(yàn)表明,NSGA-Ⅱ算法結(jié)構(gòu)簡單,易于實(shí)現(xiàn),且搜索能力強(qiáng),可適用于解決較復(fù)雜的或規(guī)模較大的傳感器目標(biāo)分配問題。

參 考 文 獻(xiàn)

[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

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

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