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"