2018, Vol. 33
在绝大多数多目标优化问题中, 不同的优化目标之间存在相互冲突, 即不存在一个最优解使得所有m维优化目标均最优.因此, 决策者通常需要寻找在某种度量方式下能够平衡不同优化目标的最优解集.为了解决这一问题, 有学者提出了一个针对多目标优化问题的最优解的概念——Pareto最优解[1].
一个多目标优化问题(Multiobjective optimization problem, MOP)可以表示为
|
(1) |
其中: Ω表示搜索空间的可行域; x=(x1, x2, …, xn)表示n维的决策向量; 在函数F:Ω→Rm中, m表示目标函数f1(x), …, fm(x)的数量, Rm表示目标空间.
令x, y∈Ω, 若对于任意i∈{1, 2, …, m}, 有fi(x)≤fi(y), 且存在j∈{1, 2, …, m}使得fj(x) < fj(y), 则称x支配y, 记作F(x)
决策者面对的实际问题往往具有较为复杂的形式, 传统的优化求解方法不能很好地解决这些问题.而事实上, 决策者只需要得到PF的近似解集, 并不需要得到精确的PF.一般情况下, 决策者关注近似性和多样性两个指标, 这两个指标分别衡量了近似解集与PF的距离和分布均匀情况.基于上述原因, 采用启发式的优化算法处理多目标优化问题是一个好的思路, 其中多目标进化算法(Multiobjective evolutionary algorithms, MOEAs)由于其天然的并行特性, 在过去的20年中吸引了绝大多数研究者的目光, 并形成了一系列优秀算法[2-3].这些多目标进化算法大致可分为基于支配关系、基于标示和基于分解3类.
随着处理的优化问题日益复杂, 基于支配关系和基于标示两种方式的多目标进化算法逐渐暴露出一些不足之处[4].在过去10年左右的时间里, 基于分解框架的MOEA吸引了大多数研究者的目光, 并陆续提出了MOEA/D[5]以及其他优秀的改进算法, 包括MOEA/D-DE[6]、MOEA/D-DRA[7]、MOEA/D-STM[8]、MOEA/DD[9]、NSGA-Ⅲ[10]、MOEA/D-AGR[11]等.对于基于分解的多目标进化算法而言, 选择策略是子问题分别选择适合解的过程; 在选择解时, 绝大多数MOEA/D改进算法只考虑了收敛性, 而用子问题之间的区别来控制多样性.MOEA/D-STM在子问题与解之间建立了互倾向的评价指标, 利用解对子问题的倾向值显性地控制多样性, 取得了较好的效果.在文献[8]的基础上, 本文从处理子问题与解的相互关系角度出发, 将解的选择建模成有权偶图最优匹配问题进行求解, 从而在平衡多样性和收敛性的前提下, 为每个子问题分配一个适合解.在此基础上, 本文提出一种新的算法MOEA/D-BM(Multiojective evolutionary algorithm based on decomposition with bigraph matching).通过与其他算法在标准测试集函数上的对比实验, 验证了本文所提出算法的有效性.
1 多目标分解进化算法本节简要介绍多目标分解进化算法MOEA/D的核心思想, 给出算法的基本流程, 并对算法中使用的选择策略存在的缺陷进行分析.
1.1 多目标分解进化算法的实现在多目标分解进化算法MOEA/D中, 多目标优化问题被分解成N个单目标优化子问题, 每个子问题对应一个权重向量λ=(λ1, …, λm), 其中λi ≥ 0, i=1, 2, …, m, 且
|
(2) |
其中: λ=(λ1, …, λm)T是预先设定的均匀分布的权重向量, 对于所有i∈{1, …, m}, 有λi≥ 0, 且λi=1.当
MOEA/D的一个核心思想是构建子问题之间的邻居关系.通常来讲, 由于权重向量的距离较小, 子问题与对应邻居子问题拥有相似的最优解.因此, MOEA/D提出了邻居的思想, 并针对繁殖交配和替换选择维护了邻居集合, 在选择交配个体和替换个体时均从相应的邻居集合里选择.
在MOEA/D中, 多目标优化问题被分解成N个单目标优化子问题, 每个子问题pi对应一个权重向量λ, 算法维护一个大小为N的种群, 其中每一个个体对应一个子问题.MOEA/D计算权重向量之间的距离, 依照距离的大小为每个子问题构建邻居集合.每次得到下一代的新个体时, 都在其对应子问题的邻居子问题上与现有个体比较, 择优替换.MOEA/D的基本流程如下.
Step 1:初始化种群、权重向量、邻居大小等参数.
Step 2:进行繁殖交配.利用该子问题对应的个体解xi与邻居集合Tm(i)中随机选取的解产生下一代解xi.
Step 3:进行选择替换.对于邻居集合Tr(i)中每一个个体解xj, 如果针对子问题pj对应的目标函数gj(xj), 有gj(xi) < gj(xj), 则用xi替换xj.
Step 4:迭代次数加1.若算法达到终止条件, 则返回结果; 否则返回Step 2.
1.2 选择策略分析在MOEA/D以及一些改进算法中, 对下一代解的选择是基于子问题的取值, 也就是说, 这些算法的选择策略显式地考虑收敛性, 而利用不同子问题的区别和分布对多样性进行控制.如图 1所示, 解a和解b分别是子问题p1和p2产生的解, 对于子问题p2而言, 当采用切比雪夫法作为分解方法时, 由于解a在子问题p2上的取值小于解b, 故解a优于解b.然而, 如果衡量解到子问题的垂直距离, 则解a接近子问题p1, 而解b接近子问题p2; 如果算法选择解a作为子问题p2的下一代解, 则子问题p2最终得到的最优解会接近于子问题p1与PF交点附近, 这样的解与子问题p1本身的解距离较小, 如此一来, 算法最终得到解集的多样性会受到影响.为了得到分布均匀的解集, 本文试图在考虑解的子问题取值的基础上, 考虑解到子问题的距离这一关键因素, 从而在解的选择上综合考虑收敛性和多样性.
|
图 1 下一代解的选择 |
基于上一节对多目标分解进化算法中选择策略的分析, 本文设计了一种基于有权偶图最优匹配的模型, 用于在子问题和解之间建立关联关系.本文提出的选择策略同时考虑解在子问题上的适应值以及解与子问题的垂直距离两个因素, 即能够平衡解的收敛性和多样性两种需求.
2.1 有权偶图的最优匹配MOEA/D中的选择策略即为每一个子问题选择一个适合的解.假设对于一个多目标优化问题, 有N个子问题和M个解, 子问题与解两两之间均有一个确定的适应值, 这样的关系可以用有权偶图进行建模.如图 2所示, 上部的点表示N个不同的子问题, 下部的点表示M个不同的解, 子问题与解之间存在赋权边的连接.
|
图 2 由子问题和解构成的有权偶图匹配问题 |
试图找到N条赋权边连接N个不同的子问题和M个解中的N个不同的解, 使得边的权值之和最大.为了给N个子问题找到N个适合的解, 可以使用Kuhn-munkres(KM)算法进行求解.KM算法的实现是基于偶图完美匹配求解的经典算法——匈牙利算法, 通过给定并不断修改偶图的可行顶点标号, 直到在某个相等子图中找到一个完美匹配为止.KM算法的具体步骤参见文献[13-14].对于本文构建的有权偶图而言, 通常有M>N, 故需要使用KM算法找到N组匹配.KM算法得到的最优匹配是具有最大权和的匹配.下面对边的赋权进行分析.
2.2 有权偶图的赋权令d⊥(xi, pj)表示解xi到子问题pj的垂直距离, 则有
|
(3) |
其中λ表示子问题pj对应的权重向量.式(3)的结果即为解xi在目标空间上的取值F(xi)与子问题pj对应的权重向量λ的欧氏距离.例如图 1所示的二维目标空间, 解b到子问题p2的距离即为点到射线的垂线段长度.
对每个解xi依照式(3)计算与子问题的垂直距离, 并将距离最小的Kv个子问题的编号保存下来, 构成长度为Kv的数组
|
(4) |
将数组
|
(5) |
若数组ψj的大小小于Ke, 则在剩下的解中选择子问题取值较优的解依次补充, 直到数组大小等于Ke.于是, 对连接解xi和子问题pj的边eji赋值如下:
|
(6) |
本文首先根据解与权重向量的垂直距离将权重向量对每个解进行排序, 这里只考虑选择与权重向量距离较近的若干解, 体现了对多样性的要求; 之后, 将上述结果表示成不同解对应权重向量的形式, 由于搜索空间的复杂性, 可能出现不同权重向量对应解的数量差别很大的结果, 算法为每个权重向量对应解的数量设定一个限值, 依照子问题的取值对解进行补充或筛选, 并进行排序, 这里的顺序即权重向量选择解的优先次序; 最后, 根据上述次序得到权重向量与解之间边的赋值, 应用KM算法获得最优匹配, 从而得到选择的下一代解.
2.3 繁殖算子差分进化算子和多项式变异算子已经被证明对于大多数多目标优化问题是高效的.设当前解xj为第1个参与交配的解x1r, 其他两个参与解xr2、xr3均从交配池中选取, 则根据差分杂交公式得到的中间解yi=(y1i, …, yni)计算方式如下:
|
(7) |
其中: CR和F是控制参数, rand是[0, 1]之间的随机数.下一步, 依照多项式变异公式计算新解xi = (x1i, …, xni), 如下所示:
|
(8) |
其中
|
(9) |
η和pm是控制参数, rand是[0, 1]之间的随机数, ak、bk是决策变量第k维的下界和上界.
2.4 MOEA/D-BM算法流程将偶图匹配的思想引入多目标分解进化算法, 构成MOEA/D-BM算法.算法流程如下.
Step 1:确定多目标优化问题、算法停止条件、种群大小N、邻居集合大小T以及偶图匹配控制参数Kv和Ke.随机初始化种群P ← {x1, …, xN}, 初始化权重向量λ ← {λ1, …, λN}, 初始化理想参考点z*.迭代次数初始化为0.
Step 2:依照式(7)~(9)对当前种群进行繁殖操作, 得到新解集合.
Step 3:将新解集合U与当前种群解集合组成混合解集合, 依照式(3)~(6)计算子问题与混合解集合中解的连接权.
Step 4:根据KM算法为每个子问题匹配解, 从而得到下一代解集合.
Step 5:迭代次数加1, 判断算法是否达到停止条件, 若达到, 则算法停止, 输出解集作为优化结果; 否则返回Step 2.
3 实验分析 3.1 实验设计为了证明本文所提出算法的有效性, 选择3种优秀的多目标分解进化算法进行对比测试, 这3种算法分别是MOEA/D-DE、MOEA/D-DRA以及MOEA/D-STM.其中: MOEA/D-DE是在经典算法MOEA/D的基础上使用差分算子进行了改进; MOEA/D-DRA对每个子问题的计算资源进行动态分配, 并获得了CEC2009的最佳算法奖; 而MOEA/D-STM首先使用了一个针对子问题和解的匹配模型来选择下一代解, 取得了一定的效果.
本文选用测试集DTLZ1~DTLZ7[15]、F1 ~F9 [16]以及MOP1~MOP7[17], 这些测试函数的特征如表 1所示.
|
表 1 测试函数特征 |
参照文献[5-6], 相关算法的参数设置如下:种群大小为300;分解方法选择切比雪夫法, 如式(2)所示; 算法停止条件为目标函数计算次数, DTLZ1~DTLZ7测试函数设置为100 000, F1~F5和F7~F9测试函数设置为150 000, F6和MOP1~MOP5测试函数设置为300 000, MOP6和MOP7测试函数设置为900 000;繁殖操作中, 差分算子参数设置为CR= 1.0, F=0.5, 多项式变异算子参数设置为pm=1/n, ηm=20;邻居大小为20;每个算法在每个测试函数上独立运行20次.
与其他3种算法不同, 参数Kv和Ke是本文所提出的算法特有的两个参数.这两个参数决定了有权偶图中非零权重边的数量, 从而控制了算法在选择下一代解时每个子问题需要考虑的解集大小.若参数Kv和Ke的取值过小, 则每个子问题对应解的个数有限, 解的多样性无法得到很好的保证; 若取值过大, 则在算法性能没有本质提升的情况下, 算法的时间复杂度进一步增大.通过多次尝试, 发现在这两个参数的取值增大至10和20的过程中, 算法得到的最终解集的IGD指标评价是逐渐变好的; 继续增大两个参数的取值, 则结果变化并不明显.故本文算法的参数Kv和Ke分别设置为10和20.
为了对不同算法的性能进行对比, 本文选择了常用的性能度量方法IGD[18]对实验结果进行分析.令P*表示PF上均匀分布的点的集合, S表示通过算法得到的最优解集, 则相应的IGD值通过下式计算:
|
(10) |
其中: dist(x, S)表示点x到集合S中最近点的欧氏距离, |P*|表示参考最优解集合P*的大小.在本文实验中, 对二维目标函数, |P*|的大小设置为1 000;对三维目标函数, |P*|的大小设置为10 000.IGD能够同时对收敛性和多样性进行度量, IGD的值越小, S对PF的近似度越优.
3.2 实验结果和分析 3.2.1 DTLZ1~DTLZ7测试函数上的实验结果和分析DTLZ1~DTLZ7测试函数的PS是线性的.4种算法在DTLZ1~DTLZ7上的IGD均值对比结果如表 2所示.
|
|
表 2 DTLZ1~DTLZ7测试函数上IGD均值对比 |
由表 2可以看到:在7个测试函数中, 本文所提出的算法MOEA/D-BM在DTLZ1~DTLZ5测试函数上表现最优, 而MOEA/D-DE和MOEA/D-DRA分别在DTLZ6和DTLZ7上表现最优; 尽管本文提出的算法在DTLZ6和DTLZ7测试函数上表现不是最优, 但与最优值差距不大; MOEA/D-STM尽管没有最优值, 但表现较为稳定.由于DTLZ测试集中测试函数的PS是线性的, 与F1~F9以及MOP1~MOP7相关测试函数相比, DTLZ测试集难度较小, 4种算法在DTLZ测试集上并无明显差距.
3.2.2 F1~F9测试函数上的实验结果和分析F1~F9是具有复杂PS的测试函数.4种算法在F1~F9上的IGD均值对比结果如表 3所示.
|
|
表 3 F1~F9测试函数上的IGD均值对比 |
由表 3可以看到:在9个测试函数中, 本文算法在F2、F4~F7五个测试函数上表现最优, 而MOEA/D-DRA在F1和F3上表现最优, MOEA/-STM在F8和F9上表现最优, 本文所提出算法在测试函数F5~F7上占优, 4种算法在其他测试函数上并无明显差距.
图 3为4种算法在测试函数F7上运行20次后得到的最优IGD度量值结果对比.可以看出, MOEA/D-DE、MOEA/D-DRA和MOEA/D-STM均有野点存在, 而本文算法MOEA/D-BM并无野点, 表现较优.
|
图 3 4种算法在F7测试函数上的结果对比 |
MOP1~MOP7测试函数同样具有较为复杂的形式.4种算法在MOP1~MOP7上的IGD均值对比结果如表 4所示.
|
|
表 4 MOP1~MOP7测试函数上的IGD均值对比 |
由表 4可以看到:本文算法在MOP1、MOP4~MOP6共4个测试函数上表现最优, 而MOEA/D-DRA在MOP2和MOP7测试函数上最优, MOEA/D-STM在MOP3测试函数上最优.本文算法在测试函数MOP1、MOP5、MOP6上与其他3种算法相比具有优势, 而4种算法在其他测试函数上并无较大差距.
图 4为4种算法在测试函数MOP1上运行20次后得到的最优IGD度量值结果对比.可以看出, MOEA/D-DE、MOEA/D-DRA和MOEA/D-STM均不能对PF完全覆盖, 解的多样性较差, 而本文算法MOEA/D-BM基本实现了对PF的覆盖, 优势明显.总体而言, MOEA/D-DE、MOEA/D-DRA以及MOEA/D-STM三种算法在不同的测试函数上得到的结果差别较小, 而MOEA/D-BM能够在多个测试函数上与其他3种算法拉开差距, 这说明了保持解的多样性的重要性.
|
图 4 4种算法在MOP1测试函数上的结果对比 |
对4种算法在测试函数DTLZ1~DTLZ7上分别运行10次, 对运行时间进行比较.为了消除不同性能计算机带来的影响, 记录各自的总运行时间与MOEA/D-DE总运行时间的比值, 结果如表 5所示.
|
|
表 5 算法的运行时间对比 |
从表 5可以看出, MOEA/D-DE、MOEA/D-DRA的运行时间较短, MOEA/D-STM次之, 本文提出的MOEA/D-BM的运行时间最长.这是由于MOEA/D-DE和MOEA/D-DRA在下一代解的选择上未考虑保持解的多样性, 而后两种算法通过各自的方式考虑了在选择时保持解的多样性, 在牺牲了一定时间效率的同时提升了算法的性能.与MOEA/D-STM中的匹配模型相比, 本文提出的MOEA/D-BM中的有权偶图匹配模型复杂度较高, 导致算法用时更长.
4 结论选择策略是影响基于分解的多目标进化算法的一个重要组成部分.目前大多数多目标分解进化算法中的选择算子并未考虑维持种群的多样性, 这可能会对最终解集的分布性产生影响.本文从改进选择策略的角度出发, 提出了采用有权偶图最优匹配对解的选择进行建模的思路, 在解的选择过程中同时考虑了多样性和收敛性, 从种群整体最优的角度选择下一代解, 并由此提出了新的算法MOEA/D-BM.与其他优秀算法在公开测试集上的对比实验表明了本文所提出算法的有效性.
从实验结果可以发现, 本文提出的MOEA/D-BM尽管在大多数测试函数上的表现优于其他优化算法, 但是由于有权偶图匹配的时间效率较低, MOEA/D-BM与其他算法相比耗时较长.如何在不影响MOEA/D-BM性能的前提下提升算法的时间效率, 是今后研究的重点.
| [1] |
Deb K, Kalyanmoy D. Multi-objective optimization using evolutionary algorithms[M]. New York: John Wiley & Sons, 2001.
|
| [2] |
蓝艇, 刘士荣, 顾幸生. 基于进化算法的多目标优化方法[J]. 控制与决策, 2006, 21(6): 601-605. (Lan T, Liu S R, Gu X S. Approaches of evolutionary multiobjective optimization[J]. Control and Desision, 2006, 21(6): 601-605. DOI:10.3321/j.issn:1001-0920.2006.06.001) |
| [3] |
公茂果, 焦李成, 杨咚咚, 等. 进化多目标优化算法研究[J]. 软件学报, 2009, 20(2): 271-289. (Gong M G, Jiao L C, Yang D D, et al. Research on evolutionary multi-objective optimization algorithms[J]. J of Software, 2009, 20(2): 271-289.) |
| [4] |
Giagkiozis I, Purshouse R C, Fleming P J. An overview of population-based algorithms for multi-objective optimisation[J]. Int J of Systems Science, 2015, 46(9): 1572-1599. DOI:10.1080/00207721.2013.823526 |
| [5] |
Zhang Q, Li H. MOEA/D: A multiobjective evolutionary algorithm based on decomposition[J]. IEEE Trans on Evolutionary Computation, 2007, 11(6): 712-731. DOI:10.1109/TEVC.2007.892759 |
| [6] |
Li H, Zhang Q. Multiobjective optimization problems with complicated pareto sets, MOEA/D and NSGA-Ⅱ[J]. IEEE Trans on Evolutionary Computation, 2009, 13(2): 284-302. DOI:10.1109/TEVC.2008.925798 |
| [7] |
Zhang Q, Liu W, Li H. The performance of a new version of MOEA/D on CEC09 unconstrained MOP test instances[C]. IEEE Congress on Evolutionary Computation. Trondheim: IEEE, 2009: 203-208.
|
| [8] |
Li K, Zhang Q, Kwong S, et al. Stable matching-based selection in evolutionary multiobjective optimization[J]. IEEE Trans on Evolutionary Computation, 2014, 18(6): 909-923. DOI:10.1109/TEVC.2013.2293776 |
| [9] |
Li K, Deb K, Zhang Q, et al. An evolutionary many-objective optimization algorithm based on dominance and decomposition[J]. IEEE Trans on Evolutionary Computation, 2015, 19(5): 694-716. DOI:10.1109/TEVC.2014.2373386 |
| [10] |
Deb K, Jain H. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, Part I: Solving problems with box constraints[J]. IEEE Trans on Evolutionary Computation, 2014, 18(4): 577-601. DOI:10.1109/TEVC.2013.2281535 |
| [11] |
Wang Z, Zhang Q, Zhou A, et al. Adaptive replacement strategies for MOEA/D[J]. IEEE Trans on Cybernetics, 2016, 46(2): 474-486. DOI:10.1109/TCYB.2015.2403849 |
| [12] |
Giagkiozis I, Purshouse R C, Fleming P J. Generalized decomposition[M]. Evolutionary Multi-Criterion Optimization. Berlin: Springer Berlin Heidelberg, 2013, 428-442.
|
| [13] |
Kuhn H W. The hungarian method for the assignment problem[M]. 50 Years of Integer Programming 1958- 2008. Berlin: Springer Berlin Heidelberg, 2010: 83– 97.
|
| [14] |
Munkres J. Algorithms for the assignment and transportation problems[J]. J of the Society for Industrial & Applied Mathematics, 1957, 5(1): 32-38. |
| [15] |
Deb K, Thiele L, Laumanns M, et al. Scalable multi-objective optimization test problems[C]. Proc of the 2002 Congress on Evolutionary Computation. Honolulu: IEEE, 2002: 825-830.
|
| [16] |
Li H, Zhang Q. Comparison between NSGA-Ⅱ and MOEA/D on a set of multiobjective optimization problems with complicated pareto sets, MOEA/D and NSGA-Ⅱ[J]. IEEE Trans on Evolutionary Computation, 2009, 13(2): 284-302. DOI:10.1109/TEVC.2008.925798 |
| [17] |
Liu H L, Gu F, Zhang Q. Decomposition of a multiobjective optimization problem into a number of simple multiobjective subproblems[J]. IEEE Trans on Evolutionary Computation, 2014, 18(3): 450-455. DOI:10.1109/TEVC.2013.2281533 |
| [18] |
Bosman P A N, Thierens D. The balance between proximity and diversity in multiobjective evolutionary algorithms[J]. IEEE Trans on Evolutionary Computation, 2003, 7(2): 174-188. DOI:10.1109/TEVC.2003.810761 |