PERMUTATION PROBLEMS

examples of two different kinds of permuation problems:
1.   8 queens problem - 8 digits, each unique, digit_i = row of the i-th queen
      each locus has a purpose!

2.   TSP - traveling sales person problem - ordered list of cities
      adjacency is important.

What kind of problem is the Ceaser Cipher Problem (simple substitution
cipher)? a key of 26 letters.

MUTATION
   locus specific problems    we can k-swap = swap k items
2-swap - easy to do but also still easy to get in local optima
3-swap and 2x2-swap - increase the exploration but still keep things local

adjacency specific problems    We can do reverse subsections
12345678
   ....
12376548

XOVER

locus specific problems

P1:   1 2 3 4 5 6 7 8 9
P2:   2 1 4 8 5 9 6 3 7
           ^       ^
Ch:   1 2 3 8 5 9 6 8 9   NO  bad idea because doesn't produce a permuation!


permutation block
P1:   1 2 3 4 5 6 7 8 9
P2:   2 1 4 8 5 9 6 3 7
          b b       b
Ch:   1 2 4 8 5 6 7 3 9


CYCLE XOVER (locus specific problems)
P1:   1 2 3 4 5 6 7 8 9
P2:   2 1 4 8 5 9 6 3 7
      a a B B c D D b D


all the same in a converged population
P1:   1 2 3 4 5 6 7 8 9
P2:   1 2 3 4 5 6 7 8 9


derangement 1/e
P1:   1 2 3 4 5 6 7 8 9
P2:   2 3 4 5 6 7 8 9 1


PMX XOVER

EXAMPLE 1:
    P1: 1 2 3 4 5 6 7 8 9
    P2: 9 3 7 8 2 6 5 1 4
        a B B a B c B a a
             ^       ^

>   Ch: . . . 4 5 6 7 . .  make look like P1
    P2: 9 3 7 8 2 6 5 1 4

Look at it from P2:  4 and 7 came in and 8 and 2 left with piece from P1

    Ch: . . . 4 5 6 7 . .  make look like P1
    P2: 9 3 7 8 2 6 5 1 4

copy parts that aren't involved in swap
>   Ch: 9 3 . 4 5 6 7 1 .  so the 8 and 2 must fill in remainder

fill the rest   2 <- 5 <- 7 <- 2
    P2: 9 3 7 8 2 6 5 1 4
>   Ch: 9 3 2 4 5 6 7 1 .  place the 2 in the cylce


>   Ch: 9 3 2 4 5 6 7 1 8  place the 8 in the cylce

ADJACENCY PROBLEMS