Source-linked AI summary
What Weights Work for You? Adapting Weights for Any Pareto Front Shape in Decomposition-based Evolutionary Multi-Objective Optimisation
Miqing Li, Xin Yao
TL;DR
Decomposition-based EMO can struggle when predefined weight distributions do not match unknown Pareto-front shapes. AdaW adapts weights during evolution using population information and archive-guided operations, and experiments report high performance across seven diverse Pareto-front categories, although adapting across different front types remains difficult.
Problem
Predefined uniform weights may fail when a problem's Pareto-front shape is irregular or unknown beforehand, making suitable weight specification an open problem.
Method
AdaW progressively updates weight vectors during evolution using population information, an archive, weight addition, and weight deletion.
Results
AdaW showed high performance across seven categories of problems with different Pareto-front properties.
Takeaways & Limitations
Weight adaptation provides a viable approach for enhancing decomposition-based EMO across diverse Pareto-front shapes.
Takeaways & Limitations
Adapting weight vectors for different Pareto fronts remains difficult because front geometries vary widely.
Abstract
from arXiv · showhide
The quality of solution sets generated by decomposition-based evolutionary multiobjective optimisation (EMO) algorithms depends heavily on the consistency between a given problem's Pareto front shape and the specified weights' distribution. A set of weights distributed uniformly in a simplex often lead to a set of well-distributed solutions on a Pareto front with a simplex-like shape, but may fail on other Pareto front shapes. It is an open problem on how to specify a set of appropriate weights without the information of the problem's Pareto front beforehand. In this paper, we propose an approach to adapt the weights during the evolutionary process (called AdaW). AdaW progressively seeks a suitable distribution of weights for the given problem by elaborating five parts in the weight adaptation --- weight generation, weight addition, weight deletion, archive maintenance, and weight update frequency. Experimental results have shown the effectiveness of the proposed approach. AdaW works well for Pareto fronts with very different shapes: 1) the simplex-like, 2) the inverted simplex-like, 3) the highly nonlinear, 4) the disconnect, 5) the degenerated, 6) the badly-scaled, and 7) the high-dimensional.
1 Introduction
Decomposition-based EMO relies on weight vectors whose distribution should match the Pareto-front shape, but predefined uniform weights can fail on irregular fronts. AdaW adapts weights during evolution using population information to seek a more suitable distribution.
- Decomposition-based EMO decomposes a multi-objective problem into simultaneously optimized single-objective subproblems using weight vectors.
- Uniformly distributed weights work well for simplex-like Pareto fronts, where they can produce uniformly distributed Pareto-optimal solutions.
- On irregular fronts, uniform weights may leave some vectors without Pareto-front intersections, assign multiple vectors to one solution, and create uneven solution spacing.
- Finding optimal weights beforehand is challenging because the Pareto-front shape is often unknown, especially in real-world problems.
- Weight adaptation remains difficult because changing vectors can deteriorate convergence and may compromise performance when the original weights already suit regular fronts.
- AdaW progressively adjusts weights during evolution using population information, an archive, and operations that add promising vectors and delete unpromising or crowded ones.
2 Related Work
Prior work mainly initializes or adapts weight vectors to improve diversity, but its effectiveness depends on Pareto-front shape. Existing adaptation methods face convergence risks, possible losses on regular fronts, and difficulty handling diverse front geometries.
- Systematic weight generators provide explicit search directions but generally assume a simplex-like Pareto front.
- On irregular fronts, multiple weight vectors may correspond to one solution, wasting computational resources and reducing algorithm performance.
- Existing adaptation strategies include random generation, periodic adjustment, archive-based interpolation, and adding or deleting vectors in sparse or dense regions.
- Changing weight vectors changes the subproblems, forcing associated solutions to readjust search directions and potentially wander in objective space.
- Adaptation may compromise performance on regular fronts by moving solutions toward wrong search directions when existing weights are already suitable.
- Adapting weights across disconnected, degenerate, inverted simplex-like, badly-scaled, highly nonlinear, and high-dimensional fronts remains difficult.
3 The Proposed Algorithm
AdaW adapts decomposition weight vectors during evolution using an archive of nondominated solutions to identify unexplored, promising search directions. It combines archive maintenance, weight addition and generation, deletion, and update scheduling while retaining a fixed population size.
- Update schedule: AdaW periodically updates weight vectors using information from the evolving population and its maintained archive.The update frequency determines how long the population evolves under the current weight vectors before adaptation.
- Archive maintenance: The archive stores nondominated solutions and removes poorly distributed members when its preset capacity is exceeded.Maintenance iteratively deletes the solution with the biggest crowding degree, which reflects neighbor number and location within a niche.
- Weight addition: AdaW selects archive solutions from undeveloped niches and tests whether they outperform neighboring population solutions on their corresponding weight vector.A candidate enters the population when it outperforms all neighboring solutions under the candidate’s scalarizing direction.
- Weight generation: For each added solution, AdaW generates an associated weight vector using the solution’s objective values and a reference point under the Tchebycheff scalarizing function.The resulting vector provides a new search direction for the evolutionary population.
- Weight deletion: After adding weights, AdaW deletes vectors associated with solutions shared by the largest number of weight vectors to restore the predefined population size.Ties are resolved by deleting the worst weight vector according to its scalarizing-function value.
- Computational cost: The additional computational cost of AdaW is bounded by O(mN^2) or O(TN^2), compared with O(mTN) for basic MOEA/D.Here m is the number of objectives, N the population size, and T the neighborhood size.
4 Results
Across 17 problems spanning seven Pareto-front shapes, AdaW was evaluated against four peer algorithms using IGD, statistical testing, and visual solution-set comparisons. AdaW generally handled irregular and high-dimensional fronts effectively while remaining competitive on simplex-like fronts.
- Experimental Setup: AdaW was compared with A-NSGA-III, RVEA, MOEA/D-AWA, and MOEA/D across 17 problems grouped into seven Pareto-front categories.The categories included simplex-like, inverted simplex-like, highly nonlinear, disconnected, degenerate, badly-scaled, and high-dimensional fronts.
- Simplex-like Pareto Fronts: On simplex-like fronts, MOEA/D, RVEA, MOEA/D-AWA, and AdaW generally obtained well-distributed solutions, whereas A-NSGA-III struggled particularly on DTLZ1 and CDTLZ2.AdaW’s solutions were described as less regular than those of the other three successful algorithms.
- Inverted Simplex-like Pareto Fronts: On inverted simplex-like fronts, AdaW maintained good coverage and uniformity, while MOEA/D and MOEA/D-AWA concentrated solutions on the boundary and RVEA produced fewer solutions than the population size.A-NSGA-III covered the front well but lacked uniformity.
- Irregular Pareto Fronts: On highly nonlinear, disconnected, degenerate, and badly-scaled fronts, AdaW was the only method to distribute solutions well on SCH1 and DTLZ7 and significantly outperformed competitors on SCH2.On ZDT3, only AdaW and A-NSGA-III maintained good distribution; on SDTLZ1 and SDTLZ2, AdaW, A-NSGA-III, and RVEA performed fairly well.
- Many-Objective Problems: For many-objective fronts far from the standard simplex, AdaW spread solutions over the whole front while competitors either failed to cover it or struggled to converge.On 10-objective DTLZ2, all five algorithms appeared to perform similarly because the front was simplex-like.
5 Conclusions
AdaW adapts weight vectors during optimisation and shows high performance across seven problem categories with varied Pareto-front properties, while requiring more computational resources than basic MOEA/D.
- Contributions: AdaW periodically adapts weight vectors by contrasting the evolutionary population with a maintained archive.The adaptation includes weight generation, addition, deletion, archive maintenance, and update frequency.
- Experimental findings: AdaW shows high performance across seven categories of problems with different Pareto-front properties.The reported categories include simplex-like, inverted simplex-like, highly nonlinear, disconnected, degenerated, badly-scaled, and high-dimensional fronts.
- Limitations: AdaW requires more computational resources than basic MOEA/D.Its time complexity is bounded by O(mN^2) or O(TN^2), compared with O(mTN) for MOEA/D.