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

作者：Kong Xiangyong^*; Gao Liqun; Ouyang Haibin; Li Steven

来源：Expert Systems with Applications, 2015, 42(12): 5337-5355.

DOI：10.1016/j.eswa.2015.02.015

• Harmony search
• Simplified binary harmony search
• 0-1 knapsack problems
• Large scale
• Ingenious improvisation scheme

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.

• 出版日期2015-7-15
• 单位东北大学