Clustering-Aided Grid-Based One-to-One Selection-Driven Evolutionary Algorithm for Multi/Many-Objective Optimization

Vikas Palakonda, Jae-Mo Kang, Heechul JungIEEE Access 2024 · DOI · OpenReview

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

Abstract

Multiobjective evolutionary algorithms are highly effective in solving multiobjective optimization problems (MOPs). The selection strategy, involving mating and environmental selection, is crucial in shaping these algorithms. However, when applied to many-objective optimization (MaOPs) with more than three objectives, existing methods face challenges due to reduced selection pressure and issues in maintaining diversity, making them less efficient. To address these challenges, we present a novel approach in this paper: the clustering-aided grid-based one-to-one selection-driven evolutionary algorithm (ClGrMOEA), designed to handle both MOPs and MaOPs effectively. The proposed ClGrMOEA introduces a hybrid approach that combines clustering-based mating selection with grid-based one-to-one environmental selection to balance convergence and diversity in MOPs and MaOPs. The mating selection employs K-means clustering to partition the objective space and utilizes a convergence indicator based on Euclidean distance to select promising solutions for offspring generation. The environmental selection combines Pareto dominance with grid-based one-to-one selection, using grid coordinate point distance to select promising solutions. An external archive based on Pareto dominance and crowding distance preserves elite individuals. Extensive experiments are conducted on 19 benchmark problems and 16 real-world problems to validate the superior performance of ClGrMOEA compared to seven state-of-the-art algorithms. The experimental results demonstrate that ClGrMOEA significantly outperforms these benchmark algorithms.
BibTeX
@article{palakonda2024clustering,
  author = {Vikas Palakonda and Jae-Mo Kang and Heechul Jung},
  title = {{Clustering-Aided Grid-Based One-to-One Selection-Driven Evolutionary Algorithm for Multi/Many-Objective Optimization}},
  journal = {IEEE Access},
  year = {2024},
  doi = {10.1109/access.2024.3398415},
}
Figure