|
|
|
|
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. |
|
|
|
|
|
|
|
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. |
|
|
|
|
|
|
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. |
|
|
|
|
|
|
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). |
|
|
|
|
|
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. |
|
|
|
|
|
|
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. |
|
|
|
|
|
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 |
|
|
|
|
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 |
|
|
|
|
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) |
|
|
|
|
|
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. |
|
|
|
|
|
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. |
|
|
|
|
|
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 |
|
|
|
|
|
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. |
|
|
|
|
|
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. |
|
|
|
|
|
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. |
|
|
|
|
|
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: |
|
|
|
|
|
|
{ |
|
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; |
|
} |
|
} |
|
|
|
|
|
|
|
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. |
|
|
|
|
|
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. |
|
|
|
|
|
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: |
|
|
|
|
|
|
|
|
|
|
|
|
|
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. |
|
|
|
|
Exemplo: Seleção dos pais |
|
|
|
|
|
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. |
|
|
|
|
|
|
|
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. |
|
|
|
|
|
|
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. |
|
|
|
|
|
|
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. |
|
|
|
|
|
|
|
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. |
|
|
|
|
|
|
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. |
|
|
|
|
|
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. |
|
|
|
|
|
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. |
|
|
|
|
|
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. |
|
|
|
|
|
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. |
|
|
|