基于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日