Baixe o app para aproveitar ainda mais
Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original
INTELIGÊNCIA ARTIFICIAL Aula 6 – Sistemas evolutivos e algoritmos genéticos Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Conteúdo programático desta aula Conceito de otimização e as soluções clássicas Inspiração dos Algoritmos Genéticos Ciclos de evolução de um algoritmo genético Operadores genéticos Parametrização dos operadores genéticos Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Conceituando um problema de otimização Encontrar o “ótimo” pode ser encontrar o máximo ou o mínimo Ex: na função f(x)= -x2+3, podemos querer achar o “x” que maximiza f(x) Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Máximos e mínimos podem ser equivalentes Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Conceituando um problema de otimização Encontrar o “ótimo” pode ser encontrar o máximo ou o mínimo Ex: na função f(x)= -x2+3, podemos querer achar o “x” que maximiza f(x) Para uma função de muitos parâmetros, temos f( x1, x2, x3,...xn) Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Conceituando um problema de otimização Encontrar o “ótimo” pode ser encontrar o máximo ou o mínimo Ex: na função f(x)= -x2+3, podemos querer achar o “x” que maximiza f(x) Para uma função de muitos parâmetros, temos f( x1, x2, x3,...xn) Função a otimizar: Função Objetivo Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Conceituando um problema de otimização Encontrar o “ótimo” pode ser encontrar o máximo ou o mínimo Ex: na função f(x)= -x2+3, podemos querer achar o “x” que maximiza f(x) Para uma função de muitos parâmetros, temos f( x1, x2, x3,...xn) Função a otimizar: Função Objetivo Intervalo de busca da solução: Espaço de Busca Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Conceituando um problema de otimização Encontrar o “ótimo” pode ser encontrar o máximo ou o mínimo Ex: na função f(x)= -x2+3, podemos querer achar o “x” que maximiza f(x) Para uma função de muitos parâmetros, temos f( x1, x2, x3,...xn) Função a otimizar: Função Objetivo Intervalo de busca da solução: Espaço de Busca Espaço de busca pode ter restrições. Ex: Função objetivo: f(x) = x2 + y2 + 4 Restrições: 2x - 3y < 5 e x + y = 7. Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Conceituando um problema de otimização Encontrar o “ótimo” pode ser encontrar o máximo ou o mínimo Ex: na função f(x)= -x2+3, podemos querer achar o “x” que maximiza f(x) Para uma função de muitos parâmetros, temos f( x1, x2, x3,...xn) Função a otimizar: Função Objetivo Intervalo de busca da solução: Espaço de Busca Espaço de busca pode ter restrições. Ex: Função objetivo: f(x) = x2 + y2 + 4 Restrições: 2x - 3y < 5 e x + y = 7. Otimização combinatória: busca-se uma sequência ótima de valores Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Características que a função a otimizar pode apresentar Mínimos locais Estabilidade da função Ex: função mono parâmetro f(x) = x sen (3 x) Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Características que a função a otimizar pode apresentar Funções multi-modais Ex: função mono parâmetro f(x) = sen (x/2) + cos (2x)/1,5 Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Soluções para problemas de otimização Existem vários modelos matemáticos de otimização: Métodos analíticos (ex: Newton-Raphson): usam cálculo diferencial e dependem das funções serem conhecidas, contínuas e diferenciáveis Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Soluções para problemas de otimização Existem vários modelos matemáticos de otimização: Métodos analíticos (ex: Newton-Raphson): usam cálculo diferencial e dependem das funções serem conhecidas, contínuas e diferenciáveis Métodos de subida de encosta (ex: gradiente descendente, recozimento simulado, busca tabu): são métodos de buscas locais, em geral rápidos, mas sensíveis a mínimos locais Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Soluções para problemas de otimização Existem vários modelos matemáticos de otimização: Métodos analíticos (ex: Newton-Raphson): usam cálculo diferencial e dependem das funções serem conhecidas, contínuas e diferenciáveis Métodos de subida de encosta (ex: gradiente descendente, recozimento simulado, busca tabu): são métodos de buscas locais, em geral rápidos, mas sensíveis a mínimos locais Métodos heurísticos (ex: algoritmos genéticos, colônia de formigas e enxames de abelhas): são métodos que exploram de forma mais uniforme o espaço de busca, são robustos quanto a mínimos locais, mas em geral são mais lentos . Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Algoritmos Genéticos: características Possibilitam exploração simultânea (paralelizável) do espaço de busca; Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Algoritmos Genéticos: características Possibilitam exploração simultânea (paralelizável) do espaço de busca; Funcionam em espaços de busca contínuos ou discretos; Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Algoritmos Genéticos: características Possibilitam exploração simultânea (paralelizável) do espaço de busca; Funcionam em espaços de busca contínuos ou discretos; Não são sensíveis à existência de mínimos locais; Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Algoritmos Genéticos: características Possibilitam exploração simultânea (paralelizável) do espaço de busca; Funcionam em espaços de busca contínuos ou discretos; Não são sensíveis à existência de mínimos locais; Capazes de descobrir várias soluções (útil para funções multi-modais); Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Algoritmos Genéticos: características Possibilitam exploração simultânea (paralelizável) do espaço de busca; Funcionam em espaços de busca contínuos ou discretos; Não são sensíveis à existência de mínimos locais; Capazes de descobrir várias soluções (útil para funções multi-modais); Não impõem condições especiais (continuidade, existência de derivada); Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Algoritmos Genéticos: características Possibilitam exploração simultânea (paralelizável) do espaço de busca; Funcionam em espaços de busca contínuos ou discretos; Não são sensíveis à existência de mínimos locais; Capazes de descobrir várias soluções (útil para funções multi-modais); Não impõem condições especiais (continuidade, existência de derivada); Funcionam bem em espaços de busca com muitas dimensões; Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Algoritmos Genéticos: características Possibilitam exploração simultânea (paralelizável) do espaço de busca; Funcionam em espaços de busca contínuos ou discretos; Não são sensíveis à existência de mínimos locais; Capazes de descobrir várias soluções (útil para funções multi-modais); Não impõem condições especiais (continuidade, existência de derivada); Funcionam bem em espaços de busca com muitas dimensões; Permitirem modelar restrições e otimizar simultaneamente múltiplas funções, mesmo que conflitantes; e, Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Algoritmos Genéticos: características Possibilitam exploração simultânea (paralelizável) do espaço de busca; Funcionam em espaços de busca contínuos ou discretos; Não são sensíveis à existência de mínimos locais; Capazes de descobrir várias soluções (útil para funções multi-modais); Não impõem condições especiais (continuidade, existência de derivada); Funcionam bem em espaços de busca com muitas dimensões; Permitirem modelar restrições e otimizar simultaneamente múltiplas funções, mesmo que conflitantes; e, São fáceis de implantar computacionalmente, não dependendo de compreensão do problema a ser otimizado e de sua modelagem. Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Algoritmos Genéticos: inspiração original Modelo computacional proposto por John Holland; Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Algoritmos Genéticos: inspiração original Modelo computacional proposto por John Holland; Inspirado na biologia evolutiva (A Origem das Espécies - Charles Darvin); Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Algoritmos Genéticos: inspiração original Modelo computacional proposto por John Holland; Inspirado na biologia evolutiva (A Origem das Espécies - Charles Darvin); Ideia principal: seres mais adaptados têm mais chances de sobrevivência Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Algoritmos Genéticos: inspiração original Modelo computacional proposto por John Holland; Inspirado na biologia evolutiva (A Origem das Espécies - Charles Darvin); Ideia principal: seres mais adaptados têm mais chances de sobrevivência Capacidade de adaptação determina a sobrevivência Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Algoritmos Genéticos: inspiração original Modelo computacional proposto por John Holland; Inspirado na biologia evolutiva (A Origem das Espécies - Charles Darvin); Ideia principal: seres mais adaptados têm mais chances de sobrevivência Capacidade de adaptação determina a sobrevivência Evolução das espécies se dá com mecanismos como: Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Algoritmos Genéticos: inspiração original Modelo computacional proposto por John Holland; Inspirado na biologia evolutiva (A Origem das Espécies - Charles Darvin); Ideia principal: seres mais adaptados têm mais chances de sobrevivência Capacidade de adaptação determina a sobrevivência Evolução das espécies se dá com mecanismos como: Seleção dos mais aptos (seleção natural) Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Algoritmos Genéticos: inspiração original Modelo computacional proposto por John Holland; Inspirado na biologia evolutiva (A Origem das Espécies - Charles Darvin); Ideia principal: seres mais adaptados têm mais chances de sobrevivência Capacidade de adaptação determina a sobrevivência Evolução das espécies se dá com mecanismos como: Seleção dos mais aptos (seleção natural) Recombinação genética (reprodução sexuada) Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Algoritmos Genéticos: inspiração original Modelo computacional proposto por John Holland; Inspirado na biologia evolutiva (A Origem das Espécies - Charles Darvin); Ideia principal: seres mais adaptados têm mais chances de sobrevivência Capacidade de adaptação determina a sobrevivência Evolução das espécies se dá com mecanismos como: Seleção dos mais aptos (seleção natural) Recombinação genética (reprodução sexuada) Mutações aleatórias (mutação genética) Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Algoritmos Genéticos: o modelo computacional Modela as soluções do problema como indivíduos de uma espécie; Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Algoritmos Genéticos: o modelo computacional Modela as soluções do problema como indivíduos de uma espécie; Lida com um conjunto de soluções chamado de população; Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Algoritmos Genéticos: o modelo computacional Modela as soluções do problema como indivíduos de uma espécie; Lida com um conjunto de soluções chamado de população; Modela cada solução como uma cadeia de bits que representa o genoma; Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Algoritmos Genéticos: o modelo computacional Modela as soluções do problema como indivíduos de uma espécie; Lida com um conjunto de soluções chamado de população; Modela cada solução como uma cadeia de bits que representa o genoma; Associa a cada solução uma medida de qualidade que reflete a capacidade do indivíduo em relação aos demais indivíduos da população; Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Algoritmos Genéticos: o modelo computacional Modela as soluções do problema como indivíduos de uma espécie; Lida com um conjunto de soluções chamado de população; Modela cada solução como uma cadeia de bits que representa o genoma; Associa a cada solução uma medida de qualidade que reflete a capacidade do indivíduo em relação aos demais indivíduos da população; A evolução se dá pela criação de sucessivas gerações de indivíduos onde novos indivíduos são criados aplicando os mecanismos genéticos de seleção natural, reprodução por combinação e mutação aleatória. Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Algoritmos Genéticos: o modelo computacional Modela as soluções do problema como indivíduos de uma espécie; Lida com um conjunto de soluções chamado de população; Modela cada solução como uma cadeia de bits que representa o genoma; Associa a cada solução uma medida de qualidade que reflete a capacidade do indivíduo em relação aos demais indivíduos da população; A evolução se dá pela criação de sucessivas gerações de indivíduos onde novos indivíduos são criados aplicando os mecanismos genéticos de seleção natural, reprodução por combinação e mutação aleatória. A evolução da população favorece o aparecimento de indivíduos mais adaptados, ou seja, de soluções otimizadas para o problema original. Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Modelo computacional: como começar Inicialmente é necessário criar uma representação para as soluções, chamado de cromossomo do indivíduo: É uma cadeia de bits que representam os parâmetros da função Pode conter valores discretos ou contínuos Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Modelo computacional: como começar Inicialmente é necessário criar uma representação para as soluções, chamado de cromossomo do indivíduo: É uma cadeia de bits que representam os parâmetros da função Pode conter valores discretos ou contínuos É necessário estabelecer uma função de avaliação da aptidão de cada indivíduo que reflita a qualidade de cada solução/indivíduo Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Modelo computacional: como começar Inicialmente é necessário criar uma representação para as soluções, chamado de cromossomo do indivíduo: É uma cadeia de bits que representam os parâmetros da função Pode conter valores discretos ou contínuos É necessário estabelecer uma função de avaliação da aptidão de cada indivíduo que reflita a qualidade de cada solução/indivíduo Estabelecer formas de aplicar os operadores genéticos de cruzamento e mutação para criação dos novos indivíduos Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Modelo computacional: como começar Inicialmente é necessário criar uma representação para as soluções, chamado de cromossomo do indivíduo: É uma cadeia de bits que representam os parâmetros da função Pode conter valores discretos ou contínuos É necessário estabelecer uma função de avaliação da aptidão de cada indivíduo que reflita a qualidade de cada solução/indivíduo Estabelecer formas de aplicar os operadores genéticos de cruzamento e mutação para criação dos novos indivíduos Estabelecer parâmetros de intensidade para aplicação dos operadores genéticos e critérios de parada para encerramento da evolução. Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL modelo computacional: ciclo evolutivo Criar aleatoriamente uma população inicial Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL modelo computacional: ciclo evolutivo Criar aleatoriamente uma população inicial Enquanto o critério de parada não for satisfeito: Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL modelo computacional: ciclo evolutivo Criar aleatoriamente uma população inicial Enquanto o critério de parada não for satisfeito: Associar grau de aptidão a cada indivíduo da população Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL modelo computacional: ciclo evolutivo Criar aleatoriamente uma população inicial Enquanto o critério de parada não for satisfeito: Associar grau de aptidão a cada indivíduo da população Criar uma nova população baseada no grau de aptidão: Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL modelo computacional: ciclo evolutivo Criar aleatoriamente uma população inicial Enquanto o critério de parada não for satisfeito: Associar grau de aptidão a cada indivíduo da população Criar uma nova população baseada no grau de aptidão: Inserir cópia de indivíduo muito apto na população do próximo ciclo Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL modelo computacional: ciclo evolutivo Criar aleatoriamente uma população inicial Enquanto o critério de parada não for satisfeito: Associar grau de aptidão a cada indivíduo da população Criar uma nova população baseada no grau de aptidão: Inserir cópia de indivíduo muito apto na população do próximo ciclo Recombinar dois indivíduos por cruzamento genético, formando dois novos indivíduos para o próximo ciclo. Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL modelo computacional: ciclo evolutivo Criar aleatoriamente uma população inicial Enquanto o critério de parada não for satisfeito: Associar grau de aptidão a cada indivíduo da população Criar uma nova população baseada no grau de aptidão: Inserir cópia de indivíduo muito apto na população do próximo ciclo Recombinar dois indivíduos por cruzamento genético, formando dois novos indivíduos para o próximo ciclo. Alterar a representação de um indivíduo em uma posição aleatória, gerando uma mutação genética desse indivíduo. Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL modelo computacional: ciclo evolutivo Criar aleatoriamente uma população inicial Enquanto o critério de parada não for satisfeito: Associar grau de aptidão a cada indivíduo da população Criar uma nova população baseada no grau de aptidão: Inserir cópia de indivíduo muito apto na população do próximo ciclo Recombinar dois indivíduos por cruzamento genético, formando dois novos indivíduos para o próximo ciclo. Alterar a representação de um indivíduo em uma posição aleatória, gerando uma mutação genética desse indivíduo. Indivíduo com maior aptidão é a melhor solução nesta geração Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL modelo computacional: ciclo evolutivo Criar aleatoriamente uma população inicial Enquanto o critério de parada não for satisfeito: Associar grau de aptidão a cada indivíduo da população Criar uma nova população baseada no grau de aptidão: Inserir cópia de indivíduo muito apto na população do próximo ciclo Recombinar dois indivíduos por cruzamento genético, formando dois novos indivíduos para o próximo ciclo. Alterar a representação de um indivíduo em uma posição aleatória, gerando uma mutação genética desse indivíduo. Indivíduo com maior aptidão é a melhor solução nesta geração Critérios de parada possíveis: Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL modelo computacional: ciclo evolutivo Criar aleatoriamente uma população inicial Enquanto o critério de parada não for satisfeito: Associar grau de aptidão a cada indivíduo da população Criar uma nova população baseada no grau de aptidão: Inserir cópia de indivíduo muito apto na população do próximo ciclo Recombinar dois indivíduos por cruzamento genético, formando dois novos indivíduos para o próximo ciclo. Alterar a representação de um indivíduo em uma posição aleatória, gerando uma mutação genética desse indivíduo. Indivíduo com maior aptidão é a melhor solução nesta geração Critérios de parada possíveis: Melhor indivíduo atual ser satisfatório Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL modelo computacional: ciclo evolutivo Criar aleatoriamente uma população inicial Enquanto o critério de parada não for satisfeito: Associar grau de aptidão a cada indivíduo da população Criar uma nova população baseada no grau de aptidão: Inserir cópia de indivíduo muito apto na população do próximo ciclo Recombinar dois indivíduos por cruzamento genético, formando dois novos indivíduos para o próximo ciclo. Alterar a representação de um indivíduo em uma posição aleatória, gerando uma mutação genética desse indivíduo. Indivíduo com maior aptidão é a melhor solução nesta geração Critérios de parada possíveis: Melhor indivíduo atual ser satisfatório Número máximo de gerações ter sido atingido Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL modelo computacional: ciclo evolutivo Criar aleatoriamente uma população inicial Enquanto o critério de parada não for satisfeito: Associar grau de aptidão a cada indivíduo da população Criar uma nova população baseada no grau de aptidão: Inserir cópia de indivíduo muito apto na população do próximo ciclo Recombinar dois indivíduos por cruzamento genético, formando dois novos indivíduos para o próximo ciclo. Alterar a representação de um indivíduo em uma posição aleatória, gerando uma mutação genética desse indivíduo. Indivíduo com maior aptidão é a melhor solução nesta geração Critérios de parada possíveis: Melhor indivíduo atual ser satisfatório Número máximo de gerações ter sido atingido Tempo limite de processamento ter sido atingido Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL modelo computacional: ciclo evolutivo Criar aleatoriamente uma população inicial Enquanto o critério de parada não for satisfeito: Associar grau de aptidão a cada indivíduo da população Criar uma nova população baseada no grau de aptidão: Inserir cópia de indivíduo muito apto na população do próximo ciclo Recombinar dois indivíduos por cruzamento genético, formando dois novos indivíduos para o próximo ciclo. Alterar a representação de um indivíduo em uma posição aleatória, gerando uma mutação genética desse indivíduo. Indivíduo com maior aptidão é a melhor solução nesta geração Critérios de parada possíveis: Melhor indivíduo atual ser satisfatório Número máximo de gerações ter sido atingido Tempo limite de processamento ter sido atingido Não haver melhora da população após várias gerações Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL modelo computacional: resumo do ciclo evolutivo Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Detalhando os operadores: seleção Ideia central: privilegiar os mais aptos sem zerar chances dos menos aptos Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Detalhando os operadores: seleção Ideia central: privilegiar os mais aptos sem zerar chances dos menos aptos Métodos mais usados: torneio e roleta Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Detalhando os operadores: seleção Ideia central: privilegiar os mais aptos sem zerar chances dos menos aptos Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Detalhando os operadores: seleção Ideia central: privilegiar os mais aptos sem zerar chances dos menos aptos Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Detalhando os operadores: seleção Ideia central: privilegiar os mais aptos sem zerar chances dos menos aptos Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Detalhando os operadores: seleção Ideia central: privilegiar os mais aptos sem zerar chances dos menos aptos Métodos mais usados: torneio e roleta Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Detalhando os operadores: seleção Ideia central: privilegiar os mais aptos sem zerar chances dos menos aptos Métodos mais usados: torneio e roleta Torneio: forma-se grupos de indivíduos e escolhe-se o mais apto do grupo Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Detalhando os operadores: seleção Ideia central: privilegiar os mais aptos sem zerar chances dos menos aptos Métodos mais usados: torneio e roleta Torneio: forma-se grupos de indivíduos e escolhe-se o mais apto do grupo Roleta (amostragem estocástica): indivíduos são selecionados por amostragem em uma roleta em que cada indivíduo ocupa uma fatia proporcional à sua aptidão relativa na população Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Detalhando os operadores: seleção Ideia central: privilegiar os mais aptos sem zerar chances dos menos aptos Métodos mais usados: torneio e roleta Torneio: forma-se grupos de indivíduos e escolhe-se o mais apto do grupo Roleta (amostragem estocástica): indivíduos são selecionados por amostragem em uma roleta em que cada indivíduo ocupa uma fatia proporcional à sua aptidão relativa na população Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Detalhando os operadores: cruzamento (crossover) Ideia central: transmitir características genéticas aos descendentes Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Detalhando os operadores: cruzamento (crossover) Ideia central: transmitir características genéticas aos descendentes Métodos mais usados: cruzamento de um ponto, multi pontos e uniforme Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Detalhando os operadores: cruzamento (crossover) Ideia central: transmitir características genéticas aos descendentes Métodos mais usados: cruzamento de um ponto, multi pontos e uniforme Cruzamento de um ponto: um ponto é escolhido e o material genético dos pais é trocado para gerar os filhos Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Detalhando os operadores: cruzamento (crossover) Ideia central: transmitir características genéticas aos descendentes Métodos mais usados: cruzamento de um ponto, multi pontos e uniforme Cruzamento de um ponto: um ponto é escolhido e o material genético dos pais é trocado para gerar os filhos Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Detalhando os operadores: cruzamento (crossover) Ideia central: transmitir características genéticas aos descendentes Métodos mais usados: cruzamento de um ponto, multi pontos e uniforme Cruzamento de um ponto: um ponto é escolhido e o material genético dos pais é trocado para gerar os filhos Multi pontos: pontos distintos são escolhidos para troca do material Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Detalhando os operadores: cruzamento (crossover) Ideia central: transmitir características genéticas aos descendentes Métodos mais usados: cruzamento de um ponto, multi pontos e uniforme Cruzamento de um ponto: um ponto é escolhido e o material genético dos pais é trocado para gerar os filhos Multi pontos: pontos distintos são escolhidos para troca do material Uniforme: para cada gene é determinada uma probabilidade de troca Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Detalhando os operadores: mutação Ideia central: alterar aleatoriamente os indivíduos para manter a diversidade genética e explorar novas regiões no espaço de buscas Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Detalhando os operadores: mutação Ideia central: alterar aleatoriamente os indivíduos para manter a diversidade genética e explorar novas regiões no espaço de buscas Método mais usado: alteração aleatória de um gene do genoma, geralmente invertendo um bit do cromossomo de um dos indivíduos também aleatoriamente escolhido Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Detalhando os operadores: mutação Ideia central: alterar aleatoriamente os indivíduos para manter a diversidade genética e explorar novas regiões no espaço de buscas Método mais usado: alteração aleatória de um gene do genoma, geralmente invertendo um bit do cromossomo de um dos indivíduos também aleatoriamente escolhido Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Ajuste dos parâmetros genéticos Tamanho da população Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Ajuste dos parâmetros genéticos Tamanho da população Taxa de cruzamento Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Ajuste dos parâmetros genéticos Tamanho da população Taxa de cruzamento Taxa de mutação Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Ajuste dos parâmetros genéticos Tamanho da população Taxa de cruzamento Taxa de mutação Taxa de elitismo Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL A escolha da representação Um solução tem um conjunto de características ou parâmetros, representados por genes, que podem ser unidos para formar um cromossomo, que é o genótipo do indivíduo. Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL A escolha da representação Um solução tem um conjunto de características ou parâmetros, representados por genes, que podem ser unidos para formar um cromossomo, que é o genótipo do indivíduo. Ex: Valores binários para ausência/presença de características Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL A escolha da representação Um solução tem um conjunto de características ou parâmetros, representados por genes, que podem ser unidos para formar um cromossomo, que é o genótipo do indivíduo. Ex: Valores binários para ausência/presença de características Valores numéricos codificados como cadeias de bits Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL A escolha da representação Um solução tem um conjunto de características ou parâmetros, representados por genes, que podem ser unidos para formar um cromossomo, que é o genótipo do indivíduo. Ex: Valores binários para ausência/presença de características Valores numéricos codificados como cadeias de bits Problemas: genótipos inválidos devem ser corrigidos Alfabeto de representação deve ser o menor possível Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL A função de aptidão É o ponto central para o funcionamento da técnica Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL A função de aptidão É o ponto central para o funcionamento da técnica Geralmente é determinante no tempo global do algoritmo Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL A função de aptidão É o ponto central para o funcionamento da técnica Geralmente é determinante no tempo global do algoritmo Associa um valor escalar a cada indivíduo, refletindo a qualidade relativa do mesmo dentro da população Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL A função de aptidão É o ponto central para o funcionamento da técnica Geralmente é determinante no tempo global do algoritmo Associa um valor escalar a cada indivíduo, refletindo a qualidade relativa do mesmo dentro da população Se a função a ser otimizada é conhecida, a função de aptidão é a própria função a ser otimizada Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL A função de aptidão É o ponto central para o funcionamento da técnica Geralmente é determinante no tempo global do algoritmo Associa um valor escalar a cada indivíduo, refletindo a qualidade relativa do mesmo dentro da população Se a função a ser otimizada é conhecida, a função de aptidão é a própria função a ser otimizada Em outros casos é uma métrica que reflita a qualidade. Ex: o tamanho do caminho (caixeiro viajante), a quantidade de regiões adjacentes de mesma cor (colorir mapas), etc. Tema da Apresentação SISTEMAS EVOLUTIVOS E ALGORITMOS GENÉTICOS – AULA 6 INTELIGÊNCIA ARTIFICIAL Na próxima aula você: Entenderá quais problemas do mundo real são passíveis de resolução usando AG Modelará a representação cromossômica de distintos problemas do mundo real Aplicará os operadores genéticos na solução de problemas de otimização Compreenderá o funcionamento básico de outros modelos evolucionários bio-inspirados Tema da Apresentação *
Compartilhar