Programação Genética

  • Published on
    09-Jun-2015

  • View
    2.303

  • Download
    0

Embed Size (px)

Transcript

<ul><li> 1. Programao Gentica Diogo Medeiros</li></ul> <p> 2. Introduo </p> <ul><li>A Programao Gentica tenta tratar uma das questesda cincia da computao: </li></ul> <ul><li> Como os computadores podem aprender a resolver problemas sem serem explicitamente programados para tal? </li></ul> <ul><li> Ou seja, como os computadores podem fazer o que deve ser feito sem serem orientados exatamente para fazerem isto? </li></ul> <p> 3. Histrico </p> <ul><li>Em 1975, John Holland (Ph.D. em Cincia da Computao - Universidade de Michigan, 1959) criou os Algoritmos Genticos. </li></ul> <ul><li>Em 1992, John Koza (Doutor em Cincia da Computao - Universidade de Michigan, 1972) usou algoritmos genticos para desenvolver programas para realizar certas tarefas. Ele chamou seu mtodo de programao gentica. </li></ul> <p> 4. Propsitos </p> <ul><li>Como qualquer outro sistema computacional inspirado na natureza, a Programao Gentica tem dois propsitos bsicos: </li></ul> <ul><li><ul><li>Servir de ferramenta para a soluo de problemas de engenharia; </li></ul></li></ul> <ul><li><ul><li>Servir de modelo cientfico simplificado para processos naturais. </li></ul></li></ul> <ul><li>Na prtica, qualquer implementao de Programao Gentica vai envolver, ao menos parcialmente, ambos os propsitos bsicos mencionados acima. </li></ul> <p> 5. reas de Utilizao </p> <ul><li>A utilizao da Programao Gentica tem sido estendida a problemas de diversas reas do conhecimento, tais como: </li></ul> <ul><li><ul><li>Biotecnologia. </li></ul></li></ul> <ul><li><ul><li>Engenharia Eltrica. </li></ul></li></ul> <ul><li><ul><li>Anlises Financeiras. </li></ul></li></ul> <ul><li><ul><li>Processamento de Imagens. </li></ul></li></ul> <ul><li><ul><li>Reconhecimento de Padres. </li></ul></li></ul> <ul><li><ul><li>Minerao de Dados. </li></ul></li></ul> <ul><li><ul><li>Linguagem Natural. </li></ul></li></ul> <p> 6. Definio </p> <ul><li>A Programao Gentica a extenso dos Algoritmos Genticos no domnio dos programas, onde: </li></ul> <ul><li><ul><li>O indivduo um programa de computador. </li></ul></li></ul> <ul><li><ul><li>O espao de busca so todos os possveis programas de computador. </li></ul></li></ul> <ul><li>Em resumo, a Programao Gentica um mtodo que busca, dentro de um espao significativamente polinomial/exponencial e restrito de programas de computador, uma soluo exata ou pelo menos aproximada para resolver determinado problema. </li></ul> <p> 7. Programas de Computadores </p> <ul><li>Um programa de computador uma expresso matemtica composta de funes e terminais. </li></ul> <ul><li>As funes podem ser operaes aritmticas (+, - , *,...), operaes booleanas (and, or, not, ...), funes matemticas (sen, cos, ...), operadores condicionais (if, then, ...), funes de iterao (while, ...), funes que causam recurso, funes especficas do domnio do problema. </li></ul> <ul><li>Os terminais podem ser variveis (representando, possivelmente, as entradas) ou constantes (nmero 5, por exemplo). </li></ul> <p> 8. Representao de Programas em PG </p> <ul><li>Os programas de computador, em Programao Gentica, so representados sob a forma de rvores . </li></ul> <ul><li>As funes aparecem nos ns internos da rvore . </li></ul> <ul><li>Os terminais aparecem nos ns folha da rvore . </li></ul> <p> 9. Representao de Programas em PG </p> <ul><li>Abaixo, temos a expresso 3 x+2x+1representada sob a forma de rvore: </li></ul> <p> 10. Exemplo de execuo da PG </p> <ul><li>Entrada: Conjunto de pontos = {1,4,5,6,9} </li></ul> <ul><li>Sada: Melhor programa encontrado tal que a funo y se aproxime mais dos pontos dados na entrada. Por exemplo, o programa x+x. </li></ul> <ul><li>Cada programa avaliado pela medida de aptido, a qual deve ser definida como parmetro, pois varia de problema para problema. </li></ul> <ul><li>A PG, atravs de operaes genticas, ir retornar o melhor programa encontrado a partir de uma populao inicial de programas criada de um conjunto de funes e terminais. </li></ul> <p> 11. Figura Ilustrativa 12. Representao de Programas em PG </p> <ul><li>A Programao Gentica evolui programas de computador a partir dos conjuntos de terminais e de funes. </li></ul> <ul><li>Para que programas criados pelo PG sejam vlidos, necessrio que os conjuntos de funes e de terminais atendam a propriedade do fechamento - closure . </li></ul> <p> 13. Propriedade do Fechamento (Closure) </p> <ul><li>Funes devem aceitar como argumento qualquer valor e tipo de dado que seja retornado por qualquer funo do conjunto de funes, e qualquer valor e tipo de dado que possa ser assumido por qualquer terminal. </li></ul> <p> 14. Fluxograma da Programao Gentica 15. Passos Preparatrios para PG </p> <ul><li>Existem 5 Passos Preparatrios na aplicao de PG: </li></ul> <ul><li>Determinar o Conjunto de Terminais; </li></ul> <ul><li>Determinar o Conjunto de Funes Primitivas; </li></ul> <ul><li>Definir uma Medida de Aptido; </li></ul> <ul><li>Estabelecer Parmetros para Controlar a Execuo; </li></ul> <ul><li>Definir um Mtodo para Determinar o Resultado e um Critrio de Parada; </li></ul> <p> 16. Medida de Aptido (Funo Fitness) </p> <ul><li>Cada indivduo tem associado a si uma medida numrica, que o resultado da interao dele com o ambiente; </li></ul> <ul><li>Ou seja, uma medida do grau de adaptao deste indivduo; </li></ul> <ul><li>Esta medida que dirige diretamente o processo evolucionrio, fazendo com que, quanto mais adaptado for um indivduo maior a sua chance de permanecer ou ter suas caractersticas propagadas para as prximas geraes. </li></ul> <p> 17. Parmetros de Controle da Execuo </p> <ul><li>tamanho da populao </li></ul> <ul><li>nmero mximo de geraes </li></ul> <ul><li>taxa de reproduo </li></ul> <ul><li>taxa de mutao </li></ul> <ul><li>taxa de crossover </li></ul> <ul><li>altura da rvore </li></ul> <ul><li>altura inicial da rvore </li></ul> <ul><li>taxa de permutao </li></ul> <ul><li>freqncia de edio </li></ul> <p> 18. Parmetros de Controle da Execuo </p> <ul><li>taxa de encapsulamento </li></ul> <ul><li>condio de chamada de destruio </li></ul> <ul><li>mtodo de gerao da populao inicial </li></ul> <ul><li>mtodo de seleo do pai (primeiro e segundo) </li></ul> <ul><li>uso de ajuste da medida de aptido </li></ul> <p> 19. Critrio de Parada </p> <ul><li>Atingir um nmero mximo de geraes; </li></ul> <ul><li>Atingir um ponto timo (satisfatrio) do problema. </li></ul> <p> 20. Criao da Populao Inicial </p> <ul><li>Gera-se uma populao inicial aleatria, formada por programas de computadores, com funes e terminais aleatrios, obedecendo a profundidade mxima da rvore (controlada por parmetro). </li></ul> <ul><li>Mtodos: </li></ul> <ul><li><ul><li>Grow </li></ul></li></ul> <ul><li><ul><li>Full </li></ul></li></ul> <ul><li><ul><li>Half-and-half </li></ul></li></ul> <ul><li><ul><li>Uniform </li></ul></li></ul> <p> 21. Mtodos de Criao da Populao Inicial: Grow </p> <ul><li>Os ns so selecionados aleatoriamente dos conjuntos F e T (exceto para o n raiz que retirado do conjunto F), por este motivo o mtodo produz rvores de formatos irregulares. Se uma ramificao contm um n terminal, esta ramificao pra, mesmo que a profundidade mxima no tenha sido atingida. </li></ul> <p> 22. Mtodos de Criao da Populao Inicial: Full </p> <ul><li>Ao invs de escolher aleatoriamente os ns do conjunto de funes e de terminais, o mtodo Full, escolhe somente funes at que um n de profundidade mxima seja selecionado, ento ele passa a escolher somente terminais. O resultado disso que cada rvore atinge a profundidade mxima. </li></ul> <p> 23. Mtodos de Criao da Populao Inicial: Half-and-half </p> <ul><li>uma combinao dos mtodos Grow e Full, ou seja, utiliza o mtodo Full em 50% das vezes e o mtodo Grow nas outras 50%, tendo por objetivo gerar um nmero igual de rvores para cada profundidade. </li></ul> <ul><li>Supondo, por exemplo, uma rvore de profundidade mxima seis (6), a populao igualmente dividida em rvores com profundidade dois, trs, quatro, cinco e seis, ou seja, 20% tero profundidade dois, 20% tero profundidade trs e assim sucessivamente. </li></ul> <ul><li>Em cada grupo, metade das rvores so geradas pelo mtodo Full e a outra metade pelo Grow. </li></ul> <p> 24. Mtodos de Criao da Populao Inicial: Uniform </p> <ul><li>Desenvolvido com o objetivo de criar rvores uniformes, geradas a partir do conjunto de todas as rvores possveis. </li></ul> <ul><li>O algoritmo calcula vrias vezes quantas rvores podero ser geradas para cada tamanho desejado, por este motivo o mtodo possui um alto custo computacional. </li></ul> <p> 25. Mtodos de Criao da Populao Inicial: Algoritmo 26. Seleo dos Indivduos </p> <ul><li>Para selecionar quais indivduos da populao faro parte de uma nova gerao e quais deles sofrero alteraes, atravs dos operadores genticos (reproduo, cruzamento e mutao), necessrio que se tenha um critrio de seleo que garanta que uma boa escolha seja realizada. </li></ul> <ul><li>Um dos mtodos mais utilizados para se efetuar esta seleo, baseia-se no valor de aptido de cada indivduo, os indivduos selecionados devero ser aqueles que apresentam melhores valores de aptido. </li></ul> <p> 27. Operadores Genticos </p> <ul><li>Reproduo </li></ul> <ul><li>Crossover (Cruzamento) </li></ul> <ul><li>Mutao </li></ul> <ul><li>Permutao </li></ul> <ul><li>Edio </li></ul> <ul><li>Encapsulamento </li></ul> <ul><li>Destruio (Decimation) </li></ul> <p> 28. Operadores Genticos: Reproduo </p> <ul><li>Um indivduo da populao selecionado de acordo com algum mtodo baseado na aptido; </li></ul> <ul><li>O indivduo copiado, sem qualquer alterao, para a prxima gerao. </li></ul> <p> 29. Operadores Genticos: Crossover </p> <ul><li>Troca de material gentico entre dois indivduos. </li></ul> <ul><li> escolhido um ponto de corte nas duas rvores e os ramos inferiores a ele so trocados. </li></ul> <p> 30. Operadores Genticos: Mutao </p> <ul><li>A mutao consiste em uma mudana aleatria de uma funo, uma entrada ou uma constante na rvore. </li></ul> <p> 31. Operadores Genticos: Permutao </p> <ul><li>Escolhe-se um ponto interno de uma expresso; </li></ul> <ul><li>Ramos so permutados; </li></ul> <ul><li>A permutao a ser realizada escolhida aleatoriamente (3 ramos: existem 3! possibilidades de permutao); </li></ul> <ul><li>se a funo comutativa, no h efeito da permutao. </li></ul> <p> 32. Operadores Genticos: Edio </p> <ul><li>Proporciona um meio para editar e simplificar expresses; </li></ul> <ul><li>Consome muito tempo; </li></ul> <ul><li>Pode tornar a expresso menos vulnervel ao crossover; </li></ul> <ul><li>Reduz a variedade de estruturas disponveis para o crossover. </li></ul> <p> 33. Operadores Genticos: Encapsulamento </p> <ul><li>Forma de identificar subrvores potencialmente teis e dar a elas um nome para que sejam referenciadas e usadas posteriormente; </li></ul> <ul><li>Seleciona-se um pai baseando-se na aptido; </li></ul> <ul><li>Seleciona-se um ponto interno desta rvore. </li></ul> <p> 34. Operadores Genticos: Destruio </p> <ul><li> uma forma de reduzir o nmero de indivduos medocres nas primeiras geraes; </li></ul> <ul><li>Controlado por dois parmetros: </li></ul> <ul><li> percentagem de indivduos mantdos; e </li></ul> <ul><li> condio que especifica quando este operadorser invocado. </li></ul> <ul><li>Indivduos so selecionados para permanecer com base na aptido. </li></ul> <ul><li>Ex: Percentagem=10% , Quando=gerao 0 </li></ul> <ul><li>Na gerao 0, 10% da populao permanece (populao ser criada 10 vezes maior na gerao 0) </li></ul> <p> 35. Exemplo </p> <ul><li>Objetivo: Dada a entrada (conjunto de pontos), fazer uma regresso simples atravs da PG. </li></ul> <ul><li>Conjunto de Funes: +,-,*,sen,cos </li></ul> <ul><li>Conjunto de Terminais: varivel x e constantes aleatrias </li></ul> <ul><li>Populao Inicial: Half-and-half </li></ul> <ul><li>Parmetros: - Tamanho da populao = 100 - crossover = 80% - mutao = 20% - reproduo = 20% </li></ul> <p> 36. Exemplo </p> <ul><li>Entrada: </li></ul> <p> 37. Simulador </p> <ul><li>Applet Java que simula uma execuo da PG para uma Regresso Simples. </li></ul> <ul><li>Site: http://alphard.ethz.ch/gerber/approx/default.html </li></ul> <ul><li>Necessrio ter Plugin Java instalado no navegador. </li></ul> <ul><li>Utiliza todos os conceitos de PG que vimos at agora. </li></ul> <p> 38. Simulador Aplicando o exemplo </p> <ul><li>Tela Inicial: </li></ul> <p> 39. Simulador Aplicando o exemplo </p> <ul><li>Clicando em Settings... podemos ajustar os parmetros: </li></ul> <p> 40. Simulador Aplicando o exemplo </p> <ul><li>Abaixo temos a figura mostrando a tela aps ajustar os parmetros. Note, no quadro Approximation, que o programa interpretou os pontos do conjunto de entrada. </li></ul> <p> 41. Simulador Aplicando o exemplo </p> <ul><li>Aps ajustar os parmetros, clicamos em Start e ele inicia a execuo da PG, sempre mostrando o melhor indivduo atual no quadro Results e a curva da sua funo na cor Azul no quadro Approximation: </li></ul> <p> 42. Simulador Aplicando o exemplo </p> <ul><li>Abaixo temos a tela aps a PG terminar a execuo (depois de 1000 geraes, no caso deste simulador). O melhor indivduo (sada da PG) foi encontrado na gerao 999. </li></ul> <p> 43. Questo 1 </p> <ul><li>O que Programao Gentica? Quais seus principais propsitos? </li></ul> <p> 44. Questo 2 </p> <ul><li>O que um programa de computador? Cite 2 exemplos. </li></ul> <p> 45. Questo 3 </p> <ul><li>Dado os programas abaixo, como estes seriam representados na Programao Gentica? (desenhe) </li></ul> <ul><li><ul><li>3x+9y-7z </li></ul></li></ul> <ul><li><ul><li>(a OR b) AND (c AND (NOT d)) </li></ul></li></ul> <p> 46. Questo 4 </p> <ul><li>Qual o programa de computador que representa cada rvore abaixo? Indique o conjunto de funes e o conjunto de terminais usado em cada rvore. </li></ul> <p> 47. Questo 5 </p> <ul><li>Simule uma execuo da Programao Gentica para o seguinte problema: </li></ul> <ul><li>Objetivo: Encontrar um programa cuja sada coincide com x+x no intervalo 0</li></ul> <ul><li>Conjunto de Funes: +,-,* </li></ul> <ul><li>Conjunto de Terminais: varivel x e constantes entre 0 e 5 </li></ul> <ul><li>Funo Fitness : soma dos erros absolutos parax = {0, 0.2, ..., 0.8, 1.0} </li></ul> <ul><li>Populao Inicial: Full </li></ul> <p> 48. Questo 5 (cont.) </p> <ul><li>Parmetros: - Tamanho da populao = 4 - crossover = 50% - mutao = 25% - reproduo = 25% - Sub-rvores sem limite de tamanho - Tamanho da rvore inicial = 3 - Nmero mximo de geraes = 4 </li></ul> <ul><li>Critrio de Parada: Um programa cuja soma dos erros absolutos menor que 0.1 encontrado ou nmero mximo de geraes atingido </li></ul> <p> 49. Questes Complementares </p> <ul><li>Exemplifique a propriedade do fechamento. </li></ul> <ul><li>Qual a complexidade algoritmica dos AGs? </li></ul> <ul><li>Em relao aos AGs, qual o seu espao de estados? </li></ul> <ul><li>Idem s duas questes anteriores, qual a complexidade da PG? </li></ul>