前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >论文研读-用于约束多目标优化的新型双阶段双种群进化算法补充材料

论文研读-用于约束多目标优化的新型双阶段双种群进化算法补充材料

作者头像
演化计算与人工智能
发布2022-03-31 16:19:31
1.2K0
发布2022-03-31 16:19:31
举报

论文研读-用于约束多目标优化的新型双阶段双种群进化算法补充材料

A Novel Dual-Stage Dual-Population Evolutionary Algorithm for Constrained Multi-Objective Optimization

  • 最近我在学习约束多目标问题的论文,其中由明博士和张教授发表在TEVC上的DD-CMOEA非常不错~
  • 原文链接 ---也埋在阅读原文中
  • 此篇文章为 M. Ming, R. Wang, H. Ishibuchi and T. Zhang, "A Novel Dual-Stage Dual-Population Evolutionary Algorithm for Constrained Multi-Objective Optimization," in IEEE Transactions on Evolutionary Computation, doi: 10.1109/TEVC.2021.3131124. 的论文学习笔记,只供学习使用,不作商业用途,侵权删除。并且本人学术功底有限如果有思路不正确的地方欢迎批评指正!

1.LITERATURE REVIEW

  • 代表作品总结在表1,这个综合表包含了现有作品的主要特征和局限性。最后,我们将本文提出的算法(即DD-CMOEA)列在该表的末尾,以显示其对于专业文献的独创性。

2.ILLUSTRATION OF DIFFERENT PHASES OF TWO STAGES

  • 以MW9为例,以实际种群(100个个体)为例,展示了算法在探索和开发阶段的性能,如图1和图2所示-其中虚线表示的是划分的子域。
  • 在开发阶段,mainPop和auxPop被设计成协同收敛于真实PF,即分别从可行和无约束PF向真实PF靠拢。图3以两个案例为例,说明了两个种群在开发阶段的移动方向。
  • 在case1的例子中,尚未被发现的可行域在真实PF附近,然而未约束的PF距离尚未发现的可行域很远。从图3(a)中可以看出当当前可行解在区域A中时,不可行解在B中情况比在C中好。即B中的解对于找到真实的PF更加有帮助。由于无约束PF与真实的PF相差甚远,因此该算法可能需要较长的计算时间才能收敛到无约束PF,并将不可行解推回真实的PF。在Case2的例子中,尚未发现的可行解接近真实 PF,无约束 PF 也接近真实 PF。因为无约束的 PF 距离真实的 PF 不远,所以 auxPop 在开发阶段开始和结束时的位置相距不远。在这种情况下,不可行解从区域 C 移动到区域 B 需要更少的时间。

3.EXPLANATION OF THE SETTING OF THE SWITCHING CONDITION

  • 在主文件中,rta、rtz 和 rtn 中的最大值用于表示总体的变化率。下面解释我们选择使用最大值而不是最小值或平均值的原因。
  • 我们使用 rta、rtz 和 rtn 中的最大值是为了保证只有当 rta、rtz 和 rtn 都小于阈值时,才进行阶段切换。即只有当总体目标值的平均、最佳和最差值几乎不变时,才能认为总体收敛达到稳定状态。设置这么严格的条件,可以避免我们对一些问题的误判。
  • 表 II 和图 4 显示了一个简单的例子,其中考虑了六个个体的种群。从表二和图4可以看出,尽管种群仍在探索新的地区,平均点从第1代到第2代没有变化,估计的理想点和估计的最低点从第2代到第3代没有变化。在这种情况下,如果我们用 rta、rtz 和 rtn 的最小值或平均值来判断,种群可能会提前进入开发阶段。
  • 为了给探索阶段分配足够的搜索努力,我们在判断是否满足切换条件时选择最大操作。这样,对于大多数(如果不是全部)问题,种群(auxPop)将在探索阶段结束时接近无约束的 PF。
  • 之所以只考虑auxPop的变化率,是因为mainPop会受到不可行区域的影响,在某些情况下会停留在可行区域,而auxPop不考虑约束,可以一路探索以更快的前向搜索速度前进。因此mainPop在探索阶段获得的变化率普遍低于auxPop。因此,当 auxPop 的变化率低于阈值时,mainPop 的变化率也低于阈值。因此,为了节省计算时间,我们只计算了 auxPop 的变化率

4. COMPARISON WITH VARIANTS

4.1 Effectiveness of the Sequential Algorithmic Scheme Between Two Phases

  • 为了检查 DD-CMOEA 中两个阶段之间的顺序算法方案的有效性,我们设计了一个变体(名为 DD-CMOEA-Alter),它在探索和利用之间交替搜索。请注意,两个版本中的所有运算符都是相同的。唯一的区别是 DD-CMOEA-Alter 在开发阶段额外考虑了切换条件。新增的切换条件与探索阶段使用的类似。即当从 auxPop 计算的变化率(rt)小于阈值时,搜索可以再次切换到探索阶段。因此,DD-CMOEA-Alter 可能会经历多个探索和开发阶段。
  • 表 III 显示了 DD-CMOEA 和 DD-CMOEA-Alter 在三个测试套件上的 IGD 结果。从表 III 中可以看出,除了 MW11、LIRCMOP5 和 LIRCMOP9 之外,DD-CMOEA 在几乎所有问题上都比 DD-CMOEA-Alter 具有更好或相当的性能。DD-CMOEA的整体性能较好,说明本文提出的顺序算法方案是合理的。当然,DD-CMOEA-Alter也有其自身的优势,即充分探索可以使其在某些问题上的表现更加鲁棒,比如LIRCMOP5和LIRCMOP9。但同时也带来了以下问题:如果搜索可以在探索和利用之间交替,很可能当群体在探索阶段之后再次转向探索时,他会重新探索已经探索过了的部分。在这种情况下,获得新的有用解决方案的可能性很小。因此,这种替代操作可能会降低搜索的效率。这也是为什么 DD-CMOEA-Alter 在大多数问题上的表现不如 DD-CMOEA 的原因。
  • 同时,也在复杂的CMOPs上对两者的性能进行了比较。如表格4和图5所示

4.2 Determination of the Baseline Optimizer

  • 实际上,双阶段双种群框架可以嵌入不同的基线优化器。在这里,我们以 MOEA/D 和 SPEA2 为例,将它们嵌入到框架中并比较它们的性能。基于 SPEA2 的版本在主文件中有详细描述。基于 MOEA/D 的版本和基于 SPEA2 的版本的主要区别在于生成新解决方案和环境选择的方式。为了便于描述,我们将基于 MOEA/D 的版本表示为 DD-CMOEA-D。事实上,双阶段双种群框架可以嵌入不同的基线优化器。这里,我们以MOEA/D和SPEA2为例,将它们嵌入到框架中,并比较它们的性能。主文件中详细描述了基于SPEA2的版本。基于MOEA/D的版本和基于SPEA2的版本之间的主要区别在于生成新解决方案和环境选择的方式。为了便于描述,我们将基于MOEA/DBA的版本表示为DD-CMOEA-D。在DD-CMOEA-D中,当选择父集合以生成新的解决方案时,从邻域中选择的概率为90%,从整个群体中选择的概率为10%。这些规范(即90%和10%)基于一些现有的研究,例如[13],[14],这些规范报告了良好的实验结果。因为允许交配父母以较低的概率(即10%)从整个种群中进行选择,除了基于局部交配的利用外,还可以利用基于全局交配的探索。DD-CMOEA-D中的交叉和变异算子与MOEA/D中使用的算子相同。至于DD-CMOEA-D中的环境选择,根据它们的标度化函数值对解决方案进行比较。
  • 由DD-CMOEA和基于MOEA/D的变体(命名为DD-CMOEA-D)在31次独立试验中获得的IGD结果总结在表V中。我们从表V中观察到,i)DD-CMOEA-D在六个LIRCMOP问题上显著优于DD-CMOEA,包括LIRCMOP5–8和LIRCMOP13–14;对于其他30个问题,DD-CMOEA表现更好。这六个问题(即LIRCMOP5–8和LIRCMOP13–14)有一个共同点,即它们的约束PF和非约束PF相对接近,约束PF是连续的。这些结果表明,DD-CMOEA-D善于处理此类问题。相比之下,DD-CMOEA的整体性能更好,适合处理更广泛的问题。DD-CMOEA的优点可能来自两个方面:i)在选择父集合时,执行锦标赛选择。这种操作可能有助于提高DD-CMOEA的收敛能力;ii)在生成新解时,整个父集合的交叉和变异可能有助于DD-CMOEA获得具有广泛分布的新解,这有助于解决具有不连续PF的问题。
  • 鉴于上述实验结果和分析,我们建议在双阶段双种群框架中嵌入SPEA2作为基线优化器,这也是主文件中当前描述的版本。

4.3 Determination of the Initialization Method

  • 此处对于初始化的方法进行讨论,正文中使用的是均匀分布的初始化方法。在另一个版本中使用拉丁超立方体抽样(LHS)方法。为了便于描述,该变体被表示为DD-CMOEA-LHS。DD-CMOEA和DD-CMOEA-LHS在31次独立运行中获得的IGD结果如表六所示。可以观察到,这两种算法在几乎所有问题上都具有相当的性能。也就是说,不同的初始化方法对算法性能几乎没有影响。毕竟,这两种方法都期望在生成总体时,变量的值在值的范围内尽可能均匀地分布。

4.4 Determination of the Sizes of Two Populations

  • 此研究两个种群的种群大小的比例,进行了对比实验,具有五个对比组,auxPop的种群大小分别是mainPop的25%,50%,75%,150%和200%。其余的设置和运算符都没有改变。实验结果如表7所示,根据表7的结果,我们有如下的观察。
  1. 这六种算法都有自己擅长解决的问题。例如,auxPop比率较小的版本适用于解决具有易于找到的约束PFs(如LIRCMOP7和LIRCMOP8)的问题。auxPop比率较大的版本适用于解决LIRCMOP1-3等非常需要不可行解帮助的问题。
  2. 由于auxPop与mainPop的尺寸比偏离100%(更小或更大),它们的性能也会因更多问题而恶化。如果mainPop和auxPop的种群规模在进化过程中是固定的,那么当两个种群的规模相同时,算法的整体性能最好。上述实验结果表明,将两个种群的大小设置为相等是合理的。

4.5. Selection of Parent Sets

  • 为了检验来自这两个群体的父个体百分比对该算法性能的影响,我们检查了以下不同设置:来自mainPop的父个体百分比:0%、10%、20%、30%、40%、50%(当前设置)、60%、70%、80%、90%、100%。其他亲本个体来自auxPop,相应的百分比分别为100%、90%、80%、70%、60%、50%(当前设置)、40%、30%、20%、10%、0%。请注意,它们生成的后代的大小始终为N。
  • 实验结果列于表VIII和表IX中。从表VIII和表IX中可以观察到:i)当前设置下的DD-CMOEA(即50%来自mainPop的亲本个体和50%来自auxPop的亲本个体)表现优于所有变体;ii)两个种群的父个体数量差异越大,算法的性能退化越严重。

4.6 Determination of the Use of mainPop

  • 在本小节中,我们设计了一个新的变体(表示为DD CMOEA rand),该变体在探索阶段不进化为mainPop,并在开发阶段开始时采用随机种群作为mainPop。变体中的所有其他操作与DD-CMOEA中的相同。DD-CMOEA和该变体在所有CTP、MW和LIRCMOP测试问题上运行了31次。表X列出了他们的IGD结果。
  • 从表X可以看出,与变体(即DD-CMOEA rand)相比,DD-CMOEA在几乎所有问题上都获得了更好或同等的性能。原因可能是,在我们的DD-CMOEA设计中,mainPop不仅用于寻找可行的解决方案,还用于指导auxPop在开发阶段的移动。然而,在变体中,在开发开始时,随机生成的群体被用作主要POP。新生成的mainPop可能广泛分布在目标空间中,很难快速定位可行区域,因此无法正确引导auxPop朝向预期区域。

5. NVESTIGATION INTO THE EFFECT OF USING DUAL STAGES

  • 为了证实两阶段算法的有效性,图6和图7显示了DD-CMOEA的两个变种生成的解,并且使用LIRCMOP1和LORCMOP9作为例子

6. COMPARISON WITH STATE-OF-THE-ART ALGORITHMS

  • 为了统计量化DD-CMOEA比每个竞争对手好多少,我们使用Vargha Delaney度量[15]来计算DD-CMOEA和每个竞争对手的影响大小。当应用于DD-CMOEA和竞争对手获得的IGD结果时,Vargha-Delaney测量值为0到1之间的值。如果该值正好为0.5,则两种算法的性能相同;如果该值小于0.5,则竞争对手的情况更糟;如果该值大于0.5,DD-CMOEA更差。越接近0.5,两种算法之间的差异越小;距离0.5越远,差异越大。将五个最先进的CMOEAS中的每一个与DD-CMOEA进行比较,并在表Table XI–Table XIII中给出了三个测试套件上获得的效果大小。此外,根据Vargha和Delaney[15],使用语言术语(s:小、m:中、l:大)来表示DD-CMOEA与比较算法之间的差异程度,如下所示:
  • 当Vargha Delaney测度的值在(0.36,0.44]和[0.56,0.64]的区间内时,两种算法之间的差异被认为很小。
  • 当Vargha Delaney测度的值在(0.29,0.36]和[0.64,0.71]的区间内时,两种算法之间的差异被认为是中等的。
  • 当Vargha Delaney测度的值在[0,0.29]和[0.71,1]的区间内时,两种算法之间的差异被认为很大。
  • 为了可视化结果,我们描述了DD-CMOEA获得的最终解,以及一些代表性CMOP上的所有比较算法,如图8–图12所示。绘制的结果取自一个典型的运行,该运行在31次运行中产生IGD中值。在这些图中,每个问题都显示有真实的PF,这样我们就可以直观地比较得到的解的接近性和多样性。
  • 此外,为了在具有复杂PFs的无约束问题上测试DD-CMOEA的行为,我们在MaF测试问题上独立运行DDCMOEA和所有比较算法31次,其IGD值列于表XVII。从表XVII可以看出,DD-CMOEA在该无约束测试套件上的总体性能明显优于所有五种最先进的算法。也就是说,尽管DD-CMOEA主要针对CMOPs.它在无约束问题上的性能也不错。这可能是因为DD-CMOEA具有强大的探索能力,尤其是在第一阶段,其auxPop在不考虑任何约束的情况下向前收敛。此外,mainPop的正向搜索不再受约束的影响。

7. COMPARISON OF ALGORITHMS ON A PROBLEM WITH DISCRETE CONSTRAINTS

  • 目前要测试提出的算法在离散问题上的性能。我们修改了离散的约束问题MW9上的性能。
  • 图13显示了mainPop和auxPop中不同搜索阶段的解的目标向量。从图13中,我们有以下观察结果:(i)auxPop可以穿过不可行区域,并在探索阶段向无约束PF移动,如图13(a)所示。(ii)在图13(b)中的切换点,auxPop覆盖整个无约束PF,而mainPop接近真实PF。在切换点,mainPop并不能覆盖整个真正的PF。(三)在开发过程中,auxPop向后搜索,并从不可行侧接近真实PF。得益于此,mainPop的目标向量对真实PF的覆盖得到了改善,如图13(c)所示。
  • 图14显示了图13中三代auxPop中解决方案的约束函数值。也就是说,图14总结了图13中蓝色三角形解决方案的约束函数值。由于使用了上述离散化机制,每个解的约束函数值始终为整数。零和负整数表示可行解。从图14中,我们有以下观察结果:(i)在探索阶段,直到切换点,auxPop可以包括一些具有零或负约束函数值的可行解,如图14(a)所示。然而,在探索阶段,可行解的数量减少,不可行解的约束违反增加。这是因为探索阶段auxPop的演变是基于目标函数值的。(ii)在切换点,auxPop中的所有解都是不可行的(即,它们具有正约束函数值),如图14(b)所示。这是因为他们已经收敛到了不受约束的PF前沿。平均而言,在切换点的auxPop中的解比其他搜索阶段中的解具有更大的约束冲突值。(iii)在开发阶段,auxPop接近真正的PF。结果,约束冲突值减少,一些解决方案变得可行,如图14(c)所示。
  • 这些观察结果表明,DD-CMOEA在MW9-D(其约束函数是离散的)上的搜索行为与MM9(其约束函数是连续的)上的搜索行为相似。它们之间唯一的区别是MW9-D上的约束函数值是整数,因此某些解决方案可能具有相同的约束冲突值。这可能会降低该算法的搜索能力,因为在开发阶段,auxPop中的每个解的评估都基于其约束冲突值。例如,两个约束冲突值为0.01和0.05的解决方案在离散化后被视为具有相同的约束冲突值1,因为离散化参数Gd为0.05。因此,对约束冲突较小的解决方案的选择压力在这两个解决方案之间消失。

8. SENSITIVITY ANALYSIS OF PARAMETER

9. REFERENCES

[1] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: NSGA-II,” IEEE Trans. Evol. Comput., vol. 6, no. 2, pp. 182–197, 2002.

[2] H. Jain and K. Deb, “An evolutionary many-objective optimization algorithm using reference-point based nondominated sorting approach, part II: Handling constraints and extending to an adaptive approach,” IEEE Trans. Evol. Comput., vol. 18, no. 4, pp. 602–622, 2013.

[3] Z. Ma, Y . Wang, and W. Song, “A new fitness function with two rankings for evolutionary constrained multiobjective optimization,” IEEE Trans. Syst., Man, Cybern., Syst., 2019.

[4] Z. Fan, W. Li, X. Cai, H. Li, C. Wei, Q. Zhang, K. Deb, and E. Goodman, “Push and pull search for solving constrained multi-objective optimization problems,” Swarm Evol. Comput., vol. 44, pp. 665–679, 2019.

[5] Z. Liu and Y . Wang, “Handling constrained multiobjective optimization problems with constraints in both the decision and objective spaces,” IEEE Trans. Evol. Comput., vol. 23, no. 5, pp. 870–884, 2019.

[6] K. Li, K. Deb, Q. Zhang, and S. Kwong, “An evolutionary many-objective optimization algorithm based on dominance and decomposition,” IEEE Trans. Evol. Comput., vol. 19, no. 5, pp. 694–716, 2015.

[7] M. Elarbi, S. Bechikh, and L. B. Said, “On the importance of isolated infeasible solutions in the many-objective constrained NSGA-III,” Knowledge-Based Systems, 2018.

[8] J. Wang, G. Liang, and J. Zhang, “Cooperative differential evolution framework for constrained multiobjective optimization,” IEEE Trans. Cybern., vol. 49, no. 6, pp. 2060–2072, 2018.

[9] K. Li, R. Chen, G. Fu, and X. Yao, “Two-archive evolutionary algorithm for constrained multiobjective optimization,” IEEE Trans. Evol. Comput., vol. 23, no. 2, pp. 303–315, 2018.

[10] Y . Tian, T. Zhang, J. Xiao, X. Zhang, and Y . Jin, “A coevolutionary framework for constrained multi-objective optimization problems,” IEEE Trans. Evol. Comput., 2020.

[11] Z. Fan, Y . Fang, W. Li, J. Lu, X. Cai, and C. Wei, “A comparative study of constrained multi-objective evolutionary algorithms on constrained multiobjective optimization problems,” in Proc. IEEE Congr . Evol. Comput. (CEC), 2017, pp. 209–216.

[12] Z. Fan, W. Li, X. Cai, H. Huang, Y . Fang, Y . Y ou, J. Mo, C. Wei, and E. Goodman, “An improved epsilon constraint-handling method in MOEA/D for CMOPs with large infeasible regions,” Soft Comput., pp. 1–20, 2017.

[13] H. Li and Q. Zhang, “Multiobjective optimization problems with complicated Pareto sets, MOEA/D and NSGA-II,” IEEE Trans. Evol. Comput., vol. 13, no. 2, pp. 284–302, 2009.

[14] M. A. Jan and R. A. Khanum, “A study of two penalty-parameterless constraint handling techniques in the framework of MOEA/D,” Appl. Soft Comput., vol. 13, no. 1, pp. 128–148, 2013.

[15] A. V argha and H. D. Delaney, “A critique and improvement of the cl common language effect size statistics of mcgraw and wong,” J Educ Behav Stat, vol. 25, no. 2, pp. 101–132, 2000.

[16] M. Ming, R. Wang, Y . Zha, and T. Zhang, “Pareto adaptive penalty-based boundary intersection method for multi-objective optimization,” Inform. Sci., vol. 414, pp. 158–174, 2017.

[17] R. Wang, J. Xiong, M.-f. He, L. Gao, and L. Wang, “Multi-objective optimal design of hybrid renewable energy system under multiple scenarios,” Renew Energ, vol. 151, pp. 226–237, 2020.

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2022-03-30,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 DrawSky 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 论文研读-用于约束多目标优化的新型双阶段双种群进化算法补充材料
  • A Novel Dual-Stage Dual-Population Evolutionary Algorithm for Constrained Multi-Objective Optimization
  • 1.LITERATURE REVIEW
  • 2.ILLUSTRATION OF DIFFERENT PHASES OF TWO STAGES
  • 3.EXPLANATION OF THE SETTING OF THE SWITCHING CONDITION
  • 4. COMPARISON WITH VARIANTS
    • 4.1 Effectiveness of the Sequential Algorithmic Scheme Between Two Phases
      • 4.2 Determination of the Baseline Optimizer
        • 4.3 Determination of the Initialization Method
          • 4.4 Determination of the Sizes of Two Populations
            • 4.5. Selection of Parent Sets
              • 4.6 Determination of the Use of mainPop
              • 5. NVESTIGATION INTO THE EFFECT OF USING DUAL STAGES
              • 6. COMPARISON WITH STATE-OF-THE-ART ALGORITHMS
              • 7. COMPARISON OF ALGORITHMS ON A PROBLEM WITH DISCRETE CONSTRAINTS
              • 8. SENSITIVITY ANALYSIS OF PARAMETER
              • 9. REFERENCES
              领券
              问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档