An effective hybrid harmony search-based algorithm for solving multidimensional knapsack problems

• A harmony memory consideration rule is developed.
• Global-best pitch adjustment rule and parallel updating strategy are employed.
• The fruit fly optimization (FFO) scheme is integrated into the improved HS as a local search strategy.

This study presents an effective hybrid algorithm based on harmony search (HHS) for solving multidimensional knapsack problems (MKPs). In the proposed HHS algorithm, a novel harmony improvisation mechanism is developed with the modified memory consideration rule and the global-best pitch adjustment scheme to enhance the global exploration. A parallel updating strategy is employed to enrich the harmony memory diversity. To well balance the exploration and the exploitation, the fruit fly optimization (FFO) scheme is integrated as a local search strategy. For solving MKPs, binary strings are used to represent solutions and two repair operators are applied to guarantee the feasibility of the solutions. The HHS is calibrated based on the Taguchi method of design-of-experiment. Extensive numerical investigations based on well-known benchmark instances are conducted. The comparative evaluations indicate the HHS is much more effective than the existing HS and FFO variants in solving MKPs.

This above fig illustrates the flowchart of our proposed algorithm. The procedure consists of two main processes: the global HS-based search process and the local FFO-based search process. The FFO scheme is integrated into the modified HS as a local search strategy. Obviously, the HMs are updated two times in each iteration, one time is for the global HS search, while the other is for the local FFO search strategy. In this way, the exploration capability of the HS scheme and the exploitation ability of the FFO scheme are both considered in this algorithm.Figure optionsDownload as PowerPoint slide