A Novel Discrete Global-Best Harmony Search Algorithm for Solving 0-1 Knapsack Problems

Wan-li Xiang, Mei-qing An, Yin-zhen Li, Rui-chun He and Jing-fang Zhang

Discrete Dynamics in Nature and Society, 2014, vol. 2014, 1-12

Abstract:

In order to better solve discrete 0-1 knapsack problems, a novel global-best harmony search algorithm with binary coding, called DGHS, is proposed. First, an initialization based on a greedy mechanism is employed to improve the initial solution quality in DGHS. Next, we present a novel improvisation process based on intuitive cognition of improvising a new harmony, in which the best harmony of harmony memory (HM) is used to guide the searching direction of evolution during the process of memory consideration, or else a harmony is randomly chosen from HM and then a discrete genetic mutation is done with some probability during the phase of pitch adjustment. Third, a two-phase repair operator is employed to repair an infeasible harmony vector and to further improve a feasible solution. Last, a new selection scheme is applied to decide whether or not a new randomly generated harmony is included into the HM. The proposed DGHS is evaluated on twenty knapsack problems with different scales and compared with other three metaheuristics from the literature. The experimental results indicate that DGHS is efficient, effective, and robust for solving difficult 0-1 knapsack problems.

Date: 2014
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://downloads.hindawi.com/journals/DDNS/2014/573731.pdf (application/pdf)
http://downloads.hindawi.com/journals/DDNS/2014/573731.xml (text/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jnddns:573731

DOI: 10.1155/2014/573731

Access Statistics for this article

More articles in Discrete Dynamics in Nature and Society from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().