vivos, BRITO et al. (2005), modelou uma evolução do que antes havia sido proposto por LEHRER (2000).
LEHRER (2000), definia indivíduos com estratégias fixas dentro da população e distribuídas aleatoriamente ao longo de toda a execução, além disso apresentava a interação fenotípica como um novo método para o operador de Seleção em Algoritmos Genéticos, o qual chamou de Hawk- Dove Roleta. Em resumo, acrescentou ao tradicional método da roleta (vide Capítulo III), uma fase anterior em que os indivíduos tinham seu valor de fitness alterado, dadas uma série de disputas entre eles.
Essa alteração de fitness possibilitou um controle maior da pressão seletiva imposta pelo método da roleta – forte característica deste método de seleção. Isto se deve ao fato de o mesmo permitir que indivíduos (soluções) menos adaptados, tivessem maiores oportunidades de recombinar (maior probabilidade na roleta). Desta forma, evitou-se, ainda que de forma insipiente, a convergência prematura e, conseqüentemente, aumentou-se a possibilidade de encontro de um ótimo global para o problema em questão.
Percebendo a comprovação estatística e as vantagens por trás da proposta, BRITO (2004), propôs a criação de um segundo cromossomo destinado a codificação de estratégias e permitiu que essas fossem recombinadas ao longo da execução, tal qual propõe o biólogo Maynard Smith. Além disso, identificando o êxito de suas modificações, em BRITO et al. (2005) e TEIXEIRA (2005), um novo algoritmo genético é apresentado em que a interação fenotípica é tratada como uma etapa independente da execução e não mais de forma atrelada a um ou outro método de seleção.
A nova estrutura é apresentada na figura 4.7 e, como dito anteriormente, é a que será utilizada para o acréscimo do agente inteligente GAIA e, faz parte de todos os testes realizados com a proposta.
Figura 4.8. Estrutura de um
4.5 CONSIDERAÇÕES F
Neste capítulo foram a inspiram a nova estrutura de A Foram descritos desde Inteligente e a Teoria da Extin sua materialização dentro do cEm todas as seções abo aquilo que de fato foi interp capítulo seguinte em que a pro
m AG segundo a abordagem híbrida de (BRIT
Fonte: (BRITO et al., 2005).
FINAIS
apresentados todos os principais elementos que Algoritmo Genético proposta.
de os aspectos puramente inspiratórios como a T tinção Cíclica de Raup-Sepkoski, até as técnicas
contexto dos algoritmos evolucionários.
bordadas, ligações prévias foram estabelecidas en rpretado e implementado, assim, preparou-se o proposta é efetivamente exposta e relacionada a to
ITO et al., 2005). ue fundamentam e Teoria do Design s utilizadas para a entre o conceito e o caminho para a todos os assuntos
CAPÍTULO V
Ordo ab chao – “Ordem a partir do caos”.
Provérbio Maçônico
5. GAIA: “GENETIC ALGORITHM INFERENCE AGENT”
Batizado por meio do acrônimo em alusão a deusa primordial da mitologia grega, Gaia14, o chamado “Genetic Algorithm Inference Agent” (Agente de Inferência em Algoritmos Genéticos) – ou simplesmente, GAIA – surge inicialmente com a proposta de tratar os dois principais problemas encontrados em técnicas de computação evolucionária: o excesso de convergência ou convergência prematura, e a árdua tarefa de definição e ajuste paramétrico, a qual sempre possuirá valores ideais diferentes e desconhecidos para cada tipo de problema.
Estes dois problemas, assim como a técnica de Algoritmos Genéticos, onde será acoplado o agente, foram exaustivamente descritos no terceiro capítulo deste trabalho. Entretanto, vale também ressaltar a dificuldade que pesquisadores não relacionados à “área meio” (computação evolucionária), mas sim à “área fim” (domínio do problema que se quer resolver), encontram para realizar suas buscas, avaliá-las e entender o porquê de nem sempre
14
Gaia, Géia, Gea ou Gê era a deusa da Terra, a Mãe Terra, uma Deusa considerada primordial pelos gregos, com notória fertilidade e capacidade geradora. Descendia do Deus primordial Caos, e era avó de Zeus, que, após
apresentarem resultados significativos, tal qual sugere a idéia da proposta original desta técnica de John Holland.
Ao longo da história das principais técnicas de computação evolucionária, até os dias de hoje, busca-se, geralmente, resolver estes dois problemas por meio do acréscimo de variáveis identificadas no meio natural, partindo da máxima de que quanto mais próximos do mundo “real”, melhores serão os resultados encontrados, e mais eficiente tornar-se-á a técnica utilizada.
Propostas deste tipo, em especial as que visam contornar o problema da convergência, são muito comuns na literatura, algumas como a utilizada de apoio neste trabalho, os Algoritmos Genéticos com Interação Fenotípica (BRITO et. al., 2005, vide Capítulo IV), apresentam relativo sucesso, uma vez que reduzem a pressão seletiva e, conseqüentemente, retardam o processo de convergência prematura e estagnação em um ótimo local. Já outras, chegam a ser exageradas, quando descrevem estruturas naturais incertas e muito mais complexas do que o próprio problema,que se quer resolver por meio da técnica.
Todas essas técnicas, segundo deduções do No Free Lunch Theorem (Capítulo IV), não passam de buscas cegas que, por mais que apresentem um melhor resultado para uma classe específica de problemas, tendem de forma compensatória a refletir resultados ainda piores para as demais classes.
Segundo Dembski (2007) e outros teóricos do Design Inteligente (Capítulo IV), a única maneira de efetivamente resolver este problema de eficácia em técnicas de computação evolucionária é adicionar conhecimento sobre o espaço de busca ao algoritmo e, ainda, segundo suas proposições, espelhar-se em outro modelo natura,l diferente do darwinismo, o qual defenda intervenções “inteligentes” durante o processo de busca.
pela Teoria da Extinção Cícl desenvolveu um agente intelig monitora certas variáveis e, d eficácia e eficiência da técnica Sendo assim, conforme para Algoritmo Genético, na q inteligente proposto, o GAIA.
Figura 5.1 – Nov
Na representação do co se pelo uso da Lógica Difusa pelas características peculiare
15 Por agente inteligente, conside
íclica de Raup-Sepkoski, é que o presente traba ligente15, o qual, acoplado a uma execução de alg , de forma automatizada, realiza intervenções vi ica de busca.
me pode ser visto na figura 5.1, é introduzida um a qual, ao término de um ciclo, ocorre a interven
.
ova Estrutura de Algoritmo Genético com o GA
conhecimento necessário ao agente para suas inte sa ou Fuzzy, apresentada no quarto capítulo. Esta ares desta lógica de aproximação dos modelos
dera-se aqui o conceito de EBERHART (1996), com
balho, modelou e lgoritmo genético, visando garantir a
ma nova estrutura enção deste agente
AIA.
tervenções, optou- sta escolha se deu s matemáticos ao
raciocínio humano, por meio dos conceitos de incerteza, representação de variáveis lingüísticas e base de regras com motor de inferência de fácil compreensão.
O GAIA, intencionalmente, da forma como foi concebido, pode ser considerado como uma “caixa-preta” do ponto de vista de um Algoritmo Genético tradicional. Isto porque não altera métodos de seleção, recombinação, mutação, nem mesmo as estruturas de codificação de indivíduos e da função de avaliação do problema.
O agente é uma estrutura à parte e independente, que será “aberta” nas próximas seções do capítulo, sendo explorados todos os aspectos de codificação da proposta, desde a escolha das variáveis até a construção do motor de inferência por meio da base de regras, assim como a forma e o período de intervenção do agente.