A Novel Discrete Global-Best Harmony Search Algorithm for Solving 0-1 Knapsack Problems
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 improvisatio...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2014-01-01
|
| Series: | Discrete Dynamics in Nature and Society |
| Online Access: | http://dx.doi.org/10.1155/2014/573731 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832561073769676800 |
|---|---|
| author | Wan-li Xiang Mei-qing An Yin-zhen Li Rui-chun He Jing-fang Zhang |
| author_facet | Wan-li Xiang Mei-qing An Yin-zhen Li Rui-chun He Jing-fang Zhang |
| author_sort | Wan-li Xiang |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-11581993a722487aa1cf43d1bc99a5ba |
| institution | Kabale University |
| issn | 1026-0226 1607-887X |
| language | English |
| publishDate | 2014-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Discrete Dynamics in Nature and Society |
| spelling | doaj-art-11581993a722487aa1cf43d1bc99a5ba2025-02-03T01:25:53ZengWileyDiscrete Dynamics in Nature and Society1026-02261607-887X2014-01-01201410.1155/2014/573731573731A Novel Discrete Global-Best Harmony Search Algorithm for Solving 0-1 Knapsack ProblemsWan-li Xiang0Mei-qing An1Yin-zhen Li2Rui-chun He3Jing-fang Zhang4School of Traffic & Transportation, Lanzhou Jiaotong University, Lanzhou, Gansu 730070, ChinaSchool of Traffic & Transportation, Lanzhou Jiaotong University, Lanzhou, Gansu 730070, ChinaSchool of Traffic & Transportation, Lanzhou Jiaotong University, Lanzhou, Gansu 730070, ChinaSchool of Traffic & Transportation, Lanzhou Jiaotong University, Lanzhou, Gansu 730070, ChinaSchool of Traffic & Transportation, Lanzhou Jiaotong University, Lanzhou, Gansu 730070, ChinaIn 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.http://dx.doi.org/10.1155/2014/573731 |
| spellingShingle | Wan-li Xiang Mei-qing An Yin-zhen Li Rui-chun He Jing-fang Zhang A Novel Discrete Global-Best Harmony Search Algorithm for Solving 0-1 Knapsack Problems Discrete Dynamics in Nature and Society |
| title | A Novel Discrete Global-Best Harmony Search Algorithm for Solving 0-1 Knapsack Problems |
| title_full | A Novel Discrete Global-Best Harmony Search Algorithm for Solving 0-1 Knapsack Problems |
| title_fullStr | A Novel Discrete Global-Best Harmony Search Algorithm for Solving 0-1 Knapsack Problems |
| title_full_unstemmed | A Novel Discrete Global-Best Harmony Search Algorithm for Solving 0-1 Knapsack Problems |
| title_short | A Novel Discrete Global-Best Harmony Search Algorithm for Solving 0-1 Knapsack Problems |
| title_sort | novel discrete global best harmony search algorithm for solving 0 1 knapsack problems |
| url | http://dx.doi.org/10.1155/2014/573731 |
| work_keys_str_mv | AT wanlixiang anoveldiscreteglobalbestharmonysearchalgorithmforsolving01knapsackproblems AT meiqingan anoveldiscreteglobalbestharmonysearchalgorithmforsolving01knapsackproblems AT yinzhenli anoveldiscreteglobalbestharmonysearchalgorithmforsolving01knapsackproblems AT ruichunhe anoveldiscreteglobalbestharmonysearchalgorithmforsolving01knapsackproblems AT jingfangzhang anoveldiscreteglobalbestharmonysearchalgorithmforsolving01knapsackproblems AT wanlixiang noveldiscreteglobalbestharmonysearchalgorithmforsolving01knapsackproblems AT meiqingan noveldiscreteglobalbestharmonysearchalgorithmforsolving01knapsackproblems AT yinzhenli noveldiscreteglobalbestharmonysearchalgorithmforsolving01knapsackproblems AT ruichunhe noveldiscreteglobalbestharmonysearchalgorithmforsolving01knapsackproblems AT jingfangzhang noveldiscreteglobalbestharmonysearchalgorithmforsolving01knapsackproblems |