inteligencia artificial

Inteligência Artificial
Busca de têmpera simulada;
Busca em feixe local;
Algoritmos Genéticos

1

Busca de têmpera simulada
(Simulated annealing search)


Combina


A subida de encosta com um percurso aleatório resultando em




Eficiência e completeza

Artifício


Agitar com força suficiente para sair dos mínimos locais, mas não o bastante para desalojá-la do mínimo global
2

1

Busca em feixe local
(Local bem search)


Algoritmo anterior




considera um nó na memória para a busca Na versão Busca em feixe local


Mantém o controle de ‘k’ estados, em vez de somente um

3

Busca em feixe local
(Local bem search)


Passos









Inicia com ‘k’ estados aleatórios
(Em cada passo) Gerar todos os sucessores de todos os ‘k’ estados
Se um deles for o objetivo =>para
Se não, selecionará os ‘k’ melhores sucessores
(da lista completa)
Repetir ação

Informações são repassadas entre os ‘k’ processos (paralelos)
Abandonando buscas infrutíferas
4

2

Busca em feixe local
(Local bem search)


Desvantagens






pode existir uma falta de diversidade
(concentração)
Busca parecida ao ‘Hill-Climbing search’

Alternativa: ...


Busca em feixe estocástica (stochastic beam search)


Escolhe ‘k’ sucessores ao acaso




probabilidade associada

Semelhante à seleção natural de um organismo
5

Algoritmos Genéticos (AG)


Variante da busca em feixe estocástica 

Estados sucessores são gerados pela combinação de dois estados pais




(em vez de serem gerados pela modificação de um único estado)

Analogia com a seleção natural

6

3

Algoritmos Genéticos (AG)


Estados sucessores são gerados pela combinação de dois estados pais.


Inicia com uma população (k estados)
Cada indivíduo (ou estados) é representado como uma cadeia sobre um alfabeto finito.



.



7

Algoritmos Genéticos (AG)

8

4