﻿ 基于超平面投影的高维多目标进化算法
 文章快速检索 高级检索
 浙江大学学报(工学版)  2018, Vol. 52 Issue (7): 1284-1293  DOI:10.3785/j.issn.1008-973X.2018.07.008 0

### 引用本文 [复制中英文]

dx.doi.org/10.3785/j.issn.1008-973X.2018.07.008
[复制中文]
BI Xiao-jun, WANG Chao. Many-objective evolutionary algorithm based on hyperplane projection[J]. Journal of Zhejiang University(Engineering Science), 2018, 52(7): 1284-1293.
dx.doi.org/10.3785/j.issn.1008-973X.2018.07.008
[复制英文]

### 文章历史

Many-objective evolutionary algorithm based on hyperplane projection
BI Xiao-jun , WANG Chao
College of Information and Communication Engineering, Harbin Engineering University, Harbin 150001, China
Abstract: A many-objective evolutionary algorithm based on hyperplane projection (HPEA) was proposed in order to better balance between convergence and distribution in many-objective optimization problems (MaOPs). The normalization method was used to construct a unit hyperplane and the population was projected onto the unit hyperplane for removing the influence of the convergence degree of individuals. Then an improved Harmonic mean distance was used to calculate the crowding density of the projected points in the above unit hyperplane. The λ-distance was constructed to better balance between convergence and distribution of solutions by considering the convergence information. Nine standard benchmark problems with three to ten objectives were tested to demonstrate the effectiveness of the proposed algorithm. The algorithm was compared with five state-of-the-art many-objective evolutionary algorithms (MaOEAs). The experimental results show that the proposed algorithm has more advantage than other algorithms, which can ensure the uniform distribution and improve the convergence.
Key words: many-objective optimization    hyperplane projection    Harmonic mean distance    convergence information    λ-distance

1 问题描述和相关工作 1.1 高维多目标优化问题的数学描述

 $\left. \begin{array}{l} \min F\left( \mathit{\boldsymbol{x}} \right) = {f_1}[\mathit{\boldsymbol{x}}), {f_2}\left( \mathit{\boldsymbol{x}} \right), \cdots , {f_M}\left( \mathit{\boldsymbol{x}} \right){]^{\rm{T}}};\\ \mathit{\boldsymbol{x}} = {\left[ {{x_1}, {x_2}, \cdots , {x_n}} \right]^{\rm{T}}} \subset \mathit{\Omega } \subset {{\bf R}^n}. \end{array} \right\}$ (1)

 $\left. \begin{array}{l} \forall i \in \left\{ {1, 2, \cdots , M} \right\}:{f_i}\left( \mathit{\boldsymbol{x}} \right) \le {f_i}\left( \mathit{\boldsymbol{y}} \right);\\ \exists i \in \left\{ {1, 2, \cdots , M} \right\}:{f_i}\left( \mathit{\boldsymbol{x}} \right) < {f_i}\left( \mathit{\boldsymbol{y}} \right). \end{array} \right\}$ (2)

 ${\rm{PF}} = \left\{ {F\left( \mathit{\boldsymbol{x}} \right) \in {{\bf R}^m}|\mathit{\boldsymbol{x}} \in {\rm{PS}}} \right\}.$
1.2 超平面投影的相关公式

 $\begin{array}{l} \left( {{{\tilde y}_1}, {{\tilde y}_2}, \cdots , {{\tilde y}_n}} \right) = \\ \left. \begin{array}{l} \;\;\;\;\left( {{y_1} - {w_1}t, {y_2} - {w_2}t, \cdots , {y_n} - {w_n}t} \right);\\ t = \sum _{i = 1}^n{w_i}{y_i} + b/\sum _{i = 1}^nw_i^2. \end{array} \right\} \end{array}$ (3)

 $d\left( {P, H} \right) = \frac{{\left| {\sum _{i = 1}^n{w_i}{y_i} + b} \right|}}{{\sqrt {\sum _{i = 1}^nw_i^2} }}.$ (4)

 $\left. \begin{array}{l} \left( {{{\tilde y}_1}, {{\tilde y}_2}, \cdots , {{\tilde y}_n}} \right) = \left( {{y_1} - t, {y_2} - t, \cdots , {y_n} - t} \right), \\ t = \left( {\sum _{i = 1}^n{y_i} - 1} \right)/n; \end{array} \right\}$ (5)
 $d\left( {P, H} \right) = \frac{{\left| {\sum _{i = 1}^n{y_i} - 1} \right|}}{{\sqrt d }}.$ (6)
2 基于超平面投影的高维多目标进化算法HPEA

2.1 超平面投影

1) 在种群R中寻找出每一维坐标轴所对应的极端点, 第i个极端点的求解公式为

 $z_i^{{\rm{extreme}}} = \mathop {\arg \min }\limits_{\mathit{\boldsymbol{u}} \in R} \left\{ {\mathop {\max }\limits_{1 \le j \le M} \left\{ {\left( {{f_j}\left( \mathit{\boldsymbol{u}} \right) - z_j^{\min }} \right)/\mathit{\boldsymbol{w}}_j^i} \right\}} \right\}.$ (7)

2) 用zextreme构造超平面H.设超平面H的截距式为

 $\frac{{{f_1}}}{{{a_1}}} + \frac{{{f_2}}}{{{a_2}}} + \cdots + \frac{{{f_M}}}{{{a_M}}} = 1.$ (8)

3) 种群R中的每一个个体可以归一化为

 $f_i^n\left( \mathit{\boldsymbol{u}} \right) = \frac{{{f_i}\left( \mathit{\boldsymbol{u}} \right) - z_i^{\min }}}{{{a_i} - z_i^{\min }}};\mathit{\boldsymbol{u}} \in R, i = \left\{ {1, 2, \cdots , M} \right\}.$ (9)

 图 1 投影示意图 Fig. 1 Illustration of hyperplane projection

1 for each uFlIN do

2   计算代表收敛信息的d1(u)

3   if $\tilde P = \emptyset$ then

4     在$\widetilde {F_{\rm{l}}^{{\rm{IN}}}}$中计算离${\mathit{\boldsymbol{\tilde u}}}$K个最近的点组成代表分布信息的d2(u)

5   else

6    K=min(|FlIN|, |P|)

7     在${\tilde P}$中计算离${\mathit{\boldsymbol{\tilde u}}}$K个最近的点组成代表分布信息的d2(u)

8   end if

9   计算D(u)=d1(u)-λd2(u)

10 end for

11 q=arg minuFlIN(D(u))

2.4 算法总体流程

1 while termination criterion not met do

2 P'= Mating_selection(P)

3 Q= Genetic_operator (P')

4 U=PQ

5 (F1, F2, …)=Non_dominated_sort (U)

6 P=∅, i=1

7 while |PFi| < N do

8   P=PFi, i=i+1

9 end while

10 临界层Fl=Fi

11 if |PFl|=N then

12   P=PFl, break

13 else

14   ($\tilde P, \widetilde {{F_{\rm{l}}}}$)=Hyperplane_projection(P, Fl)

15   J=N-|P|, j=0

16   (FlIN, FlOUT)=Hypercube_ judgment(Fl)

17   if |FlIN| < J

18   D=min(dist(FlOUT, E))

19   Rank=sort(D)

20   P=PFlINFlOUT(Rank(1:J-|FlIN|))

21   else

22     while j < J do

23       (q, ${\tilde q}$) =λ-distance(FlIN, $\tilde P, \widetilde {F_{\rm{l}}^{{\rm{IN}}}}$)

24       P=P∪{q}, ${\tilde P}$= ${\tilde P}$∪{${\tilde q}$}

25       Fl=Fl-{q}, $\widetilde {F_{\rm{l}}^{{\rm{IN}}}} = \widetilde {F_{\rm{l}}^{{\rm{IN}}}} - \left\{ {\tilde q} \right\}$

26     end while

27   end if

28   end if

29 end while

2.5 计算复杂度分析

HPEA的算法复杂度主要集中在环境选择.设种群规模为N, 目标维数为M, 考虑最坏的情况, 即所有的个体都是互不支配的.环境选择阶段包括5个过程：合并种群的非支配排序, 计算合并种群的投影点, 计算合并种群到单位超平面的垂直距离, 计算个体拥挤密度, 选择个体.前3个过程的复杂度分别为O(MN2)、O(MN)和O(MN).虽然后两个过程每当选择完一个个体都要重复计算个体的K个近邻距离, 但是可以运用数据结构和调用规则将个体之间的距离矩阵存储起来调用减少计算量, 计算复杂度为O(N2log2N)；然后用λ-distance选择一个个体, 计算复杂度为O(N).环境选择总的计算复杂度为O(MN2)+O(N2log2N).HPEA总的计算复杂度为O(MN2)+O(N2log2N).

3 仿真实验与结果分析

3.1 算法性能评价指标

 ${\rm{IGD}}(P, {P^*}) = \frac{{{\sum _{v \in {P^*}}}d\left( {\mathit{\boldsymbol{v}}, P} \right)}}{{|{P^*}|}}.$ (13)

3.2 测试函数

3.3 实验参数设置

3.4 实验仿真与分析 3.4.1 λ参数分析

 图 3 在6个不同λ下, HPEA在5目标和10目标的全部DTLZ函数上获得的IGD平均值 Fig. 3 Average IGD values obtained by different changes in value of λ on DTLZ1-7 problems with five-and ten-objective, respectively

3.4.2 实验结果分析

HPEA与SPEA2+SDE、MOEA/D-PBI、NSGA-Ⅲ、GrEA和KnEA在IGD值上的比较统计结果如表 2所示, 分别为30次独立运行结果的平均值, 其中最好的结果用黑色加粗表示.为了比较HPEA与另外5种算法获得的平均IGD值之间差异的显著性, 采用Wilcoxon秩和检验进行两两比较, 显著性水平取0.05.表 2中, “+”、“-”、“≈”分别表示HPEA显著优于、显著劣于和无差别于另外5种算法.

SPEA2+SDE算法的整体表现与HPEA接近, 在DTLZ1、DTLZ3、DTLZ5、DTLZ6和DTLZ7上都取得了很好的效果, 特别是在DTLZ1的5、8目标、DTLZ5的3目标、DTLZ6的5目标、DTLZ7的8目标以及SDTLZ1的3目标上取得了最好的结果, 在其他测试函数上效果明显, 是一个稳定且性能比较全面的算法.

MOEA/D-PBI在DTLZ2的3目标和DTLZ5的5、8目标取得了最好的结果, 但在DTLZ4和DTLZ6上的测试结果不是很理想, 说明MOEA/D-PBI不太适合解决有偏好的函数问题.另外, 在SDTLZ1和SDTLZ2上的求解效果不佳.

NSGA-Ⅲ在DTLZ1的3、10目标、DTLZ5的10目标和DTLZ7的3目标上取得了最好的结果, 但对DTLZ6的处理效果不是很好.由于NSGA-Ⅲ需要通过极端点来构造超平面, 对曲线的收敛能力不佳.此外, 在处理SDTLZ1和SDTLZ2测试问题上, NSGA-Ⅲ表现出与HPEA相当的效果, 由此说明极端点归一化技术对不同量纲目标函数问题的有效性.

GrEA在DTLZ2和DTLZ4上都能够取得很好的效果, 但在DTLZ6上表现很差, 说明该算法不太适合处理退化函数问题.值得注意的是, GrEA在SDTLZ2的5目标上取得了最好的结果, 并且在SDTLZ1和SDTLZ2的其他目标维数上取得了很好的结果.这主要是因为GrEA将目标空间的每一维划分成相同的段数, 本质上是起到目标值归一化的作用.

KnEA在DTLZ3和DTLZ7的3、5目标、DTLZ6的3、8目标上取得了最好的结果, 在DTLZ4和SDTLZ2上取得了与HPEA相近的结果.相比之下, 在DTLZ1上的表现不太理想.

 图 4 6种算法在10目标DTLZ4测试问题上最终解集的平行坐标图 Fig. 4 Parallel coordinates of final non-dominated solutions obtained by six algorithms on ten-objective DTLZ4 instance

3.4.3 λ-distance的有效性分析

4 结语

 [1] PURSHOUSE R C, FLEMING P J. On the evolutionary optimization of many conflicting objectives[J]. IEEE Transactions on Evolutionary Computation, 2007, 11(6): 770-784. DOI:10.1109/TEVC.2007.910138 [2] 孔维健, 丁进良, 柴天佑. 高维多目标进化算法研究综述[J]. 控制与决策, 2010, 25(3): 321-326. KONG Wei-jian, DING Jin-liang, CHAI Tian-you. Survey on large-dimensional multi-objective evolutionary algorithms[J]. Control and Decision, 2010, 25(3): 321-326. [3] 巩敦卫, 季新芳, 孙晓燕. 基于集合的高维多目标优化问题的进化算法[J]. 电子学报, 2014, 42(1): 77-83. GONG Dun-wei, JI Xin-fang, SUN Xiao-yan. Solving many-objective optimization problems using set-based evolutionary algorithms[J]. Acta Electronica Sinica, 2014, 42(1): 77-83. [4] 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 [5] ZITZLER E, LAUMANNS M, THIELE L. SPEA2: improving the strength Pareto evolutionary algorithm[R]. Swiss: Technical Report Gloriastrass, 2001. http://ci.nii.ac.jp/naid/10017663175 [6] CORNE D W, JERRAM N R, KNOWLES J D, et al. PESA-Ⅱ: region-based selection in evolutionary multiobjective optimization[C]//Proceedings of the 3rd Annual Conference on Genetic and Evolutionary Computation. San Francisco: Morgan Kaufmann, 2001: 283-290. http://dl.acm.org/citation.cfm?id=2955289 [7] 陈小红, 李霞, 王娜. 高维多目标优化中基于稀疏特征选择的目标降维方法[J]. 电子学报, 2015, 43(7): 1300-1307. CHEN Xiao-hong, LI Xia, WANG Na. Objective reduction with sparse feature selection for many objective optimization problem[J]. Acta Electronica Sinica, 2015, 43(7): 1300-1307. [8] 过晓芳, 王宇平, 代才. 新的混合分解高维多目标进化算法[J]. 浙江大学学报:工学版, 2016, 50(7): 1313-1321. GUO Xiao-fang, WANG Yu-ping, DAI Cai. New hybrid decomposition many-objective evolutionary algorithm[J]. Journal of Zhejiang University:Engineering Science, 2016, 50(7): 1313-1321. [9] ISHIBUCHI H, TSUKAMOTO N, NOJIMA Y. Evolutionary many-objective optimization: a short review[C]//IEEE World Congress on Computational Intelligence. Hongkong: IEEE, 2008: 2419-2426. [10] 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 [11] SATO H, AGUIRRE H E, TANAKA K. Controlling dominance area of solutions and its impact on the performance of MOEAs[M]//Evolutionary multi-criterion optimization. Berlin: Springer, 2007: 690-702. http://link.springer.com/10.1007/978-3-540-70928-2_5 [12] YANG Sheng-xiang. A grid-based evolutionary algorithm for many-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2013, 17(5): 721-736. DOI:10.1109/TEVC.2012.2227145 [13] HE Zhe-nan, YEN G G, ZHANG Jun. 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 [14] HORN J, NAFPLIOTIS N, GOLDBERG D E. A niched Pareto genetic algorithm for multiobjective optimization[C]//IEEE World Congress on Computational Intelligence. Orlando: IEEE, 1994: 82-87. http://www.researchgate.net/publication/2631294_A_Niched_Pareto_Genetic_Algorithm_for_Multiobjective_Optimization?citationList=outgoing [15] 郑金华, 申瑞珉, 李密青, 等. 一种基于信息分离的高维多目标进化算法[J]. 软件学报, 2015, 26(5): 1013-1036. ZHENG Jin-hua, SHEN Rui-min, LI Mi-qing, et al. Evolutionary algorithm based on information separation for many-objective optimization[J]. Journal of Software, 2015, 26(5): 1013-1036. [16] DEB K, JAIN H. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, Part Ⅰ:solving problems with box constraints[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(4): 577-601. DOI:10.1109/TEVC.2013.2281535 [17] LI Mi-qing, YANG Sheng-xiang, LIU Xiao-hui. Shift-based density estimation for Pareto-based algorithms in many-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(3): 348-365. DOI:10.1109/TEVC.2013.2262178 [18] ZHANG Xing-yi, TIAN Ye, JIN Y C. A knee point-driven evolutionary algorithm for many-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2015, 19(6): 761-776. DOI:10.1109/TEVC.2014.2378512 [19] 毕晓君, 张永建, 陈春雨. 基于模糊支配的高维多目标进化算法MFEA[J]. 电子学报, 2014, 42(8): 1653-1659. BI Xiao-Jun, ZHANG Yong-jian, CHEN Chun-yu. A many-objective evolutionary algorithm based on fuzzy dominance:MFEA[J]. Acta Electronica Sinica, 2014, 42(8): 1653-1659. [20] ZHANG Qing-fu, LI Hui. 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 [21] DEB K, THIELE L, LAUMANNS M, et al. Scalable test problems for evolutionary multiobjective optimization[M]//Evolutionary multiobjective optimization. London: Springer, 2005: 105-145. http://www.springerlink.com/index/q404757t4q25m64l.pdf [22] ZITZLER E, THIELE L, LAUMANNS M, et al. Performance assessment of multiobjective optimizers:an analysis and review[J]. IEEE Transactions on Evolutionary Computation, 2003, 7(2): 117-132. DOI:10.1109/TEVC.2003.810758