Óptimos Locais na Otimização da Diversidade: População de Descendentes Não-Trivial é Essencial

O principal objetivo da otimização da diversidade é encontrar um conjunto diversificado de soluções que satisfaçam algum limite inferior em sua aptidão. Algoritmos evolutivos (AEs) são frequentemente utilizados para tais tarefas, uma vez que são projetados naturalmente para otimizar populações de soluções. Esta abordagem para otimização da diversidade, chamada EDO, já foi estudada anteriormente sob uma perspectiva teórica, mas a maioria dos estudos considerou apenas AEs com uma população de descendentes trivial, como o (+ 1) AE. Neste artigo, apresentamos um exemplo de um problema de cobertura com k-vértices, que destaca uma diferença crítica da otimização da diversidade em relação à otimização regular de um único objetivo, nomeadamente que pode haver uma população localmente ótima da qual só podemos escapar substituindo pelo menos dois indivíduos de uma só vez, o que os algoritmos (+ 1) não conseguem fazer. Também mostramos que o (+) AE pode efetivamente encontrar uma população diversificada na cobertura de k-vértices, se utilizar um operador de mutação inspirado por Branson e Sutton (TCS 2023). Para evitar o problema da seleção de subconjuntos que surge no (+) AE quando otimiza a diversidade, também propomos o (1_ + 1_) EAD, que é um análogo do (1 + 1) AE para populações, e que também é eficiente na otimização da diversidade no problema de cobertura de k-vértices.