"""
Simple Genetic Algorithm, basic program designed for ShedSkin,
V. 1.0, 8 Feb 2006, by leonardo maffi.
"""

from random import random, randint, choice
from math import sin, pi
from copy import copy

infiniteNeg = -1e302


class Individual:
    def __init__(self, ngenes):
        self.ngenes = ngenes
        self.genome = [random()<0.5 for i in xrange(ngenes)]
        self.fitness = infiniteNeg
    def bin2dec(self, inf=0, sup=None): # Sup=0 for SS
        if sup is None: # == 0 for SS
            sup = self.ngenes - 1
        result = 0
        for i in xrange(inf, sup+1):
            if self.genome[i]:
                result += 1 << (i-inf)
        return result
    def computeFitness(self):
        self.fitness = self.fitnessFun(self.computeValuesGenome())
    def __repr__(self):
        return "".join([str(int(gene)) for gene in self.genome])

    def fitnessFun(self, x):
        return x + abs(sin(32*x))
    def computeValuesGenome(self, xMin=0, xMax=pi):
        scaleFactor = (xMax-xMin) / (1<<self.ngenes)
        return self.bin2dec() * scaleFactor


class SGA:
    def __init__(self):
        self.popSize = 200            # Ex. 200
        self.genomeSize = 16          # Ex. 16
        self.generationsMax = 100     # Ex. 100
        self.crossingOverProb = 0.75  # In [0,1] ex. 0.75
        self.selectivePressure = 0.75 # In [0,1] ex. 0.75
        self.geneMutationProb = 0.005 # Ex. 0.005

    def generateRandomPop(self):
        self.population = [Individual(self.genomeSize) for i in xrange(self.popSize)]

    def computeFitnessPop(self):
        for individual in self.population:
            individual.computeFitness()

    def mutatePop(self):
        nmutations = int(round(self.popSize * self.genomeSize * self.geneMutationProb))
        for i in xrange(nmutations):
            individual = choice(self.population)
            gene = randint(0, self.genomeSize-1)
            individual.genome[gene] = not individual.genome[gene]

    def tounamentSelectionPop(self):
        pop2 = []
        for i in xrange(self.popSize):
            individual1 = choice(self.population)
            individual2 = choice(self.population)
            if random() < self.selectivePressure:
                if individual1.fitness > individual2.fitness:
                    pop2.append(individual1)
                else:
                    pop2.append(individual2)
            else:
                if individual1.fitness > individual2.fitness:
                    pop2.append(individual2)
                else:
                    pop2.append(individual1)
        return pop2

    def crossingOverPop(self):
        nCrossingOver = int(round(self.popSize * self.crossingOverProb))
        for i in xrange(nCrossingOver):
            ind1 = choice(self.population)
            ind2 = choice(self.population)
            crossPosition = randint(0, self.genomeSize-1)
            for j in xrange(crossPosition+1):
                ind1.genome[j], ind2.genome[j] = ind2.genome[j], ind1.genome[j]

    def showGeneration_bestIndFind(self):
        fitnessTot = 0.0
        bestIndividualGeneration = self.population[0]
        for individual in self.population:
            fitnessTot += individual.fitness
            if individual.fitness > bestIndividualGeneration.fitness:
                bestIndividualGeneration = individual
        print str(self.generation) + ") average fitness, max:", fitnessTot/float(self.popSize), bestIndividualGeneration.fitness
        if self.bestIndividual.fitness < bestIndividualGeneration.fitness:
            self.bestIndividual = copy(bestIndividualGeneration)
            print "  Best individual found so far:", self.bestIndividual.computeValuesGenome()
            print "  Its fitness:", self.bestIndividual.fitness
            print "  Its genome:", self.bestIndividual


    def run(self):
        print "SAG running (press a key to stop). Population:", sga.popSize, "  Genome length:", self.genomeSize, "\n"
        self.generateRandomPop()
        self.bestIndividual = Individual(self.genomeSize)
        for self.generation in xrange(1, self.generationsMax+1):
            self.computeFitnessPop()
            self.showGeneration_bestIndFind()
            self.population = self.tounamentSelectionPop()
            self.mutatePop()
            self.crossingOverPop()


try: import psyco # Use Psyco if available
except: pass
else: psyco.full()

sga = SGA()
sga.generationsMax = 150
sga.genomeSize = 20
sga.geneMutationProb = 0.01
sga.run()