GECCO 21 Parallel GA KNP
1.0.0
Decidir qual técnica de otimização usar para resolver um problema de otimização específico é uma tarefa importante e árdua que tem sido enfrentada no campo da otimização há décadas. O problema acima é conhecido como Problema de Seleção de Algoritmo (ASP). Muitos pesquisadores tentaram resolver o ASP para uma ampla variedade de problemas. As técnicas de otimização consideradas em trabalhos anteriores foram, principalmente, técnicas de otimização que podem ser executadas de forma rápida. Porém, considerar abordagens de otimização mais sofisticadas para resolver o ASP, como Algoritmos Evolutivos, aumenta drasticamente o custo computacional envolvido. Estamos interessados em resolver o ASP considerando diferentes configurações de um Algoritmo Genético (AG) aplicado ao conhecido Problema da Mochila 0/1 NP-difícil (KNP). O acima exposto envolve a execução de um número significativo de configurações do referido AG, a fim de avaliar seu desempenho, quando aplicado a uma ampla gama de instâncias com diferentes características do KNP, o que é uma tarefa computacionalmente dispendiosa. Portanto, o principal objetivo do presente trabalho é fornecer, como primeiro passo para a resolução do ASP, um AG paralelo eficiente, que seja capaz de atingir resultados competitivos, em termos do valor objetivo ótimo, em um curto espaço de tempo. Os resultados computacionais mostram que nossa abordagem é capaz de escalar de forma eficiente e reduz consideravelmente o tempo médio decorrido para resolver instâncias KNP.
