Algorítimos Genéticos

Algoritmos GenéticosUma abordagem didática

Marcelo Goulart SouzaInteligência Artificial - IA

Objetivos

• Introduzir o conteúdo de algoritmos genéticos, relacionando a computação com a biologia.

Justificativa

• Dar uma visão geral sobre algoritmos genéticos, através de definições conceituais, histórico e um exemplo implementado

Introdução

• Histórico:• Algoritmos genéticos (AG) foram inventados por John

Holland e desenvolvidos por ele, seus alunos e colegas. Isso resultou no livro de Holland "Adaption in Natural and Artificial Systems" publicado em 1975.

• Em 1992 John Koza usou algoritmos genéticos para desenvolver programas para realizar certas tarefas. Ele chamou seu método de "programação genética" (PG). Foram usados programas em LISP porque programas nessa linguagem podem ser expressos na forma de árvores, que são objetos utilizados pelos algoritmos genéticos.

Introdução

• O que é Genética?– parte da biologia que estuda a passagem das

características biológicas e físicas de geração para geração.

Principais Conceitos

• Cromossoma: Cadeias de DNA compostas por genes que codificam determinadas proteínas, sendo que cada um tem sua posição.

• Reprodução: a nível genético, é a recombinação entre cromossomas dos pais, sendo que podem ser suscetíveis a erros (Mutação)

• Adaptação: sucesso na sobrevivência

Principais Conceitos

• cromossomo (genótipo) - cadeia de bits que representa uma solução possível para o problema.

• gene - representação de cada parâmetro de acordo com o alfabeto utilizado (binário, inteiro ou real).

• população - conjunto de pontos (indivíduos) no Espaço de Busca

• geração - iteração completa do AG que gera uma nova população

• genótipo x fenótipo• mitose x meiose

Aplicações

• Síntese de circuitos analógicos• Programação Genética• Gerenciamento de redes• Ciências biológicas• Problemas de otimização complexos

Parâmetros Genéticos

• Tamanho da População• Taxa de Cruzamento• Taxa de Mutação• Intervalo de Geração

Descrição de um Problema de AG

• Inspirados na teoria da evolução de Darwin• Inicialização: Uma população de N indivíduos,

sendo que cada um pode representar a solução.

• Calculo de Aptidão: determinada por uma função objetivo que depende da especificação do projeto.

Descrição de um Problema de AG

• Seleção: indivíduos mais aptos da geração atual são selecionados e utilizadas para gerar uma nova população por cruzamento.

• Cada indivíduo possui uma frequência alélica, ou seja, quando maior a FA, maior a chance do indivíduo ser selecionado

• Método de seleção é chamado de mostragem universal estocástica.

Descrição de um Problema de AG

Figura 2: Roleta de Probabilidades

- Indivíduos de regiões de maior probabilidade terãoMais chances de serem escolhidos- Como consequência seleção de indivíduos pode conter várias cópias

Descrição de um Problema de AG

• Cruzamento (cross-over): indivíduos selecionados na etapa anterior são cruzados da seguinte forma: a lista de indivíduos selecionados é embaralhada aleatoriamente criando-se, desta forma, uma segunda lista.

• A permutação é feita com a parte inicial de L1 com a parte final de L2, as partes são divididas ao acaso.

Descrição de um Problema de AG

Figura 3: Cross-Over

Descrição de um Problema de AG

• Mutação: A operação de mutação é utilizada para garantir uma maior varredura do espaço de estados e evitar que o algoritmo genético convirja muito cedo.

• A mutação é efetuada alterando-se o valor de um gene de um indivíduo sorteado aleatoriamente com uma determinada probabilidade, vários indivíduos da nova população podem ter um de seus genes alterado aleatoriamente.

Operações BásicasFigura 4. Fluxograma de um AG

Esboço Básico do Algoritmo Genético

• Procedimento AG• {

– t = 0;– inicia_população (P, t)– avaliação (P, t);– repita até (t = d)– {

• t = t +1;• seleção_dos_pais (P,t);• recombinação (P, t);• mutação (P, t);• avaliação (P, t);• sobrevivem (P, t)

– }• }• onde:

– t - tempo atual;– d - tempo determinado para finalizar o algoritmo;– P - população

Implementação

• Arquivo ag.c• Busca para encontrar o valor máximo da

função f(x) = x^2 + 5.• Pop Total = 4 Cromossomos– Cada linha é um cromossomo– Cada cromossomo é composto por 6 genes (col),

sendo um desses bits, é a aptidão (fitness) que representa o valor da função y.

Implementação

• Figura 5: Tabela de Cromossomos

Implementação

• Seleção: Escolher os dois melhores cromossomos seguindo o princípio da “sobrevivência é para os mais fortes” que é avaliada pela maior aptidão.

Figura 6 : Genes escolhidos de maior aptidão

Implementação

• Reprodução: agora no novo conjunto, temos os dois cromos colhidos a partir do antigo conjunto, eles são pais de dois outros cromos no conjunto que será gerada pela passagem ao longo dos dois cromos em um determinado ponto e trocar as duas partes como segue:

• Atravesse ocorreu após o bit 3 (note o negrito e itálico os dígitos barrado nas crianças dos pais)

Implementação

• Figura 7: Crossover

Implementação

• A mutação ocorre com uma baixa probabilidade de um cromossomo no conjunto, invertendo um dos bits para terminar o ciclo.

• agora temos um novo conjunto, então fazemos o antigo conjunto igual para o novo ... e fazer a 1,2, e 3 novamente, dependendo do n º. de iterações. =)

Conclusão• Os AG's são apropriados para problemas de otimização complexos,

que envolvem muitas variáveis e um espaço de soluções de dimensão elevada.

• Abrangem um grande número de aplicações. • O controle sobre os parâmetros do algoritmo é de fundamental

importância para uma convergência rápida. • Para problemas específicos é aconselhável a utilização de

algoritmos híbridos, que misturam as técnicas dos AG's com os métodos de otimização tradicionais.

• Devido ao grande número de variáveis que um AG trata e às populações elevadas e alto número de gerações para a cobertura do espaço de soluções, os AG's possuem um custo computacional elevado.

Questões

• 1 – Quais os principais tópicos de AG? Dê um pseudo-código de cada um usando 2 cromossomas: C1 = 010 111 e C2 = 111 001.

• 3 – O deve se concluir de um AG com taxa de mutação de 10% e crossover de 80%

• 4 – Quais os parâmetros analisados em AG?

Referencias

• M. Mitchell, An Introduction to Genetic Algorithms. MIT Press, 1996.

• Lacerda, E.G.M, Carvalho, A.C.P.L. Introdução aos algoritmos genéticos. In: Galvão, C.O., Valença, M.J.S. (orgs.) Sistemas inteligentes: aplicações a recursos hídricos e ciências ambientais. Porto Alegre: Ed. Universidade/UFRGS : Associação Brasileira de Recursos Hídricos. p. 99-150. 1999. (Coleção ABRH de Recursos Hídricos; 7.).

• http://www.obitko.com/tutorials/genetic-algorithms/portuguese/ga-basic-description.php

• http://www.icmc.usp.br/~andre/research/genetic/index.htm