Inteligncia Artificial*INTELIGNCIA ARTIFICIALRui Carlos Botelho Almeida da SilvaALGORITMOS GENTICOS

Aula 05

Inteligncia Artificial

Inteligncia Artificial*Contexto da aulaObjetivos:apresentar conceitos e tipos .

Inteligncia Artificial

Inteligncia Artificial*Roteiro da aulaHistricoConceitosTipos

Inteligncia Artificial

Inteligncia Artificial*Consideraes IniciaisTeoria da evoluo das espciesEvoluo de gerao a gerao de acordo com princpios de seleo natural e sobrevivncia dos mais fortes (Darwin -1859).

A combinao de boas caractersticas de ancestrais pode produzir superindivduos mais adaptados que seus ancestrais.

Logo, as espcies evoluem e logram caractersticas mais adaptadas ao ambiente que vivem.

1865 - Gregor Mendel (Pai da gentica) apresenta experimentos do cruzamento gentico de ervilhas.

Inteligncia Artificial

Inteligncia Artificial*Consideraes Iniciais (continuao)

A Teoria da Evoluo comeou a partir da conceituao integrada da seleo natural com a Gentica.

Os Algoritmos Genticos (AGs) usam uma analogia direta ao comportamento natural.

Desenvolvido por John Holland (1975) e seus alunos (Universidade de Michigan).

Popularizado por David Goldberg (1989).

Inteligncia Artificial

Inteligncia Artificial*ConceitosPara que servem?Busca e OtimizaoAmplamente utilizados, com sucesso, em problemas de difcil manipulao pelas tcnicas tradicionaisEficincia X Flexibilidade

VantagensPossibilidade de escapar de mximos (ou mnimos) locais;Maior robustez que os mtodos mais tradicionais.

Inteligncia Artificial

Inteligncia Artificial*Conceitos (continuao)AplicaesOtimizao de funes numricas.Otimizao de exploses combinatrias.TSP(Problema do Caixeiro Viajante (determinstico e no determinstico)MochilaSchedullingAprendizado de Mquina

Inteligncia Artificial

Inteligncia Artificial*Conceitos (continuao)AG manipula uma populao de indivduos.

Individuos so possveis solues do problema.

Os indivduos so combinados (crossover) uns com os outros, produzindo filhos que podem sofrer ou no mutao.

As populaes evoluem atravs de sucessivas geraes at encontrar a soluo tima.

Uma funo de aptido(fitness) testa os indivduos como a natureza testa a todos nesta vida

Utilizam uma codificao do conjunto de parmetros (indivduos) e no com os prprios parmetros (estados);

Inteligncia Artificial

Inteligncia Artificial*Conceitos (continuao)Vasculham vrias regies do espao de busca de cada vez;

Utilizam informaes diretas de qualidade, em contraste com as derivadas utilizadas nos mtodos tradicionais de otimizao;

Utilizam regras de transio probabilsticas e no regras determinsticas.

Algoritmos Genticos podem ser considerados como mtodos que trabalham comBuscas Paralelas Randmicas Direcionadas

Inteligncia Artificial

Inteligncia Artificial*FuncionamentoAG manipula uma populao de indivduos.

Individuos so possveis solues do problema.

Os indivduos so combinados (crossover) uns com os outros, produzindo filhos que podem sofrer ou no mutao.

As populaes evoluem atravs de sucessivas geraes at encontrar a soluo tima.

Uma funo de aptido (fitness) testa os indivduos como a natureza testa a todos nesta vida.

Inteligncia Artificial

Inteligncia Artificial*Funcionamento (continuao)1. Gerar a populao inicial.2. Avaliar cada indivduo da populao. 3. Enquanto critrio de parada no for satisfeito faa 3.1 Selecionar os indivduos mais aptos. 3.2 Criar novos indivduos aplicando os operadores crossover e mutao. 3.3 Armazenar os novos indivduos em uma nova populao. 3.4 Avaliar cada cromossomo da nova populao.

Inteligncia Artificial

Inteligncia Artificial*Funcionamento (continuao)CromossomosNa NaturezaTodo organismo vivo consiste de clulas. Em cada clula, existe o mesmo conjunto de cromossomosCromossomos consistem de genes seqncias de DNA que servem para determinar as caractersticas de um indivduo

Algoritmo GenticoEstrutura de dados que representa uma possvel soluo para o problema.Os parmetros do problema de otimizao so mapeados em uma estrura de dados adequada, cada qual com suas vantagens e seus problemas.

Inteligncia Artificial

Inteligncia Artificial*Funcionamento (continuao)Exemplos: Vetores de inteiros, reais, (2.345, 4.3454, 5.1, 3.4)Cadeias de bits, (111011011) string.rvore (Programao gentica cdigo Lisp) Mquinas de estado finito.

Inteligncia Artificial

Inteligncia Artificial*Funcionamento (continuao)ReproduoNa NaturezaDurante o processo de reproduo ocorre-se a recombinao (ou crossover (cruzamento)). Genes dos pais se combinam para formar novos cromossomos.Os descendentes criados podem sofrer mutaes, ou seja, os elementos do DNA podem ser trocadosA adaptao de um organismo pode ser medida pelo sucesso do mesmo em sua vida

Inteligncia Artificial

Inteligncia Artificial*Funcionamento (continuao)ReproduoAlgoritmos GenticosPossibilita encontros ntimos na mating poolImitao da seleo natural.Os melhores indivduos (maior aptido) so selecionados para gerar filhos atravs de crossover e mutao.Dirige o AG para as melhores regies do espao de busca.Tipos mais comuns de seleoProporcional a aptido.Torneio: escolhe-se 2 indivduos aleatoriamente, o melhor selecionado.

Inteligncia Artificial

Inteligncia Artificial*Funcionamento (continuao)Funo de aptidoAptidoNota associada ao indviduo que avalia quo boa a soluo por ele representada.A Funo de aptido pode ser facilmente encontrada em alguns casos, mas pode ser de difcil definio quando existem fatores de restries e penalidades internos, ou uma combinao de diferentes objetivos na mesma funo.

Inteligncia Artificial

Inteligncia Artificial*Funcionamento (continuao)Operadores de Crossover e de MutaoCombinam pais selecionados para produo de filhos.Principais mecanismos de busca do AG.Permite explorar reas desconhecidas do espao de busca.

Inteligncia Artificial

Inteligncia Artificial*Funcionamento (continuao)CrossoverTambm chamado de reproduo ou crossoverCombina as informaes genticas de dois indivduos (pais) para gerar novos indivduos (filhos)Verses mais comuns criam sempre dois filhos para cada operaoOperador gentico principalResponsvel por gerar novos indivduos diferentes (sejam melhores ou piores) a partir de indivduos j promissoresAplicado a cada par de indivduos com alta probabilidade (normalmente entre 0,6 e 0,99)

Inteligncia Artificial

Inteligncia Artificial*Funcionamento (continuao)Alguns Tipos de Crossover1 pontoMultipontosUniforme

Inteligncia Artificial

Inteligncia Artificial*Funcionamento (continuao)Crossover de 1 ponto

Inteligncia Artificial

Inteligncia Artificial*Funcionamento (continuao)Crossover Multiponto

Inteligncia Artificial

Inteligncia Artificial*Funcionamento (continuao)Crossover Uniforme

Inteligncia Artificial

Inteligncia Artificial*Funcionamento (continuao)MutaoOperador randmico de manipulaoIntroduz e mantm a variedade gentica da populaoGarante a possibilidade de se alcanar qualquer ponto do espao de buscaContorna mnimos locais um operador gentico secundrioUso exagerado reduz a evoluo a uma busca totalmente aleatriaLogo um indivduo sofre mutaes com probabilidade baixa (normalmente entre 0,001 e 0,1)

Inteligncia Artificial

Inteligncia Artificial*Funcionamento (continuao)Parmetros GenticosTamanho da populaoTaxa de cruzamentoTaxa de mutaoIntervalo de geraoCritrio de paradaNmero de geraes.Encontrou a soluo (quando esta conhecida).Perda de diversidade.Convergncia ( nas ltimas k geraes no houve melhora da na aptido) => Mdia ou Mxima

Inteligncia Artificial

Inteligncia Artificial*ExerccioCdigo em JavaDuas equipes1 Vai implementar o mesmo cdigo alterando o tipo de crossover de 1 para multiponto (pelo menos 2)2 Vai implementar o mesmo cdigo alterando a funo de seleo1 semana

Inteligncia Artificial

*************************