L13 - Multi-objective (Evolutionary) Algorithms

Question 1

What is the goal of a multi-objective algorithm?

Answer 1

An algorithm that is tasked with optimisation of multiple criteria simultaneously.

E.g how can we optimise cost and quality concurrently

Question 2

What optimisations might a water network aim for?

Answer 2

• Low cost
• Good pressure
• Clear water

Question 3

Give the problem definition for a Multi-objective optimisation algorithm…

Answer 3

Given a solution x, where a single objective is identified by y=f(x), a multi-objectives solution quality is defined by the objective vector -> y = ( f1(x), f2(x), f3(x),… , fN(x) )

Question 4

What is the objective vector?

Answer 4

Vector of objectives from a multi-objective problem….

y = ( f1(x), f2(x), f3(x),… , fN(x) )

N is the number of objectives

Question 5

What components do we need to get EA’s to perform multi-objective optimisation?

Answer 5

• Algorithm: generational GA
• Objective function: Multiple objectives specified
• Selection criteria: Use a dominance selection criteria
• Visualisation: Pareto front approximations

Question 6

What is the Dominance Criterion?

Answer 6

• Selection of most dominant points i.e most optimal, for selection for the next generation.

Question 7

What would make some point A dominate another point B?

Answer 7

Point A dominates B if it’s at least as good as point B on every objective, and better then B on at least one objective.

Question 8

What does it mean if 2 points are mutually non-dominating?

Answer 8

If neither point is clearly better than another.

E.g A -> f1 = 8, f2 = 4
B -> f1 = 4, f2 = 8

Question 9

What is the pareto front?

Answer 9

• The frontier of dominant points
• Each point on the pareto front is a dominant point

Question 10

How would the Pareto front be different for minimising and maximising objectives

Answer 10

• Pareto fronts will mirror each other
• Minimise objective -> Curve downward from top left to bottom right towards 0.
• maximise objective -> Curve upward from top left to bottom right away from 0.

Question 11

What are 2 desirable characteristics of the Pareto front?

Answer 11

• Solutions are evenly spaced
• Front covers the largest area possible to improve diversity of solutions

Question 12

How can we differentiate between the Pareto front and inner Pareto fronts?

Answer 12

• Using a ranking system
• We know the Pareto front are the dominant points forming the frontier
• We can rank remaining Pareto fronts by establishing the Pareto front with the 2nd most dominant points, followed by 3rd, then fourth etc.

Question 13

How does the process of multi-objective GA’s change as opposed to singular?

Answer 13

• Solution evaluation stage requires evaluating the solutions against more objectives.
• We need a new selection operator