Genetic Algorithm using fixed length vector

Question

I am trying to implement a genetic algorithm using fixed-length vectors of real numbers. I found a simple implementation online using a binary encoded values. My confusion arises when I am trying to figure out a way to initialise the array and set the bounds for this algorithm.

Below is a snippet of the code with binary decoded code:

def decode(bounds, n_bits, bitstring):
decoded = list()
largest = 2**n_bits
for i in range(len(bounds)):
    # extract the substring
    start, end = i * n_bits, (i * n_bits)+n_bits
    substring = bitstring[start:end]
    # convert bitstring to a string of chars
    chars = ''.join([str(s) for s in substring])
    # convert string to integer
    integer = int(chars, 2)
    # scale integer to desired range
    value = bounds[i][0] + (integer/largest) * (bounds[i][1] - bounds[i][0])
    # store
    decoded.append(value)
return decoded

Can this be rewritten as an array of real numbers to encode a solution and not a bit string?

The full code is from the following article: Simple Genetic Algorithm From Scratch in Python

# genetic algorithm search for continuous function optimization
from numpy.random import randint
from numpy.random import rand


# objective function
def objective(x):
    return x[0] ** 2.0 + x[1] ** 2.0


# decode bitstring to numbers
def decode(bounds, n_bits, bitstring):
    decoded = list()
    largest = 2 ** n_bits
    for i in range(len(bounds)):
        # extract the substring
        start, end = i * n_bits, (i * n_bits) + n_bits
        substring = bitstring[start:end]
        # convert bitstring to a string of chars
        chars = ''.join([str(s) for s in substring])
        # convert string to integer
        integer = int(chars, 2)
        # scale integer to desired range
        value = bounds[i][0] + (integer / largest) * (bounds[i][1] - bounds[i][0])
        # store
        decoded.append(value)
    return decoded


# tournament selection
def selection(pop, scores, k=3):
    # first random selection
    selection_ix = randint(len(pop))
    for ix in randint(0, len(pop), k - 1):
        # check if better (e.g. perform a tournament)
        if scores[ix] < scores[selection_ix]:
            selection_ix = ix
    return pop[selection_ix]


# crossover two parents to create two children
def crossover(p1, p2, r_cross):
    # children are copies of parents by default
    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(1, len(p1) - 2)
        # perform crossover
        c1 = p1[:pt] + p2[pt:]
        c2 = p2[:pt] + p1[pt:]
    return [c1, c2]


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


# genetic algorithm
def genetic_algorithm(objective, bounds, n_bits, n_iter, n_pop, r_cross, r_mut):
    # initial population of random bitstring
    pop = [randint(0, 2, n_bits * len(bounds)).tolist() for _ in range(n_pop)]
    # keep track of best solution
    best, best_eval = 0, objective(decode(bounds, n_bits, pop[0]))
    # enumerate generations
    for gen in range(n_iter):
        # decode population
        decoded = [decode(bounds, n_bits, p) for p in pop]
        # evaluate all candidates in the population
        scores = [objective(d) for d in decoded]
        # check for new best solution
        for i in range(n_pop):
            if scores[i] < best_eval:
                best, best_eval = pop[i], scores[i]
                print(">%d, new best f(%s) = %f" % (gen, decoded[i], scores[i]))
        # select parents
        selected = [selection(pop, scores) for _ in range(n_pop)]
        # create the next generation
        children = list()
        for i in range(0, n_pop, 2):
            # get selected parents in pairs
            p1, p2 = selected[i], selected[i + 1]
            # crossover and mutation
            for c in crossover(p1, p2, r_cross):
                # mutation
                mutation(c, r_mut)
                # store for next generation
                children.append(c)
        # replace population
        pop = children
    return [best, best_eval]


# define range for input
bounds = [[-5.0, 5.0], [-5.0, 5.0]]
# define the total iterations
n_iter = 100
# bits per variable
n_bits = 16
# define the population size
n_pop = 100
# crossover rate
r_cross = 0.9
# mutation rate
r_mut = 1.0 / (float(n_bits) * len(bounds))
# perform the genetic algorithm search
best, score = genetic_algorithm(objective, bounds, n_bits, n_iter, n_pop, r_cross, r_mut)
print('Done!')
decoded = decode(bounds, n_bits, best)
print('f(%s) = %f' % (decoded, score))

Jonny · Accepted Answer · 2022-11-19 02:18:47Z

It appears that you are referencing the code in this article: Simple Genetic Algorithm From Scratch in Python.

The bit-vector representation of individuals that is used in the starting code is an encoding of a real-valued vector. If you want your representation of an individual to be a real-valued vector, it means that you don't have do any decoding or encoding at all.

Initialize your population to be a vector of random real values within the bounds

def genetic_algorithm(objective, bounds, n_iter, n_pop, r_cross, r_mut):
    # initial population of random real-valued vectors
    pop = [[random.uniform(bound[0], bound[1]) for bound in bounds] for _ in range(n_pop)]
...

Then, in the genetic algorithm itself, there is no need to decode the population, since they are already real-valued vectors.

# genetic algorithm
def genetic_algorithm(objective, bounds, n_iter, n_pop, r_cross, r_mut):
    # initial population of random real-valued vectors
    pop = [[random.uniform(bound[0], bound[1]) for bound in bounds] for _ in range(n_pop)]
    # keep track of best solution
    best, best_eval = 0, objective(pop[0])
    # enumerate generations
    for gen in range(n_iter):
        # evaluate all candidates in the population
        scores = [objective(d) for d in pop]
        # check for new best solution
        for i in range(n_pop):
            if scores[i] < best_eval:
                best, best_eval = pop[i], scores[i]
                print(">%d, new best f(%s) = %f" % (gen, pop[i], scores[i]))
        # select parents
        selected = [selection(pop, scores) for _ in range(n_pop)]
        # create the next generation
        children = list()
        for i in range(0, n_pop, 2):
            # get selected parents in pairs
            p1, p2 = selected[i], selected[i + 1]
            # crossover and mutation
            for c in crossover(p1, p2, r_cross):
                # mutation
                mutation(c, r_mut)
                # store for next generation
                children.append(c)
        # replace population
        pop = children
    return [best, best_eval]

The one thing that remains to be addressed is to modify the mutation and crossover functions so that they operate on real-valued vectors, instead of bit-strings. There are many approaches to how you could implement mutation and cross-over for real-valued vectors; some examples are listed in this StackOverflow post.

You have a genome with certain genes:
genome = { GeneA: value, GeneB: value, GeneC: value }
So take for example:
genome = { GeneA: 1, GeneB: 2.5, GeneC: 3.4 }
A few examples of mutation could be:

Switch around two genes: { GeneA: 1, GeneB: 3.4, GeneC: 2.5 }

Add/substract a random value from a gene: { GeneA: 0.9, GeneB: 2.5, GeneC: 3.4 }

Suppose you have two genomes:
genome1 = { GeneA: 1, GeneB: 2.5, GeneC: 3.4 }
genome2 = { GeneA: 0.4, GeneB: 3.5, GeneC: 3.2 }
A few examples of crossover could be:

Taking the average: { GeneA: 0.7, GeneB: 3.0, GeneC: 3.3 }

Uniform (50% chance): { GeneA: 0.4, GeneB: 2.5, GeneC: 3.2 }

N-point crossover: { GeneA: 1, | CROSSOVER POINT | GeneB: 3.5, GeneC: 3.2 }

I had one more doubt regarding this code, isn't the mutation function already suitable for value encoding? As given in the article.
The mutation function given in the article takes a bitstring. It loops over each bit in the bitstring (which is a list of 1's and 0's) and flips some of the bits at random. In the real-valued vector representation, the mutation function should take in a single real value, and return a new real value that has been randomly modified in some way.

Collectives™ on Stack Overflow

Genetic Algorithm using fixed length vector

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related