Title: Solving 0-1 knapsack problem by continuous ACO algorithm

Authors: Chiranjit Changdar; G.S. Mahapatra; Rajat Kumar Pal

Addresses: Department of Computer Science, Raja N.L. Khan Women's College, Midnapore, Paschim Medinipur, West Bengal, 721102, India ' Department of Mathematics, National Institute of Technology, Puducherry, Karaikal-609605, Puducherry, India ' Department of Computer Science and Engineering, University of Calcutta, Calcutta 700 009, West Bengal, India

Abstract: This paper presents a continuous ACO approach to solve 0-1 knapsack problem. In this method, groups of candidate values of the components are constructed, and an amount of pheromone is initialised randomly for each candidate value (a real random number between 0.1 and 0.9) in each candidate group. To solve binary knapsack problem for each object a candidate group is constructed where candidate value is either 0 or 1. Each ant selects a value from each group to construct a path or a solution. After certain number of generation, store the best solution in a temporary population. When temporary population size is equal to the number of ants, then temporary population will be considered as initial population by re-initialising fresh set of pheromone. This procedure will continue until the maximum generation (defined) is reached. In experimental section, we compare the results of standard test functions and 0-1 knapsack problem with existing literature.

Keywords: candidate groups; 0-1 knapsack problem; continuous optimisation; ACO; ant colony optimisation

DOI: 10.1504/IJCISTUDIES.2013.057638

International Journal of Computational Intelligence Studies, 2013 Vol.2 No.3/4, pp.333 - 349

Received: 15 May 2012
Accepted: 20 Dec 2012

Published online: 19 Jul 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article