Meta-Heurísticas em Pesquisa Operacional – Capítulo 6

  • Título: Comparação de Métodos de Computação Evolucionária para o Problema da Mochila Multidimensional
  • Autores: Jonas Krause, Jelson André Cordeiro e Heitor Silvério Lopes
  • DOI:10.7436/2013.mhpo.06
  • Resumo: O Problema 0-1 de Múltiplas Mochilas (PMM) é um problema de otimização combinatória NP-completo bastante difundido na literatura devido à sua grande aplicabilidade no mundo real. O uso de algoritmos meta-heurísticos é uma prática comum para a resolução do PMM. Este capítulo apresenta os seguintes métodos de computação evolucionária para resolver o PMM: Algoritmos Genéticos (AG), uma versão binária da Evolução Diferencial (EDB), o algoritmo Colônia de Abelhas Artificiais (CAA) e o Algoritmo do Morcego (AM), estes dois últimos discretizados do domínio real para o binário. São apresentados e discutidos os resultados da aplicação destes métodos para algumas instâncias de teste do PMM. Os resultados e a análise estatística mostram que o EDB é o melhor método dentre os analisados.
  • Palavras-chave: Problema da mochila, Algoritmos genéticos, Evolução diferencial, Colônia de abelhas artificiais, Algoritmo do morcego.
  • Abstract: The 0-1 Multiple Knapsacks Problem (MKP) is a NP-complete combinatorial optimization problem widely found in the literature due to its applicability to real-world problems. The use of metaheuristic algorithms is a common practice to solve the MKP. This paper presents the following evolutionary computation methods for solving the MKP: Genetic Algorithms (GA), a binary version of Differential Evolution (BDE), Artificial Bee Colony (ABC) and Bat Algorithm (BA), these last two discretized from continuous to binary domains. The results and discussion of the application of these methods for some benchmark instances of the MKP are presented. Results and statistical analysis show that BDE is the best method, when compared with the other algorithms.
  • Keywords: Knapsack problems, Genetic algorithms, Differential evolution, Artificial bee colony, Bat algorithm.
PDF do capítulo (0,422 MB):
BIBTEX do capítulo:

 

Os comentários estão encerrados.