TL;DR
The Collaborative Decomposition-based Evolutionary Algorithm (CoDEA) introduces a hybrid approach to many-objective optimization by blending radial and parallel decomposition methods. By adaptively rotating reference lines and employing a dual-ranking strategy for boundary and inner subproblems, CoDEA achieves a superior balance of convergence and diversity across a wide variety of Pareto front shapes.
What Problem Does This Paper Address?
In many-objective optimization problems (MaOPs)—those involving four or more conflicting objectives—evolutionary algorithms often use "decomposition" to break a complex problem into simpler subproblems. Two dominant methods exist: Penalty-based Boundary Intersection (PBI), which uses radial lines (cone decomposition), and Normal Boundary Intersection (NBI), which uses parallel lines.
However, both have geometric "blind spots." PBI struggles with strongly convex frontiers, where its radial lines result in solutions being too densely packed at the edges and sparse in the middle. Conversely, NBI’s parallel lines often fail to capture the boundaries of concave frontiers, leading to poor diversity. Furthermore, as the number of objectives increases, solutions tend to "gather" in the center of the frontier, leaving the edges under-sampled. The authors sought a method that remains robust regardless of whether the frontier is convex, concave, or degenerate.
Methods
The authors propose CoDEA, which centers on a novel Collaborative Decomposition (CoD) method. Key technical innovations include:
- Adaptive Reference Line Rotation: Instead of choosing between radial or parallel lines, CoD starts with NBI-style parallel lines and "rotates" them toward PBI-style radial lines. The degree of rotation ($r_i$) is adaptively tuned based on the subproblem's position (closer to the edge vs. the center) and the total number of objectives ($k_m$).
- Hybrid Aggregation Function: The algorithm uses an NBI-style Tchebycheff function to drive convergence while incorporating a vertical distance penalty (from PBI) to maintain distribution uniformity.
- Dual-Layer Environmental Selection: To combat the "hollow" phenomenon in high-dimensional space, CoDEA treats boundary and inner subproblems differently. Boundary subproblems are ranked using the CoD function, while inner subproblems use an angle-based ranking strategy to push solutions away from the center, ensuring the entire frontier is covered.
Datasets
The algorithm was evaluated on 85 benchmark test instances, including:
- DTLZ1–4: Standard benchmarks for multi-objective optimization.
- WFG1–9: The Walking Fish Group suite, known for complex geometries like scaling, bias, and mixed shapes.
- Convex DTLZ1–4 (CDTLZ): Modified versions of the DTLZ suite specifically designed with strongly convex Pareto fronts to test the known weaknesses of traditional decomposition methods.
- Objective Scales: Tests were conducted across 3, 5, 8, 10, and 15 objectives.
Key Insights and Ideas
- Geometry Matters: The core "aha moment" is that fixed reference line structures are inherently biased toward certain frontier curvatures. By making the decomposition "collaborative" (hybridizing radial and parallel), the algorithm becomes geometry-agnostic.
- The High-Dimensional "Center Trap": The authors observed that in many-objective space, standard selection pressure often forces solutions toward the "center" of the hyperplane. Their use of an acute angle measure for inner subproblems acts as a centrifugal force, maintaining a "wide" population distribution.
- Inheritance of Strengths: CoDEA is designed to inherit the high convergence speed of NBI while maintaining the extensive diversity of PBI, effectively filling the gaps left by each parent method.
Key Results
CoDEA was compared against five state-of-the-art algorithms (RVEA, NSGA-III, VaEA, $\theta$-DEA, and MP-DEA) using the Hypervolume (HV) indicator:
- Overall Performance: CoDEA achieved the best HV scores in 56 out of 85 comparative groups.
- Convex Frontiers: On the CDTLZ suite, CoDEA significantly outperformed competitors, proving its adaptive rotation successfully handles high curvature where PBI fails.
- High Dimensionality: In tests with 10 and 15 objectives on the WFG suite, CoDEA won 21 out of 27 instances, demonstrating exceptional stability as the problem scale increases.
- Visual Uniformity: Parallel coordinate plots confirmed that CoDEA maintains a much more uniform spread of solutions across all objectives compared to NSGA-III or RVEA, which often showed "crowding" at specific values.
Limitations and Future Work
While CoDEA performed exceptionally well on standard and convex benchmarks, the authors noted that it (along with most competitors) still struggles with WFG3, a problem featuring a "degenerate" frontier.
Future research directions include:
- Extending CoDEA to handle constrained MaOPs (where certain regions of the search space are off-limits).
- Applying the algorithm to real-world complex problems, specifically Neural Architecture Search (NAS) for medical image segmentation, where balancing multiple performance metrics is critical.
Summary updated