Anotações
Estrutura de tópicos
Computação Evolucionária (ou  Evolutiva)
Métodos de Resolução de Problemas
métodos fortes: são concebidos para resolverem problemas genéricos, mas foram desenvolvidos para operarem em um mundo específico, onde impera linearidade, continuidade, diferenciabilidade e/ou estacionariedade.
métodos específicos: são concebidos para resolverem problemas específicos em mundos específicos.
Computação Evolucionária (ou  Evolutiva)
Métodos de Resolução de Problemas
métodos fracos: são concebidos para resolverem problemas genéricos em mundos genéricos. Operam em mundos não-lineares e não-estacionários, embora não garantam eficiência total na obtenção da solução. No entanto, geralmente garantem a obtenção de uma “boa aproximação” para a solução, em um tempo que aumenta a uma taxa menor que exponencial com o aumento do “tamanho” do problema.
Computação Evolucionária (ou  Evolutiva)
independente da aplicação, métodos fracos (soluções baseadas em computação evolutiva) devem ser considerados se e somente se métodos fortes (soluções clássicas) e métodos específicos (soluções dedicadas) não existem, não se aplicam, ou falham quando aplicados.
Computação Evolucionária (ou  Evolutiva)
conclusão: soluções baseadas em computação evolutiva devem ser consideradas como o último recurso (reforçado ainda mais pela atual imaturidade desta área de pesquisa).
alento: subtraindo-se os problemas tratáveis pelos métodos fortes e métodos específicos, o campo de aplicação para técnicas de computação evolutiva continua sendo extremamente vasto (nem tão vasto assim se considerarmos as restrições impostas pelo seu nível de maturidade).
Computação Evolucionária (ou  Evolutiva)
algoritmos genéticos, sistemas classificadores, estratégias evolutivas, programação genética e programação evolutiva
a computação evolutiva pode desempenhar os seguintes papéis básicos:
1. ferramenta adaptativa para a solução de problemas;
2. modelo computacional de processos evolutivos naturais.
sistemas naturais: metáfora diretora, fonte de inspiração.
Fundamentos dos AGs
Uma Definição
Algoritmos Genéticos (Ags) são métodos computacionais de busca baseados nos mecanismos de evolução natural e na genética. Em Ags, uma população de possíveis soluções para o problema em questão evolui de acordo com operadores probabilísticos concebidos a partir de metáforas biológicas, de modo que há uma tendência de que, na média, os indivíduos representem soluções cada vez melhores à medida que o processo evolutivo continua.
Fundamentos dos AGs
Foram desenvolvidos por John Holland, University of Michigan (1970’s) com o objetivo de:
Entender os processos adaptativos dos sistemas naturais
Projetar sistemas artificiais (software) que posssuíssem a robustez dos sistemas naturais
Fundamentos dos AGs
Provêem uma técnica eficiente e efetiva para otimização e aplicações de aprendizado de máquina
Largamente utilizados atualmente em negócios e problemas científicos e de engenharia
Componentes de um AG
Um problema a resolver, e ...
Técnica de codificação   (gene, cromossomo)
Procedimento de Inicialização     (genesis)
Função de Avaliação          (meio ambiente)
Seleção de pais               (reprodução)
Operadores Genéticos (mutação, recombinação)
Ajuste de Parâmetros           (prática e arte)
Características Primárias
AGs operam numa população (conjunto) de pontos, e não a partir de um ponto isolado.
AGs operam num espaço de soluções codificadas, e não no espaço de busca diretamente.
AGs necessitam somente de informação sobre o valor de uma função objetivo para cada membro da população, e não requerem derivadas ou qualquer outro tipo de conhecimento.
AGs usam transições probabilísticas, e não regras determinísticas.
Representação Cromossômica
Para poder aplicar AGs deve-se primeiramente representar cada possível solução x no espaço de busca como uma seqüência de símbolos s gerados a partir de um dado alfabeto finito A.
Geralmente usa-se o alfabeto binário A={0,1}, mas no caso geral tanto o método de representação quanto o alfabeto dependem de cada problema.
Cada seqüência s corresponde a um cromossomo.
Cada elemento de s é equivalente a um gene.
Representação Cromossômica
Representação Cromossômica
com números reais: (43.2 -33.1 ... 0.0 89.2)
Strings simbólicas: ¥z|vY[ ...
Permutações de elementos (E11 E3 E7 ... E1 E15)
Listas de regras  (R1 R2 R3 ... R22 R23)
Programas (para programação genética)
Qualquer estrutura de dados
Representação Cromossômica
Na maior parte dos AGs assume-se que cada indivíduo seja constituído de um único cromossomo.
A grande maioria dos AGs propostos na literatura usam uma população de número fixo de indivíduos, com cromossomos também de tamanho constante.
Representação Cromossômica
Para cada problema, encontrar uma representação cromossômica conveniente é sempre o primeiro passo.
Usa-se um vetor binário para representar cada ponto no espaço de busca.
Como há um número infinito de pontos no intervalo de interesse, a dimensão deste vetor ou seqüência binária depende da precisão requerida para o problema.
Representação Cromossômica
Assumamos, como exemplo, uma precisão de 4 casas com um espaço de busca entre os números -2 até +2.
Tal precisão significa que o porcesso d busca deve distinguir pelo menos 4 x 10.000 = 40.000 pontos.
Como resultado, seqüências binárias (cromossomos) de 16 bits são necessários, uma vez que 40.000 < 216 = 65.536.
Divide-se assim, o intervalo d busca em 65.536 partes iguais.
Representação Cromossômica
Assim, cada possível solução x será representada por uma seqüência s=[b15b14...b2b1b0] onde cada b Î {0,1}.
Primeiro converte-se o valor do cromossomo para um valor em base 10.
Em seguida, o número é mapeado de volta ao espaço de busca de acordo com:
Fluxo Básico
{
initializar população;
avaliar população;
while Criterio_de_Termino_Nao_Satisfeito
{
selecionar pais para reprodução;
realizar recombinação e mutação;
avaliar população;
}
}
Fluxo Básico
Incialização
Geralmente a população inicial de N indivíduos é gerada aleatoriamente ou através de algum processo heurístico.
É importante que a população inicial cubra a maior parte possível do espaço de busca.
Fluxo Básico
Avaliação e Adequabilidade
Ags necessitam da informação do valor de uma função objetivo para cada membro da população, que deve ser um valor não negativo.
Nos casos mais simples, usa-se o próprio valor da função que se quer maximizar.
A função objetivo dá, para cada indivíduo, uma medida de quão bem adaptado ao ambiente ele está.
A avaliação de cada indivíduo resulta num valor denominado de fitness.
Quanto maior o fitness, maiores são as chances do indivíduo sobreviver e se reproduzir.
Fluxo Básico
Seleção
Emula os processos de reprodução assexuada e seleção natural.
Em geral, gera-se uma população temporária de N indivíduos extraídos com probabilidade proporcional ao fitness relativo de cada indivíduo no população.
A probabilidade de seleção de um cromossomo S é dada por:
Fluxo Básico
Seleção
Neste processo, indivíduos com baixo fitness (adequabilidade) terão alta probabilidade de desaparecerem da população (serem extintos).
Indivíduos adequados terão grandes chances de sobreviverem.
Fluxo Básico
Exemplo: Seleção dos pais
Fluxo Básico
Exemplo: Seleção dos pais
A seleção dos pais é realizada usando-se uma roleta com tamanhos de setores de acordo com os valores obtidos na avaliação dos cromossomos.
Fluxo Básico
Recombinação (crossover)
É um processo sexuado - ou seja, envolve mais de um indivíduo.
Emula o fenômeno de “crossover”, a troca de fragmentos entre pares de cromossomos.
Na forma mais simples, é um processo aleatório que ocorre com probabilidade fixa prec que deve ser especificada pelo usuário.
Fluxo Básico
Recombinação (crossover)
Fluxo Básico
Mutação
O processo de mutação é equivalente à busca aleatória.
Seleciona-se uma posição num cromossomo e muda-se o valor do gene correspondente aleatoriamente para um outro alelo possível.
O processo é geralmente controlado por um parâmetro fixo pmut que indica a probabilidade de um gene sofrer mutação.
Fluxo Básico
Mutação
Fluxo Básico
Condições de Término
Como normalmente estamos tratando de problemas de otimização, o ideal seria que o algoritmo terminasse assim que o ponto ótimo fosse descoberto.
Pode haver situações onde todos ou o maior número possível de pontos ótimos sejam desejados.
Na prática raramente se pode afirmar se um dado ponto ótimo corresponde a um ótimo global.
Fluxo Básico
Condições de Término
Normalmente usa-se o critério de número máximo de gerações ou um tempo limite de processamento para parar um AG.
Outro critério usa a idéia de estagnação, ou, seja, para-se o algoritmo quando não se observa melhoria da população depois de várias gerações.
Fluxo Básico
Um exemplo abstrato
Exemplo
Imagine uma população inicial de 4 indivíduos, cada um representado por uma cadeia de 10 bits.
A função objetivo a maximizar é o número de bits em 1 em uma cadeia.
Para normalizar a função objetivo a valores entre 0 e 1 divide-se por 10 o número de bits em 1 de cada indivíduo.
Exemplo
Na população P1 os quatro indivíduos possuem valor de aptidão 0.3, 0.6, 0.6 e 0.9.
Teoricamente o mecanismo de seleção proporcional deveria alocar 0.5, 1.5, 1.5 e 2 descendentes para cada indivíduo.
Neste caso a alocação final de decendentes é 0, 1, 1 e 2 respectivamente.
Exemplo
A seguir as 4 cadeias são pareadas randomicamente para cruzamento.
As cadeias 1 e 4 formam um par e as cadeias 2 e 3 outro par.
Com uma taxa de cruzamento de 0.5, apenas as cadeias 1 e 4 são selecionadas para cruzamento, enquanto as cadeias 2 e 3 são deixadas intactas.
O ponto de cruzamento cai entre o quinto e o sexto bit das cadeias.
Os bits 1 a 5 das cadeias são trocados.
Exemplo
A operação de mutação na população P3 pode ser visto na população P4, no bit 10 do indivíduo 4.
Apenas um bit de um total de 40 foi trocado, representando uma taxa de mutação de 0.025.
A população P4 representa a próxima geração.
Exemplo
Este exemplo tem caracter apenas ilustrativo.
Um AG típico usa uma população de 30 a 200 indivíduos, taxas de cruzamento de 0.5 a 0.9 e taxas de mutação de 0.001 a 0.05.