Source-linked AI summary
Pareto Optimization or Cascaded Weighted Sum: A Comparison of Concepts
Wilfried Jakob, Christian Blume
TL;DR
The paper asks when Pareto optimization is not the best fit for real-world problems with many objectives or repeated, lightly modified tasks. It classifies application scenarios and compares Pareto optimization with cascaded weighted sum (CWS); CWS can focus computation on a known region of interest with less effort, especially as objectives increase.
Problem
Determining most of the Pareto front becomes more computationally demanding as conflicting objectives increase, and a complete front may not be needed when the region of interest is already known.
Source: §1 · p. 2, §4.1 · p. 14Method
The paper classifies application scenarios and compares Pareto optimization with CWS, an aggregation method described as combining weighted sum and ε-constrained approaches.
Source: §1 · p. 2, §5 · p. 17Results
CWS concentrates solutions on a region of interest with less computational effort than Pareto optimization, and this effort difference increases immensely for more than five objectives.
Source: §5 · p. 17Takeaways & Limitations
Pareto optimization suits individual projects, while CWS can benefit repeated task variants with known regions of interest and little human interaction; combining methods can help some projects with five or more objectives.
Source: §5 · p. 17For non-convex problems, weighted sum may fail to find parts of the Pareto front, including the segment between points A and B in the illustrated case.
Source: §2.2 · p. 4
Abstract
from arXiv · showhide
According to the published papers and books since the turn of the century, Pareto optimization is the dominating assessment method for multi-objective nonlinear optimization problems treated by population-based optimizers like Evolutionary Algorithms. However, is it always the method of choice for real-world applications, where either more than four objectives have to be considered, or the same type of task is repeated again and again with only minor modifications, in an automated optimization or planning process? This paper presents a classification of application scenarios and compares the Pareto approach with an extended version of the weighted sum, called cascaded weighted sum, for the different scenarios. Its range of application within the field of multi-objective optimization is discussed as well as its strengths and weaknesses.
1. Introduction
Real-world nonlinear optimization often involves conflicting objectives, while population-based search procedures commonly require a single quality value. The paper introduces cascaded weighted sum (CWS) and discusses when aggregation may compete with Pareto optimization, while noting that Pareto optimization remains appropriate in many application fields.
1. Introduction
- Pareto optimization determines a set of good compromises, after which a human decision maker usually selects one solution according to subjective preferences.A compromise is Pareto-optimal when improving one criterion requires worsening at least one other criterion.Source: §1 · pp. 1–2
- Population-based search procedures commonly need a single quality value, so multiple objectives are often aggregated; expressing objectives as costs can amount to weighted sum with suitable weights.The paper notes that converting goals to costs can require an artificial redefinition.Source: §1 · p. 2
- The effort of determining most of the Pareto front grows with the number of conflicting objectives, motivating CWS for problems where the region of interest is already known.The paper presents CWS as an aggregation method for scenarios where aggregation can compete with Pareto-based approaches.Source: §1 · p. 2
- Although the discussion later focuses on evolutionary multi-objective optimization, the issues also apply to other global optimizers that optimize sets of solutions simultaneously.Source: §1 · p. 2
2. Short Introduction to Pareto Optimization and Two Aggregation Methods
The section defines multi-objective optimization and introduces Pareto optimality, the weighted sum, and the ε-constrained method. It compares their properties and practical trade-offs.
2. Short Introduction to Pareto Optimization and Two Aggregation Methods
- A multi-objective problem maximizes usually conflicting objectives over a feasible region, whose image in objective space is the feasible objective region.The section distinguishes decision vectors in S from objective vectors in Z = f(S).Source: §2 · pp. 2–3
2.1. Pareto Optimization
- Pareto-optimal solutions are non-dominated good compromises on the feasible objective-region boundary, and their set may be non-convex or disconnected.The ideal objective vector gives the Pareto set’s upper bounds; Pareto-based methods can estimate objective ranges but not determine exact lower and upper bounds.Source: §2.1 · pp. 3–4
2.2. Weighted Sum
- The weighted sum normalizes differently scaled objectives and combines them using weights; it can reach every point on a convex Pareto front but may miss parts of a non-convex front.The missed region between A and B cannot be obtained for any weights.Source: §2.2 · p. 4, Figure 3 · p. 5
- Weighted sums can incorporate constraints through penalty factors that reduce the aggregate score as violations increase.Penalty values range from zero for maximal violation to one for no violation, and multiply the raw weighted sum.Source: §2.2 · pp. 5–6, Figure 4 · p. 6
2.3. ε-Constrained Method
- The ε-constrained method optimizes one objective while imposing lower bounds on the others; bounds outside the feasible objective region make the problem unsolvable.It can find Pareto-optimal solutions for non-convex tasks, but finding one such solution may require solving k problems.Source: §2.3 · pp. 6–7
2.4. Summary
- For new problems with little prior knowledge and an available human decision maker, population-based Pareto methods are presented as the method of choice for estimating the full front.Aggregation methods can be easier for application experts to manage when estimating objective lower bounds is more intelligible than selecting abstract weights.Source: §2.4 · pp. 7–8
3. Cascaded Weighted Sum
The paper presents CWS as a priority- and threshold-based weighted aggregation for steering population search toward a known region of interest. It argues that CWS simplifies weighting and can recover some non-convex Pareto-front regions, but requires prior problem knowledge.
3.1. Short Introduction to Evolutionary Algorithms and GLEAM
- The method is presented for population-based evolutionary search, where individuals form a population and fitness guides selection, mutation, and recombination.Source: §3.1 · p. 8, §3 · p. 8
3.2. Definition of the Cascaded Weighted Sum
- CWS assigns objectives weights and priorities, activates lower-priority groups when higher-priority thresholds are met, and deactivates them if a satisfied higher-priority group falls below threshold.Source: §3.2 · p. 9
3.3. Example of the CWS
- For the scheduling example, job time and costs share highest priority; Pareto-front estimates inform weights and thresholds, while achievable bounds normalize objectives.The example uses a 3:4 weight ratio for averaged job times and costs, and sets thresholds at 75% of cost scale and 60% of time frames.Source: §3.3 · pp. 10–11, Table 1 · p. 10
3.4. The Effect of the CWS on the Search
- Once higher-priority objectives meet their thresholds, lower-priority objectives join the score, steering search toward the region of interest and enabling access to some non-convex-front regions missed by pure weighted sum.Source: §3.4 · pp. 11–12, Figure 7 · p. 12
3.5. Summary
- CWS groups objectives to simplify weighting and can reach some non-convex Pareto-front parts missed by pure weighted sum, but may leave other parts unattainable and requires prior parameterization knowledge.Source: §3.5 · p. 13
4. Cascaded Weighted Sum and Its Field of Application
The paper relates method choice to objective count and project type: Pareto optimization suits unfamiliar individual projects, while CWS can suit known regions, task variants, and repeated planning. It presents the methods as complementary in some settings.
4.1. Number of Objectives
- For five objectives, approximating the full Pareto hyperplane requires 625 support points at five per axis or 2401 at seven; comprehension also becomes harder as objective count rises.Each data point may require several solution evaluations, which can involve simulations lasting seconds or minutes.Source: §4.1 · pp. 14–15, Figure 9 · p. 14
4.2. Classification of Application Scenarios and Examples
- Projects are nonrecurring, extended nonrecurring with variants, or recurring; design optimization exemplifies the first two, while grid scheduling and robot paths exemplify recurring tasks.Source: §4.2 · p. 15
4.3.1. Individual Optimization Project
- For an individual project with little prior knowledge of achievable objective values, Pareto optimization can estimate them and support a human's later selection or task revision.Source: §4.3.1 · p. 15
4.3.2. Optimization Project with Some Task Variants
- For task variants, Pareto optimization can identify regions of interest first, then CWS can explore them with fewer evaluations; the two methods may complement each other.The authors identify more than five objectives and one or a few known regions of interest as a possible reason to change assessment method.Source: §4.3.2 · p. 16, Figure 10 · p. 16
4.3.3. Repeated Optimization, also as Part of an Automated Process
- Repeated planning with known regions favors CWS when deadlines prevent convergence and frequent human review is unavailable; the paper also finds it suited to robot-path planning with four or five objectives.Source: §4.3.3 · pp. 16–17
5. Conclusions
The Pareto approach becomes costly as the number of conflicting objectives grows, while the cascaded weighted sum (CWS) can focus effort on a known region of interest. The paper assigns Pareto optimization, CWS, or a combination of both to different project scenarios, concluding that the methods can complement each other.
5. Conclusions
- The amount of solutions needed to approximate a Pareto front grows exponentially with conflicting objectives, and evaluations rise considerably beyond five objectives.This limits Pareto optimization in real-world applications with time-consuming evaluations, especially simulations.Source: §5 · p. 17
- CWS concentrates solutions on a known region of interest with less computational effort than Pareto optimization, especially as the number of objectives grows beyond five.The region may come from previous experience, knowledge, or an initial Pareto-based optimization.Source: §5 · p. 17
- Pareto optimization suits individual projects; combining both methods may benefit projects with variants and five or more objectives, while CWS suits repeated minor variants with known regions of interest.This can reduce effort when solutions must be fast or evaluations are limited by long run times.Source: §5 · p. 17
- Both methods have a place in multi-objective optimization and can complement each other.Source: §5 · p. 18