Populações baseadas em multisets para algoritmos evolutivos

Os algoritmos evolutivos simulam a evolução natural de uma população de indivíduos aplicando iterativamente operadores genéticos, recombinação, mutação e seleção dos mais aptos. O processo evolutivo pode ser visto como um processo de otimização. Nesse caso, os indivíduos representam soluções do problema e as variáveis do problema são codificados no equivalente aos genes. Estes algoritmos podem ser facilmente implementados e existem variantes especializadas para resolver várias classes de problemas. Uma das maiores dificuldades apresentadas por estes algoritmos é a convergência prematura da população para soluções sub-ótimas antes do espaço de procura ser devidamente explorado. Várias estratégias foram desenvolvidas para reduzir este risco e, neste trabalho, estudamos a possibilidade de substituir a representação da população. Tradicionalmente as populações são representadas como coleções de indivíduos e nesta tese propomos a sua substituição por um multiconjunto (multiset). Esta nova forma de representação das populações, que denominamos multipopulações, permite manipular um conjunto de genomas e os seus clones, multi-indivíduos, de uma forma muito eficiente. Adaptamos o processo evolutivo para otimizar multipopulações, estudamos o seu comportamento em vários tipos de algoritmos e problemas e desenvolvemos operadores genéticos especializados para trabalhar com a nova representação. Em resultado disso obtemos uma forma inovadora de manter uma elevada diversidade genética na população. As experiências realizadas permitiram-nos compreender melhor a dinâmica que a nova representação introduz no processo evolutivo e mostrar a sua eficácia.Evolutionary algorithms simulate the natural evolution of a population of individuals by iteratively applying genetic operators, recombination, mutation and selection of the fittest. The evolutionary process can be viewed as an optimization process. In this case, individuals represent problem solutions and the problem variables are encoded in that equivalent to the gene. These algorithms can be easily implemented and there are specialized variants to solve different classes of problems. One of the biggest difficulties presented by these algorithms is the premature convergence of the population to suboptimal solutions before the search space is properly explored. Several strategies were developed to reduce this risk and, in this thesis, we studied the possibility of replacing the representation of the population. Traditionally populations are represented as collections of individuals and in this thesis we propose its replacement by a multiset. This new form of population representation, which we call multipopulations, allows manipulating a set of genomes and their clones, multi-individuals, in a very efficient way. We adapt the evolutionary process to optimize multipopulations, study their behavior on various types of algorithms and problems, and develop specialized genetic operators to work with the new representation. As a result, we get an innovative way to maintain a high genetic diversity in the population. The experiments allowed us to better understand the dynamics that the new representation introduces in the evolutionary process and show its effectiveness