Computação Evolutiva : Um Novo Paradigma Para a Resolução de Problemas Complexos Aurora Pozo Pós-graduação em Informática, Pós-graduação em Métodos Numéricos para Engenharia. Grupo EsCeL, Motivação Algoritmos Genéticos e Evolutivos são eficientes métodos de otimização e planejamento inspirados na natureza baseados nos princípios da evolução natural e genética. Devido a sua eficiência e simples princípios, estes métodos são usados em uma variedade de problemas de otimização e aprendizado de maquina. Ambientação Teoria de Computação Evolucionária Modelo Biológico Natureza Modelo Computacional Teoria de Darwin Exemplos de Aplicações Reais • • • • • Projeto de Antenas Projeto de Drogas Classificação Química Circuitos Elétricos Escalonamento de Fabricas (Volvo, Deere, outras) • Projeto de Turbina • Projeto de Carros “Crashworthy” • Projeto de Redes • Projeto de Sistemas de Controle • Parâmetros de Produção • Projeto de Satélite • Stock/commodity/ analises/ tendências • Ajuste de Celulares • Data Mining Sumário • Computação Evolutiva – Conceitos básicos • Algoritmos Genéticos • Projetos Computação Evolucionária • Área da Inteligência Artificial que engloba um conjunto de métodos computacionais inspirados na Teoria da Evolução das Espécies. • auto-organização e o comportamento adaptativo Ramos • Estratégias Evolucionárias: – ênfase na auto-adaptação. O papel da recombinação é aceito, mas como operador secundário. • Programação Evolutiva: – Previsão do comportamento de máquinas de estado finitas. • Algoritmos Genéticos: – Indivíduos contém um genótipo formado por cromossomos • Programação Genética – Evolução de programas • Estimativa de Distribuição – AG competentes Historia • Estratégias Evolutivas: • Desenvolvida por Rechenberg, Schwefel, etc. em 1960. • Foco: Otimização de parâmetros de valores reais • Individuo: vetor de parâmetros de valores reais • Reprodução: Mutação Gaussiana dos parâmetros • M pais, K>>M filhos Historia • Programação Evolutiva: • Desenvolvida por Fogel in 1960 • Objetivo: evoluir comportamento inteligente • Indivíduos: Maquina de estado finita • Filhos via mutação das MEF • M pais, M filhos Historia • • • • • Algoritmos Genéticos: Desenvolvidos por Holland em 1960s Objetivo: robustos, sistemas adaptativos Utiliza uma codificação “genética” de pontos Reprodução via mutação e recombinação do código genético. • M pais, M filhos Historia • Programação Genética • Desenvolvidos por Koza em 1990s • Objetivo: Evolução de programas • Reprodução via recombinação do código genético. • M pais, M filhos Historia • • • • Alg. de Estimativa de Distribuição Inicia com os trabalhos de Baluja 1994 AG competentes ??? Modelam os relacionamentos entre as variáveis do indivíduos. • Evoluem o modelo – Alguns utilizam redes bayesianas para isto Estado Atual • Grande variedade de Algoritmos Evolutivos • Grande variedade de aplicações – Otimização, busca, aprendizado, adaptação • Analise – teórico – experimental Características Comuns • Uso de um processo de evolução pseudoDarwinian para solucionar problemas difíceis. • Computação Evolutiva Evolução Natural • Embora tenham origens bastante diversas, todas essa abordagens têm em comum o modelo conceitual inicial Características Comuns • Usam um processo de evolução baseado em Darwin para resolver problemas computacionais de IA • Inspirados na Teoria da Evolução: os indivíduos mais adaptados sobrevivem Elementos Chaves de Algoritmos Evolucionários • Uma população de indivíduos • A noção de fitness • Um ciclo de nascimento e morte baseados na fitness • A noção de herança Visão Geral do Algoritmo Evolucionário população de pais seleção recombinação população de filhos solução Visão Geral do Algoritmo Evolucionário 1. Gerar uma população inicial aleatoriamente 2. Fazer até um critério de parada: – selecionar indivíduos para pais (fitness) – produzir filhos – selecionar indivíduos para morrer (fitness) 3. Retornar um resultado Algorithmos Geneticos • • • • Holland 1960 São algoritmos de busca Objetivo: robusto, sistema adaptativo Combinam: Sobrevivência do mais ajustado com um estruturado, aleatório intercâmbio de informações AG • Apesar de aleatórios, AG não funcionam unicamente com este conceito. • Eles exploram informação histórica para experimentar novos pontos de busca. início população inicial Algoritmo seleção (fitness) pais selecionados operadores genéticos cruz repr mut filhos gerados não fim solução sim satisfeito c/ a solução? nova pop completa? sim nova população não Terminologia Biológica • Em AG são utilizados termos biológicos como analogia com a biologia. • Cromossomo: codificação de uma possível solução – individuo • Genes: Codifica uma característica particular • Genótipo x Fenótipo Indivíduos • Material genético • Conjunto de atributos da solução • Cada atributo uma seqüência de bits e o individuo como a concatenação das seqüências de bits • Codificação binária, códigos População • Conjunto de indivíduos que estão sendo cogitados como solução – Relacionado a dimensão do espaço de busca. – Populações pequenas têm grandes chances de perder a diversidade necessária (exploração de todo o espaço de soluções) – Populações grandes perderá grande parte de sua eficiência pela demora em avaliar a função de fitness Reprodução • Reprodução sexual, genes são trocados entre dois pais – crossover • Os filhos são sujeitos a modificações, na qual bits elementares são mudados mutação Função de fitness • Mede a adaptação do indivíduo ou quão boa é a solução dada por este indivíduo. • Representativa do problema: diferencie uma solução boa de uma má. • Heurística de busca no espaço de estado • Cuidados com o custo computacional. Requisitos para usar AG Representações das possíveis soluções do problema no formato de um código genético; População inicial que contenha diversidade suficiente para permitir ao algoritmo combinar características e produzir novas soluções; Existência de um método para medir a qualidade de uma solução potencial; Um procedimento de combinação de soluções para gerar novos indivíduos na população; Um critério de escolha das soluções que permanecerão na população ou que serão retirados desta; Um procedimento para introduzir periodicamente alterações em algumas soluções da população. Desse modo mantém-se a diversidade da população e a possibilidade de se produzir soluções inovadoras para serem avaliadas pelo critério de seleção dos mais aptos. Seleção • O operador escolhe quais indivíduos participarão na criação da próxima geração Exemplo Indivíduos Fitness % Fitness 10101010110101010111 12 23,08 00001001010101110010 8 15,38 00001100001011011101 9 17,31 00000110010010000010 6 11,54 11100011100010011111 12 23,08 00010101001000010000 5 9,62 Total 52 100,00 Roleta 10% 23% 23% 15% 12% 17% Reprodução • Preserva características úteis • Introduz variedade e novidades • Estratégias – Parentes únicos: clonar + mutação – Parentes múltiplos: recombinação + mutação Métodos de Recombinação • Cruzamento: cria novos indivíduos misturando características de dois indivíduos pais (crossover) • Copia de segmentos entre os pais • Crossovers multi-ponto, dois pontos, um ponto, uniforme e inversão Cruzamento • Pai 1: 10101010110101010111 • Pai 2: 00001001010101110010 • Cruzamento em um ponto – 10101010110101110010, 00001001010101010111 • Cruzamento uniforme: os filhos são formados a partir dos bits dos pais (sorteado) Mutação • Esta operação inverte aleatoriamente alguma característica do indivíduo • Cria novas características que não existiam • Mantém diversidade na população Balance Explotação-Exploração • Pressão de seleção: explotação – Reduz o espaço de busca • Reprodução: exploração – Expande o espaço de busca • Balance – Seleção forte + taxas de mutação altas – Seleção fraca + taxas de mutação baixas Quando AG é bom ? • Funções multímodas • Funções discretas ou continuas • Funções altamente dimensionais, incluindo combinatórias • Dependência não linear dos parâmetros • Usada freqüentemente para obter solução a problemas NP completos • Não usar quando outro método como hillclimbing, etc., funciona bem Técnicas Avançadas em AGs • AGs são apropriados para problemas complexos, mas algumas melhorias devem ser feitas