Algorítimo genético

Marcos04
(usa Outra)

Enviado em 15/06/2020 - 14:59h

Estou com um problema num exercício sobre algorítimo genético, preciso mostra a melhor frase o professor deu o algorítimo com uma frase, só preciso colocar mais duas e calcular qual é a melhor. A alteração tem que ser feita na função calculaAdaptabilidade, se alguém puder dar uma luz, pois não consegui entender quase nada. Obrigado!

As frases que tem que ter são essas: METHINKS IT IS LIKE A WEASEL

METHINKS IT IS LIKE AN APPLE

IGUESS THAT IS LIKE A WEASEL

import random

import math



_POPULACAO       = 100

_CROMOSSOMO      = 28

_CONDICAO_PARADA = 1000

_MAXIMO_MUTACOES = 10

_ALFABETO        = 'ABCDEFGHIJKLMNOPQRSTUVXWY '

_INICIO          = 'WDLMNLT DTJBKWIRZREZLMQCO P '

_ALVO            = 'METHINKS IT IS LIKE A WEASEL'



def geraPopulacaoInicial():

    cromossomos = []

    for i in range(_POPULACAO):

        cromossomo = []

        for j in range( 28 ):

            cromossomo.append( _INICIO[j] )

        cromossomos.append( cromossomo[:] )

    return cromossomos[:]



# Quanto mais letras mais adaptado 

def calculaAdaptabilidade( populacao ):

    indice = []

    for i in range( _POPULACAO ):

        indice.append(0)



    for i in range( _POPULACAO ):

        indiceElemento = 1

        incremento = 1

        w = 1

        for j in range( _CROMOSSOMO ):

            if populacao[i][j] == _ALVO[j]:

                incremento = incremento+1000+w*100

                w = w+1

        valor = int( math.floor(incremento) )        

        indice[i] = indiceElemento+valor

    return indice[:]



def mostraMelhorDaGeracao( condicaoParada, populacao, adaptabilidade ):

    melhor = 0

    j = 0

    posicao = 0

    for i in adaptabilidade:

        if i > melhor:

            melhor = i

            posicao = j  

        j = j + 1

    print( "Melhor cromossomo " + str( posicao ) + " da " + str( condicaoParada ) + " geração, com indice = " + str( melhor ) )

    texto = ""  

    for j in populacao[posicao]:

        texto = texto + j

    print (texto)



def somaIndices( adaptabilidade ):

    somatorio = 0

    for i in adaptabilidade:

        somatorio = somatorio + i

    return somatorio



def substituiPelaMelhor(populacao, adaptabilidade ):

    melhor = 0

    j = 0

    posicao = 0

    for i in adaptabilidade:

        if i > melhor:

            melhor = i

            posicao = j  

        j = j + 1

    melhor = populacao[posicao][:]    

    for i in range( _POPULACAO ):

        populacao[i] = melhor[:]



def geraCrossingOver( populacao, adaptabilidade ):

    soma = somaIndices( adaptabilidade )

    print( "Soma dos indices: " + str(soma) )

    novaGeracao = []

    cruzamentos = _POPULACAO / 2

    for i in range( int(cruzamentos) ):

        filhoA = []

        filhoB = []

        sorteioPai = int( math.floor( random.random() * soma ) )

        sorteioMae = int( math.floor( random.random() * soma ) )

        

        # pai

        indicePai = 0;

        while ( sorteioPai > 0 ):

            sorteioPai = sorteioPai - adaptabilidade[ indicePai ]

            indicePai = indicePai + 1

        if indicePai < 0:

            indicePai = 0

        if indicePai > (_CROMOSSOMO-1):

            indicePai = (_CROMOSSOMO-1)

            

        # mae

        indiceMae = 0;

        while ( sorteioMae > 0 ):

            sorteioMae = sorteioMae - adaptabilidade[ indiceMae ]

            indiceMae = indiceMae + 1

        if indiceMae < 0:

            indiceMae = 0

        if indiceMae > (_CROMOSSOMO-1):

            indiceMae = (_CROMOSSOMO-1)



        # Crossing over em si

        pai = populacao[ indicePai ]

        mae = populacao[ indiceMae ]



        pontoDeCrossing = 3+int( math.floor( random.random() * (_CROMOSSOMO-6 ) ) )

        for i in range( pontoDeCrossing ):

            filhoA.append( pai[i] )

            filhoB.append( mae[i] )    

        for i in range( pontoDeCrossing, _CROMOSSOMO ):

            filhoA.append( mae[i] )

            filhoB.append( pai[i] )    



        novaGeracao.append( filhoA[:] )

        novaGeracao.append( filhoB[:] )



    populacao = novaGeracao[:] 



def geraMutacoes( populacao ):

    quantidadeMutacoes = int( math.ceil( random.random()*_MAXIMO_MUTACOES ) ) 

    for i in range( quantidadeMutacoes ):

        vitima = int( math.floor( random.random()*_POPULACAO ) )

        locusGene = int( math.floor( random.random()*_CROMOSSOMO ) )

        geneMutante = _ALFABETO[int( math.floor( random.random()*len(_ALFABETO) ) )]

        populacao[vitima][locusGene] = geneMutante



# Funcao principal

def main():



    condicaoParada = _CONDICAO_PARADA



    # Inicializo a minha população de cromossomos

    populacao = geraPopulacaoInicial()

    

    while (condicaoParada>0):

        adaptabilidade = calculaAdaptabilidade(populacao)

        mostraMelhorDaGeracao( condicaoParada, populacao, adaptabilidade )

        substituiPelaMelhor( populacao, adaptabilidade )

        # geraCrossingOver( populacao, adaptabilidade )

        geraMutacoes( populacao )

        condicaoParada = condicaoParada-1





if __name__ == '__main__':

    main()