东北大学学报:自然科学版  2018, Vol. 39 Issue (3): 305-310  
0

引用本文 [复制中英文]

李飞, 刘建昌, 朱佳妮, 李晨曦. 基于目标空间分区的稳态高维多目标进化算法[J]. 东北大学学报:自然科学版, 2018, 39(3): 305-310.
[复制中文]
LI Fei, LIU Jian-chang, ZHU Jia-ni, LI Chen-xi. Steady-State Many-Objectives Evolutionary Algorithm Based on Objective Space Partition[J]. Journal of Northeastern University Nature Science, 2018, 39(3): 305-310. DOI: 10.12068/j.issn.1005-3026.2018.03.001.
[复制英文]

基金项目

国家自然科学基金资助项目(61773106, 61374137);流程工业综合自动化国家重点实验室基础科研业务项目(2013ZCX02-03)

作者简介

李飞(1988-), 男, 安徽太和人, 东北大学博士研究生;
刘建昌(1960-), 男, 辽宁黑山人, 东北大学教授, 博士生导师。

文章历史

收稿日期：2016-10-12
Contents              Abstract              Full text              Figures/Tables              PDF
基于目标空间分区的稳态高维多目标进化算法
李飞1, 刘建昌1, 朱佳妮1, 李晨曦2    
1. 东北大学 信息科学与工程学院, 辽宁 沈阳 110819;
 2. 南京航空航天大学 自动化学院, 江苏 南京 211106
收稿日期：2016-10-12
基金项目：国家自然科学基金资助项目(61773106, 61374137);流程工业综合自动化国家重点实验室基础科研业务项目(2013ZCX02-03)。
作者简介：李飞(1988-), 男, 安徽太和人, 东北大学博士研究生;
刘建昌(1960-), 男, 辽宁黑山人, 东北大学教授, 博士生导师。
摘要：针对高维多目标优化中Pareto非劣候选解所占比例很大, 常用的先考虑收敛性再考虑分布性的多目标进化算法面临选择压力衰减的问题, 提出一种先考虑分布性再考虑收敛性的高维多目标进化算法——基于目标空间分区的稳态高维多目标进化算法(SS-OSP).该算法先采用目标空间分区策略将种群按照权重向量分为多个子空间, 在每个子空间中按照分解方法中的聚合函数选择个体; 然后, 考虑到常规的PBI聚合函数的罚参数在进化过程中一直保持不变的情况, 提出一种自适应PBI聚合函数; 最后，仿真实验结果表明所提出的算法与其他三种算法相比, 具有更好的收敛性和分布性.
关键词：高维多目标优化问题    稳态进化算法    目标空间分区    自适应PBI聚合函数    分解策略    
Steady-State Many-Objectives Evolutionary Algorithm Based on Objective Space Partition
LI Fei1, LIU Jian-chang1, ZHU Jia-ni1, LI Chen-xi2    
1. School of Information Science & Engineering, Northeastern University, Shenyang 110819, China;
 2. College of Automation Engineering, Nanjing University of Aeronautics & Astronautics, Nanjing 211106, China
Corresponding author: LI Fei, E-mail: lanceleeneu@126.com
Abstract: Due to the sharp increasing of the proportion of Pareto non-dominated candidate solutions for many-objective optimization problems, the commonly used many-objective evolutionary algorithms encounter the selection pressure deterioration problem considering the convergence-first-and-diversity-second selection approach. This paper proposed a many-objective evolutionary algorithm with the diversity-first-and-convergence-second selection strategy-steady-state many-objective evolutionary algorithm based on objective space partition (SS-OSP). Firstly, it divided objective space into a large number of subspaces using a set of weight vectors. Then, one individual in each subspace was selected via adopting aggregation function. In addition, since the penalty parameter of PBI aggregation function remained constant in evolutionary process, an adaptive PBI aggregation function was proposed. Finally, the experimental results show that better convergence and diversity can be obtained using the proposed algorithm.
Key Words: many-objective optimization problems    steady-state evolutionary algorithm    objective space partition    adaptive PBI aggregation function    decomposition strategy    

进化算法(evolutionary algorithm, EA)是一种基于种群的随机全局搜索算法, 算法在一次运行后得到一组解, 因此被认为是适合解决多目标优化问题(multi-objective optimization problems, MOPs)的方法之一[1-2].但是当优化问题的目标大于或等于3时, 此类问题称为高维多目标优化问题(many-objective optimization problems, MaOPs), 随着维数的增加, 种群中Pareto非劣个体所占比例很大, 候选解的选择压力就会衰减, 这种现象称为“维数灾难”, 常规的多目标进化算法难以有效解决此类问题[3-4].

目前研究者已经提出了许多求解MaOPs的算法, 根据种群的选择机制, 可将这些算法分为以下三类:基于Pareto支配关系的算法[5]、基于性能指标的算法[6]和基于分解的算法[7].基于Pareto支配关系的算法通过Pareto支配关系对种群中的个体进行排序, 保留Pareto支配关系占优的个体, 淘汰Pareto支配关系差的个体.由于个体间存在非支配的关系, 通常在这类算法中还需考虑个体的密度信息, 通过Pareto支配关系促进种群收敛, 利用个体密度信息维持种群的分布度.在求解MaOPs时, 种群中的非支配个体数目所占比例急剧增加, 所以该方法不能直接应用到MaOPs中, 通常都需要修改常规的Pareto支配关系.He等[8]引入模糊逻辑理论[9], 提出一种基于模糊Pareto支配关系的高维多目标进化算法FD-NSGA-Ⅱ.基于性能指标的算法[6]最早由Zitzler等在2004年提出, 此类算法采用性能指标引导种群搜索, 可将多目标优化问题转化为单目标优化问题求解.常用的性能指标是Hypervolume指标[6]和R2指标[10].针对Hypervolume指标计算复杂度高的问题, Bader等[11]提出一种基于Hypervolume指标的快速高维多目标进化算法HypE, HypE采用蒙特卡洛采样法估计解的Hypervolume指标值.Hernandez等[10]提出一种基于R2指标的高维多目标进化算法MOMBI-Ⅱ, 并将该算法用于解决高维多目标优化问题.随着MOEA/D[7]的提出, 基于分解的多目标进化算法在求解MaOPs时得到了蓬勃的发展, 具有代表性的算法有DBEA[12]和θ-DEA[13]等.

常规多目标进化算法大都采用先考虑收敛性再考虑分布性的思想, 该思想适合求解MOPs, 但在求解MaOPs时难以选择合适的候选解逼近真实前沿.针对上述问题, 本文提出一种先考虑分布性再考虑收敛性的高维多目标进化算法——基于目标空间分区的稳态高维多目标进化算法(steady-state many-objective evolutionary algorithm based on objective space partition, SS-OSP).

1 背景知识 1.1 多目标优化

不失一般性, 以最小化问题为例, 多目标优化问题可以表示为以下的形式[1]:

(1)

其中:J和K表示不等式约束和等式约束个数; 代表决策变量空间; x={x1, x2, …, xn}表示一个候选解; F:Ω→Rm包含了m个相互冲突的目标, Rm称为目标空间.

求解多目标优化算法的主要目的是得到一组具有代表性的解集, 该解集尽可能逼近真实的Pareto前沿且分布均匀.

1.2 聚合函数

分解方法给每个个体赋予一个不同的权重向量, 通过聚合方法将多目标优化问题转化成单目标优化问题.通常有三种聚合方法可供选择[13]:

1) Weighted Sum聚合方法.Weighted Sum聚合方法的计算公式为

(2)

其中:w是权重向量且满足wi,j≥0;.

2) Tchebycheff聚合方法.Tchebycheff聚合方法的计算公式为

(3)

其中:zj*是参考点, 它的计算公式为

(4)

3) PBI聚合方法.PBI聚合方法的计算公式为

(5)

其中:;

;θ为罚参数.

2 算法实现 2.1 SS-OSP基本流程

本文提出的SS-OSP算法的伪码如图 1所示.在完成算法参数和权重向量初始化后, 算法进入迭代过程.算法采用模拟二进制交叉和多项式变异产生一个子代个体, 然后将子代个体与父代个体合并, 最后丢掉一个决策者所不偏好的候选解.

图 1 SS-OSP伪码图 Fig.1 Psedudo-code for SS-OSP
2.2 SS-OSP的选择策略

常见的高维多目标进化算法的选择策略通常是先考虑收敛性再考虑分布性.本文提出一种先考虑分布性再考虑收敛性的选择策略，如图 2所示.先将目标空间按权重向量分为多个子空间, 然后在子空间中选择个体.该策略分为三个部分:目标空间归一化、分区处理和个体选择.下面将分别介绍这三个部分.

图 2 选择操作伪码图 Fig.2 Psedudo-code for selection operator

首先对目标空间进行归一化处理, 如式(6)所示:

(6)

其中:理想点zj*可由种群中的第j个目标值的最小值得到; zjnad采用每个目标函数的最大值.

然后对种群进行分区处理.计算每个个体与所有权重向量的夹角, 找到夹角最小的权重向量, 将该个体放入该权重向量所对应的目标子空间中，如式(7)和式(8)所示:

(7)
(8)

其中:N表示权重向量的个数; θi表示与权重向量wi的夹角; Φi(x)表示个体x属于权重向量wi所在的区域.

最后从每个种群中采用分解方法选取个体.如果某个权重向量所在的区域中只有1个个体, 则直接保留这个个体; 如果某个权重向量所在的区域中的个体数目大于1, 则选择该区域内聚合函数值最小的个体; 如果某个权重向量所在区域中没有个体，则选择整个种群中聚合函数值最小的个体.

常规PBI聚合函数中, θ用来平衡收敛性和分布性, θ较小, PBI强调种群的收敛性, 会选择出收敛性较好的个体; θ较大, PBI强调种群的分布性, 会选择分布性较好的个体.在PBI聚合函数中, θ取5.0.在种群的进化前期强调收敛性而后期强调分布性, 在种群的进化过程中始终保持θ值不变显然不合理, θ应该随着迭代次数的增加而增加.因此, θ的计算公式如下:

(9)

其中:θ0=5.0;zmax表示当前种群中每个目标的最大值组成的向量; 表示向量zmax中最大值与最小值的比值; t表示当前的代数; MaxGen表示最大的代数.

图 3是上述选择策略的示意图.图中有4个权重向量w1~w4, 图 3所示的候选解中存在5个个体, 因此需要对候选解进行修剪.Φ1区域中有2个个体x1和x2, x1在权重向量w1上的聚合函数值更小, 选择x1个体; Φ2区域中只有一个个体x3, 因此直接选择x3个体.由于x2相对于x3在权重向量w2上的PBI聚合函数值更小, 若没有分区处理则会选择x2个体, 而一般认为x3个体更有利于种群在Φ2区域搜索; Φ3区域中有2个个体x4和x5, x4在权重向量w3上的聚合函数值更小, 选择x4个体; Φ4区域中没有个体, 则不选择个体.上述的候选解修剪策略有利于引导种群向权重向量靠近, 实现种群的均匀分布.

图 3 选择操作示意图 Fig.3 Schematic diagram of selection operator
3 算法测试及结果分析

为了验证SS-OSP算法性能, 选取WFG系列测试函数作为研究对象, 将SS-OSP与DBEA[12]，MOMBI-Ⅱ[10]和MOEA/D-PBI[14]进行比较.

本文采用超体积指标(hypervolume indiactor, IH)比较算法的性能, IH越大说明算法的收敛性和分布性越好.IH的计算公式如下:

(10)

其中:r是参考点, 取r=[3, 5, …, 2m+1];A是最终得到的解集.根据文献[11]中提出的方法, 采用蒙特卡洛采样方法估算得到IH指标值, 采样个数取为106.

为了保证公平性, 每种算法都进行30次独立实验.每个测试函数的迭代次数见表 1中的第二列.SS-OPS中的分布系数ηc=30, 交叉概率pc=1.0, 种群的数目与权重向量数目一样, 分别是5维问题取210个、8维问题取156个、10维问题取275个和15维问题取135个, 其他算法的参数设置参考相应的文献[10, 12, 14].表 1是4种算法在不同测试函数不同维数上的性能指标评价结果, 每个表格中的2个数分别代表性能指标的平均值和标准差.表 1中的“+”、“=”和“-”表示本文算法获得的IH值在显著性水平为5%的Wilcoxon检验中分别优于、等于和劣于对应列的对等算法在对应行的测试问题上的显著性区分结果, 并在最后一行列出了本文算法在所有测试问题上显著优于、等于和劣于其他算法的个数之和.

表 1 各算法IH性能指标的平均值和标准差 Table 1 Means and standard deviations of the IH performance indicator calculated by each algorithm

图 4和图 5分别列出了各算法在WFG6和WFG9的15维问题上得到的Pareto前沿的平行坐标图.由图可知, SS-OSP在这两个问题上得到的Pareto前沿的收敛性和分布性都比较好; DBEA在这两个问题上分布性都不好, 特别在WFG9的15维问题上出现种群聚集情况; MOMBI-Ⅱ在这两个问题分布性也都不好; 而MOEA/D-PBI在WFG6的15维问题上只能得到部分前沿, 而在WFG9的15维问题上收敛性可以接受, 但是分布性比SS-OSP差.

图 4 各算法在WFG6的15维问题上得到的Pareto前沿的平行坐标图 Fig.4 Parallel coordinates of Pareto front obtained by each algorithm on 15-objective WFG6 (a)—SS-OSP; (b)—DBEA; (c)—MOMBⅠ-Ⅱ; (d)—MOEA/D-PBI.
图 5 各算法在WFG9的15维问题上得到的Pareto前沿平行坐标图 Fig.5 Parallel coordinates of Pareto front obtained by each algorithm on 15-objective WFG9 (a)—SS-OSP; (b)—DBEA; (c)—MOMBⅠ-Ⅱ; (d)—MOEA/D-PBI.

从表 1可知, 本文提出的SS-OSP算法整体性能最好, DBEA性能次之, 而MOEA/D-PBI算法性能最差.其中DBEA在36个测试问题中, 有7个测试问题的性能好于SS-OSP, 但是有20个测试问题的性能比SS-OSP差; 而MOMBI-Ⅱ在10个问题上的性能好于SS-OSP, 但是有24个测试问题的性能比SS-OSP差; MOAE/D-PBI除了在WFG2的15维问题、WFG3的10维问题以及WFG9的15维问题上与SS-OSP性能相似外, 其他问题上的性能都比它差.此外, 从表 1中还可以得到, MOMBI-Ⅱ在WFG1~WFG3上的性能更好, 而SS-OSP和DBEA在WFG4~WFG9上的性能更好.综上所述, 通过与DBEA, MOMBI-Ⅱ和MOEA/D-PBI比较可知, 本文提出的SS-OSP是一种求解高维多目标优化问题的有效算法.

4 结论

由于高维多目标优化问题中Pareto非劣个体比例过大, 常规多目标进化算法无法选择出决策者偏好的个体, 本文提出一种先考虑分布性再考虑收敛性的基于目标空间分区的稳态高维多目标进化算法.通过目标空间分区策略提高种群的分布性; 然后在每个子空间中采用自适应的PBI聚合函数选择个体, 提高种群的收敛性.通过与其他三个高维多目标进化算法在WFG1~WFG9测试函数上的仿真结果表明, 该算法具有较好的收敛性和分布性.

参考文献
[1]
Coello C C, Lamont G B, van Veldhuizen D A. Evolutionary algorithms for solving multi-objective problems[M]. New York: Springer Science & Business Media, 2007: 1-30.
[2]
付亚平, 王洪峰, 黄敏. 面向多目标优化问题的基于Species的遗传算法[J]. 东北大学学报(自然科学版), 2016, 37(3): 314–318.
( Fu Ya-ping, Wang Hong-feng, Huang Min. Species-based genetic algorithm for multiobjective optimization problems[J]. Journal of Northeastern University(Natural Science), 2016, 37(3): 314–318. )
[3]
Li B, Li J, Tang K, et al. Many-objective evolutionary algorithms: a survey[J]. ACM Computing Surveys, 2015, 48(1): 1–35.
[4]
Giagkiozis I, Fleming P J. Methods for multi-objective optimization: an analysis[J]. Information Sciences, 2014, 293: 338–350.
[5]
Deb K, Pratap A, Agarwal S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182–197. DOI:10.1109/4235.996017
[6]
Zitzler E, Künzli S. Indicator-based selection in multiobjective search[C]// International Conference on Parallel Problem Solving from Nature. Berlin: Springer Heidelberg, 2004: 832-842.
[7]
Zhang Q, Li H. MOEA/D: a multiobjective evolutionary algorithm based on decomposition[J]. IEEE Transactions on Evolutionary Computation, 2007, 11(6): 712–731. DOI:10.1109/TEVC.2007.892759
[8]
He Z, Yen G G, Zhang J. Fuzzy-based pareto optimality for many-objective evolutionary algorithms[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(2): 269–285. DOI:10.1109/TEVC.2013.2258025
[9]
Zadeh L A. Fuzzy sets[J]. Information and Control, 1965, 8(3): 338–353. DOI:10.1016/S0019-9958(65)90241-X
[10]
Hernandez G R, Coello C C A. Improved metaheuristic based on the R2 indicator for many-objective optimization[C]// Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation. Madrid: ACM, 2015: 679-686.
[11]
Bader J, Zitzler E. HypE: an algorithm for fast hypervolume-based many-objective optimization[J]. Evolutionary Computation, 2011, 19(1): 45–76. DOI:10.1162/EVCO_a_00009
[12]
Asafuddoula M, Ray T, Sarker R. A decomposition based evolutionary algorithm for many objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2014, 19(3): 445–460.
[13]
Yuan Y, Xu H, Wang B, et al. A new dominance relation-based evolutionary algorithm for many-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2016, 20(1): 16–37. DOI:10.1109/TEVC.2015.2420112
[14]
Li K, Deb K, Zhang Q, et al. An evolutionary many-objective optimization algorithm based on dominance and decomposition[J]. IEEE Transactions on Evolutionary Computation, 2015, 19(5): 694–716. DOI:10.1109/TEVC.2014.2373386