Title: A self-adaptive harmony search combined with a stochastic local search for the 0-1 multidimensional knapsack problem

Authors: Abdellah Rezoug; Dalila Boughaci

Addresses: Department of Computer Science, Faculty of Sciences, University Mhamed Bougara of Boumerdes, Boumerdes, Algeria ' Department of Computer Science, University of Sciences and Technology Houari Boumedienne (USTHB), Algiers, Algeria

Abstract: This paper presents a new hybrid self-adaptive harmony search combined with a stochastic local search algorithm (SAHS-SLS) to solve the 0-1 multidimensional knapsack problem (MKP). The proposed SAHS-SLS uses SAHS to create harmonies that will be improved with SLS. We propose a dynamic adjustment of the walk probability (wp) in SLS and a technique to compute the bandwidth (bw) and the pitch adjusting rate (PAR) in SAHS. The overall method SAHS-SLS is implemented and evaluated on benchmarks in order to measure its performance in solving the MKP. It is compared to other approaches to show its effectiveness. The numerical results are encouraging and demonstrate the benefit of the proposed approach.

Keywords: multidimensional knapsack problem; MKP; self-adaptive harmony search; SAHS; multi-unit combinatorial auctions; winner determination problem; stochastic local search; hybrid heuristics; bio-inspired computation; combinatorial optimisation; evolutionary computation; walk probability; bandwidth; pitch adjusting rate.

DOI: 10.1504/IJBIC.2016.078641

International Journal of Bio-Inspired Computation, 2016 Vol.8 No.4, pp.234 - 239

Accepted: 19 May 2015
Published online: 30 Aug 2016 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article