@makiolo

# -*- coding: utf-8 -*-
# Implementacion de un Algoritmo genetico sencillo
# Autor: Ricardo Marmolejo Garcia
# Dado:
# f(x) = A*x^2-4*x-1
# Y 3 puntos:
#
tests = []
tests.append([-10, 339])
tests.append([0.0, -1])
tests.append([10, 259])
# Calcular A

# La solucion es 3 y es hallada mediante AG
# El ejemplo no es muy util, se centra en ejemplificar un AG sencillo

#########################################################
# Define la probabilidad de que haya una mutacion
pMutacionRatio = 1.0 # Siempre

# Define la probabilidad de que haya un cruce
pCruceRatio = 1.0 # Siempre

# Define la maxima perturbacion en la mutacion
maxPerturbacion = 0.05

# criterio de terminacion
UMBRAL_ERROR = 0.0001

################ AUXILIAR ###############################

import random
import math

def randomClamp(a, b):
    return random.random() * (b - a) + a

def ordenar_por_fitness(ind1, ind2):
    if ind1.fitness > ind2.fitness:
        return +1
    else:
        return -1

class Cromosoma:
    def __init__(self, a, b, c):
        self.a = a
        self.b = b
        self.c = c
        self.fitness = 0.0

    def __repr__(self):
        # aplanamiento del tipo a texto
        return "f(x) = [%f] * x^2 + [%f] * x + [%f] - ERROR = %f" % (self.a, self.b, self.c, self.fitness)

    def computarFitness(self):
        # nos dice como de apto es el individuo
        # El proceso AG busca la minimizacion, por tanto
        # menos es mejor
        error = 0
        for test in tests:
            x = test[0]
            y = test[1]
            error += y - (self.a * x * x + self.b * x + self.c)

        self.fitness = error * error

    def cruce(self, otro):

        # si hay cruce ...
        if (randomClamp(0, 1) < pCruceRatio):
            # Es un cruce multipunto
            # tenemos 3 genes con 2 puntos de corte
            # elegimos las 2 formas posibles aleatoriamente al 50%
            if (randomClamp(0, 1) < 0.5):
                # Cruce impar
                aa = self.a
                bb = otro.b
                cc = self.c
            else:
                # Crece par
                aa = otro.a
                bb = self.b
                cc = otro.c
        else:
            # No hay cruce
            aa = self.a
            bb = self.b
            cc = self.c

        return Cromosoma(aa, bb, cc)

    def mutar(self):

        # si hay mutacion ...
        if (randomClamp(0, 1) < pMutacionRatio):

            # maxPerturbacion es una constante que marca la maxima perturbacion
            # Esto define tambien la velocidad de convergencia
            # Un valor pequenio puede hacer converger lento, pero:
            # Un valor grande podria saltarse la solucion
            # solo mutamos A
            self.a += randomClamp(-1, 1) * maxPerturbacion

################ EMPIEZA PROGRAMA ###############################

# generar poblacion inicial
# 100 cromosomas son repartidos aleatoriamente en A
# El espacio de soluciones de A es un rango grande
cromosomas = []
for i in range(100):
    # 3, -4, -1
    cromosomas.append( Cromosoma(randomClamp(-10000, 10000), -4, -1) )

fin = False
gen = 0
while not fin:
    # ***** EVALUAR LA POBLACION
    for ind in cromosomas:
        ind.computarFitness()

    # SELECCION
    # En este caso *elitisita*: cogemos los 2 mejores
    # Esto supone practicamente un algoritmo voraz
    # y es facil caer en un optimo local, aunque en el ejemplo no pasa
    # Los AG no garantizan encontrar un optimo global
    # Para coger a los 2 primeros hay que ordenar por adaptacion
    cromosomas.sort(ordenar_por_fitness)
    padre = cromosomas[0]
    madre = cromosomas[1]

    # REPRODUCCION / CRUCE DE LOS SELECCIONADOS
    hijo = padre.cruce(madre)

    # MUTAMOS el descendiente
    hijo.mutar()

    # CRITERIO DE REEMPLAZO
    # Eliminar tantos peores como mejores haya (1 en este caso)
    cromosomas = cromosomas[:-1]

    # INSERCION de los hijos en la poblacion
    cromosomas.append( hijo )

    # actualizar criterio de terminacion
    fin = math.fabs(padre.fitness) < UMBRAL_ERROR

    # mostrar adaptacion del mejor adaptado
    print padre.fitness
    gen += 1

# Mostrar la solucion
print "Problema: f(x) = A*x^2-4*x-1 y 3 puntos. Calcular A:"
print "Solucion A = %f - Con un Error de %f en %d generaciones" % (cromosomas[0].a, cromosomas[0].fitness, gen)