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)