Introduction
In computational optimization, Multi-objective Optimization Problems (MOPs) involve balancing competing goals, such as maximizing energy efficiency while minimizing costs. As the number of objectives increases—typically beyond three—these problems transition into Many-objective Optimization Problems (MaOPs). In these high-dimensional spaces, traditional evolutionary algorithms often struggle due to the loss of selection pressure. A recent study published in IEEE Access introduces ClGrMOEA, a novel hybrid algorithm designed to address these challenges by integrating clustering and grid-based selection mechanisms.
The Challenge: Dominance Resistance
Evolutionary algorithms rely on two primary pillars: selection pressure (driving solutions toward the Pareto Front) and diversity (maintaining a wide spread of solutions). In MaOPs, the standard "Pareto dominance" criterion becomes less effective because most solutions in a population become non-dominated by one another. This phenomenon, known as dominance resistance, leads to stagnant search processes where the algorithm fails to distinguish between better and worse candidates.
Methodology: The ClGrMOEA Framework
The proposed ClGrMOEA algorithm employs a two-stage strategy to restore selection pressure while preserving population diversity.
1. Clustering-Aided Mating Selection
Unlike standard algorithms that often select parents randomly, ClGrMOEA utilizes K-means clustering to partition the population into distinct groups based on objective values. Within each cluster, a convergence indicator ($f_{EdI}$) is calculated based on the Euclidean distance to a local ideal point. By conducting tournaments between solutions within the same cluster, the algorithm ensures that the selected parents are both high-performing (low $f_{EdI}$) and representative of different regions of the search space.
2. Grid-Based One-to-One Environmental Selection
To determine which individuals survive to the next generation, ClGrMOEA implements a grid-based strategy. The objective space is divided into a hyper-grid. When a specific grid cell becomes overcrowded, the algorithm applies the Grid Coordinate Point Distance (GCPD) to retain only the most promising individual. This "one-to-one" selection process ensures a uniform distribution of solutions across the entire trade-off surface, preventing the population from clustering in a single region.
Experimental Evaluation
The researchers evaluated ClGrMOEA against seven state-of-the-art algorithms using three comprehensive test suites:
- WFG (1-9): Benchmarks featuring complex characteristics like multi-modality and non-separability.
- MaOP (1-10): Problems specifically designed for many-objective optimization with up to 10 objectives.
- Real-World Problems (RW1-16): 16 engineering and design scenarios.
Performance was measured using the Hypervolume (HV) metric, which assesses both the convergence and diversity of the solution set.
Key Results
ClGrMOEA demonstrated significant performance gains across the board:
- WFG Benchmarks: The algorithm outperformed or matched competitors in 91% to 100% of the test cases.
- MaOP Benchmarks: It showed superior performance in 62% to 100% of instances, with performance scaling well as the number of objectives increased to 10.
- Real-World Utility: In practical engineering scenarios, ClGrMOEA was significantly better than or comparable to state-of-the-art methods in 87% to 100% of cases.
Ablation studies further confirmed that the hybrid combination of clustering for mating and grids for environmental selection provided a synergistic advantage over using either method in isolation.
Conclusion and Future Directions
ClGrMOEA offers a robust solution for high-dimensional optimization by effectively balancing global diversity with local convergence. While the current implementation uses fixed parameters for clustering and grid density, future research will focus on developing adaptive strategies to automatically tune these parameters during the optimization process. Additionally, extending the framework to handle constrained optimization and large-scale problems with thousands of decision variables remains a priority for future development.
Summary updated