GA in python

Share it!

Here is a sample Genetic Algorithm (GA) program written in python. There are many ways to
create a GA program, this one is probably one of the simplest.

The code is self explanatory. First we create a population of entities and assign a random
chromosome to each entity. Then we apply a fitness function to each entity. This part is
application specific, in this example we just count the number of ones in the chromosome.

The roulette function selects a pair of entities, probability of being selected depends on
how close the fitness function is to the target (or the designated solution). At this point one
of three things happen to each pair selected:

  • Crossover: at a random location on the chromosome, we swap the chromosomes.
  • Mutation: we flip a bit at a random location on the chromosome.
  • No change: the pair moves on to the next generation unchanged.

This example is pretty lame and so the idea of genes do not apply. In a real example, the bit
combinations would represent alternate solutions to the problem at hand. When one of the
entities get to the target, its chromosome represents the solution to the problem.

Genetic Algorithms are very efficient search algorithms. Here is the program:

#!/usr/bin/python
 
import random
 
CROSSOVER_RATE = 0.7
MUTATION_RATE = 0.001
#MUTATION_RATE = 0.1
POPULATION = 100
CHROMO_LEN = 300
#CHROMO_LEN = 10
GENE = 4
MAX_GENERATIONS = 300
 
class Chromosome:
    # Defines a chromosome
    def __init__(self, bits, fitness):
        self.bits = bits
        self.fitness = fitness
 
def getRandomBits(len):
    # returns string of bits len long
    bits = ""
    for i in range(len):
        bits += random.choice(["0", "1"])
    return bits
 
def findFitness(bits, target):
    # return fitness compared to target
    fitness = 0.0
    for i in range(len(bits)):
        if (bits[i] == "1"):
            fitness += 1.0
    return 500.0 - abs(target-fitness)
 
def roulette(tFitness, population):
    # implements roulette algorith to pick a random member
    randFitness = random.random() * tFitness
    fitSum = 0.0
    for i in range (POPULATION):
        fitSum += population[i].fitness
        if (fitSum > randFitness):
            return population[i].bits
    return population[0].bits
 
def crossover(str1, str2):
    # crosses over two chromosomes at a random location
    if (random.random() < CROSSOVER_RATE):
        cr = random.randint(0, CHROMO_LEN - 1)
        tmp1 = str2[0:cr] + str1[cr:]
        tmp2 = str1[0:cr] + str2[cr:]
    else:
        tmp1 = str1
        tmp2 = str2
    return [tmp1, tmp2]
 
def mutate(str1):
    tmp1 = ""
    for i in range(CHROMO_LEN):
        if (random.random() < MUTATION_RATE):
            if (str1[i] == '1'):
                tmp1 += "0"
            else:
                tmp1 += "1"
        else:
            tmp1 += str1[i]
 
    return tmp1
 
 
while (1):
    str = raw_input("Input a target: ")
    target = float(str)
    print "You typed: %5.1f \n" % target
 
    # create a population
    population = []
    for i in range(POPULATION):
        population.append(Chromosome(getRandomBits(CHROMO_LEN), 0.0))
 
    gensNeeded = 0
    done = 0
 
    while (not done):
        # assign fitness to every chromosome
        totalFitness = 0.0;
        for i in range(POPULATION):
            population[i].fitness = findFitness(population[i].bits, target)
            totalFitness += population[i].fitness
 
        # check if any solution was found
        print "Check for any solution"
        for i in range(POPULATION):
            print "==> solution: %5.2f" % (population[i].fitness)
            if (abs(population[i].fitness) > 400):
                print "==> solution: %d" % i
            if (population[i].fitness == 500.0):
                done = 1
                print population[i].bits
                print "Found solution in %d generations." % gensNeeded
                break
 
        # create a new population from the previous population
        print "Create a new population"
        i = 0
        temp_pop = []
        while (i < POPULATION):
            # pick two offsprings randomly proportional to their fitness
            offspr1 = roulette(totalFitness, population)
            offspr2 = roulette(totalFitness, population)
 
            # pick randomly to apply crossover, mutation, or unchanged
            if (random.choice([1, 2, 3]) == 1): # crossover
                [offspr1, offspr2] = crossover(offspr1, offspr2)
            elif (random.choice([1, 2, 3]) == 2): # mutation
                offspr1 = mutate(offspr1)
                offspr2 = mutate(offspr2)
            else:
                pass            # do nothing
            temp_pop.append(Chromosome(offspr1, 0.0))
            temp_pop.append(Chromosome(offspr2, 0.0))
            i = i + 2
 
        population = temp_pop
 
        print "Increment generations: %d" % (gensNeeded)
        # increment generation count
        gensNeeded = gensNeeded + 1
        if (gensNeeded > MAX_GENERATIONS):
            done = 1
            print "Could not find any solutions"
Share it!
This entry was posted in Projects and tagged , . Bookmark the permalink.

Comments are closed.