A New Artificial Fish Swarm Algorithm for the Multiple Knapsack Problem

Qing LIU  Tomohiro ODAKA  Jousuke KUROIWA  Haruhiko SHIRAI  Hisakazu OGURA  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E97-D   No.3   pp.455-468
Publication Date: 2014/03/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E97.D.455
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Fundamentals of Information Systems
Keyword: 
artificial fish swarm algorithm,  multiple knapsack problem,  constraint boundary,  search region,  

Full Text: PDF(2.2MB)>>
Buy this Article




Summary: 
A new artificial fish swarm algorithm (AFSA) for solving the multiple knapsack problem (MKP) is introduced in this paper. In the proposed AFSA, artificial fish (AF) individuals are only allowed to search the region near constraint boundaries of the problem to be solved. For this purpose, several behaviors to be performed by AF individuals, including escaping behavior, randomly moving behavior, preying behavior and following behavior, were specially designed. Exhaustive experiments were implemented in order to investigate the proposed AFSA's performance. The results demonstrated the proposed AFSA has the ability of finding high-quality solutions with very fast speed, as compared with some other versions of AFSA based on different constraint-handling methods. This study is also meaningful for solving other constrained problems.