12
Algoritmo Algoritmo Genético Genético nteligência nteligência Artificial Artificial Prof. Marcelo B. de Almeida Prof. Marcelo B. de Almeida

Algoritmo Genético Inteligência Artificial Prof. Marcelo B. de Almeida

Embed Size (px)

Citation preview

Page 1: Algoritmo Genético Inteligência Artificial Prof. Marcelo B. de Almeida

Algoritmo Algoritmo GenéticoGenético

InteligênciaInteligência Artificial Artificial

Prof. Marcelo B. de AlmeidaProf. Marcelo B. de Almeida

Page 2: Algoritmo Genético Inteligência Artificial Prof. Marcelo B. de Almeida

IntroduçãoIntrodução aos Algoritmos Genéticos aos Algoritmos Genéticos

Algoritmos Genéticos, AGs, são métodos de otimização e busca inspirados nosAlgoritmos Genéticos, AGs, são métodos de otimização e busca inspirados nosmecanismos de evolução de populações de seres vivos. mecanismos de evolução de populações de seres vivos.

Estes algoritmos seguem o principio da seleção natural e sobrevivência do maisEstes algoritmos seguem o principio da seleção natural e sobrevivência do maisapto, declarado pelo naturalista e fisiologista inglês Charles Darwin. apto, declarado pelo naturalista e fisiologista inglês Charles Darwin.

““Quanto melhor um indivíduo se adaptarQuanto melhor um indivíduo se adaptarao seu meio ambiente, maior será sua ao seu meio ambiente, maior será sua chance de sobreviver e gerar descendentes”chance de sobreviver e gerar descendentes”

Charles DarwinCharles Darwin

Otimização é a busca da melhor solução para um dado problema. Consiste em tentarOtimização é a busca da melhor solução para um dado problema. Consiste em tentarvárias soluções e utilizar a informação obtida neste processo de forma a encontrarvárias soluções e utilizar a informação obtida neste processo de forma a encontrarsoluções cada vez melhores.soluções cada vez melhores.

Page 3: Algoritmo Genético Inteligência Artificial Prof. Marcelo B. de Almeida

Introdução aos Algoritmos GenéticosIntrodução aos Algoritmos Genéticos

Exemplo:Exemplo:

Achar o ponto máximo da função: Achar o ponto máximo da função: f(x)= x.sen(10. f(x)= x.sen(10. .x)+1 no intervalo -1 ≤ x ≤2 .x)+1 no intervalo -1 ≤ x ≤2

Page 4: Algoritmo Genético Inteligência Artificial Prof. Marcelo B. de Almeida

1 – Passo: Gerar uma população inicial de “cromossomos” que é formada por um 1 – Passo: Gerar uma população inicial de “cromossomos” que é formada por um conjunto aleatório de cromossomos que representam possíveis soluções do problemaconjunto aleatório de cromossomos que representam possíveis soluções do problemaa ser resolvido. Ex.:a ser resolvido. Ex.:

SS11==1000101110110101000111 22 bit’s 1000101110110101000111 22 bit’s

ConverterConverter SS11 em decimal -> b em decimal -> b1010 =2288967 =2288967

Colocar bColocar b1010 no intervalo do problema [-1,0; 2,0] utilizando a fórmula no intervalo do problema [-1,0; 2,0] utilizando a fórmula

b10 x = min + (max – min) ------- 2L – 1

2288967 x = -1 + (2 +1) ----------- = 0,637197 (222 – 1)

Um algoritmo Genético começa com uma população inicial de Um algoritmo Genético começa com uma população inicial de NN cromossomos. Neste exemplo N= 30. (os cromossomos foram cromossomos. Neste exemplo N= 30. (os cromossomos foram gerados aleatoriamente).gerados aleatoriamente).

Page 5: Algoritmo Genético Inteligência Artificial Prof. Marcelo B. de Almeida

A cada Cromossomo SA cada Cromossomo S11 é atribuída uma aptidão é atribuída uma aptidão ffii. . Aptidão é a nota Aptidão é a nota que mede o quanto a solução foi boa, essa nota é baseada na função que mede o quanto a solução foi boa, essa nota é baseada na função objetivo ( objetivo ( f(x)f(x) ). ).

Um dos métodos para dar nota de aptidão ao cromossomo é atribuir uma Um dos métodos para dar nota de aptidão ao cromossomo é atribuir uma nota arbitrária ao primeiro cromossomo por exemplo 2,0 e ao último nota arbitrária ao primeiro cromossomo por exemplo 2,0 e ao último cromossomo a nota 0,0. As demais notas foram obtidas interpolando estes cromossomo a nota 0,0. As demais notas foram obtidas interpolando estes dois extremos utilizando a seguinte função: onde N é o dois extremos utilizando a seguinte função: onde N é o tamanho da população. Veja a tabela.tamanho da população. Veja a tabela.

)1/()(2 NiNfi

AptidãoAptidão

Ex.:A aptidão do 5º cromossomo é :Ex.:A aptidão do 5º cromossomo é :

72414,1)130/()530(25 f

Feito isso com todos os cromossomos da população inicial, iremos Feito isso com todos os cromossomos da população inicial, iremos ordená-los em ordem decrescente do valor da função objetivo ( ordená-los em ordem decrescente do valor da função objetivo ( f(x) f(x) ).).

Page 6: Algoritmo Genético Inteligência Artificial Prof. Marcelo B. de Almeida
Page 7: Algoritmo Genético Inteligência Artificial Prof. Marcelo B. de Almeida

2 – Passo: Selecionar os melhores cromossomos da população inicial 2 – Passo: Selecionar os melhores cromossomos da população inicial para gerar “cromossomos filhos” (que são variantes dos pais) através para gerar “cromossomos filhos” (que são variantes dos pais) através dos operadores de dos operadores de crossover e mutaçãocrossover e mutação. .

Colocando no gráfico os pontos representados pelos cromossomos da Colocando no gráfico os pontos representados pelos cromossomos da população inicial teremos:população inicial teremos:

Page 8: Algoritmo Genético Inteligência Artificial Prof. Marcelo B. de Almeida

SeleçãoSeleção

Geralmente, os pais são selecionados com probabilidade “proporcional Geralmente, os pais são selecionados com probabilidade “proporcional à sua aptidão“. Essa probabilidade é dada por: à sua aptidão“. Essa probabilidade é dada por:

N

i i

ii

f

fp

1

Ex.: a probabilidade do 1º cromossomo da tabela ser escolhido é de : Ex.: a probabilidade do 1º cromossomo da tabela ser escolhido é de :

%100100*10,2

0,21 p

Ex.: a probabilidade do 7º cromossomo da tabela ser escolhido é de : Ex.: a probabilidade do 7º cromossomo da tabela ser escolhido é de :

%6,12100*126,055172,12

58621,17 p

Page 9: Algoritmo Genético Inteligência Artificial Prof. Marcelo B. de Almeida

Existem muitas regras de seleção. Entre elas existe o método Existem muitas regras de seleção. Entre elas existe o método culling culling no no qual todos os indivíduos abaixo de um determinado limiar são qual todos os indivíduos abaixo de um determinado limiar são descartados, este método converge com maior rapidez que a versão descartados, este método converge com maior rapidez que a versão aleatória.aleatória.

Uma “população intermediaria” é utilizada para alocar os cromossomos Uma “população intermediaria” é utilizada para alocar os cromossomos pais selecionados pela probabilidade de seleção Ppais selecionados pela probabilidade de seleção P ii de um cromossomo. de um cromossomo.

Para fazer uma população intermediária é escolhido um cromossomo Para fazer uma população intermediária é escolhido um cromossomo aleatoriamente,aleatoriamente,verifica-se sua probabilidade, se for maior que o limiar (estabelecido) verifica-se sua probabilidade, se for maior que o limiar (estabelecido) alocamos esse cromossomo na tabela intermediaria. Repetimos esse alocamos esse cromossomo na tabela intermediaria. Repetimos esse processo até completarmos a tabela intermediaria (30 valores, como na processo até completarmos a tabela intermediaria (30 valores, como na população inicial).população inicial).

Page 10: Algoritmo Genético Inteligência Artificial Prof. Marcelo B. de Almeida

População IntermediariaPopulação Intermediaria

Page 11: Algoritmo Genético Inteligência Artificial Prof. Marcelo B. de Almeida

Crossover e MutaçãoCrossover e MutaçãoO operador crossover é aplicado a um par de cromossomos retirados da O operador crossover é aplicado a um par de cromossomos retirados da populaçãopopulaçãointermediária, gerando dois cromossomos filhos. Cada um dos intermediária, gerando dois cromossomos filhos. Cada um dos cromossomos pais tem sua cadeia de bit’s cortada em um posição cromossomos pais tem sua cadeia de bit’s cortada em um posição aleatória, produzindo duas cabeças e duas caudas. As caudas são aleatória, produzindo duas cabeças e duas caudas. As caudas são trocadas, gerando dois novos cromossomos.trocadas, gerando dois novos cromossomos.

SS11 = 0010101011100000111111 = 0010101011100000111111SS22 = 0011111010010010101100 = 0011111010010010101100

filhofilho11 = 0010101011010010101100 = 0010101011010010101100filhofilho22 = 0011111010100000111111 = 0011111010100000111111

Ponto de cortePonto de corte

Após a operação de crossover, a Mutação é aplicada. A mutação inverte os Após a operação de crossover, a Mutação é aplicada. A mutação inverte os valores de bit’s, ou seja, muda o valor de um dado bit de 1 para 0 ou de 0 valores de bit’s, ou seja, muda o valor de um dado bit de 1 para 0 ou de 0 para 1. para 1.

Antes filhoAntes filho11 = 0010101011010010101100 = 0010101011010010101100 filhofilho22 = 0011111010100000111111 = 0011111010100000111111

Depois filhoDepois filho11 = 0010 = 0010000101101001010101101001011111001100 filhofilho22 = 0011111010 = 0011111010000000011111100000111111

Page 12: Algoritmo Genético Inteligência Artificial Prof. Marcelo B. de Almeida

Primeira geração Primeira geração