UM ESTUDO SOBRE O DESEMPENHO E A CONVERGÊNCIA DE ALGORITMOS GENÉTICOS / A STUDY ABOUT THE PERFORMANCE AND THE CONVERGENCE OF GENETIC ALGORITHMS

AUTOR(ES)
DATA DE PUBLICAÇÃO

1997

RESUMO

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

ASSUNTO(S)

case study algoritmos geneticos estudo de caso genetic algorithms

ACESSO AO ARTIGO

Documentos Relacionados