- Multiobjective optimization problems (MOP)
- Pareto optimality

- EC approaches
- Evolutionary spaces
- Preserving diversity

- Wide range of problems can be categorized by the presence of a
number of
*n*possibly conflicting objectives:- buying a car: speed vs. price vs. reliability
- engineering design: lightness vs. strength

- Two problems:
- finding set of good solutions
- choice of best for particular application

Decision (variable) space

Objective space

Optimization task:Minimize both f1 and f2

Then:a is better than ba is better than ca is worse than ea and d are incomparable

Objective space

- Solution x dominates solution y, (x y), if:
- x is better than y in at least one objective,
- x is not worse than y in all other objectives

**solutions dominated by x**

**solutions dominating x**

Solution x is non-dominated among a set of solutions Q if no solution from Q dominates x

A set of non-dominated solutions from the entire feasible solution space is the Pareto-optimal set , its members Pareto-optimal solutions

Pareto-optimal front : an image of the Pareto-optimal set in the objective space

Illustration of the concepts

Illustration of the concepts

A practical example: The beam design problem

Minimize weight and deflection of a beam (Deb, 2001) :

Formal definition

Minimize

m inimize

subject to

where

(beam weight)

(beam deflection)

(maximum stress)

Feasible solutions

Decision (variable) space

Goal: Finding non-dominated solutions

- Find a set of non-dominated solutions ( approximation set )
following the criteria of:
- convergence (as close as possible to the Pareto-optimal front),
- diversity (spread, distribution)

Characteristic | Singleobjective optimisation | Multiobjective optimisation |
---|---|---|

Number of objectives | one | more than one |

Spaces | single | two: decision (variable) space, objective space |

Comparison of candidate solutions | x is better than y | x dominates y |

Result | one (or several equally good) solution(s) | Pareto-optimal set |

Algorithm goals | convergence | convergence, diversity |

Preference-based: traditional, using single objective optimization methods

Ideal: possible with novel multiobjective optimization techniques,enabling better insight into the problem

Given a multiobjective optimization problem,

use higher-level information on importance of objectives

to transform the problem into a singleobjective one,

and then solve it with a single objective optimization method

to obtain a particular trade-off solution.

Modified problem:

H yperplanes in the objective space !

Given a multiobjective optimization problem,

solve it with a multiobjective optimization method

to find multiple trade-off solutions,

and then use higher-level information

to obtain a particular trade-off solution.

Population-based method

Can return a set of trade-off solutions (approximation set) in a single run

Allows for the ideal approach to multiobjective optimization

Population-based nature of search means you can
*simultaneously* search for set of points approximating Pareto
front

Don’t have to make guesses about which combinations of weights might be useful

Makes no assumptions about shape of Pareto front - can be convex / discontinuous etc.

- Way of assigning fitness,
- usually based on dominance

- Preservation of diverse set of points
- similarities to multi-modal problems

- Remembering all the non-dominated points you have seen
- usually using elitism or an archive

- Could use aggregating approach and change weights during evolution
- no guarantees

- Different parts of population use different criteria
- e.g. VEGA, but no guarantee of diversity

- Dominance
- ranking or depth based
- fitness related to whole population

- Usually done by niching techniques such as:
- fitness sharing
- adding amount to fitness based on inverse distance to nearest neighbour (minimisation)
- (adaptively) dividing search space into boxes and counting occupancy

- All rely on some distance metric in genotype / phenotype space

- Could just use elitist algorithm
- e.g. ( + ) replacement

- Common to maintain an archive of non-dominated points
- some algorithms use this as second population that can be in recombination etc.
- others divide archive into regions too, e.g. PAES

MO problems occur very frequently

EAs are very good in solving MO problems

MOEAs are one of the most successful EC subareas