Warm tip: This article is reproduced from stackoverflow.com, please click
algorithm multidimensional-array genetic-algorithm mutation crossover

genetic algorithm

发布于 2020-03-29 12:48:32

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?

Questioner
Corbuk
Viewed
85
分享
manlio 2020-01-31 17: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.

Related issues

1
pinescript
2
Crossover and crossunder functions don't respect the parameters I'm giving pine script
3
best crossover for route optimization
4
Generate a Crossover condition in Pinescript
5
Why isn't my mixed model loop working? (RStudio, Crossover design)
6
How to crossover moving average with a specific candle height? Pinescript
7
Backtest not showing any results for a SMA crossover script in tradingview
8
How to perform crossover of two nested lists without changing the contents inside their sub lists in Python?
9
how many times we should used ford-Fulkerson?
10
Rectangle selection algorithm