基于精英重组的混合多目标进化算法

D0L:10.13374.issn1001-053x.2013.09.001 第35卷第9期 北京科技大学学报 Vol.35 No.9 2013年9月 Journal of University of Science and Technology Beijing Sep.2013 基于精英重组的混合多目标进化算法 吴迪凶，李苏剑，李海涛 北京科技大学机械工程学院，北京100083 ☒通信作者，E-mail:potato851124@163.com 摘要针对多目标进化算法搜索效率低和收敛性差的问题，提出了基于精英重组的混合多目标进化算法，将多目标优 化问题分解为多个单目标优化问题单独求解，并采用基于遗传算法的精英重组策略将多个相异解重组生成唯一的精英 解.提出区域化的种群初始化方法，改进局部搜索及群体选择机制，采用以优化子群为核心的分组交叉策略及自适应多 位变异算子，并引入基于混沌优化的重启机制，有效克服了精英保存的固有缺陷，以及现有多目标进化算法存在的目标 空间解拥挤、收敛慢、易早熟等问题。多目标测试函数的数值仿真和关键步骤的性能分析证明了本文算法的有效性和优 越性. 关键词多目标优化：精英重组：遗传算法：混沌理论 分类号TP18 Elite-recombination-based hybrid multi-objective evolutionary algo- rithm WUDi凶，LISu-jian,LI Hai-tao School of Mechanical Engineering,University of Science and Technology Beijing,Beijing 100083,China Corresponding author,E-mail:potato851124@163.com ABSTRACT Considering the bad efficiency and convergence of multi-objective evolutionary algorithms,this article introduces an elite-recombination-based hybrid multi-objective evolutionary algorithm (ERHMEA).In the algorithm, the multi-objective optimization problem was decomposed into multiple single-objective optimization problems and generated the only elite solution with the genetic-algorithm-based elite recombination strategy.Strategies such as regional population initialization,improved local search and selection mechanisms,optimized subgroup based packet crossover and adaptive multiple mutation operator,and chaos optimization based restart mechanism effectively overcome the inherent defects of elite preservation,as well as the multi-objective evolutionary algorithm (MEA)existing target space solution crowding,slow convergence,prematurity,and other issues.Multi-objective test functions analysis and experimental simulation prove the effectiveness and superiority of the proposed algorithm. KEY WORDS multi-objective optimization;elite recombination;genetic algorithms;chaos theory 现实问题往往由多个相互作用相互冲突的目 标优化问题转化为一个单目标优化问题，然而由 标组成，由此产生了多目标优化问题(multi-objec- 于权重参数的不确定性导致此方法性能较差.多 tive optimization problem,MOP).多目标优化问 目标进化算法(multi-objective evolutionary algo- 题由于目标的不一致性而难以产生唯一的最优解， ithm,MEA)作为一种基于群体的智能搜索方法， 它的非劣解是由一组互相矛盾的解所构成的折中 能够并行搜索大规模空间并生成多个Pareto非 解集合.传统的求解方法是基于各目标权重将多目 劣解，在运行速度及解的质量上均优于传统方法， 收稿日期：2012-08-04

第 35 卷 第 9 期 北 京 科 技 大 学 学 报 Vol. 35 No. 9 2013 年 9 月 Journal of University of Science and Technology Beijing Sep. 2013 基于精英重组的混合多目标进化算法 吴 迪 ，李苏剑，李海涛 北京科技大学机械工程学院, 北京 100083 通信作者，E-mail: potato851124@163.com 摘 要 针对多目标进化算法搜索效率低和收敛性差的问题，提出了基于精英重组的混合多目标进化算法，将多目标优 化问题分解为多个单目标优化问题单独求解，并采用基于遗传算法的精英重组策略将多个相异解重组生成唯一的精英 解. 提出区域化的种群初始化方法，改进局部搜索及群体选择机制，采用以优化子群为核心的分组交叉策略及自适应多 位变异算子，并引入基于混沌优化的重启机制，有效克服了精英保存的固有缺陷，以及现有多目标进化算法存在的目标 空间解拥挤、收敛慢、易早熟等问题. 多目标测试函数的数值仿真和关键步骤的性能分析证明了本文算法的有效性和优 越性. 关键词 多目标优化；精英重组；遗传算法；混沌理论 分类号 TP18 Elite-recombination-based hybrid multi-objective evolutionary algo￾rithm WU Di , LI Su-jian, LI Hai-tao School of Mechanical Engineering, University of Science and Technology Beijing, Beijing 100083, China Corresponding author, E-mail: potato851124@163.com ABSTRACT Considering the bad efficiency and convergence of multi-objective evolutionary algorithms, this article introduces an elite-recombination-based hybrid multi-objective evolutionary algorithm (ERHMEA). In the algorithm, the multi-objective optimization problem was decomposed into multiple single-objective optimization problems and generated the only elite solution with the genetic-algorithm-based elite recombination strategy. Strategies such as regional population initialization, improved local search and selection mechanisms, optimized subgroup based packet crossover and adaptive multiple mutation operator, and chaos optimization based restart mechanism effectively overcome the inherent defects of elite preservation, as well as the multi-objective evolutionary algorithm (MEA) existing target space solution crowding, slow convergence, prematurity, and other issues. Multi-objective test functions analysis and experimental simulation prove the effectiveness and superiority of the proposed algorithm. KEY WORDS multi-objective optimization; elite recombination; genetic algorithms; chaos theory 现实问题往往由多个相互作用相互冲突的目 标组成，由此产生了多目标优化问题 (multi-objec￾tive optimization problem, MOP). 多目标优化问 题由于目标的不一致性而难以产生唯一的最优解， 它的非劣解是由一组互相矛盾的解所构成的折中 解集合. 传统的求解方法是基于各目标权重将多目 标优化问题转化为一个单目标优化问题，然而由 于权重参数的不确定性导致此方法性能较差. 多 目标进化算法 [1](multi-objective evolutionary algo￾rithm, MEA) 作为一种基于群体的智能搜索方法， 能够并行搜索大规模空间并生成多个 Pareto 非 劣解，在运行速度及解的质量上均优于传统方法， 收稿日期：2012-08-04 DOI:10.13374/j.issn1001-053x.2013.09.001

·1208 北京科技大学学报 第35卷 因而成为近年来多目标优化问题求解领域研究的 所有Pareto非劣解集对应的目标函数值所形 核心. 成的区域称为Pareto前沿，表示为 与单目标优化寻求最优解的目标不同，多目标 F*={f(x)|x0∈P*} (3) 进化算法具有两个目标冈：提高向Pareto非劣解 集的收敛性：维持Pareto非劣解集的多样性.学者 1.2多目标进化算法的研究现状 们针对这两个可能互相冲突的目标分别提出了很多 逼近性和多样性是衡量多目标进化算法性能 方法.目前大部分多目标进化算法以协调精英保存 的主要标准，具体表现在两个方面可：一是得到的 并同时考虑支配及密度信息为主要特点，其中部分 非支配集向真实Pareto前沿的逼近程度：二是得到 算法在求解低维多目标进化算法时具有非常良好的 解的均匀分布程度.下面针对两个目标实现方法的 表现1)，并有部分研究讨论了保持种群多样性的问 研究现状分别进行讨论 题-：但由于多目标进化算法全局搜索以及强调 对于第一方面的研究，通常采取基于Pareto 自然选择的性质，导致其在进化的快速性和可靠性 的适应值分配方法引导搜索逼近真实Pareto前沿， 方面并不十分有效，种群多样性损失的问题也难以 其基本思想在于基于占优关系对解进行排序.Zitzler 从根本上得到改善 等阁提出一种排序方法，其中每个个体均被赋 针对现有研究中面临的问题及难点，本文 予一个强度值：张师博华等闷提出了一种结合 提出基于精英重组的混合多目标进化算法(elite- Pareto排序和多目标混沌加权的个体适应度计算方 recombination-based hybrid multi-objective evolu- 法：Chang等回在多目标进化算法框架中融入自适 tionary algorithm,ERHMEA).算法的核心在于将 应局部搜索机制，在最优个体邻域中发现新的非占 多个最优化问题的相异解重组生成一个唯一的精英 优解：Qu和Suganthan1o]采用归一化的目标值，有 解，提出基于遗传算法的精英重组策略(elite recom- 效降低了非占优排序的复杂度：Shi等②采用树结 bination strategy,.ERS).该策略采用区域化方法产 构保留个体间必要的Pareto支配关系，显著降低了 生高精度及多样化的初始种群，对Pareto解集进 占优排序的比较次数：李俊青等[叫对每次迭代得 行两次自适应局部搜索及优化的交叉变异操作，并 到的邻域解集进行Pareto非支配排序，并设计了一 引入基于混沌优化的重启机制，以克服精英保存的 种Pareto档案集快速更新算法，有效提升了解的收 固有缺陷，以及多目标进化算法存在的目标空间解 敛性及收敛速度 拥挤、收敛速度慢、易早熟等问题.分别采用测试 对于第二方面的研究，一些多目标进化算法通 函数验证算法性能，并讨论关键步骤的影响，以期 过检测群密度信息以维持种群多样性，典型的有 证明本文提出算法的有效性和优越性. SPEA-Ⅱ3周、NSGA12、NSGA-Ⅱ等.李俊青等 1多目标进化算法概述 通过设置外部Pareto档案集以保存每次邻域搜索 得到的Pareto非支配解，保证了解的多样性：王 1.1多目标优化问题的相关定义 瑞琪等3引入基于改进Tent映射的自适应变尺 多目标优化问题可以表述为以下形式6： 度混沌优化方法，细化了搜索空间并提高了寻优效 max z=f(x)={f(x),f2(x),..,fn(x)}, 率：Xu等14采用异步遗传局部搜索算法，对变邻 S.t. e(x)={e1(r),e2(c),…,ee(r)}≤0. 域局部搜索产生的个体进行交叉操作生成子个体并 (1) 再次执行局部搜索，保留最优个体的同时保持了种 其中，x=(r1,x2,…,xm)∈Rm表示决策变量的 群的多样性：Jiao等)首先基于目标空间中初始 可行域，z=(a1,2,…,n)∈R”表示目标值的可 方向向量将种群划分为多个子群，然后根据各子群 行域. 协同进化的相互作用求解多目标优化问题，并进一 定义p*为Pareto非劣解集，将满足约束条件 步探讨欠开发区域以维持解空间的相对均匀分布. 的决策向量表示为可行集X,则有 尽管以上部分方法在一些基准案例中取得了 不错的表现，但由于现有算法在求解时均分别针对 p*={x°∈Xl归x2∈X:x2>x0}. (2) 两个目标，而未考虑解集收敛性与多样性的协同优 化，可能造成目标空间解拥挤、收敛速度慢、易早 其中：日表示不存在：x1>x0表示x2占优x0,即 熟等问题，因此需进一步研究快速的解空间搜索方 i,f(x)≥f(x)Λ3j:f(x2)>f(x). 法以及简单有效的多样化策略

· 1208 · 北 京 科 技 大 学 学 报 第 35 卷 因而成为近年来多目标优化问题求解领域研究的 核心. 与单目标优化寻求最优解的目标不同，多目标 进化算法具有两个目标[2]：提高向 Pareto 非劣解 集的收敛性；维持 Pareto 非劣解集的多样性. 学者 们针对这两个可能互相冲突的目标分别提出了很多 方法. 目前大部分多目标进化算法以协调精英保存 并同时考虑支配及密度信息为主要特点，其中部分 算法在求解低维多目标进化算法时具有非常良好的 表现[1,3]，并有部分研究讨论了保持种群多样性的问 题[4−5]；但由于多目标进化算法全局搜索以及强调 自然选择的性质，导致其在进化的快速性和可靠性 方面并不十分有效，种群多样性损失的问题也难以 从根本上得到改善. 针对现有研究中面临的问题及难点， 本文 提出基于精英重组的混合多目标进化算法 (elite￾recombination-based hybrid multi-objective evolu￾tionary algorithm, ERHMEA). 算法的核心在于将 多个最优化问题的相异解重组生成一个唯一的精英 解，提出基于遗传算法的精英重组策略 (elite recom￾bination strategy, ERS). 该策略采用区域化方法产 生高精度及多样化的初始种群，对 Pareto 解集进 行两次自适应局部搜索及优化的交叉变异操作，并 引入基于混沌优化的重启机制，以克服精英保存的 固有缺陷，以及多目标进化算法存在的目标空间解 拥挤、收敛速度慢、易早熟等问题. 分别采用测试 函数验证算法性能，并讨论关键步骤的影响，以期 证明本文提出算法的有效性和优越性. 1 多目标进化算法概述 1.1 多目标优化问题的相关定义 多目标优化问题可以表述为以下形式 [6]： ( max z = f(x) = {f1 (x), f2 (x), · · · , fn(x)} , s.t. e(x) = {e1(x), e2(x), · · · , ec(x)} 6 0. (1) 其中, x = (x1, x2, · · · , xm) ∈ R m 表示决策变量的 可行域，z = (z1, z2, · · · , zn) ∈ R n 表示目标值的可 行域. 定义 P ∗ 为 Pareto 非劣解集，将满足约束条件 的决策向量表示为可行集 χ，则有 P ∗ = © x 0 ∈ χ ¯ ¯ !∃ x 1 ∈ χ : x 1 Â x 0 ª . (2) 其中: !∃ 表示不存在；x 1 Â x 0 表示 x 1 占优 x 0，即 ∀i, fi (x 1 ) > fi (x 0 ) ∧ ∃j : fj (x 1 ) > fj (x 0 ). 所有 Pareto 非劣解集对应的目标函数值所形 成的区域称为 Pareto 前沿，表示为 F ∗ = {f(x 0 ) | x 0 ∈ P ∗ }. (3) 1.2 多目标进化算法的研究现状 逼近性和多样性是衡量多目标进化算法性能 的主要标准，具体表现在两个方面 [7]：一是得到的 非支配集向真实 Pareto 前沿的逼近程度；二是得到 解的均匀分布程度. 下面针对两个目标实现方法的 研究现状分别进行讨论. 对于第一方面的研究，通常采取基于 Pareto 的适应值分配方法引导搜索逼近真实 Pareto 前沿， 其基本思想在于基于占优关系对解进行排序.Zitzler 等 [3] 提出一种排序方法， 其中每个个体均被赋 予一个强度值； 张师博华等 [8] 提出了一种结合 Pareto 排序和多目标混沌加权的个体适应度计算方 法；Chang 等 [9] 在多目标进化算法框架中融入自适 应局部搜索机制，在最优个体邻域中发现新的非占 优解；Qu 和 Suganthan[10] 采用归一化的目标值，有 效降低了非占优排序的复杂度；Shi 等 [2] 采用树结 构保留个体间必要的 Pareto 支配关系，显著降低了 占优排序的比较次数；李俊青等 [11] 对每次迭代得 到的邻域解集进行 Pareto 非支配排序，并设计了一 种 Pareto 档案集快速更新算法，有效提升了解的收 敛性及收敛速度. 对于第二方面的研究，一些多目标进化算法通 过检测群密度信息以维持种群多样性，典型的有 SPEA-Ⅱ [3]、NSGA[12]、NSGA-Ⅱ [1]等.李俊青等 [11] 通过设置外部 Pareto 档案集以保存每次邻域搜索 得到的 Pareto 非支配解，保证了解的多样性；王 瑞琪等 [13] 引入基于改进 Tent 映射的自适应变尺 度混沌优化方法，细化了搜索空间并提高了寻优效 率；Xu 等 [14] 采用异步遗传局部搜索算法，对变邻 域局部搜索产生的个体进行交叉操作生成子个体并 再次执行局部搜索，保留最优个体的同时保持了种 群的多样性；Jiao 等 [15] 首先基于目标空间中初始 方向向量将种群划分为多个子群，然后根据各子群 协同进化的相互作用求解多目标优化问题，并进一 步探讨欠开发区域以维持解空间的相对均匀分布. 尽管以上部分方法在一些基准案例中取得了 不错的表现，但由于现有算法在求解时均分别针对 两个目标，而未考虑解集收敛性与多样性的协同优 化，可能造成目标空间解拥挤、收敛速度慢、易早 熟等问题，因此需进一步研究快速的解空间搜索方 法以及简单有效的多样化策略

第9期 吴迪等：基于精英重组的混合多目标进化算法 ·1209· 2基于精英重组的混合多目标进化算法 与收敛性.由于算法1开始前已具有m个个体 考虑多目标优化问题的复杂性及现有多目标 Y,且Y分别为各目标函数的最优个体，因此 进化算法的特点，本节提出基于精英重组的混合多 本文提出一种区域化的种群初始化方法(regional 目标进化算法，将多目标问题分解为多个单目标问 population initialization,RPI),以期快速产生具有 题单独求解，并在单目标问题非劣解集的基础上通 较高精度和多样性的初始种群.区域化种群初始 过精英重组确定唯一非劣解. 化方法由两步构成：(1)在每个个体Y周围生成 2.1精英重组策略 ceil(M/m)个粒子，生成方法见算法2：(2)计算所有 对于多目标优化问题，各个单目标问题的非劣 m-ceil(M/m)+m个粒子的评价指标回Pareto逼近 解集可能并不完全相同，多个解集的交集即为实现 度(Pareto ranking)和动态拥挤度(dynamic crowd- 多目标优化的全局非劣解，而相异解则难以判断和 ing),选择最优的M个粒子组成初始种群P.其中， 挑选.因此，本文提出基于遗传算法的精英重组策 在优秀个体的选择上，首先选择占优的Pareto优化 略，具体步骤如算法1所示，目的在于将相异解重 前沿个体，当多个个体处于同一优化前沿时则选择 组生成一个唯一的精英解.与精英保存策略[16不 拥挤程度小的个体 同，精英重组策略采用区域化方法产生高精度及多 算法2初始粒子生成 样化的初始种群，对Pareto解集进行两次自适应局 Fori=1:1:m/z(位，p)表示个体p得到的函数 部搜索及优化的交叉变异操作，同时采用基于混沌 i的取值，e为搜索范围，y表示生成的初始粒子 优化的重启机制，有效解决了目标空间解的拥挤度 {k=1; 问题，同时避免了精英保存可能造成的局部最优， While (k<M/m+1) 保证种群快速地朝全局最优化方向发展. {p =round(rand(1,N)); 算法1基于遗传算法的精英重组 If (z(i,p)>=z(i,Y(i))*(1+e))then {y(k)= 步骤1初始化.生成M个大小为N的个体 pk=k+1:} 构成初始种群P,设置选择比例yY∈(0,1)，最大进 2.1.2选择操作 化代数tmax,迭代次数t=1. 轮盘赌法作为广泛适用的种群选择方法存在 步骤2选择优秀个体.采用轮盘赌的方法在 两个问题：第一，由于高适应度的个体在进化初期 P(t)中挑选yM个优秀个体构成S(t) 被选择的概率很大，产生出较多后代而使得种群单 步骤3生成子种群.对S(t)中个体应用局部 一，使搜索陷入局部最优：第二，当进化后期个体 搜索得到改进后的子群S'(t).采用交叉和变异策略 适应度差异不大时，该方法选择能力较差.因此，本 生成S(t)种群的子代个体O(t). 文在轮盘赌选择方法的基础上提出一种动态调整的 步骤4更新种群.令tP(t)=S(t)US(t)U 适应度计算方法，基于迭代次数自适应地调整各粒 O(t),采用自适应局部搜索更新tP(t)中Y比例的 子被选择的概率，计算步骤如下： 优秀粒子，并根据适应值大小在更新后的P(t)中 (1)将个体粒子按评价指标由优到劣排序，并 挑选M个优秀个体构成新种群P(t+1). 依据粒子序数计算其原始适应度f片=1-k/M,其 步骤5重启机制.比较种群P(t)和P(t+1), 中k为第k个粒子在第t次迭代中的评价序数： 当种群优化停滞步数大于预设值，时采用混沌优化 (2)调整适应度F=ef,其中X为第t代 技术更新种群P(t+1)中适应度较低的(1-y)M 的调整系数，t=入min十（入max一入min)t/tmax: 个个体，从而更新种群P(t+1). (③)第k个粒子在第t次迭代中的选择概率 步骤6终止条件判断.判断迭代次数t是否 p味=F/∑F 等于tmax·若是，则转步骤7：否则，t=t+1,转步 2.1.3交叉和变异操作 骤3. 优秀个体对于种群进化具有至关重要的作用， 步骤7确定精英个体.采用评价指标衡量种 因此提出一种以优化子群为核心的分组交叉策略， 群P(t+1)中的个体质量，挑选出P(t+1)中最优 增强种群多样性的同时引导进化朝着更好的方向进 个体作为精英个体 行，如图1所示 2.1.1生成初始种群 交叉操作的关键在于选择待交叉个体及确定 随机产生初始种群带来的种群多样性有利于 交叉算子.对于改进后的子群S(t),将群内个体两 推动进化的发展，但同时可能导致较差的适应度 两交叉生成的个体全部作为子代个体，以最大程度

第 9 期 吴 迪等：基于精英重组的混合多目标进化算法 1209 ·· 2 基于精英重组的混合多目标进化算法 考虑多目标优化问题的复杂性及现有多目标 进化算法的特点，本节提出基于精英重组的混合多 目标进化算法，将多目标问题分解为多个单目标问 题单独求解，并在单目标问题非劣解集的基础上通 过精英重组确定唯一非劣解. 2.1 精英重组策略 对于多目标优化问题，各个单目标问题的非劣 解集可能并不完全相同，多个解集的交集即为实现 多目标优化的全局非劣解，而相异解则难以判断和 挑选. 因此，本文提出基于遗传算法的精英重组策 略，具体步骤如算法 1 所示 , 目的在于将相异解重 组生成一个唯一的精英解. 与精英保存策略 [16] 不 同，精英重组策略采用区域化方法产生高精度及多 样化的初始种群，对 Pareto 解集进行两次自适应局 部搜索及优化的交叉变异操作，同时采用基于混沌 优化的重启机制，有效解决了目标空间解的拥挤度 问题，同时避免了精英保存可能造成的局部最优， 保证种群快速地朝全局最优化方向发展. 算法 1 基于遗传算法的精英重组 步骤 1 初始化. 生成 M 个大小为 N 的个体 构成初始种群 P，设置选择比例 γ ∈ (0, 1)，最大进 化代数 tmax，迭代次数 t = 1. 步骤 2 选择优秀个体. 采用轮盘赌的方法在 P(t) 中挑选 γM 个优秀个体构成 S(t). 步骤 3 生成子种群. 对 S(t) 中个体应用局部 搜索得到改进后的子群 S 0 (t). 采用交叉和变异策略 生成 S 0 (t) 种群的子代个体 O(t). 步骤 4 更新种群. 令 tP(t) = S(t) ∪ S 0 (t) ∪ O(t)，采用自适应局部搜索更新 tP(t) 中 γ 比例的 优秀粒子，并根据适应值大小在更新后的 tP(t) 中 挑选 M 个优秀个体构成新种群 P(t + 1). 步骤 5 重启机制. 比较种群 P(t) 和 P(t + 1)， 当种群优化停滞步数大于预设值 τ 时采用混沌优化 技术更新种群 P(t + 1) 中适应度较低的 (1 − γ)M 个个体，从而更新种群 P(t + 1). 步骤 6 终止条件判断. 判断迭代次数 t 是否 等于 tmax. 若是，则转步骤 7；否则，t = t+1，转步 骤 3. 步骤 7 确定精英个体. 采用评价指标衡量种 群 P(t + 1) 中的个体质量，挑选出 P(t + 1) 中最优 个体作为精英个体. 2.1.1 生成初始种群 随机产生初始种群带来的种群多样性有利于 推动进化的发展，但同时可能导致较差的适应度 与收敛性. 由于算法 1 开始前已具有 m 个个体 Y ， 且 Y 分别为各目标函数的最优个体， 因此 本文提出一种区域化的种群初始化方法 (regional population initialization, RPI)，以期快速产生具有 较高精度和多样性的初始种群. 区域化种群初始 化方法由两步构成：(1) 在每个个体 Y 周围生成 ceil(M /m) 个粒子，生成方法见算法 2；(2) 计算所有 m·ceil(M /m) + m 个粒子的评价指标 [9] Pareto 逼近 度 (Pareto ranking) 和动态拥挤度 (dynamic crowd￾ing)，选择最优的 M 个粒子组成初始种群 P. 其中， 在优秀个体的选择上，首先选择占优的 Pareto 优化 前沿个体，当多个个体处于同一优化前沿时则选择 拥挤程度小的个体. 算法 2 初始粒子生成 For i =1:1:m // z(i, p) 表示个体 p 得到的函数 i 的取值，e 为搜索范围，y 表示生成的初始粒子 {k =1; While (k < M/m+1) {p =round(rand(1, N)); If (z(i, p)>= z(i, Y (i))∗ (1+e)) then {y(k) = p; k = k + 1; }}} 2.1.2 选择操作 轮盘赌法作为广泛适用的种群选择方法存在 两个问题：第一，由于高适应度的个体在进化初期 被选择的概率很大，产生出较多后代而使得种群单 一，使搜索陷入局部最优；第二，当进化后期个体 适应度差异不大时，该方法选择能力较差. 因此，本 文在轮盘赌选择方法的基础上提出一种动态调整的 适应度计算方法，基于迭代次数自适应地调整各粒 子被选择的概率，计算步骤如下： (1) 将个体粒子按评价指标由优到劣排序，并 依据粒子序数计算其原始适应度 f t k = 1−kt/M，其 中 kt 为第 k 个粒子在第 t 次迭代中的评价序数； (2) 调整适应度 F t k = e λ t ·f t k，其中 λ t 为第 t 代 的调整系数，λ t = λmin + (λmax − λmin)t/tmax； (3) 第 k 个粒子在第 t 次迭代中的选择概率 ρ t k = F t k / PF t k . 2.1.3 交叉和变异操作 优秀个体对于种群进化具有至关重要的作用， 因此提出一种以优化子群为核心的分组交叉策略， 增强种群多样性的同时引导进化朝着更好的方向进 行，如图 1 所示. 交叉操作的关键在于选择待交叉个体及确定 交叉算子. 对于改进后的子群 S 0 (t)，将群内个体两 两交叉生成的个体全部作为子代个体，以最大程度

·1210 北京科技大学学报 第35卷 地保留优秀后代.对于子群S(t)及P(t)-S(t),以 个体作为父代个体：若K=1则此个体即为父代个 随机次序择S'(t)内待交配个体，选并分别在S(t) 体：若K=0则选择子群内当前适应度最大的个体 和P(t)-S(t)内挑选与之对应的个体进行交叉操 作为父代个体.(2)已选择的个体均不能重复使用. 作.本文在文献[17]的基础上提出父代个体的挑选 POX算子1】作为当前性能较好的遗传算子能够 原则：(1)判断子群内适应度值大于待交配个体的 很好地继承父代的优良特性，因此可作为本文的交 个数K.若K>1则选择与待交配个体距离最近的 叉算子 子群S(t) 子群S(t) 子群Pt-S() 交配个体M个 交配个体M个 交配个体(1-)M个 交叉操作 子群内部 交叉操作 两两交叉 临时种群temp2(t) 临时种群templ(t) 临时种群tenp3(t) 子代个体个数yM 子代个体个数MM-1)/2 子代个体个数M TempO(t)=templ(t)+temp2(t)+temp3() 图1 基于优化子群的分组交叉策略 Fig.1 Packet crossover strategy based on the optimized subgroup 变异操作的关键在于确定变异概率、变异位数 由于变异位置应为整数，因此若计算得到的 及变异位置.本文采取文献[19]提出的自适应多位 k)非整，则取其上下两个整数均为变异位置.比 变异算子，其中变异概率0与变异位数K、的计算 较个体k经过混沌变异后的适应值，令花，表示适 见下式，变异位置采用随机方式确定 应度最大值所对应的变异位置，则更新决策变量的 搜索空间为 01 Fmax-Favg F装≥Fvg (4) Fk<Favg 2jmin =2j-w(zjmax -zjmin) (7) 之max=读，)十w(之jmax-2jmin） kk=NT(NI×(Fax-F)/(F克ax-Fi).(5) 其中，Fax、Fin及Fvg分别表示第t次迭代中 其中w为调整因子.为保证搜索范围满足约束，当 群体的最大适应度、最小适应度及平均适应度， min<之jmin时，令min=2min:当max>jmax 表示待变异个体k在第t次迭代中的适应度：0≤ 时，令2max=max。 1,2≤1；NI为常数，一般取N/4<NI<N/3. 同样采用Tent混沌映射公式生成混沌向量 2.1.4混沌优化 ”在新的取值范围[minmax内由式(6)得 随着进化过程的进行，精英个体将逐渐占据整 到新的混沌变量法将，与的线性组合作 个群体，使算法易于陷入局部最优.因此，本文引 为新的决策变量《： 入自适应混沌变异方法，采用Tet混沌映射3优 化个体的变异位置，并根据种群进化状态细化变量 张)=(（1-）十μ2k (8) 搜索空间. 其中，μ为自适应调节系数，与算法迭代次数相关 初始化决策变量.令KTk=K表示待优 2.2多目标进化算法流程 化个体k在第t次迭代中的变异位数，根据 基于以上提出的精英重组策略，下面给出基于 Tent混沌映射公式生成混沌向量ak,j,其中k∈ [1,(1-y)M,j∈[1，KTkJ.由决策变量的取值范围 精英重组的混合多目标进化算法的流程步骤 [min,2max]=[5,V-KTk+引可得到待优化个体 步骤1令迭代步骤T=1,设置迭代次数约 k的第j个变异位置k为： 束Tmax,指标初值m和m 步骤2将多目标优化模型转化为多个单目标 2k,j=2jmin+(之jmax-2jmin)·ak,j (6) 子模型.设待优化问题目标函数的个数为m,决策

· 1210 · 北 京 科 技 大 学 学 报 第 35 卷 地保留优秀后代. 对于子群 S(t) 及 P(t) − S(t)，以 随机次序择 S 0 (t) 内待交配个体，选并分别在 S(t) 和 P(t) − S(t) 内挑选与之对应的个体进行交叉操 作. 本文在文献 [17] 的基础上提出父代个体的挑选 原则：(1) 判断子群内适应度值大于待交配个体的 个数 K. 若 K > 1 则选择与待交配个体距离最近的 个体作为父代个体；若 K = 1 则此个体即为父代个 体；若 K = 0 则选择子群内当前适应度最大的个体 作为父代个体. (2) 已选择的个体均不能重复使用. POX 算子 [18] 作为当前性能较好的遗传算子能够 很好地继承父代的优良特性，因此可作为本文的交 叉算子. 图 1 基于优化子群的分组交叉策略 Fig.1 Packet crossover strategy based on the optimized subgroup 变异操作的关键在于确定变异概率、变异位数 及变异位置. 本文采取文献 [19] 提出的自适应多位 变异算子，其中变异概率 θ 与变异位数 Kv 的计算 见下式，变异位置采用随机方式确定. θ t k =    k1 F t max − F t k F t max − F t avg , Ft k > F t avg; k2, Ft k < Ft avg . (4) k t vk = INT(NI × (F t max − F t k )/(F t max − F t min)). (5) 其中，F t max、F t min 及 F t avg 分别表示第 t 次迭代中 群体的最大适应度、最小适应度及平均适应度，F t k 表示待变异个体 k 在第 t 次迭代中的适应度；0 6 k1, k2 6 1; NI 为常数，一般取 N/4 < NI < N/3. 2.1.4 混沌优化 随着进化过程的进行，精英个体将逐渐占据整 个群体，使算法易于陷入局部最优. 因此，本文引 入自适应混沌变异方法，采用 Tent 混沌映射 [13] 优 化个体的变异位置，并根据种群进化状态细化变量 搜索空间. 初始化决策变量. 令 KTk = Kt vk 表示待优 化个体 k 在第 t 次迭代中的变异位数， 根据 Tent 混沌映射公式生成混沌向量 αk,j，其中 k ∈ [1,(1 − γ)M], j ∈ [1, KTk ]. 由决策变量的取值范围 [zjmin, zjmax] = [j, N − KTk + j] 可得到待优化个体 k 的第 j 个变异位置 zk,j 为： zk,j = zjmin + (zjmax − zjmin) · αk,j . (6) 由于变异位置应为整数，因此若计算得到的 zk,j 非整，则取其上下两个整数均为变异位置. 比 较个体 k 经过混沌变异后的适应值，令 z ∗ k,j 表示适 应度最大值所对应的变异位置，则更新决策变量的 搜索空间为    z 0 jmin = z ∗ k,j − ω(zjmax − zjmin), z 0 jmax = z ∗ k,j + ω(zjmax − zjmin). (7) 其中 ω 为调整因子. 为保证搜索范围满足约束，当 z 0 jmin < zjmin 时，令 z 0 jmin = zjmin；当 z 0 jmax > zjmax 时，令 z 0 jmax = zjmax。 同样采用 Tent 混沌映射公式生成混沌向量 βk,j，在新的取值范围 [z 0 jmin, z0 jmax] 内由式 (6) 得 到新的混沌变量 z 0 k,j . 将 z 0 k,j 与 zk,j 的线性组合作 为新的决策变量 z 00 k,j： z 00 k,j = (1 − µ)z 0 k,j + µzk,j . (8) 其中，µ 为自适应调节系数，与算法迭代次数相关. 2.2 多目标进化算法流程 基于以上提出的精英重组策略，下面给出基于 精英重组的混合多目标进化算法的流程步骤. 步骤 1 令迭代步骤 T = 1，设置迭代次数约 束 Tmax，指标初值 µ e pm 和 µ e dm. 步骤 2 将多目标优化模型转化为多个单目标 子模型. 设待优化问题目标函数的个数为 m，决策

第9期 吴迪等：基于精英重组的混合多目标进化算法 1211· 变量的个数为n.分别计算m个子模型，令x,)为 所示的测试函数的最优参数， 第j个决策变量在第i个子模型的最优取值，则非 劣解集表示为X={x,1x,2,…,xi,n},i∈[1，m 表1两目标及三目标问题的测试函数参数设置 Table 1 Parameter settings for the 2-objective and 3- 步骤3确定X:的交集W及决策变量序号 objective test problems R,[W,={k=x,rk=j|工1j=…=xm,j∈ 测试函数 Tmax M Y tmax [1,nm,k=1&k=k+1}. ZDT1 200 150 0.2 200 步骤4判断R内决策变量的个数.若k=, ZDT2 400 150 0.3 400 说明各子模型非劣解完全相同，则此解即为多目标 ZDT3 400 100 0.3 800 优化模型的非劣解，转步骤9：若k<n,说明各子 ZDT4 200 100 0.2 200 DTLZ1 400 200 0.3 200 模型非劣解并不完全相同，转步骤5. DTLZ2 400 200 0.4 400 步骤5对于解集X的相异解D:=X:-W:= DTLZ3 400 300 0.4 400 {d,1d,2,…,d,N},i∈1，m,采用精英重组策略确 DTLZ4 800 300 0.2 200 定唯一非劣解D,其中N≤n. 步骤6基于交集中决策变量序号R,组合精 表2 多目标问题的测试函数参数设置 Table 2 Parameter settings for the multi-objective test 英解Xb=W+Db problems 步骤7计算X心的评价指标.若（中m < 测试函数 Tmax M Y tmax 哈m)‖($m=哈m&&哈m<m,则保留Xb为 DTLZ1-4 400 200 0.2 200 当前非劣解Xe,令哈m=中m,5m=巾m,4嵋m= DTLZ1-6 800 300 0.3 400 哈m,oin=im,转步骤8. DTLZ1-8 800 200 0.3 200 DTLZ2-4 400 200 0.3 200 步骤8判断T是否等于Tmax。若是则转步 DTLZ2-6 800 300 0.4 400 骤9：否则T=T+1,转步骤5. DTLZ2-8 400 300 0.3 400 步骤9算法终止，输出非劣解集X*=X及 注：测试函数的数字表示目标个数 最优评价指标m,5m:娟m,0m 2.3参数估计 根据种群选择及维持策略的不同，分别选择 参数设置对于所有启发式算法都是至关重要 NSGA-Ⅱ、MOPSO23及DVCMOA司作为 的.本文采取Ruiz和Stuitzle2o提出的实验分析法 ERHMEA的对比算法.各算法均独立运行30次， 进行参数估计.基于精英重组的混合多目标进化算 所得结果及分析如下. 法包括六个参数：迭代次数Tmax,指标初值Sm和 ZDT1ZDT4均具有10个决策变量，各算 m,遗传算法种群规模M,选择比例y及进化代 法得到的非劣目标域结果见图2，f五和2分 数tma·其中，指标初值对算法性能影响不大，可 别表示两个目标函数的目标值.由实验结果可看 设置为较大的正数.对于迭代次数和进化代数，当 出，NSGA-IⅡ结果距真实Pareto前沿距离较远， ANOVA分析结果相同时，均取较小值以获得更快 具有较差的收敛性：ERHMEA在四个问题中均表 的运行效率 现出最优的收敛性，且在ZDT3和ZDT4中分布 最为均匀：MOPSO在ZDT1中得到最优分布结 3仿真研究及结果分析 果，DVCMOA在ZDT2中得到最优分布结果.由以 3.1性能分析 上结果可得到，ERHMEA在解决ZDT问题时收敛 实验的目的在于研究算法在不同规模问题中 性最强，但均匀分布性有时不如MOPSO和DVC 的性能.选择ZDT1-ZDT421作为双目标测试问 MOA 题，DTLZ1-DTLZ422作为三目标测试问题，分 DTLZ1~DTLZ4均具有12个决策变量，各算 别具有4、6和8个目标函数的DTLZ1和DTLZ2 法收敛性与多样性的比较结果分别见表3和表4， 作为多目标测试问题 其中收敛性指标采用收敛矩阵C24表示，多样性 设置实验参数m=1000,娟m=1000, 指标采用分布矩阵△24表示，每个结果均由均值 Tmax=(100,200,400,800,1000),M=(100,150,(方差)构成.由实验结果可看出，NSGA-Ⅱ收敛性 200,300),y=(0.2,0.3,0.4,0.5),tmax=(100,200, 较差，其余三个算法在四个问题中均表现出最优的 400,800).通过参数估计，分别得到如表1和表2 收敛性，但相比较而言ERHⅢMEA的收敛性与多样

第 9 期 吴 迪等：基于精英重组的混合多目标进化算法 1211 ·· 变量的个数为 n. 分别计算 m 个子模型，令 xi,j 为 第 j 个决策变量在第 i 个子模型的最优取值，则非 劣解集表示为 Xi = {xi,1xi,2, · · · , xi,n}, i ∈ [1, m]. 步骤 3 确定 Xi 的交集 W 及决策变量序号 R，[W, R] = {wk = xi , rk = j | x1,j = · · · = xm,j , j ∈ [1, n], k = 1&k = k + 1}. 步骤 4 判断 R 内决策变量的个数. 若 k = n， 说明各子模型非劣解完全相同，则此解即为多目标 优化模型的非劣解，转步骤 9；若 k < n，说明各子 模型非劣解并不完全相同，转步骤 5. 步骤 5 对于解集 X 的相异解 Di = Xi −Wi = {di,1di,2, · · · , di,N }, i ∈ [1, m]，采用精英重组策略确 定唯一非劣解 Db，其中 N 6 n. 步骤 6 基于交集中决策变量序号 R，组合精 英解 Xb = W + Db . 步骤 7 计算 Xb 的评价指标. 若 (µ b pm < µ e pm) k (µ b pm = µ e pm && µ b dm < µe dm)，则保留 Xb 为 当前非劣解 Xe，令 µ e pm = µ b pm, σe pm = σ b pm, µe dm = µ b dm, σe dm = σ b dm，转步骤 8. 步骤 8 判断 T 是否等于 Tmax。若是则转步 骤 9；否则 T = T + 1，转步骤 5. 步骤 9 算法终止，输出非劣解集 X∗ = Xe 及 最优评价指标 µ e pm, σe pm, µe dm, σe pm. 2.3 参数估计 参数设置对于所有启发式算法都是至关重要 的. 本文采取 Ruiz 和 St¨utzle [20] 提出的实验分析法 进行参数估计. 基于精英重组的混合多目标进化算 法包括六个参数：迭代次数 Tmax，指标初值 µ e pm 和 µ e dm，遗传算法种群规模 M，选择比例 γ 及进化代 数 tmax. 其中，指标初值对算法性能影响不大，可 设置为较大的正数. 对于迭代次数和进化代数，当 ANOVA 分析结果相同时，均取较小值以获得更快 的运行效率. 3 仿真研究及结果分析 3.1 性能分析 实验的目的在于研究算法在不同规模问题中 的性能. 选择 ZDT1-ZDT4 [21] 作为双目标测试问 题，DTLZ1- DTLZ4 [22] 作为三目标测试问题，分 别具有 4、6 和 8 个目标函数的 DTLZ1 和 DTLZ2 作为多目标测试问题. 设置实验参数 µ e pm = 1000，µ e dm = 1000， Tmax =(100, 200, 400, 800, 1000)，M =(100, 150, 200, 300)，γ =(0.2, 0.3, 0.4, 0.5)，tmax=(100, 200, 400, 800). 通过参数估计，分别得到如表 1 和表 2 所示的测试函数的最优参数. 表 1 两目标及三目标问题的测试函数参数设置 Table 1 Parameter settings for the 2-objective and 3- objective test problems 测试函数 Tmax M γ tmax ZDT1 200 150 0.2 200 ZDT2 400 150 0.3 400 ZDT3 400 100 0.3 800 ZDT4 200 100 0.2 200 DTLZ1 400 200 0.3 200 DTLZ2 400 200 0.4 400 DTLZ3 400 300 0.4 400 DTLZ4 800 300 0.2 200 表 2 多目标问题的测试函数参数设置 Table 2 Parameter settings for the multi-objective test problems 测试函数 Tmax M γ tmax DTLZ1-4 400 200 0.2 200 DTLZ1-6 800 300 0.3 400 DTLZ1-8 800 200 0.3 200 DTLZ2-4 400 200 0.3 200 DTLZ2-6 800 300 0.4 400 DTLZ2-8 400 300 0.3 400 注：测试函数的数字表示目标个数. 根据种群选择及维持策略的不同，分别选择 NSGA-Ⅱ [1]、MOPSO [23] 及 DVCMOA [15] 作为 ERHMEA 的对比算法. 各算法均独立运行 30 次， 所得结果及分析如下. ZDT1∼ZDT4 均具有 10 个决策变量， 各算 法得到的非劣目标域结果见图 2， f1 和 f2 分 别表示两个目标函数的目标值. 由实验结果可看 出，NSGA-Ⅱ结果距真实 Pareto 前沿距离较远， 具有较差的收敛性；ERHMEA 在四个问题中均表 现出最优的收敛性，且在 ZDT3 和 ZDT4 中分布 最为均匀；MOPSO 在 ZDT1 中得到最优分布结 果，DVCMOA 在 ZDT2 中得到最优分布结果. 由以 上结果可得到，ERHMEA 在解决 ZDT 问题时收敛 性最强，但均匀分布性有时不如 MOPSO 和 DVC￾MOA. DTLZ1∼DTLZ4 均具有 12 个决策变量，各算 法收敛性与多样性的比较结果分别见表 3 和表 4， 其中收敛性指标采用收敛矩阵 C [24] 表示，多样性 指标采用分布矩阵 ∆ [24] 表示，每个结果均由均值 (方差) 构成. 由实验结果可看出，NSGA-Ⅱ收敛性 较差，其余三个算法在四个问题中均表现出最优的 收敛性，但相比较而言 ERHMEA 的收敛性与多样