Search code examples
matrixcombinationsgenetic-algorithmcrossover

Crossover algorithms for permutation matrices

I'm developing a genetic algorithm to find the optimal connections between points (minimizing distance). Let's assume we have two lists of points:

sources = {s1, s2, s3}

targets = {t1, t2, t3, t4}

I decided to represent the genome as a 2D binary array, where:

  • rows represent source points
  • columns represent target points
  • 1s represent the connection between source and target

This representation implies that each column and each row in the matrix can have at most one 1s.

Now I'm struggling to find a crossover operator which preserves the integrity of the solution.

example:

parent1 :

[0][1][0][0]
[0][0][1][0]
[1][0][0][0]

parent2 :

[0][0][1][0]
[1][0][0][0]
[0][0][0][1]

offspring : ???

Any suggestions?

Solution

  • Keeping your representation and assuming that there are more targets than sources, you could use a row-swapping crossover operator with a built-in repair algorithm.

    • Randomly select a row (i)
    • Swap parents' i-th row
    • Repair children (if required) moving the conflicting 1 to a free (random or near) column

    E.g.

    1. Row 0 randomly selected

                   PARENT 1                   PARENT 2
    ROW 0  [0][1][0][0] <-crossover-> [0][0][1][0]
    ROW 1  [0][0][1][0]               [1][0][0][0]
    ROW 2  [1][0][0][0]               [0][0][0][1]

    2. Offspring before repair

            CHILD 1            CHILD 2
    [0][0][1][0]       [0][1][0][0]
    [0][0][1][0]  and  [1][0][0][0]
    [1][0][0][0]       [0][0][0][1]

    3. CHILD2 is ok (for a column-swapping operator this doesn't happen); CHILD1 needs the repair operator

            CHILD 1
    [0][0][X][0]
    [0][0][X][0]
    [1][0][0][0]

    4. Keep the swapped row (row 0) and change the other conflicting row (row 1). Move the 1 to a free column (column 1 or 3)

            CHILD 1
    [0][0][1][0]
    [0][1][0][0]
    [1][0][0][0]

    5. Offspring

            CHILD 1            CHILD 2
    [0][0][1][0]       [0][1][0][0]
    [0][1][0][0]  and  [1][0][0][0]
    [1][0][0][0]       [0][0][0][1]