Populações baseadas em multisets para algoritmos evolutivos - Manso, António Manuel Rodrigues (2021)
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.