The ant colony metaphor for multiple knapsack problem

Authors

  • Marcelo Guillermo Cena Departamento de Informática, Universidad Nacional de San Luis, 5700 San Luis, Argentina
  • María Liz Crespo Departamento de Informática, Universidad Nacional de San Luis, 5700 San Luis, Argentina
  • Carlos Kavka Departamento de Informática, Universidad Nacional de San Luis, 5700 San Luis, Argentina
  • Mario Guillermo Leguizamón Departamento de Informática, Universidad Nacional de San Luis, 5700 San Luis, Argentina

Keywords:

Nature Based Metaheuristic, Ant Colony Optimisation, Subset Problems, Multiple knapsack Problem

Abstract

This paper presents an Ant Colony Optimisation (ACO) model for the Multiple Knapsack Problem (MKP). The ACO algorithms, as well as other evolutionary metaphors, are being applied successfully to diverse heavily constrained problems: Travelling Salesman Problem, Quadratic Assignment Problem and Bin Packing Problem. An Ant System, the first ACO algorithm that we presented in this paper, is also considered a class of multiagent distributed algorithm for combinatorial optimisation. The principle of an ACO Algorithm is adapted to the MKP. We present some results regardin its perfomance against known optimun for different instances of MKP. The obtained results show the potential power of this particular evolutionary approach for optimisation problems.

Downloads

Download data is not yet available.

Downloads

Published

2000-03-01

How to Cite

Cena, M. G., Crespo, M. L., Kavka, C., & Leguizamón, M. G. (2000). The ant colony metaphor for multiple knapsack problem. Journal of Computer Science and Technology, 1(02), 11 p. Retrieved from https://journal.info.unlp.edu.ar/JCST/article/view/1019

Issue

Section

Original Articles