basicGA.py

from random import randint
from operator import add
import random

def individual(length, minimum, maximum):
    "Initialize population member"
    return [randint(minimum, maximum) for x in range(length)]
  
def population(count, length, minimum, maximum):
    """
    Initialize a population

    count: the number of individuals in the population
    length: the number of values per individual
    min: the min possible value in an individual
    max: the max possible value in an individual
    """

    return [individual(length, minimum, maximum) for x in range(count)]
  
def fitness(individual, target):
    " Determine the fitness score of an individual. Lower is better"
    
    sum_value = sum(individual)
    return abs(target-sum_value)
  

def grade(pop, target):
    "Find the average fitness for a population"
    sum_total = sum(fitness(x, target) for x in pop)
    return sum_total/(len(pop) * 1.0)
  

def evolve(pop, target, retain=0.2, random_select=0.05, mutate=0.02):
    graded = [ (fitness(x, target), x) for x in pop]
    graded = [ x[1] for x in sorted(graded)]
    retain_length = int(len(graded)*retain)
    parents = graded[:retain_length]

    # randomly add other individuals to promote genetic diversity
    for individual in graded[retain_length:]:
        if random_select > random.random():
            parents.append(individual)

    # mutate some individuals
    for individual in parents:
        if mutate > random.random():
            pos_to_mutate = randint(0, len(individual)-1)
            # this mutation is not ideal, because it
            # restricts the range of possible values,
            # but the function is unaware of the min/max
            # values used to create the individuals,
            individual[pos_to_mutate] = randint(
                min(individual), max(individual))

    # crossover parents to create children
    parents_length = len(parents)
    desired_length = len(pop) - parents_length
    children = []
    while len(children) < desired_length:
        male = randint(0, parents_length-1)
        female = randint(0, parents_length-1)
        if male != female:
            male = parents[male]
            female = parents[female]
            half = len(male) / 2
            child = male[:len(male)//2] + female[:len(female)//2:]
            children.append(child)

    parents.extend(children)
    return parents
  
# Example usage
target = 1071
p_count = 100
i_length = 7
i_min = 0
i_max = 500
p = population(p_count, i_length, i_min, i_max)
fitness_history = [grade(p, target),]

k = False
counter = 0

while k == False:
   
    counter +=1
    fitness_history = [grade(p, target),]
    for i in range(200):
        p = evolve(p, target)
        fitness_history.append(grade(p, target))
    if fitness_history[-1]  <  1:
        k = True
    print("Generation Count: "+ str(counter) + " Grade: "+ str(grade(p, target)))