53
14/06/14 Inteligência Artificial Algoritmos Genéticos

Inteligência Artificial - Aula15 - Algoritmos Genéticos

Embed Size (px)

DESCRIPTION

Algoritmos genéticos: solução de problemas de otimização com inspiração na seleção natural.

Citation preview

Page 1: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Inteligência Artificial

Algoritmos Genéticos

Page 2: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Introdução

● Na sub-área da inteligência computacional, diversos algoritmos possuem inspiração na natureza

● Entre eles temos os Algoritmos Genéticos, que são inspirados no processo de seleção natural identificado por Darwin

Page 3: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Introdução

● A ideia é “evoluir” soluções para problemas de otimização imitando o que ocorre na natureza

● Pode ser visto como um melhoramento sobre o Simulated Annealing, onde teremos várias soluções candidatas em vez de apenas uma

Page 4: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Aplicações

● Otimização de funções● Alocação de espaço e tempo● Roteamento● Controle robótico● Treinamento de redes neurais● Problemas de otimização combinatória em geral● Qualquer problema onde Simulated Annealing e Hill Climbing

são aplicáveis● Qualquer problema que não saibamos resolver de outra forma,

mas que saibamos como avaliar a qualidade de uma solução candidata

Page 5: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Seleção Natural

● Primeiramente, vamos relembrar como se dá o processo de seleção natural propriamente dito● Cada ambiente possui seus desafios, obstáculos,

predadores, presas, alimento, clima, etc...● Indivíduos não aptos ao ambiente em que se

encontram morrem e, em média, deixam menos descendentes

● Indivíduos aptos ao ambiente vivem mais e, em média, deixam mais descendentes

Page 6: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Seleção Natural

● A reprodução dos indivíduos pode ser sexuada ou assexuada● No caso da reprodução assexuada, os descendentes herdam

características tanto do pai quanto da mãe● Isto permite que boas “soluções” sejam mescladas e “testadas” no ambiente

● Em ambos os casos, os descendentes sofrem pequenas mutações (por falhas naturais no processo de replicação de DNA)● Humanos possuem, em média, 60 mutações!● Isto permite que novas características sejam introduzidas na população● O que, por sua vez, pode criar novas maneiras de resolver antigos problemas em

determinados ambientes● A maioria das mutações é inofensiva, seguidas pelas prejudiciais● Mas se apenas 1 indivíduo em 1 bilhão for “premiado” com uma boa mutação, isso basta

para que ele comece a superar os outros e propagar seus genes, tornando-se algo comum ao longo de muitas gerações

Page 7: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Seleção Natural

● Este processo se repete ao longo de muitas gerações e pode ser observado em espécies com tempo de vida mais curto

● Na medida em que as gerações avançam, surgem indivíduos cada vez mais aptos aos seus ambientes

Page 8: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Algoritmos Genéticos

● Agora imagine que um ambiente é um problema

● Um indivíduo é uma solução● E os genes são os valores da

solução

Page 9: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Algoritmos Genéticos

● Com isto, podemos aplicar o processo de seleção natural a problemas quaisquer e obter soluções cada vez melhores ao longo do tempo!

Page 10: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Algoritmos Genéticos

● Para resolver problemas utilizando Algoritmos Genéticos, precisamos dos seguintes componentes:● Representação: como transformar uma solução em uma

sequência de genes (um cromossomo)?● Crossover (Cruzamento): como podemos mesclar 2 soluções?● Mutação: como podemos causar pequenas variações

aleatórias em nossas soluções?● Fitness: como calcular a aptidão de um indivíduo? Ou em

outras palavras, o custo/erro/utilidade de uma solução?● Seleção: como faremos a seleção dos mais aptos?

Page 11: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Representação

● Algoritmos Genéticos são versáteis em termos de representação, bastando que as operações de crossover e mutação sejam adequadamente escolhidas

● Mas uma representação muito popular é a de vetores

● Mais especificamente, podemos usar vetores de bits

Page 12: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Representação - Exemplo

● Problema da mochila: um ladrão invade uma casa com sua sacola e precisa roubar os objetos que somem o maior valor possível, desde que caibam na sacola

● Vamos supor os seguintes objetos:1.Notebook ($3000, tamanho 4)

2.Tablet ($1500, tamanho 3)

3.Celular ($1000, tamanho 2)

4.Colar ($700, tamanho 2)

5.Anel ($400, tamanho 1)

● E supunha que a sacola tem capacidade 5

Page 13: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Representação - Exemplo

● Podemos representar uma solução como uma sequência de bits que diz se o ladrão deve ou não levar um objeto

01010 = Tablet + Colar

00111 = Celular + Colar + Anel

Page 14: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Representação - Exemplo

● Um outro problema é o do caixeiro viajante: encontre o caminho mais curto que passe por todas as cidades (nós em um grafo) e retorne ao início sem repetir cidades

● A representação binária já não é tão adequada, sendo melhor usar uma representação de permutação

CBADE (cidade C, depois B, A, D, E e retorna para C)DABEC

Page 15: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Representação - Exemplo

● Já para um problema contínuo, como achar o máximo de uma equação, necessitamos de uma representação contínua

● 2x - 3y + 5z - 4w + 2xy – 3xz + 1● Quais os valores de x,y,z e w que

maximizam a função?

0.1 1.7 9.1 -3 (o valor de cada variável)-1 0.2 5.2 1.4

Page 16: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Representação

● Portanto, não existe uma forma única de representar um problema para aplicar um algoritmo genético

● Cada problema tem uma representação mais adequada!

Page 17: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Fitness

● Agora que já definimos como as soluções para o nosso problema serão representadas, precisamos definir como elas serão avaliadas

Page 18: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Fitness

● No caso do problema da mochila, queremos o maior valor possível sem ultrapassar o limite da mochila

● Podemos representar a “aptidão” de uma solução como a soma dos valores dos objetos e com uma penalidade para soluções que passam do limite de volume

Page 19: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Fitness

01010 =Tablet + Colar1500 + 700 = 2200Tamanho 3 + 2 = 5, ok

00111 = Celular + Colar + Anel1000 + 700 + 400 = 2100Tamanho 2 + 2 + 1 = 5, ok

10101 = Notebook + Celular + Anel3000 + 1000 + 400 = 4400Tamanho 4 + 2 + 1 = 7, estourou, penalidade de 10000Fitness final = -5600

Page 20: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Fitness

● No caso do caixeiro viajante, bastaria somar o custo de cada trecho do caminho na solução

● No caso da maximização de função, poderíamos simplesmente computar o resultado da função com os valores da solução

Page 21: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Seleção

● Agora que já medimos a qualidade de cada solução, podemos proceder para a seleção

● Um método simples seria selecionar as N (a definir) melhores soluções

● Mas isto tem a desvantagem de tornar o algoritmo mais propenso a cair em máximos locais

● Uma solução mais usada é a da roleta

Page 22: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Seleção

● Com a roleta, cada solução tem uma probabilidade de ser selecionada proporcionalmente ao seu fitness

● Com isso, mesmo as piores soluções podem se reproduzir, apesar de mais raro

Page 23: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Seleção - Exemplo

● No problema da mochila, usamos o exemplo com as 3 soluções com os seguintes fitness: 2200, 2100, -5600

● Primeiro devemos subtrair o menor valor (-5600) de todos os valores para eliminar os negativos● 2200 - (-5600) = 7800

2100 - (-5600) = 7700-5600 – (5600) = 0

● Agora calculamos o fitness total:7800 + 7700 + 0 = 15500

● E as proporções:7800 / 15500 = 0,5032258067700 / 15500 = 0,4967741940 / 15500 = 0

● Estas são as probabilidades de selecionar cara solução!

Page 24: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Mutação

● Na mutação, devemos alterar algum elemento do cromossomo aleatoriamente, com uma probabilidade pequena (a definir)

Page 25: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Mutação

Page 26: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Mutação - Exemplo

01010 → 01011 (tablet + colar → tablet + colar + anel)

BCADE → CBADE

0.1 8 3.4 2.1 → 0.1 8.1 3.4 2.1● As mutações ajudam a evitar

máximos locais e a encontrar soluções inéditas

Page 27: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Crossover

● No crossover, mesclaremos pares de soluções que foram selecionadas previamente

● Parte da premissa de que se as 2 são boas, suas combinações provavelmente também serão

Page 28: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Crossover

Page 29: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Crossover

● O tipo de crossover na animação anterior é o crossover por ponto único

● Ele consiste em escolher um ponto aleatoriamente nos cromossomos e trocar o conteúdo dos vetores a partir daquele ponto

● Também existe o crossover com 2 pontos, onde o vetor é dividido em 3 partes que são trocadas entre os 2 indivíduos

● E há também o crossover uniforme, onde cada elemento pode ser puxado de um pai diferente

Page 30: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Crossover - Exemplo

01010 = tablet + colar

00111 = celular + colar + anel

Filhos:

01011 = tablet + colar + anel

00110 = celular + colar● Note que nenhuma solução envolve o Notebook e portanto seria impossível

que ele aparecesse na população apenas com crossover● Por isso que é necessário aplicar mutações depois dos cruzamentos!● Após aplicar mutações, estas 2 soluções seguirão para a próxima geração

(próxima iteração do algoritmo)● Uma variação disto, chamada de seleção elitista, poderia manter as boas

soluções da geração atual para a próxima geração também● Evita que percamos as melhores soluções até o momento

Page 31: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Algoritmos Genéticos

Page 32: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Algoritmos Genéticos – Exemplo Completo

● Vamos tentar resolver o problema da mochila por completo, considerando a seguinte população inicial gerada aleatoriamente:

0100010000001000011001100

Page 33: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Algoritmos Genéticos – Exemplo Completo

● Primeiro passo: avaliação

01000 → 1500 (tamanho 3)10000 → 3000 (tamanho 4)00100 → 1000 (tamanho 2)00110 → 1700 (tamanho 4)01100 → 2500 (tamanho 5)

Page 34: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Algoritmos Genéticos – Exemplo Completo

● Segundo passo: seleção

Soma dos fitness = 9700

01000 → 1500 / 9700 = 0,15463917510000 → 3000 / 9700 = 0,30927835100100 → 1000 / 9700 = 0,10309278400110 → 1700 / 9700 = 0,17525773201100 → 2500 / 9700 = 0,257731959● 2 indivíduos foram selecionados aleatoriamente de acordo com as

probabilidades● Usaremos elitismo: os 2 pais serão mantidos na próxima geraãço

juntamente com seus 2 filhos

Page 35: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Algoritmos Genéticos – Exemplo Completo

● Terceiro passo: cruzamento

1000001100● Este ponto de crossover foi escolhido

aleatoriamente

Filhos:1010001000

Page 36: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Algoritmos Genéticos – Exemplo Completo

● Quarto passo: mutação

10100 → 10100 (não mudou nada)01000 → 01001 (mudou o último bit)

Page 37: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Algoritmos Genéticos – Exemplo Completo

● Repetindo: avaliação da nova população

10000 → 3000 (tamanho 4)01100 → 2500 (tamanho 5)10100 → 4000 (tamanho 6) → -600001000 → 1500 (tamanho 3)

Page 38: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Algoritmos Genéticos – Exemplo Completo

● Repetindo: seleção● Soma dos fitness: 25000 (somando 6000 em cada um

para eliminar o negativo)

10000 → 9000 / 25000 = 0,3601100 → 8500 / 25000 = 0,34 10100 → 0 / 25000 = 001000 → 7500 / 25000 = 0,3● 2 pais selecionados aleatoriamente de acordo com as

probabilidades

Page 39: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Algoritmos Genéticos – Exemplo Completo

● Repetindo: cruzamento● Ponto de crossover escolhido aleatoriamente

1000001000

● Filhos:

1000001000● Sim, são iguais! Sem problema.

Page 40: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Algoritmos Genéticos – Exemplo Completo

● Repetindo: mutação

10000 → 1000101000 → 01010

Page 41: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Algoritmos Genéticos – Exemplo Completo

● Repetindo: avaliação da nova população

10000 → 3000 (tamanho 4)01000 → 1500 (tamanho 3)10001 → 3700 (tamanho 5)01010 → 2200 (tamanho 5)

Page 42: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Algoritmos Genéticos – Exemplo Completo

● Repetindo: seleção● Soma dos fitness: 10400

10000 → 3000 / 10400 = 0,288461501000 → 1500 / 10400 = 0,144230710001 → 3700 / 10400 = 0,355769201010 → 2200 / 10400 = 0,2115384● 2 indivíduos selecionados aleatoriamente de

acordo com as probabilidades

Page 43: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Algoritmos Genéticos – Exemplo Completo

● Repetindo: cruzamento● Ponto de crossover escolhido aleatoriamente

1000010001

● Filhos:

1000110000● Iguais aos pais, sem problema.

Page 44: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Algoritmos Genéticos – Exemplo Completo

● Repetindo: mutação

1001110010

Page 45: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Algoritmos Genéticos – Exemplo Completo

● Repetindo: avaliação da nova geração

10001 → 3400 (tamanho 5)10000 → 3000 (tamanho 4)10011 → 4100 (tamanho 7) → -590010010 → 3700 (tamanho 6) → -6300

Page 46: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Algoritmos Genéticos – Exemplo Completo

● Melhor fitness (3400) não mudou em relação à geração anterior, podemos parar (é apenas um critério de parada possível entre vários)

● Melhor solução:10001 → Notebook + Anel

Page 47: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Programação Genética

● Também é possível evoluir programas completos com algoritmos genéticos, é a chamada Programação Genética

● Uma forma comum de representar um programa é através de árvores sintáticas

Page 48: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Programação Genética

Page 49: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Algoritmos Genéticos Interativos

● Uma variação dos algoritmos genéticos permite que humanos selecionem as suas soluções preferidas em uma população, dispensando o cálculo do fitness

● Pode ser usado em tarefas mais subjetivas, como geração automática de arte (visual, musical, literária, etc...)

● A vantagem é que, implicitamente, acabamos usando funções de fitness muito mais complexas

● A desvantagem é que não podemos rodar o algoritmo por várias gerações automaticamente, visto que um humano deve analisar cada solução e fazer a seleção manualmente, tornando o processo muito mais lento

Page 50: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Algoritmos Genéticos Interativos

Page 51: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Algoritmos Genéticos Interativos

Page 52: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Algoritmos Genéticos Interativos

Page 53: Inteligência Artificial - Aula15 - Algoritmos Genéticos

14/06/14

Algoritmos Genéticos Interativos