[pt] 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 Deb 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êcia 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 funções matemáticas, incluindo as já citadas, e ainda as funções de teste propostas por De Jong (apud Goldberg, op. cit) e a função decepcionante de Liepins e Vose (apud Deb et al, 1994). Também é realizada uma extensão da medida de dificuldade FDC estudada, buscando adequá-la a uma visão mais dinâmica de Algoritmos Genéticos. Para executar estes testes, o ambiente GENEsYs 1.0, desenvolvido por Thomas Bäck (1992) (a partir de seu precursor Genesis de JOhn Grefenstette (apud Ribeiro et alli, 1994), foi adaptado e extendido. / [en] This wok investigates the convergence and the performance
of Genetic Algorithms: the problems, solutions and
proposed measures. It is divided into five topics: a
discussion on the mathematical foundations that explains
how Genetic Algorithms work: a study of the most important
problems associated to their convergence and performance;
an analysis of techniques and alternative Genetic
Algorithms to achieve better convergence; a study of
measures trying to estimate the level of difficulty for
the convergence of GA s; and case study.
The mathematical foundations are based in conceps of
schema and building blocks, developed by Holland (apud
Goldberg, 1989a). Although they constitute the fundamental
theory about Genetic Algorithms convergence, there has
been a lot of questions about the process in which
schemata interact during the evolution of GA s (Forrest et
al, 1993b). This work presents a discussion on the most
important questions that have been raised about the
validity of these foundations. Specifically the objections
pointed out by Thorton (1995) about the conference of the
association between schema and building blocks; the
contradiction between schema theorem and Price theorem,
mentioned by Altenberg (1994); and the new ideas raised by
the variance of fitness concept.
The most important problems related to the convergence and
performance of GA s are discussed, i.e. the Deception and
the Epistasis. Even though Deception can difficult the
convergence, the former does not constitute a sufficient
factor for the late (Grefenstette, 1993). The Walsh
coefficients (Goldberg, 1989b0 and their relation with
schema are presented, and also their utilization in
deceptive fuctions. Some functions are analised, based on
the concepts of Deception and Epistasis: the 6-bits fully-
deceptive function by Deb et all (1994): the 3-bits fully-
deceptive functions, by Deb et alli (1989); the functions
deceptive but easy and non-deceptive but hard of
Grefenstette (op. cit.) the F2 and F3 functions of Whitley
(1992) as well as the NK functions (apud Harvey, 1993) and
the Royal Road functions (Forrest et al, op. cit.).
The techniques included the alternative GA s, with special
carachteristics. The Messy GA of Goldberg (1989), the
Structured GA of Dasgupta (s.d.), the Augmenated GA of
Grefenstette (ibidem) and GA s fo Paredis (1996b). The
importance of a correct choice of parameters is also
discussed.
The study of measures classifies those Ga´s into two
types: probabilistics and based on landscapes. The
considerations of Koza (1994) and Altenberg (op. cit.) are
also discussed. It is given special enfasis to the FDC (
Fitness Distance Correlacion) measure, proposed by Jones
and Forrest (1995b).
The case study consists of the analysis of the behavior of
GA by the measure FDC, applied to a set of mathematical
functions. The environment used is GENEsYs 1.0, developed
by Thomas Bäck (1992) over the Genesis of Grefenstette.
The GENEsys 1.0 was adapted and expanded to fullfil the
requirements of this work.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:8784 |
| Date | 07 August 2006 |
| Creators | RODRIGO MORAES LIMA DE ARAUJO COSTA |
| Contributors | MARLEY MARIA BERNARDES REBUZZI VELLASCO, MARCO AURELIO CAVALCANTI PACHECO, MARCO AURELIO CAVALCANTI PACHECO |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | TEXTO |
Page generated in 0.02 seconds