Memorial de projetos : fundamentos dos algoritmos genéticos

Abstract

Resumo: Algoritmos genéticos podem ser definidos como um conjunto de técnicas inspiradas nas teorias de evolução natural para buscar soluções em problemas de otimização e busca. Inspirados nos postulados da teoria de Darwin sobre a seleção natural e a sobrevivência dos indivíduos mais adaptados no curso da evolução, os algoritmos genéticos utilizam estruturas de dados que imitam cromossomos e simulam processos de seleção natural, cruzamento e mutação ao longo de sucessivas gerações. Os algoritmos genéticos sofreram muitas alterações e adaptações desde sua primeira proposição e avanços importantes foram conseguidos para minimizar ou suprimir suas limitações. Desde o seu surgimento, em 1975, já demonstraram eficácia na resolução de inúmeros problemas, bem como revelaram-se úteis a diferentes campos de conhecimento e aplicações. Ainda há, contudo alguns desafios a serem resolvidos para o avanço futuro e evolução dos algoritmos genéticos: encontrar um tamanho ótimo para a população inicial; uso de diversidade para evitar a convergência prematura (encontro precoce de uma solução subótima); seleção eficiente da função fitness em função do número de iterações e do custo computacional; balanceamento adequado entre mutação e crossover

Abstract: Genetic algorithms can be defined as a set of techniques inspired by theories of natural evolution to seek solutions to optimization and search problems. Inspired by the postulates of Darwin's theory about natural selection and the survival of the most adapted individuals in the course of evolution, genetic algorithms use data structures that imitate chromosomes and simulate processes of natural selection, crossing over and mutation over successive generations. Genetic algorithms have undergone many changes and adaptations since their first proposal and important advances have been achieved to minimize or eliminate their limitations. Since their emergence in 1975, they have demonstrated effectiveness in solving countless problems, as well as proving to be useful in different fields of knowledge and applications. However, there are still some challenges to be resolved for the future advancement and evolution of genetic algorithms: finding an optimal size for the initial population; use of diversity to avoid premature convergence (early finding of a suboptimal solution); efficient selection of the fitness function depending on the number of iterations and computational cost; adequate balance between mutation and crossover