# Representations and Crossovers - Traveling Salesman Problem

## 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:

- Find the position of
**tour**element in the`i`

-th**reference list** - Pick a number and append it to ordinal list
**Remove number**from the reference list**Pick next**city from Tour.- 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 ELEMENT | REFERENCE | ORDINAL |
---|---|---|

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

REFERENCE | ORDINAL | TOUR 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

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

## Source

- https://pl.wikipedia.org/wiki/Problem_komiwoja%C5%BCera
*A. E. Eiben, J. E. Smith: Introduction to Evolutionary Computing , Springer-Verlag, Berlin, 2003.*- https://youtu.be/HATPHZ6P7c4?t=194
- https://youtu.be/c2ft8AG8JKE
- https://youtu.be/DJ-yBmEEkgA?t=109

Maybe you want to share? :)