|
Esta dissertação investiga a convergência e o desempenho
de Algoritmos Genéticos: os problemas, soluções e medidas
propostas. O trabalho consiste de cinco partes principais:
uma discussão sobre os fundamentos matemáticos que buscam
explicar o funcionamento de um Algoritmo genético; um
estudo dos principais problemas associados à convergência
e ao desempenho de Algoritmos genéticos; uma análise das
técnicas e algoritmos alternativos para a melhoria da
convergência; um estudo de medidas para estimar o grau de
dificuldade esperado para a convergência de Algoritmos
Genéticos; e estudo de casos.
Os fundamentos matemáticos de Algoritmos Genéticos têm por
base os conceitos de schema e blocos construtores,
desenvolvidos por Holland (apud Goldberb, 1989a). Embora
estes conceitos constituam a teoria fundamental sobre a
qual a convergência se baseia, há, no entanto, questões
importantes sobre o processo através do qual schemata
interagem durante a evolução de um Algoritmo genético
(Forrest et al, 1993b). Este trabalho apresenta uma
discussão sobre os principais questionamentos que têm sido
levantados sobre a validade destes fundamentos. São
discutidas as controvérsias geradas pela necessidade de
uma visão dinâmica dos Algoritmos Genéticos, onde a
amostra da população e os resultados obtidos pela
recombinação sejam considerados. Em especial, as objeções
apontadas pro Thornton (1995) quanto à coerência da
associação dos conceitos de schema e blocos construtores,
a contradição entre os Teoremas schema e Price vista por
Altemberg (1994), e as idéias de adequação do Teorema
Fundamental de Algoritmos Genéticos ao conceito de
variância dentro de uma população.
Os principais problemas de convergência e desempenho de um
Algoritmo Genético foram discutidos: a Decepção e a
Epistasia. à apresentada a idéia de que a Decepção, embora
esteja fortemente ligada à dificuldade de convergência de
Algoritmos Genéticos, não constitui fator suficiente para
que um problema seja considerado difÃcil para um Algoritmo
genético (GA-hard problems) (Grefenstette, 1993). São
também apresentados os coeficientes de Walsh (Goldberg,
1989b) e demonstrada a sua relação com as idéias de schema
e epistasia, e sua utilização em funções decepcionantes.
São analisadas diversas funções decepcionantes. São
analisadas diversas funções, associadas aos conceitos de
Decepção e Epistasia: as funções fully-deceptive e fully
easy com 6 bits, propostas por Déb e Goldberg (1994); as
funções deceptive but easy e non-deceptive but hard de
Grefenstette (op. Cit.); as funções F2 e F3 de Whitley
(1992), e ainda, as funções NK (apud Harvey, 1993) e Royal
Road (Forrest et al, op. Cit.)
Técnicas alternativas para melhorar a convergência incluem
basicamente algoritmos evolucionários com caracterÃsticas
especÃficas a determinado tipo de problema. São analisados
alguns algoritmos alternativos, como o Messy de Goldberg
et alli (1989), o Estruturado de Dasgupta et al (s.d.), o
aumentado de Grefenstette (ibidem) e os algoritmos
propostos por Paredis (1996b). Ã ainda discutida e
exemplificada a importância da escolha adequada de
parâmetros e da representação de cromossomas, para que a
convergência seja mais facilmente alcançada.
O estudo de medidas de convergência de Algoritmos
Genéticos fornece uma classificação: medidas
probabilÃsticas e medidas baseadas em landscapes. São
apresentadas também as colocações de Koza (1994) e
Altemberg (op. Cit.) sobre a convergência de Algoritmos
Evolucionários. à dado destaque para medida da dificuldade
esperada para convergência baseada no Coeficiente de
Correlação entre a Aptidão e a Distãncia (FDC Fitness
Distance Correlation), como proposto por Jones e Forrest
(1995b).
O estudo de casos consiste da análise do comportamento de
Algoritmos Genéticos pela medida FDC, quando aplicados a
um conjunto de f
|
