How to perform crossover in a 2-dimensional array - genetic algorithm

Question

I have the following two chromosomes which are represented as a 2D array.

// First chromosome
[
  [ 12 45 23 ]
  [ 34 01 89 ]
  [ 33 90 82 ]
]

// Second chromosome
[
  [00 45 89 ]
  [00 00 34 ]
]

The constraints on the chromosome are that each array in the chromosome array must remain together. For example in the first chromosome [ 12 45 23 ] must remain together. With this in mind, I believe the way to perform crossover with the above chromosome structure is to randomly select a horizontal crossover point. such as the following:

// First produced off-spring
[
  [ 12 45 23 ] // First chromosome
  [ 00 00 34 ] // Second chromosome
]

// Second produced off-spring
[
  [ 00 45 89 ] // Second chromosome
  [ 34 01 89 ] // First chromosome
  [ 33 90 82 ] // First chromosome
]

Is this the correct way to perform mutation on a 2D chromosome array which rows must remain intact? If this is, does this method have a specific name? Or would this come under One-point crossover?

It is very dependant of the problem, which you are solving. Without this information it will be difficult to say. — Todor Balabanov, Jan 26 '20 at 12:42

score 2 · Accepted Answer · answered Jan 31 '20 at 09:52

does this method have a specific name? Or would this come under One-point crossover?

In various papers about variable length genetic algorithms it's called one point crossover.

For variable length chromosomes one point crossover is often proposed in a more general way: you can select a distinct crossover point for each chromosome. E.g.

C1 = [ A1, A2, A3, A4, A5, A6]

C2 = [ B1, B2, B3, B4]

Choosing crossover point 1 for C1 and 3 for C2 you get:

C1 = [ A1 | A2, A3, A4, A5, A6]

C2 = [ B1, B2, B3 | B4]


C1' = [A1 B4]
C2' = [B1, B2, B3, A2, A3, A4, A5, A6]

This allows the chromosome length to start growing. Depending on the specific problem it could be a requirement or just bloating (in both cases you may need to account for that in the fitness function).

Is this the correct way to perform mutation on a 2D chromosome array which rows must remain intact?

It's a simple method (so a good one). Uniform crossover is another simple approach.

Synapsing Variable-Length Crossover: Meaningful Crossover for Variable-Length Genomes (Benjamin Hutt and Kevin Warwick, IEEE Transactions on Evolutionary Computation, vol. 11, no. 1, february 2007) describes other interesting (more complex) possibilities.

The best crossover is very problem specific.

How to perform crossover in a 2-dimensional array - genetic algorithm

1 Answers1