关键词: 多维背包问题, 二进制和声搜索算法, 组合优化, 精英局部搜索, 价值密度

Abstract: Harmony search （HS） is a meta-heuristic method that has been applied widely to continuous optimization problems. The Multidimensional Knapsack Problem（MKP）is a kind of typical combinatorial optimization problems. In order to solve this problem, an Improved Binary Harmony Search（IBHS）algorithm was proposed. The proposed algorithm generated a binary population through a Bernoulli random process, introduced a dynamic adaptive parameter p in the candidate harmony generation operator, and coordinated the global search and local search of the algorithm through the adaptive adjustment of the algorithm parameter p,and proposed an effective method to measure the multidimensional weighted value density of commodities for binary individual correction and optimization; the introduction of an elite local search mechanism for collaborative optimization was improved the convergence speed of IBHS. By solving 10 sets of typical multidimensional knapsack examples of different scales and comparing with Greedy Binary Lion Swarm Optimization （GBLSO）algorithm, Modified Binary Differential Evolution（MBDE）algorithm and Binary Modified Harmony （BMHS）algorithm, the experimental results show that the proposed algorithm has fast convergence efficiency, high optimization accuracy and good robustness when solving MKP.

Key words: multidimensional knapsack problem（MKP）, binary harmony search（BHS） algorithm, combinatorial optimization, elite local search, value density