A simplified binary harmony search algorithm for large scale 0-1 knapsack problems

Kong, X, Gao, L, Ouyang, H and Li, S 2015, 'A simplified binary harmony search algorithm for large scale 0-1 knapsack problems', Expert Systems with Applications, vol. 42, no. 12, pp. 5337-5355.


Document type: Journal Article
Collection: Journal Articles

Title A simplified binary harmony search algorithm for large scale 0-1 knapsack problems
Author(s) Kong, X
Gao, L
Ouyang, H
Li, S
Year 2015
Journal name Expert Systems with Applications
Volume number 42
Issue number 12
Start page 5337
End page 5355
Total pages 19
Publisher Pergamon Press
Abstract As an important subset of combinatorial optimization, 0-1 knapsack problems, especially the high-dimensional ones, are often difficult to solve. This study aims to provide a new simplified binary harmony search (SBHS) algorithm to tackle such NP-hard problems arising in diverse research fields. The key difference between SBHS and other HS methods is in the process of improvisation. The differences among harmonies stored in harmony memory rather than the pitch adjustment rate (PAR) and step bandwidth (bw) are employed to produce new solutions and this can greatly alleviate the burden of setting these important factors manually. Moreover, the harmony memory considering rate (HMCR) is dynamically adjusted in terms of the dimension size to improve convergence of the algorithm. Therefore, the proposed method does not require any tedious process of proper parameter setting. To further enhance the population diversity, a specific heuristic based local search around infeasible solutions is carried out to obtain better quality solutions. A set of 10 low dimensional knapsack problems as well as large scale instances with up to 10,000 items are used to test the effectiveness of the proposed algorithm. Extensive comparisons are made with the most well-known state-of-the-art HS methods including 9 continuous versions and 5 binary-coded variants. The results reveal that the proposed algorithm can obtain better solutions in almost all cases and outperforms the other considered HS methods with statistical significance, especially for the large scale problems.
Subject Mathematical Sciences not elsewhere classified
Keyword(s) 0-1 knapsack problems
Harmony search
Ingenious improvisation scheme
Large scale
Simplified binary harmony search
DOI - identifier 10.1016/j.eswa.2015.02.015
Copyright notice © 2015 Elsevier Ltd. All rights reserved.
ISSN 0957-4174
Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 50 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 29 times in Scopus Article | Citations
Altmetric details:
Access Statistics: 157 Abstract Views  -  Detailed Statistics
Created: Wed, 25 Nov 2015, 08:21:00 EST by Catalyst Administrator
© 2014 RMIT Research Repository • Powered by Fez SoftwareContact us