[go: up one dir, main page]
Scribd
Upload
75 views28 pages

Non Dominated Sorting

The document describes the non-dominated sorting algorithm for multi-objective optimization problems. It works by comparing each solution to every other to determine if one solution dominates the other based on the objectives being minimized. Solutions that are not dominated by any others are placed in the first non-dominated front. The algorithm then removes these solutions and repeats the process to find additional non-dominated fronts.

Uploaded by

Sourav Das
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
75 views28 pages

Non Dominated Sorting

The document describes the non-dominated sorting algorithm for multi-objective optimization problems. It works by comparing each solution to every other to determine if one solution dominates the other based on the objectives being minimized. Solutions that are not dominated by any others are placed in the first non-dominated front. The algorithm then removes these solutions and repeats the process to find additional non-dominated fronts.

Uploaded by

Sourav Das
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 28

Example of the non-dominated sorting algorithm.

The NSGA-II algorithm uses a more efficient version,


but the result is the same.

Example

Solution f1
f2
(minimise) (minimise)

13

35

f2
35
30

1
6

25

20

18

2
18

18

10

10

10

25

30

8 10 13

f1

18 20

f2
35
30

1
6
5

25

2
18

10

3
5

8 10 13

f1

18 20
3

f2
35
30

1
6
5

25

2
18

10

3
5

8 10 13

f1

18 20
4

Does 2 dominate 1?

f2
35

If no, then

30

1
6
5

25

Does 1 dominate 2?

18

10

3
5

8 10 13

f1

18 20
5

Does 2 dominate 1? NO

f2
35

If no, then

30

1
6
5

25

Does 1 dominate 2? NO

18

They do not dominate eachother

10

4
3

8 10 13

f1

18 20
6

Does 2 dominate 1? NO

f2
35

If no, then

30

1
6
5

25

Does 1 dominate 2? NO

18

They do not dominate eachother

10

4
3

So put 2 in the nondominated set and go to the


next solution

8 10 13

f1

18 20
7

Does 3 dominate 1?

f2
35

If no, then

30

1
6
5

25

Does 1 dominate 3?

18

10

3
5

8 10 13

f1

18 20
8

Does 3 dominate 1? No

f2
35

If no, then

30

1
6
5

25

Does 1 dominate 3? No

18

They do not dominate eachother

10

4
3

8 10 13

f1

18 20
9

f2
35
30

1
6
5

25

2
18

There are more in the nondominated set, so


compare with the next one

10

3
5

8 10 13

f1

18 20
10

Does 3 dominate 2?

f2
35

If no, then

30

1
6
5

25

Does 2 dominate 3?

18

10

3
5

8 10 13

f1

18 20
11

Does 3 dominate 2? Yes

f2
35

If no, then

30

1
6
5

25

Does 2 dominate 3?

18

10

3
5

8 10 13

f1

18 20
12

Does 3 dominate 2? YES

f2
35

If no, then

30

1
6
5

25

Does 2 dominate 3?

18

So delete 2

10

4
3

We would then move to the next one, but there


are none left

8 10 13

f1

18 20
13

We have been through all of the current


nondominated set without finding one that
dominates 3, so we insert three into the
nondominated set

f2
35
30

1
6
5

25

2
18

10

3
5

8 10 13

f1

18 20
14

Does 4 dominate 1?

f2
35

If no, then

30

1
6
5

25

Does 1 dominate 4?

18

10

3
5

8 10 13

f1

18 20
15

Does 4 dominate 1? YES

f2
35

If no, then

30

1
6
5

25

Does 1 dominate 4?

18

So delete 1, and move to the next one

10

4
3

8 10 13

f1

18 20
16

Does 4 dominate 3?

f2
35

If no, then

30

1
6
5

25

Does 3 dominate 4?

18

10

3
5

8 10 13

f1

18 20
17

Does 4 dominate 3? NO

f2
35

If no, then

30

1
6
5

25

Does 3 dominate 4? NO

18

They do not dominate eachother


There are no more to compare to, and we
havent found one which dominates 4, so put 4
in the nondominated set and go to the next
solution

10

4
3

8 10 13

f1

18 20
18

Does 5 dominate 3?

f2
35

If no, then

30

1
6
5

25

Does 3 dominate 5?

18

10

3
5

8 10 13

f1

18 20
19

Does 5 dominate 3? NO

f2
35

If no, then

30

1
6
5

25

Does 3 dominate 5? NO

18

They are nondominated with respect to each


other.
Move to the next solution

10

4
3

8 10 13

f1

18 20
20

Does 5 dominate 4? NO

f2
35

If no, then

30

1
6
5

25

Does 4 dominate 5? YES

18

Go to the next candidate solution, as 5 is


dominated

10

4
3

8 10 13

f1

18 20
21

Does 6 dominate 3?

f2
35

If no, then

30

1
6
5

25

Does 3 dominate 6?

18

10

3
5

8 10 13

f1

18 20
22

Does 6 dominate 3? NO

f2
35

If no, then

30

1
6
5

25

Does 3 dominate 6? NO

18

10

3
5

8 10 13

f1

18 20
23

Does 6 dominate 4? NO

f2
35

If no, then

30

1
6
5

25

Does 4 dominate 6? NO

18

So add 6

10

4
3

8 10 13

f1

18 20
24

f2

This is the non-dominated set

35
30

1
6
5

25

2
18

10

3
5

8 10 13

f1

18 20
25

f2

You can then repeat this


process WITHOUT
solutions 3, 4, and 6.

35
30

25

2
18
10
5

8 10 13

f1

18 20
26

f2

You get this new nondominated front.

35
30

25

We call this the second


non-dominated front

18
10
5

8 10 13

f1

18 20
27

If we repeat this process, we


get three fronts
F1, F2, F3
These are used in some
multiobjective algorithms.

f2
35
30

1
6
5

25

2
18

10

3
5

8 10 13

f1

18 20
28

You might also like