Apresentação Título : Introdução à Programação Genética Aluno : Gustavo Henrique Flores Caldas Profa. : Inês Dutra Objetivo Apresentar a Programação Genética como um algoritmo capaz de produzir programas de computador com um mínimo de intervenção humana. Conteúdo ● Introdução ⊙ Descrição do Problema ⊙ Breve Histórico ● Programação Genética ⊙ A Representação ⊙ O Algoritmo ◎ Fitness ◎ Operadores Genéticos ⊙ Parâmetros Comuns ⊙ Aplicações ● Conclusão Descrição do Problema Busca do melhor programa... ... no espaço de todos os programas. Metáfora Biológica da PG Breve Histórico Ano Inventor Técnica Indivíduo 1958 Friedberg Máquina Aprendiz Assembler Virtual 1959 Samuel Matemática Polinômio 1965 Fogel, Owens e Walsh Programação Evolucionária Autômato 1975 Rechenberg e Schwefell Estratégias Evolucionárias Vetor Numérico 1978 Holland Algoritmos Genéticos String Binária 1980 Holland e Reitmann Sistema Genético de Classificação Regras 1985 Smith Programação Genética Inicial Strings Binárias Variáveis 1986 Cramer Programação Genética Inicial Árvore 1987 Hicklin Programação Genética Inicial LISP 1987 Fugiki e Dickinson Programação Genética Inicial LISP 1987 Dickmanns, Chmidhuber e Winkhofer Programação Genética Inicial Assembler 1992 Koza Programação Genética Árvore Requisitos para Adaptação ◈ Reprodução entre indivíduos dentro da população ◈ Hereditariedade na reprodução ◈ Variações que afetam as condições de sobrevivência dos indivíduos ◈ Recursos limitados causando competição Representação dos “Indivíduos” (+ (* (+ 1 2) (- (+ 3 4) 5)) (- (* 6 7) 8)) Ou (+ (* (+ 1 2) (- (+ 3 4) 5)) (- (* 6 7) 8)) + Ou * + 1 * 2 + 3 5 4 6 8 7 Algoritmo de Programação Genética G := 0 Criar População Inicial Critério de Término foi Satisfeito? Sim Designar Resultado Não Avaliar o Desempenho de Cada Indivíduo na População G := G + 1 Aplicação de Operadores Genéticos Fim População Inicial Funções : F = {+, *, , } + 1 * – 2 = -3 4 Terminais : T = {0, 1, 2, 3, 4} Funções : F = {Se, E, Ou} Terminais : T = {L1, L2, Verdadeiro, Falso} 3 Se E L1 Ou Verdadeiro L2 Ou Falso Verdadeiro L2 L1 Falso Cuidados com os Indivíduos + 0 Verdadeiro Completude Ou 0 Funções : F = {+, Ou} Terminais : T = {Verdadeiro, 0} + + Suficiência 0 + 0 0 Funções : F = {+} Terminais : T = {0} 0 Fitness & Casos Fitness 1.0 x x 0.8 x x 0.6 x 2 Aproximação de y = x3 no intervalo [0, 1] 3 4 5 y 0.4 1.0 3 x 0.2 0.8 0.0 0.00 0.25 0.50 0.75 Casos Fitness 1.00 0.6 x y 0.4 0.2 0.0 0.00 0.25 0.50 x 0.75 1.00 Seleção Indivíduos Selecionados da População População 1 1 2 3 1 1 4 2 5 6 3 2 7 8 4 9 4 9 Reprodução Indivíduos Selecionados da População 1 1 1 2 4 3 2 4 4 9 Próxima Geração Crossover Indivíduos Selecionados da População 1 1’ 1 1 2 3 2 3’ 4 4 9 Próxima Geração Crossover + * + 1 * 2 + 3 5 6 8 3 * 7 1 2 4 + * + 1 3 2 * 6 8 7 * 1 2 + 3 5 4 Mutação Indivíduos Selecionados da População 1 1 1 2 9’ 3 2 4 4 9 Próxima Geração Mutação * 3 + * 1 2 1 2 * 1 4 + 2 3 Finalização G := 0 Criar População Inicial Critério de Término foi Satisfeito? Sim Designar Resultado Não Avaliar o Desempenho de Cada Indivíduo na População G := G + 1 Aplicação de Operadores Genéticos Fim Parâmetros Comuns População = 500 Gerações = 50 Seleção = Proporcional a Fitness Crossover = 80 % Mutação = 10 % Reprodução = 10 % Aplicações da PG 250 150 100 o N de Publicações 200 50 0 1989 1990 1991 1992 1993 Ano 1994 1995 1996 Domínio de Aplicação Primeira Publicação Algoritmos 1992 Arte 1993 Biotecnologia 1993 Gráficos de Computador 1991 Computação 1992 Controle (Geral) 1992 Controle (Processo) 1990 Controle (Robôs e Agentes) 1992 Controle (Espaçonave) 1996 Data Mining 1996 Engenharia elétrica 1994 Mercado Financeiro 1994 Sistemas Híbridos 1993 Processamento de Imagens 1993 Evolução Interativa 1991 Modelagem 1994 Linguagem Natural 1994 Otimização 1994 Reconhecimento de Padrões 1994 Processamento de Sinais 1992 Conclusão A Programação Genética encontra-se ainda em estágio de desenvolvimento, mas já é possível aplicá-la satisfatoriamente em várias áreas diferentes do conhecimento. Tudo isso com quase nenhuma intervenção humana.