Representations

Path representation

  • The most natural representation
TOUR:  0-2-4-6-1-5-9-10-7-3-8 - Connected Cities Cycle

PATH: (0 2 4 6 1 5 9 10 7 3 8)

Adjacency representation

  • Tour is represented as a list of n cities.
  • Each City connection is defined by a list index
TOUR:         0-2-4-6-1-5-9-10-7-3-8 - Connected Cities Cycle

INDEX:        0 1 2 3 4 5 6 7 8 9 10
ADJACENCY:   [2 5 4 8 6 9 1 3 0 10 7]

Ordinal representation

  • Tour is represented as a list of n cities.
  • i-th element of the list is a number

Translation:

Given:

  • Tour to translate e.g. 0-2-4-6-1-5-9-10-7-3-8
  • Reference list (example path) e.g. (0 1 2 3 4 5 6 7 8 9 10)
  • Empty ordinal list ( )

Algorithm:

  1. Find the position of tour i-th element in the reference list
  2. Pick a number and append it to ordinal list
  3. Remove number from the reference list
  4. Pick next city from Tour.
  5. Go to point 1
TOUR:            0-2-4-6-1-5-9-10-7-3-8
INDEX:           0 1 2 3 4 5 6 7 8 9 10
REFERENCE LIST: (0 1 2 3 4 5 6 7 8 9 10)

CONVERSION FROM TOUR(& REFERENCE) TO ORDINAL:
TOUR ELEMENTREFERENCEORDINAL
0(0 1 2 3 4 5 6 7 8 9 10)(0)
2(1 2 3 4 5 6 7 8 9 10)(0 1)
4(1 3 4 5 6 7 8 9 10)(0 1 2)
6(1 3 5 6 7 8 9 10)(0 1 2 3)
1(1 3 5 7 8 9 10)(0 1 2 3 0)
5(3 5 7 8 9 10)(0 1 2 3 0 1)
9(3 7 8 9 10)(0 1 2 3 0 1 3)
10(3 7 8 10)(0 1 2 3 0 1 3 3)
7(3 7 8)(0 1 2 3 0 1 3 3 1)
3(3 8)(0 1 2 3 0 1 3 3 1 0)
8(8)(0 1 2 3 0 1 3 3 1 0 0)
CONVERSION FROM ORDINAL(& REFERENCE) TO TOUR:
ORDINAL LIST:   (0 1 2 3 0 1 3 3 1 0 0)
REFERENCE LIST: (0 1 2 3 4 5 6 7 8 9 10)
REFERENCEORDINALTOUR ELEMENT
(0 1 2 3 4 5 6 7 8 9 10)(0 1 2 3 0 1 3 3 1 0 0)0
(1 2 3 4 5 6 7 8 9 10)(1 2 3 0 1 3 3 1 0 0)2
(1 3 4 5 6 7 8 9 10)(2 3 0 1 3 3 1 0 0)4
(1 3 5 6 7 8 9 10)(3 0 1 3 3 1 0 0)6
(1 3 5 7 8 9 10)(0 1 3 3 1 0 0)1
(3 5 7 8 9 10)(1 3 3 1 0 0)5
(3 7 8 9 10)(3 3 1 0 0)9
(3 7 8 10)(3 1 0 0)10
(3 7 8)(1 0 0)7
(3 8)(0 0)3
(8)(0)8

Crossovers

Partially Mapped Crossover (PMX)

  • Select two random cut points in strings - representing parent tours
  • Mapping sections - Substrings between cut points
  • Mapping sections are exchanged between parents
  • Already present city it is replaced by the value from the previous parent
P - Parent
V - Offspring

P1 = (1 2 |3 4 5| 6 7 8)
P2 = (3 7 |5 1 6| 8 2 4)

Values map P1 <=> P2 :
3 <=> 5
4 <=> 1
5 <=> 6

V1 = (x x |5 1 6| x x x)
P1 = (1 2 |- - -| 6 7 8) - Apply rest of the values
----------------------------------
V1 = (x 2 |5 1 6| x 7 8) - Apply mappings 1 => 4, 6 => 5 => 3
V1 = (4 2 |5 1 6| 3 7 8) 


V2 = (x x |3 4 5| x x x)
P2 = (3 7 |- - -| 8 2 4) - Apply rest of the values
----------------------------------
V2 = (x 7 |3 4 5| 8 2 x) - Apply mappings 3 => 5 => 6, 4 => 1
V2 = (6 7 |3 4 5| 8 2 1)

Order Crossover (OX)

  • Order of cities is important (relative sequence kept)
  • Select two random cut points in strings
  • Copy from 1 parent substring into offspring
  • Rest fill with the second parent sequence
  • Skip duplicates
P - Parent
V - Offspring

P1 = (1 2 |3 4 5| 6 7 8) - Create offspring from taken subsequence
P2 = (2 4 |6 8 7| 5 3 1)

V1 = (x x |3 4 5| x x x) - Rest fill with sequence from P2, starting from point P1 subsuqence end
V1 = (8 7 |3 4 5| 1 2 6) - If there is duplicate take next one from P2 sequence

V2 = (x x |6 8 7| x x x) - x-ies fill with sequence from P1
V2 = (4 5 |6 8 7| 1 2 3) - On duplicate take next one from P1 sequence

Cycle Crossover (CX)

  • Creates offspring by exchange cycles between two parents
  • The cycle is created by finding corresponding values between two parents, starting from the beginning
P - Parent
V - Offspring


P1 = (1 2 3 4 5 6 7 8 9)
P2 = (9 3 7 8 2 6 5 1 4)

1st Cycle - Start from 1 element at P1.
P1 | P2
1 => 1
8 <= 1
4 <= 8
9 <= 4
1 <= 9

1st Cycle: 1=>8=>4=>9=>1

2nd Cycle - Start from 2 element at P1.
P1 | P2
2 => 2
5 <= 2
7 <= 5
3 <= 7
2 <= 3

2nd Cycle: 2=>5=>7=>3=>2
3rd Cycle: 6=>6

Crossover on 2nd cycle:
P1 = (1 2 3 4 5 6 7 8 9)
V1 = (1 x x 4 x 6 x 8 9)
V1 = (1 3 7 4 2 6 5 8 9) - Fill missing P1=>P2 with 2nd cycle. Remember about DIRECTION

P2 = (9 3 7 8 2 6 5 1 4)
V2 = (9 x x 8 x 6 x 1 4) - Fill missing P2=>P1 with 2nd cycle. Remember about DIRECTION
V2 = (9 2 3 8 5 6 7 1 4)

Alternating edge crossover

  • Builds the offspring from two parents by *randomly choosing an edge from the first parent
  • Then selecting the appropriate edge from the second parent.
  • Operator extends by choosing edges from alternating parents
  • In case of duplication take the random remaining edge.
P - Parent
V - Offspring

P1 = 0-1-5-3-2-4
P2 = 0-1-2-5-3-4

Let's start from value 5 in P1

V1 = 5-3 - Find City 5 in P1 and pick next one
V1 = 5-3-4 - Find City 3 in P2 and pick next one
V1 = 5-3-4-0 - Find City 4 in P1 and pick next one
V1 = 5-3-4-0-1 - Find City 0 in P2 and pick next one
V1 = 5-3-4-0-1-2 - Pick random remaining as duplicate happen

Subtour chunks crossover

  • More general version of Alternating edge
  • Randomly choose how many transitions can be done before Parent switch
  • In case of duplicates take random remaining
P1 = 0-1-5-3-2-4
P2 = 0-1-2-5-3-4

Let's start from value 5 in P1

V1 = 5-3-2-4 - Randomly chosen amount (3) of transitions from P1
V1 = 5-3-2-4-0-1 - Randomly chosen amount (2) of transitions from P2

Heuristic crossover

  1. Choose random City as a starting point
  2. Compare edges of parents. Edge with shorter distance added to child
  3. The chosen the closest city is the starting point of next City selection
  4. If the selected city is already in the child, replace the selected city with random one left.
  5. Go to: 2, till the tour complete.

Source

Related Posts: