Solving large-scale multidimensional knapsack problems with a new binary harmony search algorithm

doi:10.1016/j.cor.2015.04.018

Return

Solving large-scale multidimensional knapsack problems with a new binary harmony search algorithm

2015-11-01

PRE

孔祥勇 (Xiangyong Kong) *

高立群 (Liqun Gao)

Haibin Ouyang

Steven Li

DOI：10.1016/j.cor.2015.04.018

Original

Original request for help

Save

Abstract

En 中文

Harmony search (HS) is a meta-heuristic method that has been applied widely to continuous optimization problems. In this study, a new binary coded version of HS, named NBHS, is developed for solving large-scale multidimensional knapsack problem (MKP). In the proposed method, focus is given to the probability distribution rather than the exact value of each decision variable and the concept of mean harmony is introduced in the memory consideration. Unlike the existing HS variants which require specifications of parameters such as the pitch adjustment rate and step bandwidth, an ingenious pitch adjustment scheme without parameter specification is executed in the proposed HS according to the difference between two randomly selected harmonies stored in the harmony memory to generate a new candidate harmony. Moreover, to guarantee the availability of harmonies in the harmony memory, a simple but effective repair operator derived from specific heuristic knowledge of the MKP is embedded in the proposed method. Finally, extensive numerical simulations are conducted on two sets of large-scale benchmark problems, and the results reveal that the proposed method is robust and effective for solving the multidimensional knapsack problems with large dimension sizes. (C) 2015 Elsevier Ltd. All rights reserved.

Keywords:

Harmony search

Multidimensional knapsack problems

Probability distribution

Ingenious pitch adjustment scheme

Repair operator

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.