#!/usr/bin/python
##########################
#
# Simple Genetic Algorithm
#
# Joerg Rings 100114
#
##########################

import sys

import copy
import logging
import os.path
import random
import re
import string

###################
#
# Use logging
# One to console (>=INFO)
# All to file (>=DEBUG)
#

log = logging.getLogger("log")
log.setLevel(logging.DEBUG)

h1 = logging.FileHandler("logging.out")
h1.setLevel(logging.DEBUG)
formatter = logging.Formatter('%(levelname)s ## %(message)s ')
h1.setFormatter(formatter)

h2 = logging.StreamHandler(sys.stdout)
h2.setLevel(logging.INFO)
formatter2 = logging.Formatter('%(levelname)s ## %(message)s ')
h2.setFormatter(formatter2)
log.addHandler(h1)
log.addHandler(h2)


####################
#
# Functions
#

def Usage():
    """Wrong parameters given, exits"""
    log.error("Usage: ga.py TARGETSTRING population-size crossover-probability mutation-rate generations")
    sys.exit()

def getLetter():
    """Returns a random letter from A-Z"""
    
    iRandom = random.randint(0,25)
    return string.ascii_uppercase[iRandom]

def getFitness(sTarget, sChromo):
    """Calculates the match between two strings
    Fitness adds 1 for each matching letter"""

    if len(sTarget) != len(sChromo):
        log.error("Target string and chromosome have different lengths!")
        sys.exit()

    iFitness = 0

    for i in range(len(sTarget)):
        if sTarget[i] == sChromo[i]:
            iFitness += 1

    return iFitness

def printChromo(chromo, iCutPos = -1):
    st = ""
    for i in range(len(chromo)):
        if iCutPos != 0:
            if iCutPos == i:
                st += "|"
        st += chromo[i]

    return st

def printGeneration(aC, iG):
    log.info("Generation %i:" % (iG,))
    for i in range(len(aC)):
        chromo = aC[i][0]
        iFitness = aC[i][1]
        log.debug("Chromosome %i: %s (Fitness %i)" 
                 % ((i+1), printChromo(chromo), iFitness))

def printFittest(aChromosomes):
    """Print fittest individual"""
    iMax = 0
    indi = ""
    med = 0
    for chromo in aChromosomes:
        med += float(chromo[1])
        if chromo[1] > iMax:
            iMax = chromo[1]
            indi = chromo[0]

    log.info("Fittest individual (Values %i/%i/%f): %s" %
             (iMax, len(indi), med/float(len(aChromosomes)), printChromo(indi)))
    if iMax == len(indi):
        log.info("Success!")
        sys.exit()

###################
###################
###################
#
# MAIN SCRIPT
#
#

##################
#
# Get parameters from command line
# 
# 1: Target String (without spaces or anything but A-Z)
# 2: Population size
# 3: Crossover probability
# 4: Mutation probability per gene
# 5: Number of generations

if len(sys.argv) < 6: 
    Usage() #exits

sTarget = sys.argv[1].upper() #all in CAPS
sTarget = re.sub("[^A-Z]", "", sTarget) #Remove all non-letter characters
iLength = len(sTarget) #chromosome length

log.info("The target string will be %s" % (sTarget,))

try:
    iPopSize = int(sys.argv[2])    #population size
    fCrossProb = float(sys.argv[3])#crossover probability
    fMutRate = float(sys.argv[4])  #mutation rate
    iGenerations = int(sys.argv[5])#number of generations
except Exception, e:
    log.error(str(e))
    Usage() #exits


###################
#
# Initialize population
# of n chromosome
# with random letters
#

iGeneration = 0

aChromosomes = []
for i in range(iPopSize):
    lChromosome = [getLetter() for j in range(iLength)]
    log.debug("Chromosome %i initialized as %s" % ((i+1), printChromo(lChromosome)))
    iFitness = getFitness(lChromosome,sTarget)
    log.debug("Chromosome %i has Fitness %i" % ((i+1), iFitness))
    aChromosomes.append((lChromosome,iFitness)) #Chromosome and fitness

##################
#
# Generations

for iGen in range(iGenerations):
    printGeneration(aChromosomes, iGeneration)
    iGeneration += 1

    #Build proposal zoo
    aZoo = []
    for chromo in aChromosomes:
        iFitness = chromo[1]
        aZoo.append(copy.deepcopy(chromo[0])) #one chance for everyone
        
        #More chances for fit individuals
        for i in range(iFitness):
            aZoo.append(copy.deepcopy(chromo[0])) 
            #this copy stuff is needed as python does copy by reference only
        
    #Keep the best in
    iMax = 0
    best = None
    for chromo in aChromosomes:
        if chromo[1] >= iMax:
            iMax = chromo[1]
            sndbest = best
            best = chromo

    aChromosomes = []
    #Breed n new individuals
    #The best one is in
    if best != None:
        aChromosomes.append(best)
    if sndbest != None:
        aChromosomes.append(sndbest)
    
    while len(aChromosomes) < iPopSize:

        #Breed them by making a cut at a random position and combining the parts
        #then mutating the child
        aParents = random.sample(aZoo,2) #Choose two individuals from the zoo

        #Crossover
        fProb = random.random()
        if fProb <= fCrossProb:
            
            iCutPosition = random.randint(0,iLength)

            child1 = copy.deepcopy(aParents[0][0:iCutPosition] + aParents[1][iCutPosition:])
            child2 = copy.deepcopy(aParents[1][0:iCutPosition] + aParents[0][iCutPosition:])
    
            log.debug("%s and %s breeded %s" 
                      % (printChromo(aParents[0]),printChromo(aParents[1]),
                         printChromo(child1, iCutPosition)))
            log.debug("%s and %s breeded %s" 
                      % (printChromo(aParents[0]),printChromo(aParents[1]),
                         printChromo(child2, iCutPosition)))
        else:
            child1 = copy.deepcopy(aParents[0])
            child2 = copy.deepcopy(aParents[1])

        #Mutate
        iMut = 0
        for j in range(len(child1)):
            fMutate = random.random() #float between 0 and 1
            if fMutate < fMutRate:
                child1[j] = getLetter() #random new letter
                iMut += 1

        log.debug("Child mutated to %s (%i Mutations)" % (printChromo(child1),iMut))

        aChromosomes.append((child1,getFitness(child1,sTarget)))
        iMut = 0
        for j in range(len(child2)):
            fMutate = random.random() #float between 0 and 1
            if fMutate < fMutRate:
                child2[j] = getLetter() #random new letter
                iMut += 1

        log.debug("Child mutated to %s (%i Mutations)" % (printChromo(child2),iMut))

        if len(aChromosomes)<iPopSize:
            aChromosomes.append((child2,getFitness(child2,sTarget)))

    printFittest(aChromosomes)