teste
Algoritmos Genéticos
Fundamentos dos
Algoritmos Genéticos
“Quanto melhor um indivíduo se adaptar ao seu meio ambiente, maior será sua chance de sobreviver e gerar descendentes.” (DARWIN, 1859)
O que são?
Os Algoritmos Genéticos são uma classe de procedimentos, com passos distintos bem definidos.
Essa classe se fundamenta em analogias a conceitos biológicos já testadas à exaustão.
Cada passo distinto pode ter diversas versões diferentes.
Para que servem?
Busca e Otimização
Amplamente utilizados, com sucesso, em problemas de difícil manipulação pelas técnicas tradicionais
Eficiência X Flexibilidade
Características Gerais
Utilizam uma codificação do conjunto de parâmetros (indivíduos) e não com os próprios parâmetros (estados);
Vasculham várias regiões do espaço de busca de cada vez;
Utilizam informações diretas de qualidade, em contraste com as derivadas utilizadas nos métodos tradicionais de otimização;
Utilizam regras de transição probabilísticas e não regras determinísticas.
Características Gerais
Algoritmos Genéticos podem ser considerados como métodos que trabalham com
Buscas Paralelas Randômicas
Direcionadas
Funcionamento
Fundamental
1. Gerar População Inicial
2. Descartar uma parte dos Indivíduos
menos aptos
3. Aplicar operadores de reprodução
4. Aplicar operadores de mutação
5. Se o critério de parada foi satisfeito, encerrar. Senão, voltar ao passo 2.
Modelagem
Indivíduos X Estados
Cada indivíduo possui um código genético Esse código é chamado cromossomo
Tradicionalmente, um cromossomo é um vetor de bits
Vetor de bits nem sempre é o ideal
Exemplo de Modelagem
Problema das N-Rainhas:
A
posição de cada rainha é dada por uma subcadeia do cromossomo
Exemplo para N = 4:
=
R1
01 11 00 10
R2
R3
R4
Operadores Fundamentais
Seleção Natural
Manipulação Genética por Mutação
Manipulação Genética por Reprodução
Seleção Natural
Princípio