Ranking Constraints via Topological Dual-Directional Search in Evolutionary Multi-Objective Optimization
Authors: Ruiqing Sun, Dawei Feng, Sheng Qi, Xing Zhou, Lianghao Li, Bo Ding, Yijie Wang, Rui Wang, Huaimin Wang
Organizations: National Key Laboratory of Parallel and Distributed Computing, College of Computer Science and Technology, National University of Defense Technology, Changsha 410000, P.R. China · College of System Engineering, National University of Defense Technology, Changsha 410000, P.R. China · College of Intelligence Science and Technology, National University of Defense Technology, Changsha 410073, P.R. China · State Key Laboratory of Complex & Critical Software Environment, College of Information and Communication, National University of Defense Technology, Wuhan 430019, P.R. China
Existing evolutionary algorithms for Constrained Multi-objective Optimization Problems (CMOPs) typically treat all constraints uniformly, overlooking their distinct geometric relationships with the true Constrained Pareto Front (CPF). In reality, constraints play different roles: some directly shape the final CPF, some create infeasible obstacles, while others are irrelevant. To exploit this insight, we propose a novel algorithm named RCCMO, which sequentially performs unconstrained exploration, single-constraint exploitation, and full-constraint refinement. The core innovation of RCCMO lies in a constraint prioritization method derived from these geometric insights, seamlessly coupled with a unique dual-directional search mechanism. Specifically, RCCMO first prioritizes constraints that constitute the final CPF, approaching them from the evolutionary direction (optimizing objectives) to locate the CPF directly shaped by single-constraint boundaries. Subsequently, for constraints that merely hinder the population's progress, RCCMO searches from the anti-evolutionary direction (targeting the infeasible boundaries where hindering constraints intersect with the CPF) to effectively discover how these constraints obstruct and form the final CPF. Meanwhile, irrelevant constraints are intentionally bypassed. Furthermore, a series of specialized mechanisms are proposed to accelerate the algorithm's execution, reduce heuristic misjudgments, and dynamically adjust search directions in real time. Extensive experiments on 5 benchmark test suites and 29 real-world CMOPs demonstrate that RCCMO significantly outperforms seven state-of-the-art algorithms.
Figures & tables
Figure 1: Three types of constraint priority situations based on their geometric relationships with the final CPF.
Figure 2: Flowchart of the proposed RCCMO
Figure 3: Working principle of Probe population: used to detect constraints that hinder the main population from further evolving towards the Pareto optimal direction.
Figure 4: A step-by-step example demonstrating the constraint prioritizing mechanism in RCCMO.
Problem Suite
APSEA
C3M
FCDS
IMTCMO
MCCMO
MSCMO
MTOTC
RCCMO
DASCMOP ( + / − / ≈ )
4/5/0
1/6/2
5/3/1
3/3/3
0/6/3
0/9/0
0/7/2
-
Avg. Rank
5.22
5.11
2.67
3.67
4.89
6.22
5.11
3.11
DOC ( + / − / ≈ )
0/8/1
3/6/0
0/7/2
3/2/4
4/4/1
0/8/1
0/6/3
-
Avg. Rank
6.22
3.67
6.22
2.67
2.44
7.11
5.22
2.44
LIRCMOP ( + / − / ≈ )
0/14/0
0/14/0
2/9/3
1/11/2
1/12/1
0/13/1
1/9/4
-
Avg. Rank
7.93
5.21
3.29
4.93
3.71
5.50
3.86
1.57
Table 1: Statistical Summary of IGD Values ( + / − / ≈ ) and Average Ranks across Test Suites.
Problem Suite
APSEA
C3M
FCDSU
IMTCMO
MCCMO
MSCMO
MTOTC
RCCMO
RWMOP ( + / − / ≈ )
5/15/8
5/15/8
5/17/6
6/10/12
7/15/6
2/20/6
8/13/7
-
Avg. Rank
4.61
4.46
5.32
4.18
4.43
5.93
3.86
3.21
Note: Nemenyi test Critical Difference (CD) = 1.98 at α=0.05 .
Table 2: Statistical Summary of HV Values ( + / − / ≈ ) and Average Ranks across RWMOPs.
Problem Suite
APSEA
C3M
FCDS
IMTCMO
MCCMO
MSCMO
MTOTC
RCCMO w/o AUS
RCCMO
DASCMOP
7.74 (1.32)
29.12 (7.73)
43.68 (2.99)
14.66 (6.63)
45.20 (29.62)
13.14 (5.33)
64.59 (18.79)
22.05 (5.67)
16.62 (5.33)
DOC
14.04 (3.94)
35.69 (30.37)
46.02 (16.95)
17.07 (5.43)
25.15 (10.98)
33.04 (10.47)
70.96 (36.81)
25.51 (4.07)
25.60 (4.84)
LIRCMOP
9.54 (4.10)
13.25 (4.47)
61.60 (18.83)
21.84 (11.42)
22.02 (11.12)
12.22 (3.79)
45.09 (35.91)
19.62 (2.23)
19.15 (2.22)
SDC
11.76 (3.14)
13.75 (4.32)
39.00 (12.30)
13.66 (3.64)
20.93 (5.63)
13.57 (11.77)
29.21 (16.41)
20.02 (2.88)
19.66 (3.56)
ZXH_CF
14.98 (4.85)
19.46 (6.83)
73.25 (13.64)
24.69 (6.19)
33.76 (13.95)
14.36 (4.10)
92.00 (30.72)
24.31 (5.58)
23.31 (6.44)
Overall Average
11.61
22.25
52.71
18.38
29.41
17.26
60.37
22.30
20.87
Table 3: Average Running Time (in seconds) and Standard Deviation across Test Suites. The shortest time is bolded , and the second shortest is underlined .
Figure 5: Comparison of the performance and running time of RCCMO under different interval parameter V .
Problem Suite
w/o AUS
Only-Neg
w/o Re-rank
w/o Flip
Only-Pos
Rand-Priority
RCCMO (Baseline)
DASCMOP ( + / − / ≈ )
0/0/9
0/0/9
1/2/6
0/0/9
0/2/7
1/3/5
-
Avg. Rank
3.44
3.67
4.56
4.56
3.44
4.22
4.11
DOC ( + / − / ≈ )
1/0/8
1/1/7
0/2/7
0/1/8
0/6/3
0/2/7
-
Avg. Rank
3.33
3.67
3.56
4.00
6.33
4.33
2.78
LIRCMOP ( + / − / ≈ )
0/1/13
0/8/6
0/1/13
1/1/12
2/4/8
1/2/11
-
Avg. Rank
4.07
5.50
3.64
4.14
3.86
3.50
3.29
Table 4: Statistical Summary of IGD Values ( + / − / ≈ ) and Average Ranks for Ablation Variants across Test Suites.
Real-world constrained multi-objective optimization problems (CMOPs) commonly involve multiple constraints, and understanding and exploiting their coupling relationships is crucial for efficient optimization. Recent constraint-decoupling methods handle individual constraints separately, but they generally search only in the evolutionary direction to approximate single-constraint Pareto fronts (SCPFs). In this study, we show that part or all of the constrained Pareto front (CPF) may be unrelated to any SCPF and instead be shaped by the boundaries of infeasible regions. We refer to such a portion as the independent CPF (ICPF) and introduce the reverse CPF (RCPF) to characterize its associated informative infeasible boundaries. Based on these observations, we propose a bidirectional constraint-decoupling coevolutionary algorithm named DCF2D. DCF2D dynamically identifies the constraints obstructing the main population and activates constraint-specific auxiliary populations. These populations adaptively search in the evolutionary direction for the corresponding SCPFs or in the reverse evolutionary direction for the corresponding RCPFs. Its three-stage framework integrates unconstrained global exploration, event-driven bidirectional coevolution, and final convergence refinement. Experiments on 87 benchmark instances from seven test suites and 28 real-world engineering CMOPs demonstrate that DCF2D achieves the best overall performance among nine algorithms. Code available at: https://github.com/RuiqingS/DCF2D.
Ruiqing Sun, Dawei Feng, Xing Zhou +6
College of Computer Science and Technology, National University of Defense Technology, Changsha 410000, P.R. China · College of Intelligence Science and Technology, National University of Defense Technology, Changsha, 410000, P.R. China · State Key Laboratory of Complex & Critical Software Environment, College of Information and Communication, National University of Defense Technology, Wuhan 430019, P.R. China +1
Constrained multiobjective optimisation requires fast feasibility attainment together with stable convergence and diversity preservation under strict evaluation budgets. This report documents RDEx-CMOP, the differential evolution variant used in the IEEE CEC 2025 numerical optimisation competition (C06 special session) constrained multiobjective track. RDEx-CMOP integrates an ε-level feasibility schedule, a SPEA2-style indicator-driven fitness assignment, and a fitness-oriented current-to-pbest/1 mutation operator. We evaluate RDEx-CMOP on the official CEC 2025 CMOP benchmark using the median-target U-score framework and the released trace data. Experimental results show that RDEx-CMOP achieves the highest total score and the best overall average rank among all released comparison algorithms, with strong target-attainment behaviour and near-zero final violation on most problems.
Sichen Tao, Yifei Yang, Ruihan Zhao +3
Department of Engineering, University of Toyama, Toyama-shi 930-8555, Japan · Cyberscience Center, Tohoku University, Sendai-shi 980-8578, Japan · Faculty of Science and Technology, Hirosaki University, Hirosaki-shi 036-8560, Japan +5
Structural optimization problems often involve a large number of decision variables and highly non-convex feasible regions, making convergence to the true Pareto front extremely challenging. Even when convergence is achievable, it typically requires thousands of function evaluations, resulting in significant computational cost. This highlights the need for efficient and robust optimization algorithms for real-world engineering applications. In this study, we introduce a novel constrained multi-objective evolutionary algorithm, termed DPCME. The algorithm employs two interacting populations that exchange information, enabling effective global exploration and reducing the risk of convergence to local optima. To further enhance performance, a recent repair-based constraint-handling technique is incorporated, and alternative repair approaches are proposed and systematically evaluated. The proposed algorithm is tested on three engineering problems: the 72-bar truss, the 120-bar truss, and a chemical tanker structure, each involving hundreds of nonlinear failure constraints. Its performance is evaluated against state-of-the-art constrained multi-objective optimization algorithms from the latest PlatEMO package. A total of 43 algorithms are initially tested, from which the 12 best-performing methods are selected for detailed comparison. The results demonstrate that DPCME achieves superior or competitive convergence and diversity across all test cases, and that the inclusion of repair-based constraint handling further improves its performance.
Fardad Homafar, Jasmin Jelovica
Department of Mechanical Engineering, The University of British Columbia, 6250 Applied Science Ln, Vancouver, V6T 1Z4, Canada · Department of Civil Engineering, The University of British Columbia, 6250 Applied Science Ln, Vancouver, V6T 1Z4, Canada