Exemplo de Algoritmo Genético v2

'''
Created on 24/06/2013

@author: Luis Antonio Tavares (luis.tavares@msn.com)
'''
import string
import random

def inicia():
    alvo = 'BRASIL'                     # alvo pretendido pelo algoritmo
    numIndividuos = 400                 # tamanho da populacao
    pm = 0.02                           # porcentagem de mutacao
    limite = 200                        # limite de geracoes

    comp = len(alvo)                    # comprimento da string
    geracao = 1                         # numero da geracao

    print 'Exemplo Algoritmo Genetico'
    print 'Individuo alvo: ', alvo
    print 'Tamanho do individuo: ', comp
    print 'Tamanho da populacao: ', numIndividuos
    print 'Chance de mutacao: ', pm, '\n'

    p = geraPopulacaoInicial(comp, numIndividuos)
    print 'Populacao: ', p

    '''Calculando o fitness de cada individuo (pais)'''
    n = calculaNota(p, alvo, comp)

    ''' Mostrando melhor resultado ate o momento'''
    nMelhor, vMelhor = achaMelhor(p, n)
    print "\nGeracao: ", geracao
    print "Melhor solucao: ", vMelhor
    print "Fitness: ", nMelhor, "\n"

    ''' Verificando se a resposta ja foi encontrada '''
    if nMelhor == 0:
        return

    while geracao <= limite:
        ''' Proxima geracao '''
        geracao += 1

        ''' Fazendo o crossover de um ponto de 2 em 2 pais'''
        filhos = reproduz(p, comp, numIndividuos)

        ''' Aplicando mutacao nos filhos gerados '''
        filhos, numMutacoes = aplicaMutacao(filhos, comp, pm)
        print 'Numero de mutacoes: ', numMutacoes

        ''' Calculando fitness dos filhos '''
        notaFilhos = calculaNota(filhos, alvo, comp)

        ''' Mostrando melhor resultado ate o momento'''
        nMelhor, vMelhor = achaMelhor(filhos, notaFilhos)
        print "\nGeracao: ", geracao
        print "Melhor solucao: ", vMelhor
        print "Fitness: ", nMelhor, "\n"

        ''' Verificando se ja achou a resposta entre os filhos gerados '''
        if nMelhor == 0:
            break

        ''' Juntando pais e filhos em uma mesma variavel '''
        p = p + filhos
        notas = n + notaFilhos

        ''' Selecionando os mais aptos para a proxima geracao '''
        sobreviventes = roleta(p, notas, numIndividuos)
        p = sobreviventes

        '''Calculando o fitness de cada individuo da populacao '''
        n = calculaNota(p, alvo, comp)

''' Faz a selecao dos mais aptos para continuar na proxima geracao atraves da roleta viciada '''
def roleta(p, notas, numIndividuos):
    notasAux = map(lambda x: 1.0 / x, notas)
    soma  = sum(notasAux)
    normalizadas = map(lambda x: x / soma, notasAux)

    ''' Calculando os valores acumulados da nota '''
    acumulada = []
    vAcumulado = 0
    for nota in normalizadas:
        vAcumulado = vAcumulado+nota
        acumulada.append(vAcumulado)

    ''' Sorteando individuos para compor a populacao pelo metodo da roleta viciada '''
    selecionados = [0] * len(p)
    i = 0               # conta quantos individuos ja foram selecionados
    sobreviventes = []  # indica quem ja foi selecionado (valor 1), pra nao selecionar um cara 2 vezes
    while (i <= numIndividuos):
        vSorteo = random.random()
        j = 0 # varre o vetor acumulada
        while vSorteo > acumulada[j]:
            j += 1
        if selecionados[j] == 0:
            sobreviventes.append(p[j])
            selecionados[j] = 1
            i += 1
    return sobreviventes

''' Aplica mutacao nos individuos de acordo com porcentagem de chance '''
def aplicaMutacao(filhos, comp, pm):
    numMutacoes = 0
    filhosPosMutacao = []
    for filho in filhos:
        acaso = random.random()
        if acaso <= pm:
            ponto = random.randint(0,comp-1)
            letraAletoria = random.choice(string.ascii_uppercase)
            filhoMutante = filho[:ponto] + letraAletoria + filho[ponto+1:]
            filho = filhoMutante
            numMutacoes += 1
        filhosPosMutacao.append(filho)
    return filhosPosMutacao, numMutacoes

''' Reproducao atraves de crossover de 2 pontos '''
def reproduz(p, comp, nIndividuos):
    f = []
    i = 0
    while i < nIndividuos:
        ponto = random.randint(1,comp-1)

        pai1 = p[i]
        pai2 = p[i+1]
        filho1 = pai1[0:ponto] + pai2[ponto:comp]
        filho2 = pai2[0:ponto] + pai1[ponto:comp]

        f.append(filho1)
        f.append(filho2)
        i += 2
    return f


''' Encontra a melhor solucao ate o momento '''
def achaMelhor(p, n):
    melhorNota = min(n)
    indice = n.index(melhorNota)
    melhorValor = p[indice]
    return melhorNota, melhorValor

''' Calcula o fitness de toda a populacao '''
def calculaNota(p, alvo, comp):
    notas = []
    for individuo in p:
        dif = 0
        for i in range(comp):
            dif += abs(ord(individuo[i]) - ord(alvo[i]))
        notas.append(dif)
    return notas

''' Gera a populacao inicial para o algoritmo '''
def geraPopulacaoInicial(comp, numIndividuos):
    pop = []
    for i in range(numIndividuos):
        tokens = string.ascii_uppercase #quais caracteres aceitos
        numChar = comp #numero de caracteres por segmento
        aleatoString = ''.join(random.choice(tokens) for y in range(numChar))
        pop.append(aleatoString)
    return pop

if __name__ == '__main__':
    inicia()