Ver para crer

Perceber como um algoritmo está a funcionar é muito importante. No caso dos algoritmos de que vamos tratar ainda mais. Visualizar o modo como a qualidade das soluções evolui ao longo do tempo ajuda imenso a perceber o que se está a passar. Para nos ajudar nisso vamos recorrer ao módulo matplotlib.

Vejamos como podemos fazer a visualização nos casos simples que nos interessam.

import matplotlib.pyplot as plt

def mostra_dados(dados):
    plt.title('')
    plt.xlabel('Generation')
    plt.ylabel('Cost')
    x = range(len(dados))
    y = dados
    plt.plot(x,y,'r-o')
    plt.show()

Se consultar o manual do matplotlib verá que pode fazer muito mais.

Agora só precisamos de alterar o programa principal, coligindo os valores ao longo das iterações para, no final, proceder à sua visualização.

def meu_padrao(problema,max_iter):
    candidato = prima_sol(problema)
    custo_candidato = qualidade(candidato)
    dados = [custo_candidato]
    for  i in range(max_iter):
        novo_candidato = proxima_solucao(problema, candidato)
        custo_novo_candidato = qualidade(novo_candidato)
        if melhor(custo_novo_candidato,custo_candidato):
            candidato = novo_candidato
            custo_candidato = custo_novo_candidato  
        dados.append(custo_candidato)
    mostra_dados(dados)
    return candidato,custo_candidato

Correndo o programa eis um resultado possível.




Como veremos mais adiante, porque se trata de algoritmos estocásticos, o normal é correr o algoritmo várias vezes, tipicamente um número maior ou igual a 30, e apresentar os valores médios. Eis um resultado possível.



É uma curva típica: uma melhoria rápida na fase inicial e depois maior dificuldade em nos aproximarmos do óptimo. A alteração ao código envolve o programa principal que é alterado por forma a devolver o resultado de cada execução e o modo como se faz a preparação dos dados. Vejamos como.

if __name__ =='__main__':
    resultados = []
    for i in range(30):
        padrao, dist, dados = meu_padrao((4,5),100)
        resultados.append(dados)
    
    valores = zip(*resultados)
    final = [ sum(gera)/float(len(gera)) for gera in valores]
    mostra_dados(final)

Notar o modo como se usa a função zip.