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.

Recordando uma aula

Na aula extraordinária (?) da semana passada sugeri um pequeno exemplo para ilustrar como é simples a implementação de um algoritmo de optimização. O exemplo envolvia o reconhecimento de padrões simples, no caso caracteres; o algoritmo era um trepa colinas básico -- estocástico, uma solução de cada vez, busca local. O desenvolvimento foi feito em tempo real o que permitiu irmos discutindo alguns aspectos da implementação, incluindo os erros. A abordagem seguida para o desenvolvimento foi do topo para a base, usando camadas de abstracção.

Começámos então pelo programa principal.

def meu_padrao(problema,max_iter):
    candidato = prima_sol(problema)
    custo_candidato = qualidade(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   
    return candidato,custo_candidato

Com esta aproximação o que abstraímos foram:
o problema
a geração aleatória de soluções
a geração dos vizinhos
a determinação da qualidade das soluções

Começando pelo problema. Resolvemos considerar uma discretização dos caracteres, ou seja, usar matriz de mXn células, cada uma podendo assumir o valor preto ou o valor branco. A representação correspondente em Python, mais simples, é uma lista de listas. Assim, por exemplo, o número um será representado pela lista.

[[0,0,1,0,0],[0,1,1,0,0],[0,0,1,0,0],[0,0,1,0,0]]

Definido o problema e a representação, podemos passar às restantes questões.

Geração aleatória de soluções

A estratégia é a de construir a matriz que represetna o caractere, linha a linha.

 def prima_sol_b(problema):
    mat = []
    for lin in range(problema[0]):
        linha = []
        for col in range(problema[1]):
            linha.append(random.randint(0,1))
        mat.append(linha)
    return mat

Geração de um vizinho

Escolhemos um índice de forma aleatória e mudamos o seu valor. Recorre-se a uma cópia da solução

def proxima_solucao(problema,solucao):
    linha = random.randint(0,problema[0]-1)
    coluna = random.randint(0,problema[1]-1)
    pixel = solucao[linha][coluna]
    novo_pixel = (pixel + 1) % 2
    nova_solucao = copy.deepcopy(solucao)
    nova_solucao[linha][coluna] = novo_pixel
    return nova_solucao

Note-se o recurso ao módulo copy e à operação deepcopy. Isto é necessário para evitar a modificação, por efeito lateral, da solução dada como referência, visto estarmos a usar listas de listas.

Qualidade

A qualidade de um indivíduo é dada pelo número de posições em que é diferente do caractere de referência.

def qualidade(solucao):
    padrao = [[0,0,1,0,0],[0,1,1,0,0],[0,0,1,0,0],[0,0,1,0,0]]
    return distancia(solucao,padrao)

def distancia(candi_1, candi_2):
    return sum([1 for linha in range(len(candi_1)) for coluna in range(len(candi_1[0]))\
                if candi_1[linha][coluna] != candi_2[linha][coluna]])

Acrescentamos a tudo isto a comparação de qualidade das soluções. Como calculamos a qualidade usando a distância é óbvio que quanto menor esse valor, melhor:

def melhor(quali_1, quali_2):
    return quali_1 < quali_2

E pronto. Já está. É só juntar tudo. Ou talvez não! Será que não estamos ainda satisfeitos? É um facto que as funções para geral soluções aleatoriamente e calcular a distância seguem um padrão que nos leva a pensar em listas por compreensão. Feita a substituição, aqui fica o código final.

import random
import copy

def meu_padrao(problema,max_iter):
    candidato = prima_sol(problema)
    custo_candidato = qualidade(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   
    return candidato,custo_candidato


def prima_sol(problema):
    sol = [[random.randint(0,1) for col in range(problema[1])] for linha in range(problema[0])]
    return sol 

 
def proxima_solucao(problema,solucao):
    linha = random.randint(0,problema[0]-1)
    coluna = random.randint(0,problema[1]-1)
    pixel = solucao[linha][coluna]
    novo_pixel = (pixel + 1) % 2
    nova_solucao = copy.deepcopy(solucao)
    nova_solucao[linha][coluna] = novo_pixel
    return nova_solucao


def qualidade(solucao):
    padrao = [[0,0,1,0,0],[0,1,1,0,0],[0,0,1,0,0],[0,0,1,0,0]]
    return distancia(solucao,padrao)


def melhor(quali_1, quali_2):
    return quali_1 < quali_2

def distancia(candi_1, candi_2):
    return sum([1 for linha in range(len(candi_1)) for coluna in range(len(candi_1[0]))\
                if candi_1[linha][coluna] != candi_2[linha][coluna]])

                
def mostra(padrao):
    for linha in padrao:
        print linha, '\n'

if __name__ =='__main__':   
    padrao_ref = [[0,0,1,0,0],[0,1,1,0,0],[0,0,1,0,0],[0,0,1,0,0]]
    pad,dist = meu_padrao((4,5),50)
    mostra(padrao_ref)
    print 20 * '+'
    mostra(pad)
    print dist
    print qualidade(pad)

Retomar o caminho

Este blogue tem tido pouca actividade. Agora que começa uma nova edição da cadeira, vamos tentar manter uma intervenção mais regular. A ideia é a mesma: exemplos, desafios, ideias e outras coisas mais, tudo relacionado com a computação de inspiração biológica. Contribuições são bem vindas.