Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Algoritmo Genético com Python

Algoritmo Genético com Python

Slides usados na apresentação da palestra "Algoritmo Genético com Python" na Python Nordeste 2018 e Python Brasil 2018.

Ana Paula Mendes

October 18, 2018
Tweet

More Decks by Ana Paula Mendes

Other Decks in Programming

Transcript

  1. ~$ whoami Ana Paula Mendes Desenvolvedora full stack e pesquisadora

    em inteligência artificial @anapaulamendes /ananoterminal @ananoterminal
  2. Base biológica: “It is not the strongest of the species

    that survives, nor the most intelligent , but the one most responsive to change.” (Charles Darwin)
  3. Base biológica: • Inspirado em modelos biológicos: ◦ Teoria da

    Evolução de Darwin (1859); ◦ Genética de Mendel (1865);
  4. O que são técnicas de otimização? • Definição do termo

    “melhor” em otimização; • Conjuntos das soluções;
  5. O que são técnicas de otimização? • Um problema de

    otimização pode ser representado da seguinte forma: ◦ Dados: uma função f : A → R de algum conjunto A de números reais; ◦ Buscando: um elemento x0 em A tal que f(x0) ≤ f(x) para todo x em A ("minimização") ou tal que f(x0) ≥ f(x) para todo x em A ("maximização").
  6. Introdução: Algoritmos genéticos • Problemas np; • Falha de métodos

    baseados em gradientes; • Obter uma boa solução rapidamente.
  7. Algoritmo Genético Início Inicia a população Cálculo de aptidão mutação

    crossover seleção Solução encontrada Fim não sim
  8. Algoritmos genéticos • Cruzamento (Crossover): ◦ Aleatório; ◦ Single Arithmetic

    Crossover; ◦ Simple Arithmetic Crossover; ◦ Partially-Matched Crossover.
  9. Cruzamento - Algoritmos genéticos • Single Arithmetic Crossover: Pai 1={0.5,

    1.0, 1.5, 2.0}, Pai 2={0.2, 0.7, 0.2, 0.7} a = 0.4 e k = 3 Filho 1={0.5, 1.0, (0.4)(0.2)+(0.6)(1.5), 2.0} = {0.5, 1.0, 0.98, 2.0} Filho 2={0.2, 0.7, (0.4)(1.5)+(0.6)(0.2), 0.7} = {0.2, 0.7, 0.72, 0.7}
  10. Cruzamento - Algoritmos genéticos • Simple Arithmetic Crossover: Pai 1={0.5,

    1.0, 1.5, 2.0}, Pai 2={0.2, 0.7, 0.2, 0.7} a = 0.4 e k = 3 Filho 1={0.5, 1.0, (0.4)(0.2)+(0.6)(1.5), (0.4)(0.7)+(0.6)(0.2)} = {0.5, 1.0, 0.98, 1.48} Filho 2={0.2, 0.7, (0.4)(1.5)+(0.6)(0.2), (0.4)(2.0)+(0.6)(0.7} ={0.2, 0.7, 0.72, 1.22}
  11. Cruzamento - Algoritmos genéticos • Partially-Matched Crossover: Pai 1 =

    1 2 4 6 3 7 5 8 -> Substring 463 Pai 2 = 5 4 1 7 2 6 8 3 -> Substring 172 ------------------- 5 4 4 6 3 6 8 3 5 1 4 6 3 7 8 2 -> Números repetidos são substituídos
  12. Bibliotecas de Algoritmo genético • Pyvolution: Very modular and very

    extensible evolutionary algorithms framework, with complete documentation, Apache License 2.0; • deap: Distributed Evolutionary Algorithms in Python, GNU Lesser GPL; • pySTEP: Python Strongly Typed gEnetic Programming, MIT License; • Pyevolve: Pyevolve was developed to be a complete genetic algorithm framework written in pure python;
  13. Bibliotecas de Algoritmo genético • PyRobot: Evolutionary Algorithms (GA +

    GP) Modules, Open Source; • PonyGEa: small, one source file implementation of GE, with an interactive graphics demo application GNU GPL v3; • inspyred: Biologically inspired computation encompasses a broad range of algorithms including evolutionary computation, swarm intelligence, and neural networks, GNU GPL v3; • DRP: Directed Ruby Programming, Genetic Programming & Grammatical Evolution Library, GNU GPL;
  14. Referências bibliográficas: • Coppin, ben. Inteligência Artificial. Rio de janeiro:

    LTC, 2013. • Artero, Almir Olivette. Inteligência Artificial: teoria e Prática. São Paulo: Editora Livraria da Física, 2009. @anapaulamendes /ananoterminal @ananoterminal