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

Xiangyong Kong

doi:10.1016/j.eswa.2015.02.015

2015-07-01

PRE

孔祥勇 (Xiangyong Kong) *

高立群 (Liqun Gao)

Haibin Ouyang

Steven Li

DOI：10.1016/j.eswa.2015.02.015

原文链接

原文求助

摘要

En 中文

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. (C) 2015 Elsevier Ltd. All rights reserved.

Keyword:

Harmony search

Simplified binary harmony search

0-1 knapsack problems

Large scale

Ingenious improvisation scheme