CEAAE 2006
Disciplina EE-09:
Inteligência Artificial
Algoritmos Genéticos
Por: CT(EN) ALI KAMEL
OBJETIVO
O objetivo deste trabalho é apresentar
de forma sintética, os princípios
básicos dos algoritmos genéticos e
suas aplicações.
ROTEIRO
•
•
•
•
•
•
INTRODUÇÃO – ORIGENS
PARÂMETROS TÍPICOS
ALGORITMO GENÉTICO TRADICIONAL
SELEÇÃO E CROSSOVER
ESTUDO DE CASOS:
CASO 1(ARTIGO) – DISTRIBUIÇÃO DE
RADARES PARA MELHOR COBERTURA
RADAR
• CASO 2 (VÍDEO) – OTIMIZAR VÔO DE UM
PASSÁRO
• CONCLUSÃO
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.”
Charles
Darwin
Teoria da Evolução
.
Gregor
Mendel
• 1865- Gregor Mendel apresenta
experimentos do cruzamento
genético de ervilhas.
– Pai da genética.
• A Teoria da Evolução começou
a partir da conceituação
integrada da seleção natural
com a Genética.
Algoritmos Genéticos com
Parâmetros Contínuos e
Representação Binária
• É historicamente importante, foi utilizado
nos trabalhos pioneiros de Holland (1975).
• A representação tradicional.
• Fácil de usar e manipular.
• Simples de analisar teoricamente.
• Não há uniformidade nos operadores.
– Mutação nos primeiros bits do gene afeta mais
a aptidão que mutação nos últimos bits do gene
PARÂMETROS TÍPICOS
• Cromossomo (genótipo) - cadeia de bits que representa uma
solução possível para o problema. Existem três tipos de
representação possíveis para os cromossomos: binária,
inteira ou real. A essa representação se dá o nome de
alfabeto do AG. De acordo com a classe de problema que se
deseje resolver pode-se usar qualquer um dos três tipos.
• Gene - representação de cada parâmetro de acordo com o
alfabeto utilizado (binário, inteiro ou real).
• Fenótipo - cromossomo codificado;
• População - conjunto de pontos (indivíduos) no Espaço de
Busca;
• Geração - iteração completa do AG que gera uma nova
população;
• Aptidão bruta - saída gerada pela função objetivo para um
indivíduo da população; Aptidão normalizada - aptidão bruta
normalizada, entrada para o algoritmo de seleção;
• Aptidão máxima - melhor indivíduo da população corrente; e
• Aptidão média - aptidão média da população corrente.
Algoritmo Genético Tradicional
REF [3]
Seleção proporcional
a aptidão (Roleta)
REF [3]
“CROSSOVER”
REF [3]
PROBLEMA 1: Otimizar a distribuição de radares para
que
tenhamos
uma
melhor
cobertura.
Artigo estudado: “Algoritmo Genético Aplicado à
Otimização da Cobertura do Sinal gerdo por Radares
Terrestres” – Felipe Leonardo Lobo de Medeiros et all.
–IEAv
EXEMPLO DE APLICAÇÃO
REF [5]
DEFINIÇÃO DOS PARÂMETROS
REF [5]
REF [5]
PROBLEMA 2: Otimizar o vôo de um
pássaro, USANDO REDES NEURAIS
E ALG. GENÉTICOS
(SISTEMA HÍBRIDO).
“Evolution of neuro-controllers for a flapping-wing
animat.” - Stéphane Doncieux, Jean-Baptiste Mouret, Laurent
Muratet et all
FROM ANIMALS TO ANIMATS 9
The Ninth International Conference on the SIMULATION OF ADAPTIVE BEHAVIOR (SAB'06)
25 - 29 September 2006, CNR, Roma, Italy
http://www.ele.ita.br/~alikamel/Listex1/evolving.mp4
http://www.ele.ita.br/~alikamel/Listex1/Doncieux_JMD.pdf
(Necessário uso do software Quick Time)
REF [4]
CONCLUSÕES
• Os AG's são apropriados para problemas de
otimização complexos, que envolvem muitas
variáveis e um espaço de soluções de dimensão
elevada.
• Abrangem um grande número de aplicações.
• O controle sobre os parâmetros do algoritmo é de
fundamental importância para uma convergência
rápida.
• Para problemas específicos é aconselhável a
utilização de algoritmos híbridos, que misturam as
técnicas dos AG's com os métodos de otimização
tradicionais.
• Devido ao grande número de variáveis que um AG
trata e às populações elevadas e alto número de
gerações para a cobertura do espaço de soluções,
os AG's possuem um custo computacional elevado.
REFERÊNCIAS:
•
1 – Notas de Aula da Disciplina EE-09 Inteligência Artificial do Curso
de Especialização em Análise de Ambiente Eletromagnético do
Instituto Tecnológico de Aeronáutica;
•
2 – Tutorial de Algoritmo Genético – Darrel Whitley e Christian Willy
Asmussen – http://xpusp.sorceforge.net/ga_tutorial.html;
•
3 – Algoritmos Genéticos: Fundamentos e Aplicações – Márcio Nunes
de Miranda - http://gta.ufrj.br/~marcio/genetic.html;
•
4 – “Evolution of neuro-controllers for a flapping-wing animat.” Stéphane Doncieux, Jean-Baptiste Mouret, Laurent Muratet et all
•
5 – “Algoritmo Genético Aplicado à Otimização da Cobertura do Sinal
gerdo por Radares Terrestres” – Felipe Leonardo Lobo de Medeiros et
all. –IEAv