Source-linked AI summary
IGD Indicator-based Evolutionary Algorithm for Many-objective Optimization Problems
Yanan Sun, Gary G. Yen, Zhang Yi
TL;DR
Many-objective evolutionary algorithms need selection that preserves both convergence and diversity despite weakened traditional dominance pressure. The paper proposes MaOEA/IGD with efficient reference-point construction, dominance and proximity assignments, and global selection; experiments across 8-, 15-, and 20-objective benchmarks find it very competitive against peer algorithms.
Problem
Traditional dominance comparisons can produce many non-dominated solutions in many-objective problems, while uniformly distributed Pareto-front reference points are difficult to obtain.
Method
MaOEA/IGD combines DNPE for constructing a Utopian Pareto front, reference-point-based dominance ranking, three proximity-distance assignments, and linear assignment selection.
Results
Experiments on 8-, 15-, and 20-objective benchmark problems indicate that MaOEA/IGD is very competitive against selected many-objective optimization algorithms.
Takeaways & Limitations
The proposed components collectively improve evolution toward the Pareto front while addressing convergence and diversity simultaneously.
Abstract
from arXiv · showhide
Inverted Generational Distance (IGD) has been widely considered as a reliable performance indicator to concurrently quantify the convergence and diversity of multi- and many-objective evolutionary algorithms. In this paper, an IGD indicator-based evolutionary algorithm for solving many-objective optimization problems (MaOPs) has been proposed. Specifically, the IGD indicator is employed in each generation to select the solutions with favorable convergence and diversity. In addition, a computationally efficient dominance comparison method is designed to assign the rank values of solutions along with three newly proposed proximity distance assignments. Based on these two designs, the solutions are selected from a global view by linear assignment mechanism to concern the convergence and diversity simultaneously. In order to facilitate the accuracy of the sampled reference points for the calculation of IGD indicator, we also propose an efficient decomposition-based nadir point estimation method for constructing the Utopian Pareto front which is regarded as the best approximate Pareto front for real-world MaOPs at the early stage of the evolution. To evaluate the performance, a series of experiments is performed on the proposed algorithm against a group of selected state-of-the-art many-objective optimization algorithms over optimization problems with $8$-, $15$-, and $20$-objective. Experimental results measured by the chosen performance metrics indicate that the proposed algorithm is very competitive in addressing MaOPs.
I. INTRODUCTION
Many-objective optimization requires algorithms that preserve both convergence and diversity as traditional dominance loses selection pressure with increasing objectives. The paper proposes MaOEA/IGD, combining IGD-based selection, efficient dominance comparison, proximity assignments, and nadir estimation.
- Motivation: MaOPs involve more than three conflicting objectives, requiring uniformly distributed solutions that closely approximate the Pareto Front.Applications include land-exploitation policy management with 14 objectives and automotive-engine calibration with 10 objectives.
- Motivation: Traditional MOEAs do not scale well because many-objective populations contain a large proportion of non-dominated solutions, weakening selection pressure.This makes conventional dominance comparisons ineffective at discriminating solutions with similar proximity.
- Related work: Existing MaOEA families emphasize reference-based diversity, decomposition, convergence enhancement, or indicators, but each involves limitations such as conversion choices or costly hypervolume computation.The related approaches include NSGA-III, MOEA/D variants, dominance modifications, and HV-based algorithms including HypE.
- Contributions: The paper proposes MaOEA/IGD to address MaOPs using an IGD indicator-based evolutionary algorithm.Its contributions include DNPE, a reference-point comparison scheme, three proximity-distance assignments, and a selection mechanism.
- Contributions: DNPE estimates nadir points by transforming an m-objective problem into m single-objective problems, reducing computational cost relative to peer estimators.The estimated nadir points support construction of the Utopian Pareto Front for sampling IGD reference points.
- Contributions: The proposed comparison and selection designs jointly promote convergence and diversity while lowering comparison complexity through reference-point-based dominance relations.Three proximity assignments distinguish solutions sharing a front rank, and linear assignment selects representatives globally.
B. IGD+-EMOA
IGD+-EMOA uses IGD+ for selection, but its approximate reference Pareto front performs poorly on MaOPs with multiple local Pareto-optimal fronts. The proposed MaOEA/IGD addresses this limitation with DNPE-based reference construction.
- IGD+ modifies IGD’s distance calculation to better distinguish generated solutions that are nondominated relative to reference points.IGD+-EMOA uses IGD+ as its selection mechanism.
- IGD+-EMOA samples reference points from an approximate Pareto front obtained by solving a unit-simplex equation using current nondominated solutions.
- The approximate-front construction performs poorly when MaOPs contain multiple local Pareto-optimal fronts, limiting IGD+-EMOA to problems with no more than 8 objectives.
- MaOEA/IGD constructs its reference points from a Utopian Pareto front using an estimated nadir point, enabling application to problems with many more objectives than IGD+-EMOA.
III. PROPOSED ALGORITHM
The proposed MaOEA/IGD is an IGD indicator-based evolutionary algorithm for many-objective optimization problems. Its framework and component mechanisms are presented before complexity analysis and discussion of convergence and diversity promotion.
- MaOEA/IGD is proposed as an Inverted Generational Distance indicator-based evolutionary algorithm for many-objective optimization problems.
- The section presents the algorithm framework, details each step, analyzes computational complexity, and discusses mechanisms promoting diversity and convergence.
A. Framework of the Proposed Algorithm
The algorithm generates uniformly distributed reference points on a Utopian Pareto front, initializes and evaluates a population, then repeatedly assigns ranks and proximity distances during evolution.
- Reference-point generation: Reference points p* are generated uniformly on a constrained (m −1)-dimensional hyperplane and transformed into the Utopian Pareto front.
- Evolutionary framework: The evolutionary loop initializes a feasible population, evaluates fitness, assigns ranks and proximity distances, generates offspring, and repeats until stopping criteria are met.
- Nadir-point estimation: The algorithm estimates extreme points individually by decomposing the m-objective problem into m single-objective problems with different weights.
- Reference-point generation: After extracting ideal and nadir points, the method samples k reference points from the constrained hyperplane and transforms them for IGD calculation.
- Nadir-point estimation: For each extreme-point estimate, the method combines the squared L2 norm of the other objectives with the absolute value of the associated objective, weighted by λ > 1.
C. Assigning Ranks and Proximity Distances
Individuals are ranked by dominance relations with sampled reference points, while rank-specific proximity distances guide convergence and diversity selection. For rank r2, the proposed distance corrects the preference produced by ordinary Euclidean distance.
- Rank assignment: Rank values distinguish proximity to the Utopian Pareto front from reference-point comparisons, while proximity distances indicate convergence and diversity among solutions.
- Rank assignment: The algorithm uses three ranks: r1 individuals dominate at least one reference point, r2 individuals are nondominated to all, and r3 individuals are dominated by some or all reference points.
- Proximity-distance assignment: For rank r2, equation (4) uses a one-sided objective difference, and the minimum distance across reference points is used for comparisons.
- Proximity-distance assignment: For rank r3, proximity distance is Euclidean distance; for rank r1, it is the negative Euclidean distance to each reference point.
- Proximity-distance assignment: In the illustrative r2 example, Euclidean distances favor x1, whereas equation (4) gives x2 the smallest distance and identifies its more promising convergence.
- Proximity-distance assignment: The r2 proximity-distance design is also used in IGD+, and smaller proximity distance denotes better proximity when the exact Pareto front is unknown.
D. Generating Offspring
Offspring generation fills a gene pool, selects parent pairs, and applies SBX crossover and polynomial mutation until the pool is exhausted.
- D. Generating Offspring: The algorithm fills the gene pool from the current population before generating offspring.The process continues until the specified gene-pool size is reached.
- D. Generating Offspring: Two parent solutions are selected from the gene pool and removed before offspring generation.
- D. Generating Offspring: SBX crossover generates offspring from the selected parents.
- D. Generating Offspring: Polynomial mutation is applied to the generated offspring before the process repeats.
- D. Generating Offspring: Binary tournament selection compares randomly chosen individuals using their ranks and proximity distances.The corresponding crossover and mutation operators are SBX and polynomial mutation.
E. Environmental Selection
Environmental selection copies complete lower-ranked fronts and uses proximity-distance assignment to fill any remaining population slots.
- E. Environmental Selection: Environmental selection chooses survivors from the current population according to assigned ranks and proximity distances.
- E. Environmental Selection: The algorithm adds complete fronts until the next front would exceed the available population size.
- E. Environmental Selection: If the next front does not fit, the remaining slots are filled by selecting individuals from that front.
- E. Environmental Selection: The final representatives minimize total proximity distances to the reference points through a linear assignment problem.The Hungarian method solves this assignment problem in the proposed algorithm.
F. Computational Complexity
The proposed algorithm has overall computational complexity O(tN^3), dominated by environmental selection through linear assignment across t generations.
- F. Computational Complexity: The complexity analysis considers m objectives, n decision variables, N desired solutions, and t generations.
- F. Computational Complexity: The genetic algorithm estimates extreme points using SBX and polynomial mutation as genetic operators.
- F. Computational Complexity: O(tN^3) is the proposed algorithm's overall complexity over t generations.
- F. Computational Complexity: Environmental selection ranges from O(N) in the best case to O(N^3) when N individuals are assigned to reference points.
G. Discussions
The discussion addresses lost selection pressure in MaOPs by combining approximate Utopian Pareto-front reference points, proximity distances, and global assignment selection.
- G. Discussions: Traditional dominance comparisons lose selection pressure because MaOP populations contain a large proportion of non-dominated solutions.
- G. Discussions: The algorithm compares individuals with reference points used to calculate the IGD indicator.
- G. Discussions: Evenly distributed points in the Utopian PF approximate the difficult-to-obtain uniformly distributed PF reference points.
- G. Discussions: Three proximity distances account for dominance relations to approximate reference points, with smaller values indicating better proximity.
- G. Discussions: Linear assignment simultaneously selects representatives against the IGD indicator, giving each selected reference point a distinct individual.Choosing individuals one by one does not necessarily guarantee diversity.
IV. EXPERIMENTS
The experiments compare MaOEA/IGD with five peer algorithms on DTLZ and WFG benchmarks using normalized HV across 8-, 15-, and 20-objective problems.
- NSGA-III, MOEA/D, HypE, RVEA, and KnEA are selected as state-of-the-art peer competitors.
- DTLZ1-DTLZ7 and WFG1-WFG9 benchmark problems are evaluated with 8, 15, and 20 objectives.
- HV measures convergence and diversity, using specified reference points and normalization to [0, 1].Exact HV computation is used below 10 objectives and Monte Carlo simulation when m ≥10.
- Each algorithm is run independently 30 times, with objective-dependent function-evaluation limits serving as termination criteria.The limits are 2.3 × 10^6, 4.3 × 10^6, and 5.5 × 10^6 evaluations for 8-, 15-, and 20-objective problems, respectively.
- Results are statistically evaluated with the Mann-Whitney-Wilcoxon rank-sum test at a 5% significance level.
4) Population Size:
The experiments compare MaOEA/IGD with peer algorithms across DTLZ and WFG problems using HV and nadir-point estimation evaluations. MaOEA/IGD is generally competitive, while DNPE uses fewer function evaluations than compared methods on DTLZ1.
- Population Size: Population sizes depend on associated reference points or vectors for MaOEA/IGD, NSGA-III, MOEA/D, and RVEA, with matched sizes used for HypE and KnEA.Reference points and vectors are sampled using the two-layer method.
- DTLZ Results: MaOEA/IGD achieves the best HV performance on several DTLZ tasks, including 8- and 20-objective DTLZ1 and DTLZ7, but loses selected comparisons to KnEA, RVEA, and NSGA-III.It also wins on 8- and 15-objective DTLZ4 and DTLZ6, while NSGA-III performs better at 20 objectives on those problems.
- WFG Results: MaOEA/IGD outperforms competitors on several WFG tasks across 8- and 15-objective settings, while showing similar results to winners on WFG3 and WFG4 for 8 objectives.The reported comparisons include WFG1, WFG2, WFG5, WFG6, WFG7, WFG8, and WFG9.
- PF-Shape Analysis: MaOEA/IGD wins 9 of 12 comparisons on test problems with linear Pareto fronts and remains competitive on problems with concave Pareto fronts.The authors associate the linear-front results with sampled Utopian-PF reference points and the r2 proximity-distance assignment.
- Indicator Comparison: The HV-based comparison reports MaOEA/IGD outperforming HypE on all considered test problems despite HypE receiving many more function evaluations.The paper identifies HV's higher computational complexity relative to IGD as a theoretical shortcoming.
- Nadir-Point Estimation: DNPE finds satisfactory DTLZ1 nadir points within the evaluation limit and uses the fewest function evaluations among the compared methods across four objective counts.The estimation study covers DTLZ1, DTLZ2, and WFG2 with 8-, 10-, 15-, and 20-objective settings.
V. CONCLUSION AND FUTURE WORKS
The paper proposes an IGD-based evolutionary algorithm for many-objective optimization, combining nadir estimation, dominance and proximity assignments, and linear-assignment selection. Experiments report competitive optimization performance and satisfactory nadir estimation, while identifying more accurate Pareto fronts and constrained problems as future directions.
- The proposed algorithm combines decomposition-based nadir estimation, dominance comparison, proximity distances, and linear-assignment selection for IGD-based many-objective optimization.These components construct reference points and jointly address convergence and diversity during selection.
- Experiments on one real-world many-objective problem report satisfactory results demonstrating the proposed algorithm’s superiority.
- The proposed nadir estimation method obtains satisfactory results on DTLZ1, DTLZ2, and WFG2, covering linear, concave, and convex Pareto-front shapes and differing objective-value scales.
- Future work targets more accurate Pareto fronts with limited prior information and extension to constrained many-objective optimization problems.