BSMA: A novel metaheuristic algorithm for multi-dimensional knapsack problems: Method and comprehensive analysis

doi:10.1016/j.cie.2021.107469

2021-09-01

PRE

Mohamed Abdel‐Basset

Reda Mohamed *

Karam M. Sallam

Ripon K. Chakrabortty

Michael J. Ryan

DOI：10.1016/j.cie.2021.107469

原文链接

原文求助

摘要

En 中文

The Multi-dimensional Knapsack Problems (MKP) has been widely accepted as a challenging research topic due to its NP-hard nature. In this paper, a binary version of the recently developed slime mould algorithm (BSMA) is proposed to solve MKP. As SMA was originally proposed to solve continuous optimization problems, it is not applicable to solve the MKP, which is a discrete one, in the classical form. Therefore, three different transfer function families: V-shaped, S-shaped, and U-shaped were extensively investigated with the standard algorithm to become suitable for tackling this problem in a binary variant called BSMA. However, this variant significantly suffers from stagnation into local minima preventing it from reaching better outcomes. Therefore, two various improvement steps are applied to escape the local optima and to guide the search process to better areas; the first one is based on flipping an unselected item, picked randomly, within the best-so-far solution and checking if the new solution is better or not; the second one re-initializes the population after a predefined number of iterations. These two improvements are integrated with the BSMA to develop an efficient variant abbreviated as IBSMA. For handling constraints and infeasible solutions within these two variants, a repair mechanism is utilized. The performance of the proposed algorithms is tested by solving two benchmarks MKPs. The performance of the proposed algorithm is evaluated on two well-known small-scale and large-scale problems. An extensive comparison with selected state-of-the-art algorithms shows the superiority of our proposed algorithms.

Keyword:

Multi-dimensional knapsack problem (MKP)

Slime mould algorithm (SMA)

Transfer function

Penalty function

Infeasible solution