genetic_algo.py

import random
import math
from collections import defaultdict
import os
import numpy as np
import textwrap
import sys

class Chromosome:
  gene_dict = {
    "0001": "1",
    "0010": "2",
    "0011": "3",
    "0100": "4",
    "0101": "5",
    "0110": "6",
    "0111": "7",
    "1000": "8",
    "1001": "9",
    "1010": "+",
    "1011": "-",
    "1100": "*",
    "1101": "/",
  }

  def __init__(self, genome, target):
    self.target = target

    if genome:
      self.genome = genome
    else:
      self.genome = Chromosome.random_genome()

  # Allows sorting of an array of Chromosomes based on fitness.
  def __cmp__(self, other):
        return cmp(self.fitness(), other.fitness())

  # Return a string version of the binary genome as numbers/operators
  def decode_genome(self):
    # Split the genome into 4 genes
    genes = textwrap.wrap(self.genome, 4)
    
    # decode the binary genes into string form.
    decoded_genes = [Chromosome.lookup_gene(gene) for gene in genes]
    # Validate the genome
    if not Chromosome.validate_genome(decoded_genes):
      return None
    
    # If valid, join the genome together and return
    return "".join(decoded_genes)

  # Boolean value which represents if the genome is viable for evaluation.
  def is_viable(self):
    # note: "not not" just converts truthy/falsey value to True/False
    return not not self.decode_genome()

  # Return the value of the chromosome.
  def value(self):
    if not self.is_viable():
      return None
    else:
      return eval(self.decode_genome())

  # Measures fitness of a chromosome based on absolute difference between target and value.
  def fitness(self):
    if not self.is_viable():
      return None
    elif self.target-self.value():
      return sys.maxint
    else:
      return 1.0/((self.target-self.value())**2)


  ### STATIC UTILITY METHODS ###

  # Create a random 20 gene 'genome string'
  @staticmethod
  def random_genome():
    return ''.join([str(x) for x in np.random.randint(2, size=(20,))])

  # Converts binary gene to literal version.
  @staticmethod
  def lookup_gene(gene):
    try:
      return Chromosome.gene_dict[gene]
    except KeyError:
      return ""
  
  # Takes an array of genes.
  # Validates genome is mathematically operable.
  @staticmethod
  def validate_genome(genes):
    # First gene must be a number
    number_required = True
    for gene in genes:
      is_number = False
      # Try to convert string value into an int.
      try:
        int(gene)
        # If line above doesn't throw an error, string is number.
        is_number = True
      except ValueError:
        False
    
      if number_required and (not is_number):
        return False

      elif (not number_required) and is_number:
        return False

      elif gene == genes[-2]:
        number_required = True
      
      elif gene == "":
        continue

      elif number_required and is_number:
        # next run, number is not required.
        number_required = False
      elif (not number_required) and (not is_number):
        # next run, number is required.
        number_required = True

    # Return true if loop completes without failure.
    return True

os.system('clear')

### OPTIONS ###\

# The value that is sought through evolution.
target_value = 42

# Number of chromosomes to start with.
starting_population = 200

# Breeding can be between 0 and 1 inclusive.
breeding_proportion = 0.5

# Kill proportion. Controls how many of the inviable solutions die per generation
# Killing of inviable genomes is 0.005 by default.
kill_chance = 0.005

# Mutation chance can be between 0.000 and 1. 0.001 recommended.
mutation_chance = 0.01

# How many iterations of breeding/mutation are allowed.
generations_limit = 1000

# If true, breeding is random, not based on fitness. 
# If falsem, population is sorted on fitness, and breeding
# occurs between chromosomes of similar fitness.
breeding_shuffle = True

# Number of trials to run with parameters above.
trials = 5

#### END OPTIONS ####

population = [Chromosome(None, target_value) for _ in range(starting_population)]

def reset():
  global population
  population = [Chromosome(None, target_value) for _ in range(starting_population)]
  
# Breed two chromosomes by selecting a random pivot index
# and swapping the genes after that pivot forming
# two new offspring.
def breed(chrom1, chrom2):
  # select a pivot that ensures at least one base swaps
  pivot = random.randint(1, (len(chrom1.genome)-2))
  new_chrom1 = chrom1.genome[:pivot] + chrom2.genome[pivot:]
  new_chrom2 = chrom2.genome[:pivot] + chrom1.genome[pivot:]
  return (Chromosome(new_chrom1, target_value), Chromosome(new_chrom2, target_value))

# Mutate a chromosome by choosing a random location
# and 'flipping' the gene at that location.
def mutate(chrom):
  mutation_location = random.randint(0, (len(chrom.genome)-1))
  bases = list(chrom.genome)
  
  # Flip the base
  bases[mutation_location] = str((int(bases[mutation_location])-1)**2)
  return Chromosome("".join(bases), target_value)

# Determine if a chromosome matches the desired value.
def eval_population():
  for chromosome in population:
    if chromosome.value() == target_value:
      return chromosome
  return False

generations = 0 

def run_simulation(simulation_index):
  global generations
  global population

  # Counter for generations that have passed.
  generations = 0 
  # Loop until a solution is found, or the generation limit is reached, or 
  # the population dies out.
  while not eval_population() and (generations < generations_limit) and (len(population) > 0):
    # print "trial:", simulation_index+1, "/", trials, "generation: ", generations + 1, "/", generations_limit,"\r",
    
    # Kill some chromosomes, if configured to do so.
    # if kill_chance > 0:
    population = [x for x in population if not ((not x.is_viable()) and (1000*kill_chance >= random.randint(1, 1000)))]

    if breeding_shuffle:
    # Shuffle chromosome order to randomise breeding.
      random.shuffle(population)
    else:
      population.sort()
    
    # Breed the number of pairs based on breeding proportion.
    num_breeding_pairs = int((len(population)/2)*breeding_proportion)

    for index in range(0, num_breeding_pairs, 2):
      (new_crom1, new_crom2) = breed(population[index], population[index+1])
      population[index] = new_crom1
      population[index+1] = new_crom2

    # Mutate some chromosomes based on chance.
    for index, chromosome in enumerate(population):
      if 1000*mutation_chance >= random.randint(1, 1000):
        population[index] = mutate(chromosome)

    generations += 1

# Run analysis on parameters. 

results = []
spell = input("What do you want to spell?\n")

for character in spell:
  target_value = ord(character)

  success_case = None
  while not success_case:
    reset()
    run_simulation(0)
    success_case = eval_population()
  
  results.append([character, ord(character), success_case.genome, success_case.decode_genome()])
  print results[len(results)-1]

print
print "Full genome:" +  "".join([result[2] for result in results])