Wk 8 Multi-Objective (Evolutionary) Algorithms

Question 1

Multi-Objective (Evolutionary) Algorithms example use :

Answer 1

Company wants to see the ‘trade-off’ between the costs and benefits of solutions.

Question 2

SOGA & MOGA

Answer 2

Single-Objective Genetic Algorithms (SOGA)

Multi-Objective Genetic Algorithms (MOGA)

Question 3

MOGA

Answer 3

aims to find a set of solutions that represents the trade-offs between multiple objectives and provides a diverse set of optimal or near-optimal solutions.

Question 4

How can we get EAs to perform Multi-Objective
computation?

Answer 4

• Generational Genetic Algorithms
• Revised Objective Functions
• Revised Selection Criteria– Domination Criterion
• Revised Visualisation

Question 5

Domination Criterion

Answer 5

A solution a is said to ‘dominate’ another b in the population if it is at least as good as b in every dimension and better than b in at least one
dimension.

Question 6

Pareto-Front

Answer 6

The best solutions will lie along a curve consisting of non-dominated points.

Pareto front represents the set of optimal trade-off solutions, there are other solutions that are not as desirable.

Question 7

Desirable Characteristics of the Pareto-Front

Answer 7

• Evenly-spaced solutions
• Covering the largest possible area of the front

Question 8

Discrimination in Multiple Objectives

Answer 8

refers to the process of distinguishing and ranking solutions that are not on the Pareto front. ( less desirable solutions )

Question 9

Ranking I (Non-Dominated Sorting)

Answer 9

Preto fronts are iteratively ranked the lower the rank the more dominated are the points in that front

Question 10

Ranking II (Dominance Count” or “Rank Count”)

Answer 10

For each solution, count the number of solutions that dominate it, the count is the rank it is assigned.

Question 11

meaning : two solutions are non-dominated

Answer 11

neither solution is better than the other in all objectives

Question 12

Pareto Domination Tournament

Answer 12

Select two random individuals from the population, if one dominates the other then select it.

Question 13

Pareto Domination Tournament issues

Answer 13

• Selection pressure is not sufficient
• Tiebreak if both sets dont dominate eachother

Question 14

Pareto Domination Tournament improve selection pressure

Answer 14

Select two random individuals a & b and a separate comparison set c from the population.

If a or b is non-dominated with respect to c, then select.

Size of c can be used as a parameter to change the selection pressure

Question 15

Tiebreak Resolution

Answer 15

Niching:
-Separate the fitness landscape or genotype into ‘Niches’
- Prefer individuals in a niche with less other individuals

Question 16

NPGA - Niched Pareto Genetic Algorithm

Answer 16

1 .Generate initial population of solutions

2. Select individuals: repeatedly run pareto-tournament domination selection. If one solution is non-dominated and so is the other compute niched fitness to separate solutions.
3. Crossover and mutate to generate new population

Question 17

Non-Dominated Sorting Genetic Algorithm (NSGA):

Answer 17

uses non-dominated sort:
Solutions that are not dominated by any other solution belong to the first front, while solutions dominated by the first front belong to the second front, and so on.

Uses crowding distance as a tie-breaker

Question 18

Crowding Distance:

Answer 18

Crowding distance measures the density of solutions in the objective space.

It helps maintain diversity by favoring solutions that are located in less densely populated areas of the Pareto front.

Question 19

How do you calculate the crowding distance ?

Answer 19

Calculate the crowding distance for solutions within each rank.

Measure the diversity or spread of solutions based on the distances between neighboring solutions in the objective space.

Question 20

NSGAII Execution

Answer 20

• Initialization:
• Perform non-dominated sorting
• Crowding Distance Calculation
• Selection
• Reproduction
• Population Update
• Termination

Question 21

Elitist MOGAs (PAES, SPEA, NSGAII) have somewhat superseded non-elitist versions why?

Answer 21

-NSGAII requires no extra parameters (e.g. niche sizes)
-Executes & converges faster

Question 22

Alternatives to Multi Objective GA

Answer 22

The population-based approach of Single objective GAs is ideal for MO optimisation, by weighting each objective, we can optimise for different points
on the pareto-curve.