﻿ 基于子目标进化的高维多目标优化算法
 文章快速检索 高级检索

Many-objective optimization based on sub-objective evolutionary algorithm
LEI Yuyao, JIANG Wenzhi , LIU Lijia, MA Xiangling
Department of Ordnance Science and Technology, Naval Aeronautical and Astronautical University, Yantai 264001, China
Abstract: many-objective optimization is widely used in engineering area. There are some flaws to deal with many-objective optimization problem which the number of objectives exceeded three. The method which could chose proper individual solution is very crucial to solve high-dimension many-objective optimization problem. A sub-objective evolutionary algorithm (SOEA) was put forward to solve this problem. It was given in an abstract way to get the non-dominance solutions of high-dimension many-objective optimization problem. Firstly, the value of sub-objective function was sorted, and then partial Pareto non-dominance solutions of evolutional set were obtained quickly. By using the information of sorting, it could reduce the times of solution comparison in evolutional set and could get the solutions quickly. A uniform difference Minkowski distance algorithm and "k-neighbor" strategy were applied to compute fitness function. By using this method, it could improve the convergence speed to approach Pareto non-dominance solutions. Compared with the algorithms which can solve many-objective optimization problem for computing standard testing functions, it was showed the better performance of the SOEA algorithm.
Key words: many-objective optimization     sub-objective evolutionary algorithm     Pareto non-dominance solution set     Minkowski distance     genetic algorithm

1 多目标优化相关表述

n个决策变量和m个目标变量的多目标优化问题[2]可以表述为

1) 若对于∀i=1,2,…,m;fi(xa)≤fi(xb)且∃j=1,2,…,m;fj(xa)＜fj(xb)，则记作xasxb,也称为xa强支配xb.

2) 若对于∀i=1,2,…,m;fi(xa)≤fi(xb)记作xaxb,也称为xa弱支配xb.文中的支配概念,均是该定义下的弱支配.

2 高维优化SOEA算法 2.1 理论可行性证明

1) 多目标优化问题的各个子目标函数在解空间上是连续的.若存在可去间断点和阶跃间断点,则利用目标函数在解空间连续的方法进行讨论,而不影响问题求解结果.

2) 解空间是Rn上的有界闭子空间.

2.2 SOEA算法 2.2.1 进化过程

SOEA算法是以进化种群中子目标函数值排序为基础.根据求取的是目标函数的最大(最小)值,对子目标函数值进行排序.通过子目标值的排序,快速找出非支配解.以子目标函数f1为例,要求取目标函数的最小值.进化过程如图 1所示,通过排序,得到使f1取最小值的解空间中的点A,A为通过目标函数f1获得的第1个非支配解.继续该过程得到CC1f1上的函数值仅比A大,但是CC1在子目标f2上的函数值比A小,故CC1相对于A为非支配解.但是C支配C1,故C为非支配解.由此可见,子目标进化算法的方向性很强.

 图 1 进化过程示意图Fig. 1 Schematic of evolution process

SOEA算法利用了SPEA2算法的框架,与SPEA2算法不同之处有:利用子目标函数值排序,快速获得非支配解集,而不需要通过进化种群中的解之间两两比较来获得非支配解;利用归一化函数差值的Minkowski距离进行解之间的距离计算,通过“k近邻”距离来评判密度值的大小.而不是通过计算进化种群中解之间的欧氏距离.利用从外部种群中获取下一代进化的解,而不是在外部集合和进化种群中选取下一代的进化种群.

2.2.2 算法流程

2.2.3 非支配解获取

2.2.4 基于归一化Minkowski距离的“k近邻”方法

Minkowski距离计算公式为

p值较小时,对差值的影响不明显,相当于均衡考虑各个目标;当p值较大时,差值大的目标对距离的影响明显.可以看出,NSGAⅡ和SPEA2中的距离计算公式是式(2)在p取值为1和2时的特例.在高维多目标优化时,非支配解的数目增长很快,均衡的进化方法势必导致收敛到Pareto前沿的速度过慢,因此适当地增大p的取值可以加速收敛速度.本文中采用随机的p值选取方法,在[1,H]的范围内随机选取一个p值,H为某正整数,作为每一代进化的Minkowski距离计算公式中的幂次,在同一代进化中p取相同的值.

2.2.5 外部集合解的选取

1) 非支配解个数小于外部集合时解的选取.

D(i)的计算按归一化Minkowski距离的“k近邻”方法进行.

2) 非支配解个数大于外部集合时解的选取.

2.2.6 时间复杂度分析

3 测试结果与分析 3.1 测试函数及评价指标

1) 测试函数.

2) 收敛性指标[17].

G*={g1,g2,…,g|G*|}是理想的均匀分布的Pareto最优解集，Q={a1,a2,…,aQ}是通过进化算法得到的Pareto最优解集.则对于集合Q中的解ai,通过式(3)得到该解距离G*的最小欧氏距离:

IGD评价方法用于衡量所求的Pareto前沿面到真实的Pareto前沿面的收敛程度,该指标的值越小,表明算法得到的解的收敛性越好,越接近理想Pareto前端,定义为

3) 覆盖率指标C[19].

EF是优化问题的两个解集,覆盖率指标C定义为

3.2 测试结果及分析

SOEA算法在进化的过程中,并没有减少目标函数的个数,所以在进化过程中解之间的支配关系不会发生变化.求得的非支配解必定是原来的多目标优化问题的Pareto最优解,从表 1中的数据也能说明这一点.可以看出SOEA算法的IGD值比BZ算法和JC算法得到的值要小,说明SOEA算法获得的Pareto前沿与最优Pareto前沿接近程度更好.JC算法由于删除了过多的目标函数,解的支配情况与BZ算法相比改变程度会大一些,得到的IGD值也比BZ算法得到的要大.

 目标数量 BZ算法 JC算法 SOEA算法 6 0.394 6 0.479 3 0.184 3 12 0.502 5 0.625 2 0.363 8 18 0.423 7 0.384 6 0.374 1 24 0.388 2 0.402 7 0.256 9 30 0.584 9 0.601 9 0.436 2

 目标数量 C(SOEA,BZ) C(BZ,SOEA) C(SOEA,JC) C(JC,SOEA) 6 0.538 4 0.383 7 0.547 9 0.317 4 12 0.544 3 0.396 2 0.560 4 0.328 3 18 0.560 2 0.398 5 0.569 3 0.335 9 24 0.572 8 0.403 6 0.568 5 0.347 2 30 0.510 5 0.345 1 0.533 4 0.319 6

 图 2 求解DTLZ2~DTLZ7时各算法运行时间Fig. 2 DTLZ2-DTLZ7 computation time of every algorithm

 目标数量 BZ算法 JC算法 SOEA算法 6 0.148 7 0.294 2 0.138 2 12 0.364 2 0.577 5 0.154 9 18 0.405 4 0.291 2 0.236 1 24 0.506 8 0.195 6 0.362 2 30 0.313 2 0.380 3 0.285 7

 目标数量 C(SOEA,BZ) C(BZ,SOEA) C(SOEA,JC) C(JC,SOEA) 6 0.452 6 0.357 2 0.487 3 0.324 9 12 0.473 2 0.365 5 0.501 6 0.336 4 18 0.514 7 0.382 4 0.535 7 0.338 1 24 0.537 2 0.389 7 0.562 8 0.345 3 30 0.557 8 0.392 5 0.595 4 0.327 5

 目标数量 BZ算法 JC算法 SOEA算法 6 0.438 4 0.564 9 0.427 5 12 18.79 18.93 11.48 18 58.96 58.37 24.72 24 72.48 73.06 36.44 30 85.15 87.17 78.53

 目标数量 C(SOEA,BZ) C(BZ,SOEA) C(SOEA,JC) C(JC,SOEA) 6 0.568 2 0.287 5 0.597 4 0.225 6 12 0.583 4 0.292 8 0.612 7 0.228 6 18 0.597 6 0.293 9 0.638 4 0.248 3 24 0.601 4 0.295 1 0.652 8 0.246 3 30 0.632 7 0.294 9 0.657 3 0.245 9
4 结 论

1) 高维多目标优化问题Pareto非支配解x*的求取,可以通过分解为f1,f2,…,fm个子目标,并在子目标函数值排序的基础上获得,且此法获得的Pareto非支配解完备.

2) 解的适应度值求取时,在基于归一化函数差值的Minkowski距离计算方法中采用随机在[1,H]范围内选取p值的方法可以加快算法的收敛速度.

3) 将本文提出的SOEA算法与BZ、JC算法比较,得出SOEA算法在收敛性和覆盖率两个指标上均优于BZ、JC算法.运行的时效性JC算法最优,SOEA算法次之,BZ算法最差.

 [1] 孔维健,丁进良,柴天佑.高维多目标进化算法研究综述[J].控制与决策,2010,25(3):321-326.Kong W J,Ding J L,Chai T Y.Survey on large-dimensional multi-objective evolutionary algorithms[J].Control and Decision,2010,25(3):321-326(in Chinese). Cited By in Cnki (36) [2] 公茂果,焦李成,杨咚咚,等.进化多目标优化算法研究[J].软件学报,2009,20(2):271-289.Gong M G,Jiao L C,Yang D D,et al.Evolutionary multi-objective optimization algorithm[J].Journal of Software,2009,20(2):271-289(in Chinese). Cited By in Cnki (469) [3] Deb K,Pratap A,Agarwal S,et al.A fast and elitist multiobjective genetic algorithm:NSGA-II[J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197. Click to display the text [4] Zitzler E,Laumanns M,Thiele L.SPEA2:Improving the strength Pareto evolutionary algorithm,TIK-Rep103[R].Lausanne:Swiss Federal Institute of Technology,2001. Click to display the text [5] Corne D W,Jerram N R,Knowles J D,et al.PESA-Ⅱ:Region-based selection in evolutionary multi-objective optimization[C]∥Proceeding of the Genetic and Evolutionary Computation Conference,GECCO 2001.San Francisco:Morgan Kaufmann Publishers,2001:283-290. Click to display the text [6] Khare V,Yao X,Deb K.Performance scaling of multi-objective evolutionary algorithms[C]∥Proceeding of the 2nd Conference on Evolutionary Multi-Criterion Optimization,EMO 2003.Berlin:Springer-Verlag,2003:376-390. Click to display the text [7] Bandyopadhyay S,Bhattacharya R.Solving multi-objective parallel machine scheduling problem by a modified NSGA-II[J].Applied Mathematical Modelling,2013,37(10-11):6718-6729. Click to display the text [8] Saxena D K,Deb K.Non-linear dimensionality reduction procedure for certain large-dimensional multi-objective optimization problems:Employing correntropy and a novel maximum variance unfolding[C]∥Proceedings of the 4th International Conference on Evolutionary Multi-Criterion Optimization.Berlin:Springer-Verlag,2007:772-787. Click to display the text [9] Hernández-Diaz A G,Santana-Quintero L V,Coello Coello C A,et al.Pareto-adaptiveε-dominance[J].Evolutionary Computation,2007,15(4):493-517. Click to display the text [10] 刘立佳,李相民,颜骥.解决高维多目标优化的分组进化算法[J].四川大学学报,2013,45(1):118-122.Liu L J,Li X M,Yan J.Group divided dimensional reduction evolutionary algorithm for multi-objective pptimization[J].Journal of Sichuan University,2013,45(1):118-122(in Chinese). Cited By in Cnki [11] Wagner T,Beume N,Naujoks B.Pareto-,aggregation-,and indicator-based methods in many-objective optimization[C]∥Lecture Notes in Computer Science.Berlin:Springr-Verlag,2007:742-756. Cited By in Cnki (0) | Click to display the text [12] Hughes E J.Multiple single objective Pareto sampling[C]∥Congress on Evolutionary Computation (CEC03).Piscataway,NJ:IEEE Press,2003:2678-2684. Click to display the text [13] di Piero F.Many objectives evolutionary algorithms and applications to water resources engineering[D].Exeter:University of Exeter,2006. Click to display the text [14] 巩敦卫,季新芳,孙晓燕.基于集合的高维多目标优化问题的进化算法[J].电子学报,2014,42(1):77-83.Gong D W,Ji X F,Sun X Y.Solving many-objective optimization problems using set-based evolutionary algorithms[J].Acta Electronica Sinica,2014,42(1):77-83(in Chinese). Cited By in Cnki (6) [15] Brockhoff D,Zitziler E.Are all objectives necessary? On dimensionality reduction in evolutionary multi objective optimization[C]∥Parallel Problem Solving from Nature.Berlin:Springer,2006:533-542. Click to display the text [16] Brockhoff D,Zitziler E.Objective reduction in evolutionary multi objective optimization:Theory and applications[J].Evolutionary Computation,2009,17(2):135-166. Click to display the text [17] Jaimes A L,Coello C A C,Chakraborty D,et a1.Objective reduction using a feature selection technique[C]∥Proceedings of the Genetic and Evolutionary Computation Conference(GECCO 08).Atlanta:ACM Press,2008:673-680. Click to display the text [18] Deb K,Thiele L,Laumanns M,et a1.Scalable multi objective optimization test problems[C]∥Congress on Evolutionary Computation(CEC02).Piscataway,NJ:IEEE Press,2002:825-830. Click to display the text [19] Knowles J,Corne D.On metrics for comparing non-dominated sets[C]∥Proceeding of the IEEE Congress on Evolutionary Computation.Piscataway,NJ:IEEE Press,2002:711-716. Click to display the text [20] 时宝,王兴平,盖明久.泛函分析引论及其应用[M].北京:国防工业出版社,2009:104-110.Shi B,Wang X P,Gai M J.Introduction to functional analysis with application[M].Beijing:National Defense Industry Press,2009:104-110(in Chinese).

#### 文章信息

LEI Yuyao, JIANG Wenzhi, LIU Lijia, MA Xiangling

Many-objective optimization based on sub-objective evolutionary algorithm

Journal of Beijing University of Aeronautics and Astronsutics, 2015, 41(10): 1910-1917.
http://dx.doi.org/10.13700/j.bh.1001-5965.2014.0706