P�ginas

AD 468x60

sexta-feira, 1 de julho de 2011

AI Tutorials - Otimização com algorítmos genéticos

Olá queridos leitores, decidi reativar o blog mais uma vez para postar uma série de mini-tutoriais básicos sobre inteligência artificial.

Um dos tópicos mais úteis ao meu ver em IA é otimização que basicamente consiste em achar a melhor solução para um dado problema. Pode parecer simples e/ou improvável de se generalizar, mas existem uma série de técnicas e algoritmos que podem ser aplicados, em sua estrutura básica, na grande maioria dos problemas onde toda possível solução possa ter um determinado custo, que é o objeto de minimização.

É necessário portanto que se tenha uma função de custo, que receba uma dada possível solução e determine o quão "errada" ela está, o quão inconveniente ou inaplicável ela seria caso fosse aplicada como solução do problema.

Existem vários algoritmos de otimização, tais algoritmos são independentes da função de custo, tendo em vista que esta retorne um valor numérico propício a comparação. Nesse post iremos entender um pouco do algoritmo genético, esse algoritmo trata as soluções como código genético, geralmente expressadas como uma array numérica, mas antes vou explicar um método bem mais básico e que a meu ver não requer um post separado, mas que serve para mostrar a necessidade da inteligencia nesses algoritmos.

Primeiramente devemos ter em mente qual exatamente é o problema, quais são as variáveis e valores a serem atribuídos. O problema que suponho para este exemplo é o seguinte: Tens que comprar uma lista de produtos em lojas diferentes, tendo em mente o valor do produto, a qualidade, valor do frete e tempo de espera pelo produto como variáveis, vamos escrever uma função de custo. A primeira dúvida que temos geralmente é como armazenar e ler os dados, pois bem, para esse problema acho que seria interessante representarmos da seguinte maneira: um arquivo contendo as lojas e seus produtos e preços e qualidade (de 1 a 5):

id,loja,frete
id,produto,preço,qualidade
id,produto,preço,qualidade

id,loja,frete

id,produto,preço,qualidade
...

Não vou entrar em detalhes sobre como ler uma database tão simples, o próximo passo é decidir como representar a solução numericamente, uma maneira simples seria: [iditem,idloja,iditem,idloja,iditem...].
Agora iremos criar uma função, que recebe uma representação numérica da solução e retorna o custo.

(A propósito, eu uso Python) :D

def cost_function(solution, db):
    assert len(solution)%2==0
    cost = 0
    for i in range(solution)[::2]:
        iditem = solution[i]
        idloja = solution[i+1]
        cost += db[idloja]['frete']
        cost += db[idloja][iditem]['preço']
        cost *= (1+(5.01-db[idloja][iditem]['qualidade'])/10)
    return cost


Nessa função nós percorremos a solução de dois em dois numeros ([::2]), lendo o id do item, da loja, e buscando na db seus valores, o custo é o preço+frente e um adicional percentual inversamente proporcional a qualidade.


Agora a parte divertida, o algoritmo de otimização, hoje veremos o genético, mas como eu disse irei levantar uma questão mais simples antes. Pense um pouco, qual a maneira mais simples de se chegar a solução ideal? Testando todas as possíveis permutações da representação numérica da solução e retornando a com menor custo certo? Esse é um dos métodos de otimização. Vamos implementar ele:


from random import randint
def random_optimization(domain, costf, iterations):
    best = [999999,[]]
    for i in range(iterations):
        trial = [randint[*domain[i]] for i in len(domain)]
        cost = costf(trial)
        if cost < best[0]:
            best = [cost, trial]
    return best


Como era de se esperar, qualquer algoritmo de otimização necessita saber qual domínio as soluções numéricas deve estar, ou seja, qual o range que cada número pode estar.
A otimização randômica tem um desempenho viável em problemas simples, de soluções curtas e domínios curtos, mas para a maioria dos problemas do mundo real, não é recomendado.
Antes de implementar o algoritmo genético irei explicar como o mesmo funciona. Basicamente, a representação numérica da solução é tratada como código genético(ex. DNA), esse código genético sofre mutação, crossover, e seleção natural um número n de vezes(gerações) até que se chegue a uma solução ideal. Vamos a implementação:



def genetic_optimization(popsize, generations, costf, domain
                 maxpop=4, mutratio=0.05, eliteratio=0.2):
def crossover(code1, code2):
newcode = []
for i in range(slots):
if random.random() > 0.5:
newcode.append(code1[i])
else:
newcode.append(code2[i])
return newcode
def mutate(code):
i = random.randint(0, len(domain))
v = random.randint(*domain[i])
code[i] = v
return code

population = [[random.randint(*domain[i])\
  for i in len(domain)]\
   for j in range(popsize)]
chosens = []
for ng in range(generations):
rankedpop = sorted([(costf(c),c) for c in population])
chosens = [c for (cost, c)\
  in rankedpop[:int(len(population)*eliteratio)]]
maxpopsz = int(popsize*(maxpop+random.random()))
population = [c for (cost, c) in rankedpop][:maxpopsz]
sons = []
for i in range(len(chosens)):
partner = i
while partner==i:
partner = random.randint(0,len(chosens)-1)
son = crossover(chosens[i], chosens[partner])
if random.random() < mutratio:
son = mutate(son)
sons.append(son)
population.extend(sons)
return (costf(chosens[0]), chosens[0])


Basicamente, nós criamos uma população inicial randomica especificada no argumento 'popsize', no laço for, nós iteramos a cada geração, analisando o custo de cada código genético, sorteando-os e selecionando uma 'elite', especificada pelo argumento 'eliteratio', essa elite vai ser 'cruzada' com a função 'crossover', gerando filhos que serão adicionados a população, havendo uma chance de 'mutratio' de cada filho sofrer uma mutação aleatória. então, em uma nova geração a população sofre seleção natural novamente, e o processo continua, e finda por retornar o código genético mais bem sucedido.
Todas os argumentos do algoritmo genético são fortemente dependentes do tipo de problema, devendo ser modificados pra atingir um desempenho melhor em aplicações específicas.

Espero que tenham gostado, obrigado, e aguardem mais posts.