TL;DR
This paper introduces MOEA-CRL, a novel multiobjective evolutionary algorithm that enhances population diversity and convergence by incorporating both ideal and nadir points into a "cross-reference line" method. This approach effectively addresses the Pareto incompatibility problem found in existing reference line methods, leading to superior performance, especially on problems with convex Pareto fronts.
What Problem Does This Paper Address?
Multiobjective optimization problems (MOPs) involve finding a set of solutions that represent the best trade-offs between multiple conflicting objectives. Evolutionary algorithms (MOEAs) are popular for tackling these problems, aiming to achieve both convergence (finding solutions close to the true Pareto front) and diversity (spreading solutions evenly across the front). While reference line methods have shown promise for diversity enhancement, existing approaches often rely solely on the ideal point. This oversight can lead to a "Pareto incompatibility problem," where the algorithm's selection criteria conflict with Pareto dominance, hindering convergence. Furthermore, these methods can struggle with irregular Pareto front shapes.
Methods
The core innovation is the Cross-Reference Line Method. Unlike traditional methods that use a single reference point or line, this approach constructs "cross-reference lines" by pairing ideal point reference lines with nadir point reference lines. This creates "attraction areas" that guide solutions.
To quantify the quality of solutions within these areas, the authors propose the Dominant Penalty Distance (DPD) indicator. This indicator combines the distance to the ideal point reference line and a weighted distance to the nadir point reference line. The DPD indicator is designed to:
- Solve Pareto Incompatibility: By considering both ideal and nadir points, it aligns better with Pareto dominance principles, improving convergence.
- Enhance Diversity: Particularly on convex Pareto fronts, it helps spread solutions more effectively.
- Adapt to Irregular PFs: An adaptive mechanism adjusts the cross-reference lines based on contributing solutions, ensuring uniform distribution regardless of population size.
The algorithm, MOEA-CRL, integrates this cross-reference line method and DPD indicator into a standard MOEA framework, including initialization, mating selection, and environmental selection.
Datasets
The paper evaluates MOEA-CRL on a suite of benchmark problems:
- DTLZ1-DTLZ7: These are standard test problems for evaluating MOEAs, particularly for their scalability with the number of objectives.
- WFG1-WFG9: These problems are designed to test algorithms on various Pareto front shapes, including irregular ones.
- MaF3, MaF11, MaF15: These problems feature highly irregular "convex" Pareto fronts, posing a significant challenge for diversity maintenance.
Key Insights and Ideas
- Nadir Point is Crucial for Diversity: The paper strongly argues that ignoring the nadir point in reference line methods is a significant drawback, leading to convergence issues and poor diversity, especially on convex PFs.
- Cross-Reference Lines Offer a Balanced Approach: By combining ideal and nadir point reference lines, the method creates a more robust framework that balances convergence and diversity.
- DPD Indicator Solves Pareto Incompatibility: The proposed DPD indicator effectively resolves the conflict between reference line evaluations and Pareto dominance, a key limitation of prior methods.
- Adaptive Cross-Reference Lines for Robustness: The adaptive nature of the cross-reference lines, driven by the DPD indicator and contributing solutions, makes the algorithm less sensitive to population size and better equipped to handle irregular PFs.
- Flexibility in Population Size: A significant advantage highlighted is that the algorithm's performance is not strictly tied to the number of reference points, offering flexibility in population size settings.
Key Results
MOEA-CRL was compared against several state-of-the-art MOEAs (MOEA/D, NSGA-III, RVEA, and KnEA) on various benchmark problems.
- Superiority on Convex PFs: MOEA-CRL consistently outperformed other algorithms on problems with convex Pareto fronts, demonstrating its effectiveness in maintaining diversity.
- Good Performance on Irregular PFs: The algorithm also showed competitive performance on problems with irregular Pareto fronts.
- Effective for Many-Objective Problems (MaOPs): While performance can degrade with increasing dimensions, MOEA-CRL generally showed better overall performance on MaOPs compared to the other algorithms.
- Sensitivity Analysis: The weight coefficient $\mu$ in the DPD indicator was found to be crucial, with $\mu=0.25$ showing optimal performance for the tested problems. The sensitivity analysis also confirmed the benefit of including the nadir point for convergence.
Limitations and Future Work
- High-Dimensional Deterioration: The authors acknowledge that MOEA-CRL's performance can deteriorate in high-dimensional objective spaces, a common challenge in multi- and many-objective optimization.
- Complex Convex PF Challenges: The paper notes that dealing with "more complex convex PF problems" remains an area for further research.
- Future Work: The authors suggest exploring further research into high-dimensional deterioration and more complex PF shapes. The adaptability of the cross-reference line method for improving performance on irregular PFs is also highlighted as a promising direction.
Summary updated