第41 卷第8 期自动化学报Vol. 41, No. 82015 年8 月ACTA AUTOMATICA SINICA August, 2015基于目标分解的高维多目标并行进化优化方法巩敦卫1; 2 刘益萍1 孙晓燕1 韩玉艳1摘要高维多目标优化问题普遍存在且难以解决, 到目前为止, 尚缺乏有效解决该问题的进化优化方法. 本文提出一种基于目标分解的高维多目标并行进化优化方法, 首先, 将高维多目标优化问题分解为若干子优化问题, 每一子优化问题除了包含原优化问题的少数目标函数之外, 还具有由其他目标函数聚合成的一个目标函数, 以降低问题求解的难度; 其次, 采用多种群并行进化算法, 求解分解后的每一子优化问题, 并在求解过程中, 充分利用其他子种群的信息, 以提高Pareto 非被占优解的选择压力; 最后, 基于各子种群的非被占优解形成外部保存集, 从而得到高维多目标优化问题的Pareto 最优解集. 性能分析表明, 本文提出的方法具有较小的计算复杂度. 将所提方法应用于多个基准优化问题, 并与NSGA-II、PPD-MOEA、"-MOEA、HypE 和MSOPS 等方法比较, 实验结果表明, 所提方法能够产生收敛性、分布性, 以及延展性优越的Pareto 最优解集.关键词进化优化, 高维多目标优化, 分解, 并行, Pareto 占优引用格式巩敦卫, 刘益萍, 孙晓燕, 韩玉艳. 基于目标分解的高维多目标并行进化优化方法. 自动化学报, 2015, 41(8):1438¡1451DOI 10.16383/j.aas.2015.c140832Parallel Many-objective Evolutionary Optimization UsingObjectives DecompositionGONG Dun-Wei1; 2 LIU Yi-Ping1 SUN Xiao-Yan1 HAN Yu-Yan1Abstract Many-objective optimization problem is common in real-world applications, however, so far few evolutionaryalgorithms are suitable for them due to the di±culties of the problem. A parallel many-objective evolutionary optimizationalgorithm based on objectives decomposition is proposed. First, the many-objective optimization problem is decomposedinto several sub-problems, which contain only some objectives of the original optimization problem together with aconstructed objective by aggregating all the other objectives. Then, a multi-population parallel evolutionary algorithm isadopted to solve these sub-problems. The pressure on selecting non-dominated solutions for a sub-problem is improvedby taking full advantage of the information obtained from other sub-populations. The ¯nal Pareto set of the optimizedmany-objective is achieved by archiving those sets of non-dominated solutions coming from the sub-populations. Theperformance of the proposed algorithm on reducing computation complexity is qualitatively analyzed. Furthermore, thealgorithm is applied to several benchmark problems and compared with NSGA-II, PPD-MOEA, "-MOEA, HypE, andMSOPS. The results experimentally demonstrate that the algorithm is strengthened in obtaining solutions with betterconvergence, distribution and approximation.Key words Evolutionary algorithm, many-objective optimization, decomposition, parallel, Pareto dominationCitation Gong Dun-Wei, Liu Yi-Ping, Sun Xiao-Yan, Han Yu-Yan. Parallel many-objective evolutionary optimizationusing objectives decomposition. Acta Automatica Sinica, 2015, 41(8): 1438¡1451在现实生活中, 存在很多包含多个目标的优化收稿日期2014-12-01 录用日期2015-04-08Manuscript received December 1, 2014; accepted April 8, 2015国家重点基础研究发展计划(973 计划) (2014CB046306-2), 国家自然科学基金(61375067), 江苏省自然科学基金(BK2012566) 资助Supported by National Basic Research Program of China (973Program) (2014CB046306-2), National Natural Science Founda-tion of China (61375067), and Natural Science Foundation ofJiangsu Province (BK2012566)本文责任编委沈轶Recommended by Associate Editor SHEN Yi1. 中国矿业大学信息与电气工程学院徐州221116 2. 兰州理工大学电气工程与信息工程学院兰州7300501. School of Information and Electronic Engineering, ChinaUniversity of Mining and Technology, Xuzhou 221116 2. Col-lege of Electrical and Information Engineering, Lanzhou Univer-sity of Technology, Lanzhou 730050问题, 如控制器设计[1]、电能调度[2]、半导体制造[3]等. 其共同点在于, 它们不仅包含多个目标, 而且这些目标之间是相互冲突的, 即不能找到一个解, 使其在所有目标上都达到最优, 这类优化问题通常称为多目标优化问题. 如果一个优化问题包含四个及以上目标, 那么, 该问题就称为高维多目标优化问题.不失一般性, 本文考虑如下多目标优化问题:minf (x) = (f1 (x) ; f2 (x) ; ¢ ¢ ¢ ; fm (x))s:t: x 2 S ½ Rn (1)式中, x 为n 维决策向量, S 为x 的可行域, fi (x),i = 1; 2; 3; ¢ ¢ ¢ ; m; 为第i 个目标函数, m 为目标函8 期巩敦卫等: 基于目标分解的高维多目标并行进化优化方法1439数个数, 当m ¸ 4 时, 该问题是一个高维多目标优化问题. 作为典型的多目标进化优化方法(Multi-obj-ective evolutionary algorithm, MOEA), NSGA-II[4]、SPEA2[5] 等已成功地应用于大量多目标优化问题. 但是, 它们都基于Pareto 占优关系进行个体比较, 因此, 仅适用于包含较少目标的优化问题.实际的优化问题可能涉及高维多目标, 如果仍然基于已有的Pareto 占优关系比较个体, 那么, 上述方法的应用效果将很差. 这是因为随着目标函数的增多, 种群中非被占优个体的数量将指数增加, 从而降低了Pareto 最优解选择的压力.为了将上述方法应用于高维多目标优化问题,目前主要有三类途径: 1) 通过目标函数缩减[6¡7], 删除优化问题中冗余的目标函数, 将高维多目标优化问题转化为传统的多目标优化问题. 但是, 该方法仅适用于优化问题存在冗余目标函数的情况. 2) 改进密度估计策略[8¡9], 减少远离Pareto 前沿的非被占优解数量, 提高算法的收敛性能. 但是, 该方法可能导致解集多样性降低. 3) 修改已有的Pareto 占优关系[10¡13], 使得个体之间能够相互比较, 以提高Pareto 最优解的选择压力. 但是, 该方法往往难以得到完整的Pareto 前沿. 例如, 基于Pareto 局部占优的MOEA[10¡11] 仅采用优化问题的部分目标函数, 计算进化个体的Pareto 序值. 由于无法权衡所有的目标函数, 使得得到的优化解并非都是问题的全局最优解. 因此, 寻求更为有效的方法, 解决高维多目标优化问题, 是十分有意义的.采用进化优化方法求解高维多目标优化问题时,为了比较不同个体的性能, 需要计算该个体的所有目标函数值, 并对这些个体进行Pareto 占优排序,这往往需要消耗很长的时间. 多种群并行进化算法采用多个子种群协同进化, 以求解复杂的优化问题,能够大大提高问题求解的速度. 如果采用多种群并行进化算法, 求解高维多目标优化问题时, 每一子种群优化不同的少量目标函数, 并基于Pareto 局部占优, 比较子种群中进化个体的性能, 那么将无疑能够提高优化问题求解的效率.鉴于此, 本文提出一种基于目标分解的高维多目标并行进化优化方法, 主要思想是: 基于相关关系将优化问题的目标函数分为若干组, 并在每组目标中加入一个聚合目标, 形成若干子优化问题; 在并行环境下, 采用多种群并行进化算法求解转化后的优化问题时, 每一子种群通过进化求解一个子优化问题, 并在求解过程中, 利用其他子种群的优势个体;基于所有子种群产生的非被占优个体, 采用新的保存集形成策略, 构建优化问题的Pareto 最优解集.本文方法的创新之处在于: 1) 将高维多目标优化问题转化为若干个目标函数更少的多目标优化(子) 问题, 从而易于采用传统的多目标进化优化方法求解; 2) 基于Spearman 相关系数对目标函数分组, 保证了同一组的目标函数具有较高的相似度, 为子优化问题的高效求解提供了保障; 3) 在每一子问题中加入了聚合目标, 以融入全局优化信息, 有利于寻找优化问题的全局最优解; 4) 对于每组目标函数形成的子优化问题, 通过多种群并行进化算法的一个子种群, 在同构并行环境的一个进程上进化, 提高了问题求解的速度; 5) 采用改进的外部保存集形成策略, 基于各子种群的最优个体, 在一个新的进程上形成外部保存集, 保证了优化问题Pareto 最优解集的逼近与分布性能.本文的结构安排如下: 第1 节综述相关工作; 提出的方法在第2 节详细阐述; 第3 节是所提方法在多个基准优化问题中的应用及对比实验; 最后, 第4节总结全文, 并指出需要进一步研究的问题.1 相关工作1.1 高维多目标进化优化作为一种特殊的多目标优化问题, 高维多目标优化问题的目标函数通常不少于4 个. 若仍采用基于Pareto 占优的MOEA 求解该类问题, 其求解效率往往很低, 甚至难以得到问题的最优解. 引言中所述的三类改进方法, 使得基于Pareto 占优的MOEA能够求解高维多目标优化问题. 除此之外, 还存在如下三类非Pareto 占优方法: 1) 基于优化问题的所有目标, 计算新指标的值, 评价个体的性能, 如IBEA[14]、HypE[15] 等; 2) 采用目标聚合方法, 将高维多目标优化问题转化为若干单目标优化问题, 并行搜索Pareto 最优解, 如MSOPS[16]、MOEA/D[17]等; 3) 采用集合进化优化方法, 求解高维多目标优化问题, 如文献[18] 和文献[19] 中提出的方法.在上述方法中, Sato 等[10] 提出的基于Pareto局部占优的多目标进化算法(PPD-MOEA), 仅利用部分目标函数比较个体的性能, 从而提高了Pareto最优解的选择压力. 在PPD-MOEA 中, 算法以NSGA-II 为框架, 采用Pareto 局部占优关系, 代替传统的Pareto 占优关系, 对个体进行占优等级排序;在进化过程中, 通过不断变化这些部分目标, 使得所有目标都能够被优化; 此外, 基于占优区域控制, 更新外部保存集, 以提高Pareto 最优解集的性能.Jaimes 等[11] 也基于Pareto 局部占优关系, 比较候选解的性能. 但是, 他们选择部分目标时, 基于目标函数之间的线性相关关系. 实验结果表明, 基于线性相关关系选择部分目标, 比随机选择部分目标取得了更好的优化结果.但是, 基于Pareto 局部占优关系, 得到的最优1440 自动化学报41 卷解难以合理权衡所有目标函数. 这是因为, 采用上述方法得到的非被占优解往往不是全局占优的; 尽管全局占优解一定是局部占优解, 但是, 局部占优解却不一定是全局占优解.为了克服上述缺陷, 本文通过目标聚合, 在已选择的部分目标中加入一个新的目标, 该目标融合了其余未选择目标的信息, 从而采用Pareto 局部占优关系比较个体性能时, 能够权衡所有目标.1.2 多种群并行进化优化所谓多种群并行进化优化, 是指多个子种群并行进化, 以求解某一优化问题. 该方法将整个种群分为多个子种群, 且每个子种群独立进化; 在子种群进化过程中, 通过迁徙算子引入其他子种群的优势个体, 以提高子种群的性能. 可以采用多种方式迁徙子种群之间的个体, 常用的方式包括: 1) 完全迁徙, 每个子种群的优势个体迁徙到所有其他子种群; 2) 环状迁徙, 所有子种群形成一个环, 每个子种群的优势个体仅迁徙到环中相邻的两个子种群; 3) 星形迁徙,以一个子种群作为中心, 连接其他所有子种群, 中心子种群的优势个体能够迁徙到所有其他子种群, 而其他子种群的优势个体仅能迁徙到中心子种群.已有研究表明, 采用多种群并行进化优化方法求解多目标优化问题, 能够提高问题求解的效率[20¡21]. 但是, 目前尚没有用于求解高维多目标优化问题的多种群并行进化优化方法. 本文针对分解后每一子优化问题, 采用一个子种群进化求解, 使得不同子种群朝着不同的方向进化, 能够很好地求解高维多目标优化问题.2 提出的方法2.1 总体框架本文提出一种基于目标分解的高维多目标并行进化优化方法, 其总体框架如图1 所示.首先, 将高维多目标优化问题分解为若干(K个) 子问题, 每一子问题仅包含原问题的部分目标以及一个聚合目标, 且这些部分目标之间具有较大的相关性, 从而显著降低优化问题的求解难度; 其次, 在并行环境下, 采用基于传统Pareto 占优的MOEA 求解每一子问题, 并通过迁徙算子, 充分利用其他子种群提供的有价值的信息, 使得问题求解的效率大大提高; 最后, 基于各子种群产生的非被占优解形成外部保存集, 使得高维多目标优化问题的Pareto 最优解集具有优越的性能.容易看出, 高维多目标优化问题的分解、子优化问题的并行求解以及外部保存集的形成等, 是本文需要解决的关键技术. 在后续的3 个小节中, 将详细阐述这些关键技术.2.2 高维多目标优化问题的分解本节通过目标分组与聚合方法, 将式(1) 表示的图1 总体框架Fig. 1 General framework8 期巩敦卫等: 基于目标分解的高维多目标并行进化优化方法1441高维多目标优化问题分解为若干子问题, 其中, 每一子优化问题包含较少的目标函数, 在这些目标函数中, 有的是原优化问题的目标函数, 有的是原优化问题若干目标函数的聚合.2.2.1 目标分组为了求解式(1) 描述的高维多目标优化问题, 本文基于目标函数之间的相关关系, 将该问题的目标函数分组. 在之前的研究中[6¡7], 目标函数之间的相关关系也被用来删除冗余的目标函数, 以缩减目标函数个数. 但是, 实际的优化问题很少具有冗余的目标函数. 如果删除相关程度较高的目标函数, 将难以得到完整的Pareto 前沿. 因此, 本文保留所有的目标函数, 并将其分组. 进一步, 基于该分组, 将高维多目标优化问题分解为若干个传统的多目标优化问题, 从而降低问题求解的难度, 使得采用传统的多目标进化优化方法求解这些分解后的问题成为可能.若两个目标函数之间的相关关系为负, 且一个目标函数减小, 那么, 另一个目标函数会增大; 反之,若两个目标函数之间的相关关系为正, 那么, 它们会同时增加或减小. 这样一来, 如果一个候选解对某一目标函数是较优的, 那么, 该候选解对与之相似的目标函数也具有较优的性能. 因此, 求解目标函数之间相关程度较高的优化问题时, 算法将更容易找到同时对这些目标函数较优的折中解, 从而具有更佳的收敛性能. 鉴于此, 本文基于目标函数之间的相关关系, 将相关程度较高的目标函数分为一组, 对于提高问题求解的效率, 是非常有意义的.为了按照相关关系对目标函数分组, 需要计算这些目标函数之间的相关程度. 本文通过计算目标函数之间的Spearman 相关系数, 以反映这些目标函数之间的相关程度. Spearman 相关系数又称为秩相关系数, 它利用两个变量的秩次值, 进行相关关系分析, 对变量的形式及其满足的分布没有任何要求.鉴于本文研究的优化问题, 包含的目标函数可能是非连续或者非线性的, 采集到的样本也可能不服从正态分布, 因此, 采用Spearman 相关系数进行相关关系分析是完全可行的. 记目标函数fi 与fj 之间的Spearman 相关系数为½ij . ½ij 的计算方法可参阅文献[22]. 可知, ½ij 2 [¡1; 1], 且½ij 越大, 目标函数fi 和fj 之间的相关程度就越大.本文期望采用同构的并行环境, 求解分解后的若干多目标优化问题. 为了提高问题求解的效率, 希望并行环境的每一同构计算节点的负荷大体相同,这样一来, 将目标函数均分是十分必要的. 本文将目标函数分为K 组, 那么, 每组目标函数的个数不超过dm=Ke. 组数K 根据优化问题包含的目标函数个数以及可用的计算资源确定. 一般来讲, K 的取值应使得每组包含的目标函数个数小于或等于3.为了得到合理的目标函数分组, 需要采用一定的准则, 对分组结果进行评价. 本文借鉴文献[23]的方法, 首先, 计算组内目标函数相关系数的平均值p(Gk), k = 1; 2; ¢ ¢ ¢ ;K; 然后, 对所有组求取上述指标的平均值, 记为p, 用于反映分组结果的性能:p =1KXKk=1p(Gk) (2)p(Gk) =8>><>>:Pfi;fj2Gk½ijmk ¡ 1 ; mk ¸ 21; mk = 1(3)式中, Gk 表示由第k 组目标函数形成的集合, mk为组Gk 包含的目标函数个数. 由式(2) 和式(3) 可知, p 越大, 组内目标函数之间的相似程度越高, 从而分组性能越好.基于上述准则, 本文提出的目标函数分组方法的步骤如下:步骤1. 将目标函数随机分为K 组, 且每组包含的目标函数个数不超过dm=Ke, 令迭代次数q =0, 计算p(q).步骤2. 判断分组终止准则(本文设终止准则为q ¸ m3) 是否满足, 若满足, 转步骤5.步骤3. 随机选择两组, 如果这两组包含的目标函数均为dm=Ke 个, 那么, 从每组中随机选择一个进行交换; 如果只有一组包含dm=Ke 个目标函数,那么, 从该组中随机选择一个, 放入另一组中; 否则,从一组中随机选择一个目标, 放入另一组.步骤4. 令q = q + 1, 计算p(q), 如果p(q) >p(q ¡ 1), 那么, 更新分组结果, 转步骤2.步骤5. 输出分组结果, 终止算法.根据上述分组方法, 式(1) 描述的高维多目标优化问题的目标函数可以分成如下K 组:G1 = ff11(x); f12(x); ¢ ¢ ¢ ; f1m1(x)gG2 = ff21(x); f22(x); ¢ ¢ ¢ ; f2m2(x)g...GK = ffK1(x); fK2(x); ¢ ¢ ¢ ; fKmK(x)g (4)式中, fkh(x), k = 1; 2; ¢ ¢ ¢ ;K, h = 1; 2; ¢ ¢ ¢ ;mk;为组Gk 包含的第h 个目标函数; mk 为组Gk 包含的目标函数个数, 且满足PKk=1mk = m, mk ·dm/Ke.2.2.2 子优化问题的形成基于式(4) 中每组的目标函数, 可以形成一个传统的多目标优化问题, 其中, 每一多目标优化问题1442 自动化学报41 卷均为原高维多目标优化问题的子问题. 但是, 如果通过求解这些子优化问题, 得到原优化问题的最优解,那么, 这些最优解很可能是原优化问题的局部最优解, 而很难成为该优化问题的全局最优解. 这是因为, 每一子优化问题, 仅考虑了原优化问题的少部分目标函数. 为了得到原优化问题的全局最优解, 需要在每一子优化问题中, 增加反映其他目标函数信息的目标函数, 称之为这些目标函数的聚合目标.对于组Gk 包含的目标函数, 在形成的子优化问题中, 引入聚合目标, 记为fk0(x), 其表达式为fk0(x) = F(G1; ¢ ¢ ¢ ;Gk¡1;Gk+1; ¢ ¢ ¢ ;GK);k = 1; 2; ¢ ¢ ¢ ;K (5)由式(5) 可以看出, fk0(x) 是由除本组包含的目标函数之外, 其余目标函数聚合而成的新的目标函数,因此, 它包含了这些目标函数的信息. 这样一来, 根据式(4) 中组Gk 包含的目标函数以及聚合目标fk0(x), 可以形成一个新的多目标优化问题, 从而式(1) 描述的高维多目标优化问题可以分解为如下K个子问题:8><>:minfG1 (x) =(f10 (x) ; f11 (x) ; f12 (x) ; ¢ ¢ ¢ ; f1m1 (x))s:t: x 2 S ½ Rn8><>:minfG2 (x) =(f20 (x) ; f21 (x) ; f22 (x) ; ¢ ¢ ¢ ; f2m2 (x))s:t: x 2 S ½ Rn...8><>:minfGK (x) =(fK0 (x) ; fK1 (x) ; fK2 (x) ; ¢ ¢ ¢ ; fKmK (x))s:t: x 2 S ½ Rn(6)求解式(6) 中的每一子优化问题时, 既可以同时优化原优化问题的少数目标函数, 又因为聚合目标的存在, 可以对原优化问题的其他目标函数进行优化, 从而平衡了原优化问题的所有目标函数. 此外, 由于子优化问题目标函数的减少, 使得问题的求解难度显著降低, 从而Pareto 最优解的选择压力大大提高, 这有利于问题的高效求解.由式(6) 可以看出, fk0(x) 对于每一子优化问题的形成与求解是非常关键的. 尽管式(5) 给出了fk0(x) 的形式表达式, 但是, 采用不同的方法, 可以得到fk0(x) 不同的表达形式. 例如, 可以将其余目标函数进行算术运算, 从而聚合为一个目标函数; 也可以基于这些目标函数, 得到候选解在每组目标空间上的Pareto 序值, 并对这些序值进行算术运算,作为该候选解的聚合目标值; 还可以计算候选解在其余目标空间上的超体积贡献度, 作为该候选解的聚合目标值, 等等. 容易知道, 虽然这些方法都能够反映候选解针对其余目标函数的优劣, 但是, 不同方法的计算复杂度是不同的. 鉴于后两种方法的计算复杂度较高, 因此, 本文采用第一种方法计算候选解的聚合目标值, 其表达式为fk0(x) =vuutXKg=1;g6=kXmgh=1(!ghfgh (x))2;k = 1; 2; ¢ ¢ ¢ ;K (7)其中, !gh 为目标函数fgh 的权重系数, 其取值可以根据该目标的重要程度确定. 本文假定每个目标函数都是同等重要的, 那么, 所有的!gh = 1=(m ¡mk); 其中, g = 1; ¢ ¢ ¢ ; k¡1; k+1; ¢ ¢ ¢ ;K; h = 1; 2,¢ ¢ ¢ , mg. 可以看出, 式(7) 反映了在其他子目标空间中, 候选解x 的目标函数值形成的向量到原点的欧氏距离. 采用式(7) 计算候选解的聚合目标值, 不但需要的计算量小, 而且对候选解的区分能力也强.2.3 子优化问题的并行求解为了高效求解式(1) 描述的高维多目标优化问题, 基于第2.2 节建立的K 个子优化问题, 本节通过多种群并行进化优化方法, 采用NSGA-II[4] 求解每一子问题, 并在求解过程中充分利用其他子种群提供的有价值信息.针对每一子优化问题, 采用一个子种群进化. 尽管在多种群并行进化算法中, 不同的子种群可以具有不同的规模, 但是, 由于本文分解后的不同子优化问题, 包含的目标函数个数大体相当, 使得优化不同子问题所需的计算量大体相同, 因此, 这里优化不同子问题的子种群规模均为np. 这样一来, 用于求解本文问题的子种群共有K 个, 这些子种群的规模之和为N = npK. 鉴于每一子优化问题包含的目标函数比较少, 因此, 针对每一子种群中的不同进化个体, 可以采用传统的Pareto 占优关系, 比较它们的性能. 此外, 由于不同子种群优化的目标函数不同,因此, 不同子种群的进化方向不同, 这有利于整个种群保持良好的多样性.在子种群进化求解过程中, 为了利用其他子种群提供的有价值信息, 需要在这些子种群之间迁徙部分进化个体. 进化个体迁徙时, 采用完全迁徙的方式, 迁徙间隔代数为Tm, 迁徙率为® 2 (0; 1). 这样一来, 每隔进化代数Tm, 每一子种群需要选择d®npe 个优势个体作为迁徙个体, 并发送给其他子种群.8 期巩敦卫等: 基于目标分解的高维多目标并行进化优化方法1443通常, 我们希望选择的迁徙个体具有较好的性能, 为了评价迁徙个体的性能, 与NSGA-II 评价进化个体的方式一样, 也采用如下两个指标: 1) Pareto序值, 通过Pareto 占优关系, 计算某迁徙个体的Pareto 序值, 用于评价该个体的逼近性能; 2) 拥挤距离, 基于NSGA-II 提出的方法, 计算迁徙个体的拥挤距离, 用于衡量该个体的分布性能. 每一子种群选择迁徙个体的具体步骤本文不再赘述, 详细可参阅文献[4]. 基于该方法选择的d®npe 个迁徙个体,不但具有很好的逼近性能, 而且具有很好的分布性能, 这有利于其他子种群的进化.鉴于不同子种群优化的目标函数不同, 因此, 一个子种群的优势个体, 对其他子种群而言, 未必也是优势个体. 这表明, 虽然某一子种群接收了其他子种群发送的优势个体, 该子种群也需要基于优化的子问题, 对这些发送的优势个体重新评价其性能. 进一步, 由于某一子种群接收了(K ¡ 1)d®npe 个迁徙个体, 而该子种群的规模np 却是固定不变的, 因此, 需要对该子种群的当代个体以及接收的迁徙个体, 基于Pareto 序值和拥挤距离重新排序, 以生成规模为np 的子代种群.2.4 外部保存集的形成在多种群进化优化中, 采用外部保存集, 保留各子种群进化过程中的优势个体, 对于保证Pareto 最优解集的完备性与多样性, 是非常必要的. 对于本文的基于目标分解的高维多目标并行进化优化方法而言, 也是如此. 一般地, 与通过合并各子种群的Pareto 最优解集, 形成优化问题的Pareto 最优解集相比, 外部保存集的Pareto 最优解集, 具有更好的分布性能. 这是因为, 在高维空间上均匀分布的点集, 在低维子空间上也是均匀分布的, 但反之不然.由于本文方法各子种群的Pareto 最优解集, 都是在低维目标空间上得到的, 尽管这些解集中的解, 在低维目标空间上均匀分布, 但是, 它们在高维目标空间上却不一定是均匀分布的. 这样一来, 基于各子种群的Pareto 最优解集, 在高维目标空间中, 按照一定的策略选择, 以形成外部保存集, 能够保证Pareto最优解集具有好的分布性能.然而, 基于各子种群的Pareto 最优解集形成保存集时, 难以基于这些解关于所有目标的Pareto 序值, 得到逼近性能好的解. 这是因为, 需要优化的目标函数增多, 使得这些解的Pareto 序值几乎相同.因此, 本节提出一种能够兼顾逼近与分布性能的外部保存集形成策略.尽管在高维目标空间中, 难以区分上述解的逼近性能, 但是, 对于来自同一子种群的Pareto 最优解而言, 由于需要优化的目标函数较少, 因此, 基于这些解在子种群中的Pareto 序值, 仍然能够得到具有好的逼近性能的外部保存集. 记第t 代的外部保存集为At = [Kk=1Atk, 其中, Atk, k = 1; 2; ¢ ¢ ¢ ;K;表示Atk 中来自第k 个子种群的Pareto 最优解集,jAtj · N. 将Atk 中的解与第k 个子种群当前代的Pareto 最优解集Ptk 合并, 得到Ctk = Atk [ Ptk. 基于第k 个子优化问题的目标函数, 计算Ctk 中解的Pareto 序值, 选择Pareto 序值为1 的解, 形成一个新的集合, 记为Ctk0. 考虑所有子优化问题, 将Ctk0,k = 1, 2, ¢ ¢ ¢ ;K 合并, 可以得到Ct = [Kk=1Ctk0, 那么, Ct 中的解对于所有的优化目标, 将具有好的逼近性能.为了使得下一代外部保存集At+1 中的解具有好的分布性能, 当jCtj > N 时, 在高维目标空间中,基于拥挤距离, 从Ct 中选择N 个解, 得到下一代外部保存集At+1. 如果jCtj · N, 那么, Ct 即为下一代外部保存集.通过上述方式形成的保存集, 不但具有好的逼近性能, 也具有好的分布性能, 这有利于寻找问题的Pareto 最优解集.2.5 算法步骤本文提出的基于目标分解的高维多目标进化优化方法的步骤如下:步骤1. 采用第2.2 节的方法, 将高维多目标优化问题分解为K 个子问题;步骤2. 设定算法所需参数的值, 初始化K 个子种群, 令t = 0, At = ;;步骤3. 得到子种群的Pareto 最优解集, 并发送至外部保存集;步骤4. 采用第2.4 节的方法, 形成外部保存集;步骤5. 判断是否满足终止条件, 若是, 转步骤9;步骤6. 判断是否满足迁徙条件, 若否, 转步骤8;步骤7. 采用第2.3 节的方法, 迁徙个体;步骤8. 子种群进化, 形成子代个体, 令t = t +1, 转步骤3;步骤9. 基于外部保存集, 得到Pareto 最优解集并输出, 算法终止.2.6 性能分析本文方法主要分为三个部分: 问题分解、子问题的并行求解以及外部保存集的形成.在问题分解时, 计算目标函数之间Spearman相关系数的计算复杂度为O(2mL2), 目标函数分组所需的计算复杂度为O(m3).在并行求解子问题时, 每个子种群均采用NSGA-II 求解一个子优化问题. NSGA-II 每进化1444 自动化学报41 卷一代的计算复杂度为O(m(2N)2). 本文方法所有子种群每代迁徙个体和生成新种群所需的计算复杂度为O(m((® + 1=K)2 + (2=K)2)N2). 由于® 2(0; 1), K ¸ 2, 因此, m((®+(1=K))2 +(2=K)2)N2< m(2N)2, O(m((® + (1=K))2 + (2=K)2)N2) <O(m(2N)2). 这表明, 本文方法的子种群每进化一代, 需要的总的计算复杂度小于NSGA-II; 此外, 迁徙率® 越小且分组个数K 越大, 那么, 本文方法的计算复杂度越低. 需要说明的是, 每个进程仅实施一个子种群的进化, 因此, 每一进程完成每代进化, 需要的时间远远少于NSGA-II.形成外部保存集的最大计算复杂度为O(m=K(2N)2), 小于NSGA-II 的相应操作. 由于采用一个新的进程来专门实施外部保存集的形成,因此, 种群每进化一代, 形成外部保存集所需的时间都小于NSGA-II.对于本文方法处理的实际问题, 一般来说, m,N 和L 均为同一数量级, 那么, 问题分解与种群进化一代所需的计算复杂度是相似的, 因此, 在整个问题求解过程中, 问题分解消耗的计算资源可以忽略不计. 此外, 通过上述分析可知, 所有子种群进化和外部保存集形成所需的计算复杂度, 均小于已有的典型方法. 后续的实验结果也验证了本节的分析.3 实验本节通过实验评价本文所提方法的性能. 实验包括如下两部分: 1) 考察包含的参数和策略, 如目标函数分组个数、基于相关关系的目标函数分组,以及外部保存集的形成对本文方法性能的影响; 2)将本文方法与NSGA-II、PPD-MOEA、"-MOEA、HypE 和MSOPS 等比较, 验证本文方法的优越性.3.1 优化问题采用DTLZ 系列优化问题[24] 中的DTLZ1、DTLZ2、DTLZ3、DTLZ5、DTLZ7 和多目标旅行商问题(Multi-objective travelling salesman prob-lem, MOTSP)[25], 评价不同方法的性能. 其中,DTLZ1 是一个多模态优化问题, 该问题的Pareto前沿为一个平面; DTLZ2 是一个Pareto 前沿为凹面的优化问题; DTLZ3 的Pareto 前沿与DTLZ2 相同, 但是, 该问题是一个多模态优化问题, 因此, 问题求解的难度增大; DTLZ5 的Pareto 前沿为一条曲线, 选择该优化问题是为了考察不同方法在高维空间中收敛到低维Pareto 前沿的能力; DTLZ7 具有一组不连续的Pareto 前沿, 该问题能够检测不同方法在多个Pareto 前沿保持分布度的能力; MOTSP是一类著名的NP 难问题. 在构建该问题时, 可以通过相关参数决定目标函数之间的相关程度. 当相关参数的值分别为正、0 和负时, 该问题的相邻目标函数分别具有正、0 和负相关关系. 因此, 该问题非常适合用于考察本文方法的性能.上述优化问题的数学模型可参阅相关文献. 需要说明的是, 对于DTLZ 系列问题, 决策变量个数为n = m+v¡1, 其中, m 为目标函数的个数, v 为一个取值为整数的参数. 实验中, 对于优化问题DTLZ1、DTLZ2、DTLZ3、DTLZ5 和DTLZ7, v 的取值分别为5、10、5、10 和20. 所有优化问题决策变量的取值范围均为[0, 1]. 对于MOTSP, 节点数目为30,相关参数分别取0.5、0 和¡0:5.在实验的第一部分, 对于不同的参数或策略, 通过求解不同的优化问题, 评价这些参数或策略对本文方法性能的影响. 具体地, 1) 通过求解24 目标优化问题DTLZ2, 评价目标函数分组个数对本文方法性能的影响; 2) 基于6 目标优化问题DTLZ2, 构建并求解目标相关程度不同的多个优化问题, 以说明本文提出的基于相关关系的目标函数分组方法的有效性; 3) 通过求解6 目标优化问题DTLZ2, 评价本文所提外部保存集形成方法的有效性.在实验的第二部分, 通过求解目标函数个数分别为6、9、12 和15 的优化问题DTLZ1、DTLZ2、DTLZ3、DTLZ5 和DTLZ7, 以及目标函数个数分别为6 和12 的优化问题MOTSP, 并与其他方法比较, 验证本文所提方法的优越性.3.2 性能指标采用世代距离(Generation distance, GD)[26]、空间评价指标(Spacing, SP)[26]、最大传播距离(Maximum spread, MS)[27]、反世代距离(Invertedgeneration distance, IGD)[28] 和超体积(Hypervol-ume, HV)[15] 5 个性能指标, 以及并行程序耗时Tp,评价不同方法的性能, 其中, GD 用于评价方法的逼近性能; SP 用于反映方法的分布性能; MS 用于衡量方法的延展性能; IGD 和HV 可同时测量方法的逼近、分布以及延展性能; Tp 用于考察并行算法的运行速度.对于指标GD、SP、MS、IGD 和HV, 相应的计算方法可参阅上述文献. 容易知道, 某方法的GD 值越小, 那么, 该方法的逼近性能越好, 特别地, 当GD= 0 时, 该方法得到的所有优化解都在真实Pareto前沿上; 某方法的SP 值越小, 那么, 该方法的分布性能越好, 所得Pareto 前沿中优化解的分布越均匀;某方法的MS 值越大, 那么, 该方法的延展性能越好, 特别地, 当MS = 1 时, 该方法所得Pareto 前沿完全覆盖整个真实Pareto 前沿; 某方法的IGD值越小或HV 值越大, 那么, 该方法越能平衡逼近、分布以及延展性能, 所得Pareto 前沿对真实Pareto8 期巩敦卫等: 基于目标分解的高维多目标并行进化优化方法1445前沿的拟合度越高.对于指标Tp, 其计算方法为Tp = pnTs (8)其中, pn 为程序包含的并行进程的个数, Ts 为运行时间最长的进程所需的时间, Tp 和Ts 的单位均为秒.在实验的第一部分, 采用GD、SP、MS, 以及Tp 等4 个指标, 详细考察一些参数和策略对本文方法性能的影响; 在实验的第二部分, 采用IGD 指标比较各方法求解DTLZ 的性能, 并且还采用HV 指标, 比较各方法求解MOTSP 的性能. 需要说明的是, 由于MOTSP 的真实Pareto 前沿是未知的, 本文选取所有运行结果所得解的最大目标值, 作为计算超体积时的参考点.3.3 对比方法本文选取NSGA-II[4]、PPD-MOEA[10]、"-MOEA[12]、HypE[15] 和MSOPS[16] 作为对比方法.由于本文方法的每一子种群都基于NSGA-II 进化机制求解相应的子优化问题, 且选择迁徙个体和形成外部保存集时, 都用到了NSGA-II 的进化个体选择机制, 因此, 将本文方法与NSGA-II 对比, 是十分必要的; 鉴于本文方法基于Pareto 局部占优关系比较进化个体的性能, 因此, 与PPD-MOEA 对比也是很有意义的; 此外, 尽管"-MOEA、HypE 以及MSOPS 与本文方法没有明显的共同之处, 但是, 它们均为求解高维多目标优化问题的有效方法. 因此,与这些方法进行比较, 能够充分评价本文方法的性能.上述对比方法中的NSGA-II1、"-MOEA2、HypE3 以及MSOPS4 的程序代码, 均可在论文作者的主页上下载, PPD-MOEA 的程序代码由我们根据原文算法自己编写. 本文的实验结果均通过运行这些程序得到.3.4 参数设置对于所有方法, 均采用相同的遗传算子. 对于DTLZ, 采用模拟二元交叉和多项式变异, 且交叉和变异算子的分布指数分别为20 和10. 对于MOTSP, 采用顺序交叉和逆转变异交叉, 变异概率分别为0.8 和0.01, 交配选择采用二元锦标赛方法.算法的终止条件为个体评价次数达到预先设定的值,对于优化问题DTLZ1、DTLZ3 和MOTSP, 该值为100 000; 对于DTLZ2、DTLZ5 和DTLZ7, 该值为30 000. 对于方法NSGA-II、PPD-MOEA、HypE和MSOPS, 种群规模为100. 对于本文方法, 当目标函数的分组个数为3 或6 时, 种群规模为102; 当目标函数的分组个数为8 时, 种群规模为104, 使得不同子种群包含相同个数的进化个体. 对于"-MOEA,由于该方法的种群规模与" 的取值有关, 为了公平比较, 根据不同的优化问题, 采取不同的" 取值, 使得在算法终止时, 种群规模保持在100 左右. " 的取值如表1 和表2 所列.表1 DTLZ 优化问题的" 取值Table 1 The settings of " for DTLZ problems目标个数DTLZ1 DTLZ2 DTLZ3 DTLZ5 DTLZ76 0.06 0.23 0.24 0.12 0.279 0.09 0.29 0.42 0.13 0.6912 0.17 0.30 0.81 0.15 0.7815 0.32 0.31 0.92 0.15 0.83表2 MOTSP 问题的" 取值Table 2 The settings of " for MOTSP目标个数相关参数"6 0.5, 0, ¡0:5 0.42, 1.3, 2.712 0.5, 0, ¡0:5 3.0, 4.1, 5.3对于本文方法涉及的其他参数, 我们先前的研究表明, 合理地设置迁徙间隔与迁徙率, 不但对算法的运行速度影响较小, 而且能够提升算法性能. 因此, 在本文实验中, Tm = 1, ® = 0:1. 此外, 如果没有特别说明, 当优化问题包含6 或9 个目标函数时,分组个数为3; 包含12 个目标函数时, 分组个数为4; 包含15 个目标函数时, 分组个数为5.对于PPD-MOEA, 每次选取的目标函数为2个, 进行目标变换的间隔代数为10; 在HypE 中, 估计超体积所需的采样点个数为10 000; MSOPS 的权重向量为100 个.对于每一优化问题, 采用每种方法独立运行30次, 计算第3.2 节各性能指标的值, 并统计它们的均值和方差. 此外, 采用Mann-Whitney U 分布方法,对不同方法得到的上述指标值进行假设检验, 以评价不同方法性能差异的显著性.3.5 实验结果3.5.1 不同参数或策略对本文方法性能的影响1) 目标函数分组个数1http://www.iitk.ac.in/kangal/codes/nsga2/nsga2-v1.0.tar2http://www.iitk.ac.in/kangal/codes/eps-moea/epsmoea.tar3http://www.tik.ee.ethz.ch/pisa/selectors/hype/hype c source.tar.gz4http://homepage.ntlworld.com/evan.hughes1/msops.zip1446 自动化学报41 卷目标函数分组个数是本文方法新引入的参数,它的取值与本文方法的收敛性能、计算资源的分配以及运行效率密切相关. 通过将24 目标优化问题DTLZ2 的目标函数分为1、2、3、4、6、8、12 组, 考察目标函数分组个数对本文方法性能的影响. 容易知道, 当目标函数的分组个数仅为1 时, 本文方法即为NSGA-II. 图2 给出了各性能指标随目标函数分组个数的变化趋势.图2 各项性能指标随目标函数分组个数的变化趋势Fig. 2 Curves of metrics w.r.t. number of subproblems由图2 可以看出, 随着目标函数分组个数的增多, 1) GD 逐渐减小, 说明较多的目标函数分组个数, 能够改善本文方法所得Pareto 前沿的逼近性能;2) MS 逐渐减小, 说明目标函数分组个数越多, 本文方法所得Pareto 前沿的延展性越差, 可能的原因是当目标函数分组个数很多时, 每个子种群包含的进化个体数很少, 使得子种群所得的Pareto 最优解集难以完整覆盖真实的Pareto 前沿; 3) SP 逐渐减小,尽管如此, 这并不能说明本文方法所得Pareto 前沿的分布更加均匀, 因为即使某两个近似Pareto 前沿的分布性能相同, 对于逼近性能较好或延展性能较差的近似Pareto 前沿, 它的SP 指标值也会较小;4) 本文方法的运行时间大体呈下降趋势, 并在分组个数为6 时, 取得了最快的运行速度. 但是, 当分组个数为8 时, 运行时间开始略微回升. 说明即使增加进程个数, 本文方法的运行效率也不一定提高. 但是, 只要目标函数分组个数大于1, 本文方法的运行速度就会快于NSGA-II.基于上述实验结果, 对于24 目标优化问题DTLZ2, 当目标函数分为6 组时, 可在多个性能指标上取得较为理想的结果.2) 基于相关关系的目标函数分组方法本部分参考文献[29] 的方法, 基于6 目标优化问题DTLZ2, 构建目标相关程度不同的5 个优化问题, 分别采用基于相关关系和随机的目标函数分组方法, 求解这些优化问题, 以评价本文所提目标函数分组方法的性能. 这些问题的数学模型为min(gi (x) = fi (x) ; i = 1; 2; 3gi (x) = ¸fi¡3 (x) + (1 ¡ ¸) fi (x) ; i = 4; 5; 6(9)其中, fi(x), i = 1; 2; 3; 4; 5; 6; 分别为6 目标优化问题DTLZ2 的原目标函数. ¸ 2 [0; 1] 为相关强度系数, 且¸ 越大, gi(x) 与g(i¡3)(x) 相似程度越高.特别地, 当¸ = 0 时, 该优化问题即为6 目标优化问题DTLZ2; 当¸ = 1 时, 该优化问题具有3 组完全相关的目标函数. 按照第2.2 节给出的分组方法,当¸ 取值较大时, 这些优化问题的目标函数更倾向于被分为如下3 组: 1) G1 = g1(x); g4(x); 2) G2 =g2(x); g5(x); 3) G3 = g3(x); g6(x). 本文设置¸ =0, 0.25, 0.5, 0.75, 1, 从而分别得到目标相关程度不同的多个优化问题.对于基于相关关系和随机法得到的目标函数分组, 采用本文提出的方法求解上述优化问题, 实验结果如表3 所列, 表中括号外的数据表示均值, 括号内的数据为标准差, 粗体显示的数据为两种方法得到的最优结果.由表3 可以看出, 1) 对于所有的优化问题, 基于相关关系的目标函数分组方法的GD 指标均显著优于随机分组方法, 且¸ 越大, 即目标函数之间的相关程度越高, 基于相关关系的目标函数分组方法的收敛性越好; 2) 当¸ = 0 和¸ = 0:25 时, 两种方法的SP 指标没有明显差异, 当¸ > 0:25 时, 基于相关关系的目标函数分组方法, 能够显著提升解集的分布性能; 3) 无论采用哪种分组方法, 得到的Pareto 前沿的MS 值均达到最大值; 4) 两种方法的Tp 指标没有显著差异, 这说明, 计算目标分组花费的时间,对算法总的运行时间几乎没有影响. 总体来讲, 基于相关关系的目标函数分组方法, 不仅所需的计算资源少, 而且能够明显提升算法的收敛与分布性能.3) 外部保存集将本文提出的外部保存集形成策略与传统的策略比较, 以评价本文的外部保存集形成策略对本文方法性能的影响. 这里传统的策略基于所有目标计算候选解的Pareto 序值, 并基于序值和拥挤距离形成外部保存集. 分别基于这两种外部保存集形成策略, 并采用本文的方法, 求解6 目标优化问题DTLZ2, 实验结果如表4 所列.由表4 可以看出, 1) 采用本文的外部保存集形成策略, 得到的Pareto 前沿的SP 值与传统的策略不相上下; 2) 两种策略得到的Pareto 前沿的MS 值均达到最大值, 但是, 传统策略的稳定性略优于本文8 期巩敦卫等: 基于目标分解的高维多目标并行进化优化方法1447表3 目标函数分组策略对本文方法性能的影响Table 3 The e®ect of the strategy of objectives decomposition¸GD SP MS Tp相关分组随机分组相关分组随机分组相关分组随机分组相关分组随机分组0 1.029E¡2(3.9E¡3)1.324E¡2(4.0E¡3)y2.218E¡1(1.2E¡2)2.125E¡1(1.8E¡2)1.000E+0(1.1E¡4)1.000E+0(1.5E¡4)3.931E¡1(3.8E¡2)3.903E¡1(4.1E¡2)0.25 7.405E¡3(3.8E¡3)1.291E¡2(4.2E¡3)y1.992E¡1(1.3E¡2)2.021E¡1(1.3E¡2)1.000E+0(1.2E¡4)1.000E+0(8.3E¡5)4.027E¡1(4.6E¡2)3.998E¡1(3.3E¡2)0.5 2.037E¡3(7.1E¡4)1.311E¡2(1.5E¡3)y1.643E¡1(1.0E¡2)1.936E¡1(2.7E¡2)y1.000E+0(7.1E¡5)1.000E+0(1.8E¡4)3.891E¡1(7.1E¡2)4.082E¡1(5.8E¡2)0.75 8.214E¡4(4.2E¡4)1.285E¡2(1.1E¡3)y8.921E¡2(6.3E¡3)1.284E¡1(1.9E¡2)y1.000E+0(9.8E¡5)1.000E+0(6.2E¡5)4.100E¡1(6.4E¡2)4.081E¡1(4.5E¡2)1 3.436E¡4(2.0E¡4)1.290E¡2(6.3E¡4)y5.765E¡2(5.2E¡3)6.228E¡2(4.7E¡3)y1.000E+0(3.8E¡6)1.000E+0(4.3E¡6)3.915E¡1(5.6E¡2)3.923E¡1(7.3E¡2)y 表示, 对于相关分组, 随机分组的该项指标具有显著差异(Mann-Whitney U 分布检验, 置信水平为0.05)表4 外部保存集形成策略对本文方法性能的影响Table 4 The e®ect of the strategy of external archiveGD SP MS Tp本文策略1.029E¡2(3.9E¡3)2.218E¡1(1.2E¡2)1.000E+0(1.1E¡4)3.931E¡1(3.8E¡2)传统策略4.364E¡2(3.0E¡3)y2.198E¡1(1.8E¡2)1.000E+0(8.9E¡5)4.453E¡1(3.1E¡2)yy 表示, 对于本文策略, 传统策略的该项指标具有显著差异(Mann-Whitney U 分布检验, 置信水平为0.05)的策略; 3) 虽然两种策略得到的Pareto 前沿的SP和MS 值没有显著差异, 但是, 对于其他两个指标GD 和Tp, 本文的策略均显著优于传统的策略. 这说明, 采用本文提出的外部保存集形成策略, 得到的Pareto 前沿在保证分布和延展性能的同时, 不但具有更好的逼近性能, 而且所需的计算时间更短. 因此, 采用本文提出的外部保存集形成策略, 能够提高求解高维多目标优化问题的性能.通过第一部分的实验结果与分析, 可以得到如下结论: 本文提出的基于相关关系的目标函数分组方法和外部保存集形成策略是非常有效的. 此外, 合理的目标函数分组个数也有助于提高本文方法的性能.3.5.2 与其他方法的对比通过求解6、9、12、15 目标优化问题DTLZ1、DTLZ2、DTLZ3、DTLZ5、DTLZ7 及6 和12 目标优化问题MOTSP, 并与NSGA-II、PPD-MOEA、"-MOEA、HypE 和MSOPS 比较, 评价本文方法的性能. 表5 列出了不同方法求解DTLZ 所得Pareto 前沿的IGD 指标; 表6 列出了这些方法求解MOTSP 所得Pareto 前沿的HV 指标. 为了便于观察和对比, 以本文方法为基准, 对其他方法所得的HV 指标进行标准化处理. 表中, 粗体显示的数据为这些方法得到的该问题的最优结果.首先, 分析不同方法求解优化问题DTLZ1 和DTLZ3 的性能. 通过指标IGD 的值可知, 1) 本文方法得到的Pareto 前沿具有最好的性能, 其次是MSOPS, 但是, 除了6 目标优化问题DTLZ1 和15目标优化问题DTLZ3 之外, MSOPS 与本文方法在求解大多数优化问题时, 没有显著差异; 2) 虽然"-MOEA 对于6 目标优化问题DTLZ1 和DTLZ3表现出很好的性能, 但是, 在更高维目标优化问题上, 该方法的性能却急剧下降, 这是因为, DTLZ1和DTLZ3 的目标函数值域很大, 其真实Pareto 前沿的值域却很小, 导致" 的取值难以合理确定; 3)HypE、PPD-MOEA 和NSGA-II 得到的Pareto 前沿的性能明显劣于本文方法.其次, 分析不同方法求解优化问题DTLZ2 的性能. 根据不同方法得到的Pareto 前沿的IGD 指标, 这些方法性能优劣的排名依次是"-MOEA、本文方法、MSOPS、PPD-MOEA、HypE 和NSGA-II, 且这些方法的性能差异是显著的. 值得注意的是,"-MOEA 对于不同目标函数的优化问题DTLZ2,显著优于本文方法. 这表明, 当" 取合适的值时,"-MOEA 的性能也是能够优于本文方法的.再次, 分析不同方法求解优化问题DTLZ5 的性能. 根据IGD 指标的值, 1) 本文方法和MSOPS都取得了很好的性能, 且对于6 和9 目标优化问题DTLZ5, 本文方法显著优于MSOPS; 虽然MSOPS1448 自动化学报41 卷表5 不同方法求解DTLZ 的IGD 指标Table 5 Metric IGD of di®erent methods for DTLZ problems测试问题目标个数NSGA-II PPD-MOEA "-MOEA HypE MSOPS 本文方法DTLZ16 4.784E+1(2.5E+1)y1.069E+0(7.9E¡1)y1.157E¡1(1.1E¡1)y1.616E+0(1.0E+0)y1.127E¡1(4.5E¡2)y7.853E¡2(2.8E¡3)9 5.652E+1(4.2E+1)y2.326E+0(1.5E+0)y5.769E¡1(3.8E¡1)y1.777E+0(8.4E¡1)y1.763E¡1(6.5E¡2)1.628E¡1(5.4E¡2)12 7.818E+1(5.0E+1)y3.388E+0(2.5E+0)y1.824E+0(2.1E+0)y2.522E+0(9.7E¡1)y2.085E¡1(1.4E¡1)1.828E¡1(1.2E¡1)15 9.347E+1(5.5E+1)y4.924E+0(4.3E+0)y2.774E+0(3.5E+0)y3.184E+0(2.7E+0)y2.413E¡1(1.3E¡1)1.961E¡1(7.3E¡2)DTLZ26 1.722E+0(1.9E¡1)y4.709E¡1(4.8E¡2)y2.659E¡1(6.4E¡3)y5.340E¡1(5.4E¡2)y3.228E¡1(2.1E¡2)y3.005E¡1(8.1E¡3)9 2.071E+0(1.4E¡1)y6.431E¡1(6.7E¡2)y4.213E¡1(1.1E¡2)y6.967E¡1(4.2E¡2)y5.338E¡1(1.9E¡2)y4.909E¡1(1.3E¡2)12 2.139E+0(2.0E¡1)y7.527E¡1(6.7E¡2)y5.010E¡1(1.3E¡2)y8.508E¡1(6.0E¡2)y6.174E¡1(1.7E¡2)y5.866E¡1(2.8E¡2)15 2.194E+0(1.9E¡1)y8.260E¡1(4.9E¡2)y5.846E¡1(4.1E¡2)y9.393E¡1(2.9E¡2)y6.898E¡1(2.3E¡2)y6.474E¡1(1.9E¡2)DTLZ36 1.207E+2(5.7E+1)y1.071E+0(5.6E¡1)y4.606E¡1(1.2E¡1)y3.259E+0(3.0E+0)y3.439E¡1(1.6E¡2)3.248E¡1(2.2E¡2)9 1.343E+2(7.3E+1)y2.510E+0(1.5E+0)y1.615E+0(1.9E+0)y3.439E+0(2.4E+0)y6.023E¡1(2.1E¡1)5.616E¡1(2.3E¡2)12 1.405E+2(8.6E+1)y3.789E+0(1.9E+0)y2.531E+1(2.7E+1)y3.874E+0(1.8E+0)y6.872E¡1(3.4E¡1)6.460E¡1(2.9E¡2)15 2.008E+2(1.4E+2)y4.621E+0(3.9E+0)y7.074E+1(8.5E+1)y5.514E+0(3.4E+0)y8.154E¡1(1.1E¡1)y7.017E¡1(6.4E¡2)DTLZ56 1.461E¡1(3.2E¡2)y8.474E¡2(2.6E¡2)y8.187E¡2(1.4E¡2)y1.565E¡1(7.4E¡2)y3.144E¡2(5.8E¡3)y2.140E¡2(8.0E¡3)9 4.711E¡1(3.0E¡1)y1.106E¡1(2.1E¡2)y1.014E¡1(2.3E¡2)y1.980E¡1(7.7E¡2)y3.240E¡2(2.9E¡3)y2.856E¡2(5.4E¡3)12 9.118E¡1(2.6E¡1)y1.660E¡1(6.0E¡2)y1.019E¡1(1.8E¡2)y2.096E¡1(9.9E¡2)y3.252E¡2(5.8E¡3)3.322E¡2(1.0E¡2)15 1.754E+0(6.3E¡1)y1.946E¡1(7.2E¡2)y1.259E¡1(2.4E¡2)y2.313E¡1(6.2E¡2)y3.375E¡2(8.7E¡3)3.623E¡2(7.6E¡3)DTLZ76 1.401E+0(3.1E¡1)y1.104E+0(2.0E¡1)y5.976E¡1(1.1E¡2)y1.186E+0(3.6E¡1)y3.778E+0(1.7E¡1)y8.653E¡1(2.2E¡1)9 1.877E+0(7.5E¡1)y1.873E+0(6.2E¡1)y1.467E+0(3.2E¡1)y1.637E+0(5.2E¡1)y7.157E+0(1.7E¡1)y1.185E+0(3.3E¡1)12 3.482E+0(1.6E+0)y4.113E+0(1.6E+0)y6.477E+0(2.1E+0) y2.216E+0(9.2E¡1)y1.152E+1(2.2E¡1)y1.664E+0(2.6E¡1)15 3.608E+0(1.2E+0)y4.908E+0(1.5E+0)y1.007E+1(1.7E+0)y2.951E+0(8.0E¡1)y1.481E+1(6.9E¡2)y2.007E+0(5.1E¡1)y 表示对比方法与本文方法的IGD 指标具有显著差异(Mann-Whitney U 分布检验, 置信水平为0.05)8 期巩敦卫等: 基于目标分解的高维多目标并行进化优化方法1449表6 不同方法求解MOTSP 的HV 指标Table 6 Metric HV of di®erent methods for MOTSP目标个数相关参数NSGA-II PPD-MOEA "-MOEA HypE MSOPS 本文方法60.5 37.3y 52.1y 94.6y 39.6y 89.2y 1000 32.6y 41.1y 101.5 45.0y 97.2y 100¡0:5 31.2y 39.9y 98.7 41.7y 87.8y 100120.5 29.4y 49.7y 79.6y 35.1y 96.1y 1000 24.6y 46.9y 81.3y 36.8y 93.2y 100-0.5 21.5y 45.7y 72.7y 32.7y 90.3y 100y 表示对比方法与本文方法的HV 指标具有显著差异(Mann-Whitney U 分布检验, 置信水平为0.05)求解12 和15 目标优化问题DTLZ5 时, 得到了更好的IGD 指标均值, 但是, 与本文方法得到的IGD指标均值不具有显著差异. 本文方法取得很好的性能的原因是, 在优化问题DTLZ5 中, 前m¡ 1 个目标函数之间的相关程度非常高, 通过目标函数的分组与聚合, 求解任一子优化问题, 即可得到原优化问题的近似Pareto 前沿, 还大幅度减少了目标函数;2) 虽然PPD-MOEA、HypE 和NSGA-II 得到的Pareto 前沿的IGD 值也较好, 但是劣于"-MOEA.然后, 分析不同方法求解优化问题DTLZ7 的性能. 从IGD 指标值可以知道, 1) 对于6 目标优化问题DTLZ7, "-MOEA 取得了最佳性能, 本文方法次之, 但是, 在更高维目标优化问题上, 本文方法保持了优越的性能, 而"-MOEA 的性能却明显下降,这仍归因于" 的取值; 2) 虽然求解6 和9 目标优化问题DTLZ7, PPD-MOEA 与HypE 的性能略优于NSGA-II, 但是, 它们在求解12 和15 目标优化问题时, 性能却劣于NSGA-II; 3) 在这些方法中,MSOPS 取得了最差的性能.最后, 分析不同方法求解优化问题MOTSP 的性能. 根据表6 中的HV 指标, 1) 除了相关参数为0的6 目标优化问题MOTSP 之外, 本文方法均取得最好的性能; 2) 虽然求解相关参数为0 和¡0:5 的6 目标优化问题MOTSP 时, 本文方法与"-MOEA没有显著差异, 但是, 当该问题的相关参数为0.5 时,即目标函数具有较大的相关关系时, 本文方法明显优于"-MOEA. 这说明, 本文方法对于目标相关程度较高的优化问题更有效; 3) "-MOEA 求解6 目标优化问题MOTSP 时取得的很好的性能, 优于大部分其他方法, 但是, 在求解12 目标优化问题MOTSP时, MSOPS 取得了仅次于本文方法的性能.通过第二部分的实验结果与分析, 可以得到如下结论: 1) 由于Pareto 占优的局限性, NSGA-II 在处理大多数优化问题时, 均取得了最差的性能, 但是,在求解Pareto 前沿不连续的优化问题时, 其他方法并不一定比其更优; 2) "-MOEA、MSOPS、HypE和PPD-MOEA 均能够有效求解大部分高维多目标优化问题, 但是, 对于"-MOEA 和MSOPS, 需要设置合适的参数, 以获得优异的性能; 3) 除了求解优化问题DTLZ2、6 目标优化问题DTLZ7 以及相关参数为0 的6 目标优化问题MOTSP, 本文方法得到的Pareto 前沿劣于"-MOEA 之外, 对于其他优化问题, 本文方法均具有最佳的性能.4 总结及下一步的工作高维多目标优化问题包含的目标函数增多, 使得该问题的求解非常困难. 如果采用合适的方法, 将目标函数分解, 那么, 有可能降低问题求解的难度.本文提出一种基于目标分解的高维多目标优化问题并行进化求解方法, 通过目标函数分组与聚合, 将一个高维多目标优化问题分解为若干子问题, 从而降低了问题求解的难度. 与其他分解方法不同的是,本文基于Spearman 相关系数对目标函数分组, 保证了同一组的目标函数具有较高的相似度, 这为子优化问题的高效求解提供了保障; 对于每组目标函数形成的子优化问题, 通过多种群并行进化算法的一个子种群, 在同构并行环境的一个子进程上进化,提高了问题求解的速度; 采用改进的外部保存集形成策略, 基于各子种群的最优个体, 在一个新的进程上, 形成外部保存集, 保证了优化问题Pareto 最优解集的逼近与分布性能.将所提方法应用于求解DTLZ 和MOTSP 优化问题, 并与多种典型的进化优化方法比较. 实验结果表明, 本文提出的基于Spearman 相关系数的目标函数分组方法能够有效提高所提方法的性能; 此外, 目标函数分组个数也会影响本文方法的性能, 并通过实验给出了分组个数的合理取值, 以得到各项指标均衡的Pareto 最优解集; 最后, 与其他5 种方法相比, 本文方法求解多数优化问题时, 取得了最佳的性能, 表明了本文方法是一种非常优越的求解高维多目标优化问题的方法.1450 自动化学报41 卷在本文的实验中, 仅通过几个典型的基准优化问题来验证本文方法的有效性, 还没有将其应用于实际的优化问题. 因此, 下一步将考虑本文方法在更多实际优化问题中的应用, 以全面评价所提方法的性能; 除了本文给出的目标函数聚合方法之外, 还可以采用其他的聚合方法, 如MOEA/D 中的切比雪夫方法和PBI (Penalty-based boundary intersec-tion) 方法等. 这些方法基于理想点聚合目标函数,具有不同的几何意义, 可能更加适用于具有某种类型Pareto 前沿的优化问题. 因此, 寻找合适的目标函数聚合方法, 也是下一步需要研究的问题; 最后,对于不同的子优化问题, 包含的目标函数的相关程度是不同的, 一般来讲, 相关度较高的目标函数形成的子优化问题, 对问题Pareto 最优解集的贡献度较小, 但是, 本文用于求解任一子优化问题的子种群规模都是相同的, 这使得消耗了很大的计算量来用于求解对Pareto 最优解集贡献较小的子问题. 如果根据对Pareto 最优解集的贡献度, 合理确定用于求解每一子优化问题的子种群规模, 那么, 将会进一步提高本文方法的求解高维多目标优化问题的效率. 因此, 多种群并行遗传算法每一子种群规模的确定, 是我们需要进一步研究的问题.References1 Zhang Xiao-Dong, Yao Xiao-Lan, Wu Qing-He, Li Dao-Ping. Design and application of a class of multiplexed re-ceding horizon controllers for looper control system. ActaAutomatica Sinica, 2011, 37(3): 380¡384(张晓东, 姚小兰, 伍清河, 李道平. 一类基于滚动时域优化原理的多路控制器设计及其在活套控制中的应用. 自动化学报, 2011, 37(3):380¡384)2 Kong Wei-Jian, Chai Tian-You, Ding Jin-Liang, Wu Zhi-Wei. A real-time multiobjective electric energy allocationoptimization approach for the smelting process of magne-sia. Acta Automatica Sinica, 2014, 40(1): 51¡61(孔维健, 柴天佑, 丁进良, 吴志伟. 镁砂熔炼过程全厂电能分配实时多目标优化方法研究. 自动化学报, 2014, 40(1): 51¡61)3 Zuo Xing-Quan, Wang Chun-Lu, Zhao Xin-Chao. Com-bining multi-objective immune algorithm and linear pro-gramming for double row layout problem. Acta AutomaticaSinica, 2015, 41(3): 528¡540(左兴权, 王春露, 赵新超. 一种结合多目标免疫算法和线性规划的双行设备布局方法. 自动化学报, 2015, 41(3): 528¡540)4 Deb K, Pratap A, Agarwal A, Meyarivan T. A fast and elitistmultiobjective genetic algorithm: NSGA-II. IEEE Transac-tions on Evolutionary Computation, 2002, 6(2): 182¡1975 Zitzler E, Laumanns M, Thiele L. SPEA2: improving thestrength Pareto evolutionary algorithm for multiobjectiveoptimization. In: Proceedings of the 5th Conference on Evo-lutionary Methods for Design, Optimization and Controlwith Applications to Industrial Problems. Athens, Greece:CIMNE, 2001. 95¡1006 Deb K, Saxena D K. Searching for Pareto-optimal solu-tions through dimensionality reduction for certain large-dimensional multi-objective optimization problems. In: Pro-ceedings of the 2006 IEEE Congress on Evolutionary Com-putation. Vancouver, Canada: IEEE, 2006. 3353¡33607 Jaimes A L, Coello C A C, Chakraborty D. Objective re-duction using a feature selection technique. In: Proceedingsof the 10th Annual Conference on Genetic and EvolutionaryComputation. New York, USA: ACM, 2008. 673¡6808 Adra S F, Fleming P J. Diversity management in evolu-tionary many-objective optimization. IEEE Transactions onEvolutionary Computation, 2011, 15(2): 183¡1959 Li M Q, Yang S X, Liu X H. Shift-based density estima-tion for Pareto-based algorithms in many-objective opti-mization. IEEE Transactions on Evolutionary Computation,2014, 18(3): 348¡36510 Sato H, Aguirre H E, Tanaka K. Pareto partial dominanceMOEA and hybrid archiving strategy included CDAS inmany-objective optimization. In: Proceedings of the 2010IEEE Congress on Evolutionary Computation. Barcelona,Spain: IEEE, 2010. 1¡811 Jaimes A L, Coello C A C, Aguirre H, Tanaka K. Objec-tive space partitioning using con°ict information for solvingmany-objective problems. Information Sciences, 2014, 268:305¡32712 Deb K, Mohan M, Mishra S. Evaluating the "-dominationbased multi-objective evolutionary algorithm for a quickcomputation of Pareto-optimal solutions. EvolutionaryComputation, 2005, 13(4): 501¡52513 Kukkonen S, Lampinen J. Ranking-dominance and many-objective optimization. In: Proceedings of the 2007 IEEECongress on Evolutionary Computation. Singapore: IEEE,2007. 3983¡399014 Zitzler E, KÄunzli S. Indicator-based selection in multiobjec-tive search. In: Proceedings of the 8th International Con-ference on Parallel Problem Solving from Nature. Berlin:Springer-Verlag, 2004. 832¡84215 Bader J, Zitzler E. HypE: an algorithm for fast hyper-volume-based many-objective optimization. EvolutionaryComputation, 2011, 19(1): 45¡7616 Hughes E J. Multiple single objective Pareto sampling. In:Proceedings of the 2003 IEEE Congress on EvolutionaryComputation. Canberra, Australia: IEEE, 2003. 2678¡268417 Zhang Q F, Li H. MOEA/D: a multiobjective evolutionaryalgorithm based on decomposition. IEEE Transactions onEvolutionary Computation, 2007, 11(6): 712¡73018 Zitzler E, Thiele L, Bader J. On set-based multiobjectiveoptimization. IEEE Transactions on Evolutionary Compu-tation, 2010, 14(1): 58¡7919 Gong Dun-Wei, Ji Xin-Fang, Sun Xiao-Yan. Solving many-objective optimization problems using set-based evolution-ary algorithms. Acta Electronica Sinica, 2014, 42(1): 77¡83(巩敦卫, 季新芳, 孙晓燕. 基于集合的高维多目标优化问题的进化算法. 电子学报, 2014, 42(1): 77¡83)20 Toro F, Ortega J, Fernandez J, Diaz A. PSFGA: a par-allel genetic algorithm for multiobjective optimization. In:Proceedings of the 10th Euromicro Workshop on Parallel,Distributed and Network-based Processing. Canary Islands:IEEE Computer Society, 2002. 384¡39121 Qi R B, Ma T Y, Sun F, Qian F. Evolutionary algo-rithm based on the evolution of Pareto archive and indi-vidual migration. In: Proceedings of the 2011 InternationalSymposium on Advanced Control of Industrial Processes.Hangzhou, China: IEEE, 2011. 90¡958 期巩敦卫等: 基于目标分解的高维多目标并行进化优化方法145122 Wang Xing. Non-Parametric Statistics. Beijing: TsinghuaUniversity Press, 2009. 180¡184(王星. 非参数统计. 北京: 清华大学出版社, 2009. 180¡184)23 Murata T, Taki A. Examination of the performance of ob-jective reduction using correlation-based weighted-sum formany objective knapsack problems. In: Proceedings of the10th International Conference on Hybrid Intelligent Sys-tems. Atlanta, GA: IEEE, 2010. 175¡18024 Deb K, Thiele L, Laumanns M, Zitzler E. Scalable test prob-lems for evolutionary multiobjective optimization. In: Pro-ceedings of the 2005 Evolutionary Multiobjective Optimiza-tion. London: Springer-Verlag, 2005. 105¡14525 Corne D W, Knowles J D. Techniques for highly multiob-jective optimisation: some nondominated points are bet-ter than others. In: Proceedings of the 9th Annual Confer-ence Genetic Evolutionary Computation. London, England:ACM, 2007. 773¡78026 van Veldhuizen D A, Lamont G B. On measuring multiob-jective evolutionary algorithm performance. In: Proceedingsof the 2000 IEEE Congress on Evolutionary Computation.San Diego, CA, US: IEEE, 2000. 204¡21127 Zitzler E, Deb K, Thiele L. Comparison of multiobjec-tive evolutionary algorithms: empirical results. Evolution-ary Computation, 2000, 8(2): 173¡19528 Zhang Q F, Zhou A M, Zhao S Z, Suganthan P N, Liu WD, Tiwari S. Multiobjective Optimization Test Instances forthe CEC 2009 Special Session and Competition, TechnicalReport CES-487, University of Essex, Colchester, UK, andNanyang Technological University, Singapore, 2008.29 Ishibuchi H, Akedo N, Nojima Y. Behavior of multi-objective evolutionary algorithms on many-objective knap-sack problems. IEEE Transactions on Evolutionary Compu-tation, 2015, 19(2): 264¡283巩敦卫中国矿业大学信息与电气工程学院教授. 1999 年在中国矿业大学获博士学位. 主要研究方向为进化计算与应用. E-mail: dwgong@vip.163.com(GONG Dun-Wei Professor at theSchool of Information and ElectronicEngineering, China University of Min-ing and Technology. He received hisPh. D. degree from China University of Mining and Tech-nology in 1999. His research interest covers evolutionarycomputation and its applications.)刘益萍中国矿业大学信息与电气工程学院博士研究生. 2012 年在中国矿业大学获学士学位. 主要研究方向为多目标进化优化. 本文通信作者.E-mail: lyp.cumt@gmail.com(LIU Yi-Ping Ph. D. candidate atthe School of Information and Elec-tronic Engineering, China University ofMining and Technology. He received his bachelor degreefrom China University of Mining and Technology in 2012.His research interest covers evolutionary computation andmulti-objective optimization. Corresponding author of thispaper.)孙晓燕中国矿业大学信息与电气工程学院教授. 2009 年在中国矿业大学获博士学位. 主要研究方向为交互式进化计算. E-mail: xysun78@126.com(SUN Xiao-Yan Professor at theSchool of Information and ElectronicEngineering, China University of Min-ing and Technology. She received herPh. D. degree from China University of Mining and Tech-nology in 2009. Her research interest covers interactiveevolutionary computation.)韩玉艳中国矿业大学信息与电气工程学院博士研究生. 2012 年在聊城大学获硕士学位. 主要研究方向为调度优化.E-mail: yuyanhan1023@163.com(HAN Yu-Yan Ph. D. candidate atthe School of Information and Elec-tronic Engineering, China University ofMining and Technology. She receivedher master degree from Liaocheng University in 2012. Herresearch interest covers scheduling optimization.)