What is the best way to perform vector crossover in genetic algorithm?

I'm using genetic algorithm "to learn" the best parameters for a draughts/checkers AI. This parameters are stored in a vector of double.

[x1 x2 x3 x4 x5 x6 x7 x8 x9]

Actually I do the crossover using two simple methods: one-point crossover and two-point crossover. Unfortunately, in my opinion, this methods are not good enough.

For example if I have a genetic pool with:

[10 20 1]
[30 10 9]
[100 1 10]

If the theoretical optimum for x1 value is 50 I can't never find it by crossover. My only hope is to spawn a mutation with x1=50 good enough to pa开发者_运维技巧ss in the next generation.

So, there is a better way to perform crossover with an array of numbers?

---

It seems that you have an encoding problem,- not a crossover. If you want more variability in chromosome - then encode data as sequence of bytes (or even bits). Suppose you have 3 integer parameters,- then you can represent them as 3*4=12 byte vector:

{114,2,0,214, // first 32-bit int
14,184,220,7, // second 32-bit int
145,2,32,12,  // etc...
}

then after crossover your ints will evolve with great variability. Also you can use not 1/2 point crossover, but uniform crossover - when at each chromosome point you will randomly decide what gene version you will use. In such case you will get even more variability. But keep in mind that too much variability in crossover is also disastrous because results in population which may never reach optimal solution, because even sub-optimal solution are teared apart by big random fluctuations in crossover operation. Stabilized evolution is main keyword here.

Another approach - is not to use genetic algorithm, but evolution strategy algorithms which changes all genes in chromosome. But this approach is feasible if number of different gene versions is not very big. So this may not fit your problem with floats/doubles.

HTH!

---

It really depends on how the fitness function. In the crossover you could also average over the values (again, if it make sense for the fitness function) but probably this would drive the algorithm to converge too easily to a population with very similar individuals.

I think that is the mutation that should drive the single values toward the best ones, you should get 50 because of the mutation if you can't get it because of the crossover.

Consider doing some kind of local search on the single individuals as well (memetic algorithm).

---

There exist a very huge number of possible crossover (and mutation) and the literature about it is almost infinite. If you wish to use that representation (vector of double) then you might want to look at the simulated binary crossover or blend crossover and gaussian mutation operator, they are most likely gonna help you to find children that are blends of their parents genes rather than simple exchanges.

For example, the simulated binary with eta = 0.5 will give (there is randomization implied) from those two parents

[30 10 9]
[100 1 10]

The two childs

[52 8 9]
[77 2 10]

As far as I know, almost all major EC frameworks implement those operators (Open Beagle, ECJ, DEAP, EO, etc.)

---

The crossover algorithm in my GA is different than what you are using--not better, just different. In sum, rather than substitution, i coded crossover as an array splicing/concatenation operation in which the splicing point is randomized (and also 'synchronized' so that when the two spliced portions are assembled the child vector that results is the same length as each parent.

I think it's much easier to explain in code:

DOMAIN_LENGTH = 14

def crossover(v1, v2):
    crossover_point = random.randint(1, DOMAIN_LENGTH-2)
    return v1[:crossover_point] + v2[crossover_point:]

# create a simple function to generate a couple of 'parent' vectors
>>> fnx = lambda v : [random.choice(range(10)) for c in range(DOMAIN_LENGTH)]

# now generate those parent vectors
>>> v1 = fnx(DOMAIN_LENGTH)
>>> v2 = fnx(DOMAIN_LENGTH)
>>> v1
  [7, 9, 5, 6, 6, 7, 6, 9, 8, 6, 6, 4, 5, 8]
>>> v2
  [2, 2, 9, 7, 1, 4, 6, 9, 0, 7, 1, 9, 3, 0]
>>> len(v1); len(v2)
  14
  14

# create the child vector via crossover
>>> child_01 = crossover(v1, v2)
>>> child_01
  [7, 9, 9, 7, 1, 4, 6, 9, 0, 7, 1, 9, 3, 0]
>>> len(child_01)
  14

so for:

• domain size (vector length) of 5
• a *crossover_point* of 2, and t
• he two parent vectors are [4, 3, 2, 4, 8] and [1, 3, 1, 6, 3]

then:

# fragment contributed from first parent:
>>> f1 = p1[:2]
>>> f1
  [4, 3]

# fragment contributed from second parent:
>>> f2 = p2[2:]
>>> f2
  [1, 6, 3]

# now just concatenate the two fragments to produce the child fragment
>>> child = f1 + f2
>>> child
  [4, 3, 1, 6, 3]
>>> len(child) == len(p2)
  True