# Genetic algorithm
# String 'evolver'
# (C) Matthew Earnshaw 2010

import random

#######################################################

# Mutation rate should be kept low, crossover rate high
# Large genome sizes will slow down the search but
# resolve in fewer generations. Genome size must be even.

mutationRate = 0.01
crossoverRate = 0.95
maxGeneration = 1000
genomeSize = 500
target = "genetic"

#######################################################

chromoLen = len(target)

class Genome:
    fitSum = 0
    genomeMembers = 0
    genomeAvg = 0
    bestFit = 0
    bestChromo = 0

    def __init__(self, genome):
        Genome.genomeMembers += 1
        self.member = genome
        self.reCalc()
        
    def reCalc(self):
        self.member.sort(key=lambda x: x.fit, reverse=True)
        
        Genome.fitSum = 0
        for i in range(len(self.member)):
            Genome.fitSum += self.member[i].fit

        for i in range(len(self.member)):
            self.member[i].prob = self.member[i].fit / float(Genome.fitSum)
            
        if len(self.member) != 0:
            Genome.genomeAvg = Genome.fitSum / len(self.member)
            Genome.bestFit = self.member[0].fit
            Genome.bestChromo = self.member[0].chromo

    def printStats(self, genNum):
        print 'here'
        print   genNum,' :',\
                self.bestChromo,'-',\
                'Best:',round(self.bestFit,10),\
                'Avg:',round(self.genomeAvg,10)
 
            
class Chromosome:
    def __init__(self, chromo):
        self.chromo = chromo
        self.fit = fit(self.chromo)
        self.prob = 0

    def __getitem__(self, i):
        return self.chromo[i]
    
def fit(chromo):
    fit = 0
    
    for i in range(len(target)):
        fit += abs(ord(chromo[i]) - ord(target[i]))

    if fit!=0:
        return 1.0/fit
    else:
        print chromo
        raw_input("Found solution.") #hack
        

def randGenome():
    '''Creates a random generation 0 Genome'''

    genome = Genome([])
   
    for i in range(genomeSize):
        gene = []
        
        for j in range(chromoLen):
            gene.append( chr(random.randint(32, 126)) ) # printable ascii

        chromo = Chromosome(gene)
        genome.member.append(chromo)
        genome.reCalc()
        genome.member.sort(key=lambda x: x.fit, reverse=True)

    genome.printStats(0)    
        
    return genome


def mutate(parents):
    for i in range(len(parents)):
        if random.random() <= mutationRate:
            randGene = parents[i][random.randint(0,chromoLen-1)]
            randGene = chr(random.randint(32, 126))
    return parents

def crossover(parents):
    if random.random() <= crossoverRate:
        randPos = random.randint(0, chromoLen-1)

        parents[0][randPos:], parents[1][randPos:]\
        = parents[1][randPos:], parents[0][randPos:]

    return parents
        
def selectFittest(genome):
    '''Uses a fitness proportionate selection model
        to select two parent chromosomes'''

    parents = []
    
    while len(parents) < 2:
       
        rndChoice = random.uniform(0,1)
        for i in range(len(genome.member)):
            if rndChoice > genome.member[i].prob:
                parents.append(genome.member[i].chromo)
                del genome.member[i]
                break

    return parents


def mate(lastGen, genNum):
    
    bestFitOverall = 0

    if genNum < maxGeneration:
        genNum += 1

        newGen = Genome([])

        while len(newGen.member) < genomeSize:
            
            parents = selectFittest(lastGen)
            parents = crossover(parents)
            parents = mutate(parents)

            for i in range(0,2):
                newGen.member.append(Chromosome(parents[i]))
                newGen.reCalc()

        newGen.printStats(genNum)
        
        mate(newGen,genNum)
    
    else:
        print "Reached maximum number of generations (",maxGeneration,")"


########################################################################

print 'Genetic algorithm string evolver - v0.1 \n (C) M. Earnshaw 2010'

# Build a random initial genome
genome = randGenome()

# Start generation 1
mate(genome,1) #recursive