0

I have been trying to attempt writing a Genetic Algorithm using value encoding (fixed-length vectors of real numbers) instead of binary encoding. So far the code I have written works, but needs quite a lot more population than the binary encoded code to converge to 0.

This is the code I am using:

#one-point crossover

def crossover(p1, p2, r_cross):
c1, c2 = p1.copy(), p2.copy()


check for recombination


if rand() < r_cross:
    # select crossover point that is not on the end of the string
    pt = randint(0, len(p2))
    # perform crossover
    c1 = p1[:pt] + p2[pt:]
    c2 = p2[:pt] + p1[pt:]
return [c1, c2]


mutation operator


def mutation(nval, r_mut):
    for i in range(len(nval)):
    # check for a mutation
    if rand() < r_mut:
        # flip the bit
        nval[i] = 1 - nval[i]

I have tried working it out following the instructions in the below link to rewrite my code, but am not sure if my crossover or mutation function works as it is supposed to: How do mutation and crossover work with real-valued chromosomes?

No_Name
  • 1

1 Answers1

1

With real-valued encodings, you need to adjust your crossover and mutation operators. Basically binary encodings let something like one point crossover pick a crossover point that’s "inside" a parameter. If you have two parameters p1 and p2 that are say (0.4, 2.6) in one parent and (1.2, 1.7) in the other parent, your children can only be drawn from {(0.4, 2.6), 0.4, 1.7), (1.2, 2.6), (1.2, 1.7)}. That’s just not enough ability to explore new solutions. Binary encoding those same two parameters with say 10 bits each gives you 20 possible crossover points and thus 20 possible offspring instead of just four, because it’s able to split the encoding inside a parameter. That gives you much greater power to create offspring that are different than their parents while still being similar enough that selection is meaningful.

There are specific types of operators designed to work with real-valued encodings. Look up "simulated binary encoding" or SBX for an example. Similar story for mutation. You need an operator that is able to do a better job of generating variation. A common choice is to mutate a parameter by adding a random number to it drawn from a Normal distribution with 0 mean and some standard deviation that’s customized to be appropriate for each specific problem or parameter.

deong
  • 681
  • 3
  • 4