1 12-MultiobjectiveEAs

2 Multiobjective Evolutionary Algorithms

• Multiobjective optimization problems (MOP)
  • Pareto optimality
• EC approaches
  • Evolutionary spaces
  • Preserving diversity

3 Multi-Objective Problems (MOPs)

• 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

4 An example: Buying a car

5 Two spaces

Decision (variable) space

Objective space

6 Comparing solutions

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

7 Dominance relation

• 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

8 Pareto optimality

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

9 Goal of multiobjective optimizers

• 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)

10 Single- vs. multiobjective optimization

11 Two approaches to multiobjective optimization

Preference-based: traditional, using single objective optimization methods

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

12 Preference-based approach

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.

13 An example approach: Weighted-sum

Modified problem:

H yperplanes in the objective space !

14 Ideal approach

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.

15 Multiobjective optimization with evolutionary algorithms

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

16 EC approach: Advantages

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.

17 EC approach: Requirements

• 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

18 EC approach: Fitness Assignment

• 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

19 EC approach: Diversity maintenance

• 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

20 EC approach: Remembering Good Points

• 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

21 MOP - summary

MO problems occur very frequently

EAs are very good in solving MO problems

MOEAs are one of the most successful EC subareas