DMOEA-eC算法介绍 2019-01-16 20:40:13
    enlightenedenlightenedenlightened
    北京理工大学陈杰教授、李娟博士和专委会委员辛斌副教授关于ε-约束框架下基于分解的多目标进化算法DMOEA-εC求解多目标优化问题取得了新的进展,相关的研究成果在国际知名期刊《IEEE Transactions on Evolutionary Computation》上发表。



    分解是求解多目标优化问题的高效策略,该策略的成功性已在MOEA/D及其变体上得到验证。基于分解的方法利用标量化函数将多目标优化问题分解为一系列标量化子问题或简单多目标子问题。现有基于分解的多目标进化算法大都采用加权法、Tchebycheff 和PBI 等聚合函数,该论文综合数学规划领域的ε-约束法和分解策略提出ε-框架下基于分解的多目标进化算法DMOEA-εC。DMOEA-εC 选择一个主目标函数,通过给每个非主目标函数的可能取值分配一个上界将多目标优化问题分解为一系列单目标约束优化子问题。DMOEA-εC 利用基于可行性规则的进化算法同时优化所有子问题,且在优化每个子问题时仅用到其邻域子问题信息。

图1. ε-约束法示例

 

 文章主要贡献如下:
    1.  该文章首次尝试将ε-约束法融入分解策略,通过利用邻域信息协同优化一系列单目标约束优化子问题来求解多目标优化问题,这个想法促成了一个新的、有效的多目标进化算法DMOEA-εC。数值实验结果表明,DMOEA-εC求解多数连续基准问题时的性能不劣于比较算法,求解多目标0-1背包问题时展现出明显优势。
    2.  在ε-约束框架下,DMOEA-εC倾向于为每个子问题保留其可行解,而这样会对主目标函数的优化造成不利影响,因此提出周期性地切换主目标来解决这一问题。
    3.  在采用了主目标切换策略之后,由于所有子问题的主目标函数发生了改变,在切换之前对当前解性能较好的解可能对切换主目标之后的子问题性能会变差。因此提出解-子问题匹配机制来为每个子问题分配距离其最近的解,该匹配机制在主目标切换策略之后使用。
    4.  当交叉变异生成新解时,该新解可能对当前子问题性能不佳,而对其他子问题性能较好。为了避免浪费潜在优秀解并充分利用这些新解,文中提出在生成新解之后利用子问题-解匹配机制来为新解找到具有约束违反值最小的子问题,上述两个匹配机制主要用于平衡收敛性和多样性。

 


图2. DMOEA-εC求解连续测试算例时得到最小IGD 值时的种群分布

图3. DMOEA-εC求解两目标MOKP 算例时得到最小IGD 值时的种群分布

 

    该工作得到国家自然科学基金(61673058, U1609214, 61304215)、国家自然科学基金创新研究群体(61321002)、重点(地区)合作研究项目(61120106010)、北京市优博基金(20131000704)、高等学校博士学科点专项科研基金(20131101120033)的资助。
相关论文及源码下载链接
http://pris.bit.edu.cn/rydw/qtry/xinbin.htm
论文信息
TitleDMOEA-εC: Decomposition-Based Multiobjective Evolutionary Algorithm With the ε-Constraint Framework
Authors: Jie Chen, Juan Li, Bin Xin
Journal: IEEE Transactions on Evolutionary Computation, 2017, 21(5): 714–730
DOI10.1109/TEVC.2017.2671462
全文链接
https://ieeexplore.ieee.org/document/7858787