Inteligência Artificial para Jogos - Algoritmos Genéticos

Inteligência Artificial para Jogos

Algoritmos Genéticos

GT-JEDI – Jogos DigitaisInteligência Artificial para Jogos

UNISINOS

Prof. MSc. João Ricardo Bittencourt

Update: 20 Nov. [email protected]

Agradeço ao Prof. Osórioe ao Gustavo Pessin

“Tome a pílulavermelha”

http://creativecommons.org/licenses/by-nc-sa/2.5/br/

UNISINOS - João Ricardo Bittencourt

Conceitos básicos Técnica de busca e otimização. Metáfora da teoria da Evolução das Espécies (Charles

Darwin). Desenvolvido por John Holland (1975) e popularizado

por David Goldberg (1989). Implementação computacional baseada nos princípios

naturais da genética e da evolução


Conceitos básicos Teoria da Evolução

1859 - Charles Darwin publica o livro A Origem das Espécies

• As espécies evoluem pelo principio da seleção natural e sobrevivência do mais apto.

• Quanto melhor um indivíduo se adaptar ao seu meio ambiente, maior será sua chance de sobreviver e gerar descendentes

Gregor Mendel, em 1865, apresenta experimentos do cruzamento genético de ervilhas.

Teoria da evolução => conceituação integrada da seleção natural com a genética.


Conceitos básicos Otimização

Buscar a melhor solução para um determinado problema

As técnicas de otimização apresentam:• Espaço de busca – onde estão as possíveis

soluções de um problema• Função objetivo (fitness) – avaliar a solução

encontrada Em termos matemáticos

• Achar uma solução que corresponda ao ponto máximo ou mínimo de uma função


Características Algoritmos estocastícos Lida com uma coleção de soluções Fáceis de serem implementados

computacionalmente Necessita de uma função de avaliação (fitness) Fácil de integrar com outras técnicas de IA Funcionam com parâmetros contínuos ou

discretos


Terminologia Indivíduo

Membro da população. É descrito por um cromossomo

Gene Codifica um único parâmetro do problema

Alelos Os valores que um gene pode assumir

Cromossomo Coleção de genes Estrutura de dados que codifica o problema

Genótipo Informação contida nem um cromossomo


Dificuldades As principais dificuldades para aplicar AG

Como representar os parâmetros que definem o problema?

Quem é a população inicial? Como definir a função objetivo (fitness)?


Algoritmo Algoritmo genético típico


Funcionamento AG manipula uma população de indivíduos. Indivíduos são possíveis soluções do problema. Os indivíduos são combinados (crossover) uns

com os outros, produzindo filhos que podem sofrer ou não mutação.

As populações evoluem através de sucessivas gerações até encontrar a solução ótima.


Funcionamento Indivíduo (Cromossomo)

Estrutura de dados que representa uma possível solução para o problema.

Os parâmetros do problema de otimização são representados por cadeias de valores.• Vetores de reais: (2.345, 4.3454, 5.1, 3.4)• Cadeias de bits: (111011011)• Vetores de inteiros: (1,4,2,5,2,8)

Aptidão de um indivíduo Resultado do →fitness


Funcionamento Seleção

Seleciona um par de indivíduos para reprodução

Critério de seleção função → fitness Imitação da seleção natural.

• Os melhores indivíduos (maior aptidão) são selecionados para gerar filhos através de crossover e mutação.

Dirige o AG para as melhores regiões do espaço de busca.

Tipo mais comum de seleção:• Seleção proporcional a aptidão


Funcionamento Reprodução

Conjunto de operações (crossover, mutação,...) aplicada a um par na geração de um novo indivíduo.

Crossover e Mutação Combinam pais selecionados para produção

de filhos. Principais mecanismos de busca do AG. Permite explorar áreas desconhecidas do

espaço de busca.


Funcionamento Crossover

Troca de material genético entre os pais

Se o crossover é aplicado ospais trocam suas caudas gerandodois filhos, caso contrário os doisfilhos serão cópias exatas dospais.

O crossover é aplicado com uma dadaprobabilidade denominada taxa de

crossover (60% a 90%)


Funcionamento Crossover

Troca de material genético entre os pais

Crossover 2 pontosCrossover 4 pontos


Funcionamento Mutação

Pequenas mudanças aleatórias na seqüência de bits

Mutação inverte os valores dos bits

A mutação é aplicada com dada probabilidade, denominada taxa demutação (~1%), em cada um dos

bits do cromossomo.

A taxa de mutação não deve ser nem altanem baixa, mas o suficiente para

assegurar a diversidade de cromossomosna população.


Funcionamento Elitismo

Problema: o melhor cromossomo poder ser perdido de uma geração para outra

Solução: manter na próxima geração o melhor indivíduo da geração atual

Esta estratégia é chamada de elitismo


Funcionamento Função de avaliação (fitness)

Função usada para avaliar o membro de uma geração

Estas funções podem ser extremamente complexas. Efetuar toda uma simulação para obter a avaliação.

Usar duas funções objetivos:• Uma simplificada no inicio da busca• Uma mais refinada quando encontra-se

uma solução


Funcionamento Critério de Parada

Número de gerações Encontrou a solução (quando esta é

conhecida) Convergência

• nas últimas k gerações não houve melhora na aptidão:

• Média• Máxima


Referências Goldberg, D. E. Genetic Algorithms in Search,

Optimization and Machine Learning. Addison-Wesley, 1989.

Tom M. Mitchell. Machine Learning. McGraw-Hill, 1997. Eberhart, R; Simpson, P; Dobbins, R. Computational

Intelligence PC Tools. Academic Press,1996.

Documents

Inteligência Artificial para Jogos - Algoritmos Genéticos