·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] 首先基于目标空间中初始 方向向量将种群划分为多个子群，然后根据各子群 协同进化的相互作用求解多目标优化问题，并进一 步探讨欠开发区域以维持解空间的相对均匀分布. 尽管以上部分方法在一些基准案例中取得了 不错的表现，但由于现有算法在求解时均分别针对 两个目标，而未考虑解集收敛性与多样性的协同优 化，可能造成目标空间解拥挤、收敛速度慢、易早 熟等问题，因此需进一步研究快速的解空间搜索方 法以及简单有效的多样化策略