第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 的收敛性与多样