Aula_06

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
*