Journal of Computer Applications ›› 2024, Vol. 44 ›› Issue (1): 269-277.DOI: 10.11772/j.issn.1001-9081.2023010012

• Advanced computing • Previous Articles    

Constrained multi-objective evolutionary algorithm based on two-stage search and dynamic resource allocation

Yongjian MA(), Xuhua SHI, Peiyao WANG   

  1. Faculty of Electrical Engineering and Computer Science,Ningbo University,Ningbo Zhejiang 315211,China
  • Received:2023-01-06 Revised:2023-03-26 Accepted:2023-03-29 Online:2023-06-06 Published:2024-01-10
  • Contact: Yongjian MA
  • About author:SHI Xuhua, born in 1967, Ph. D., professor. Her research interests include system modeling and optimization.
    WANG Peiyao, born in 2000, M. S. candidate. Her research interests include multi-objective optimization.
  • Supported by:
    National Natural Science Foundation of China(61773225)

基于两阶段搜索与动态资源分配的约束多目标进化算法

马勇健(), 史旭华, 王佩瑶   

  1. 宁波大学 信息科学与工程学院,浙江 宁波 315211
  • 通讯作者: 马勇健
  • 作者简介:史旭华(1967—),女,浙江宁波人,教授,博士,主要研究方向:系统建模与优化;
    王佩瑶(2000—),女,河南南阳人,硕士研究生,主要研究方向:多目标优化。
    第一联系人:马勇健(1996—),男,浙江嘉兴人,硕士研究生,主要研究方向:多目标优化;
  • 基金资助:
    国家自然科学基金资助项目(61773225)

Abstract:

The difficulty of solving constrained multi-objective optimization problems lies in balancing objective optimization and constraint satisfaction, while balancing the convergence and diversity of solution sets. To solve complex constrained multi-objective optimization problems with large infeasible regions and small feasible regions, a constrained multi-objective evolutionary algorithm based on Two-Stage search and Dynamic Resource Allocation (TSDRA) was proposed. In the first stage, infeasible regions were crossed by ignoring constraints; in the second stage, two kinds of computing resources were allocated dynamically to coordinate local exploitation and global exploration, while balancing the convergence and diversity of the algorithm. The simulation results on LIRCMOP and MW series test problems show that compared with four representative algorithms of Constrained Multi-objective Evolutionary Algorithm with Multiple Stages (CMOEA-MS), Two-phase (ToP), Push and Pull Search (PPS) and Multi Stage Constrained Multi-Objective evolutionary algorithm (MSCMO), the proposed algorithm obtains better results in both Inverted Generational Distance (IGD) and HyperVolume (HV). TSDRA obtains 10 best IGD values and 9 best HV values on LIRCMOP series test problems, and 9 best IGD values and 10 best HV values on MW series test problems, indicating that the proposed algorithm can effectively solve problems with large infeasible regions and small feasible regions.

Key words: Constrained Multi-objective Optimization Problem (CMOP), two-stage search, resource allocation, non-dominated sorting, convergence, diversity

摘要:

解决约束多目标优化问题(CMOP)的难点在于平衡目标优化和约束满足的同时兼顾解集的收敛性和多样性。为解决具有大型不可行区域和较小可行区域的复杂约束多目标优化问题,提出一种基于两阶段搜索与动态资源分配的约束多目标进化算法(TSDRA)。该算法在第一阶段通过忽略约束跨越不可行区域;然后在第二阶段通过动态分配两种计算资源协调局部开发和全局探索,兼顾算法的收敛性和多样性。在LIRCMOP和MW系列测试问题上进行的仿真实验结果表明,与四个代表性的算法CMOEA-MS(Constrained Multi-Objective Evolutionary Algorithm with Multiple Stages)、ToP(Two-phase)、PPS(Push and Pull Search)和MSCMO(Multi Stage Constrained Multi-Objective evolutionary algorithm)相比,所提算法在反转世代距离(IGD)和超体积(HV)上得到了更优异的结果。在LIRCMOP系列测试问题上,TSDRA获得了10个最佳的IGD值和9个最佳的HV值;在MW系列测试问题上,TSDRA获得了9个最佳的IGD值和10个最佳的HV值,表明所提算法可以更有效地解决具有大型不可行区域和较小可行区域的问题。

关键词: 约束多目标优化问题, 两阶段搜索, 资源分配, 非支配排序, 收敛性, 多样性

CLC Number: