Binary light spectrum optimizer for knapsack problems: An improved model

Mohamed Abdel‐Basset

doi:10.1016/j.aej.2022.12.025

2023-03-01

DOI：10.1016/j.aej.2022.12.025

原文链接

查看原文

摘要

En 中文

This paper presents a binary variant of a novel physics-based meta-heuristic optimization algorithm, namely Light spectrum optimizer (LSO), for tackling both the 0-1 knapsack (KP01) and multidimensional knapsack problems (MKP). Because of the continuous nature of the standard LSO that contradicts the knapsack problem's discrete nature, two various transfer functions: S-shaped and X-shaped, are used to convert the continuous values produced by LSO into discrete ones. Some binary solutions produced by the binary LSO (BLSO) may be infeasible, so an improvement-repair strategy is used to convert those solutions into feasible ones by making some improvements on them. Moreover, the classical LSO was modified in this study to propose a new binary variant, namely BMLSO, with better exploration and exploitation operators for overcoming the knapsack problems. Additionally, a novel method, which simulates the swarm intelligence behaviors and the simulated binary crossover (SBX) to accelerate the convergence speed with avoid-ing stuck into local minima, has been proposed for producing a new binary variant of MLSO known as BHLSO. To verify the performance of the proposed binary variants of LSO, 45 bench- mark instances of KP01 and 30 benchmark instances of MKP used commonly in the literature have been used in our experiments. The experimental findings show the superiority of BHLSO for both KP01 and MKP compared with several well-known algorithms in terms of CPU time, convergence speed, and accuracy.(c) 2022 THE AUTHORS. Published by Elsevier BV on behalf of Faculty of Engineering, Alexandria University. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/ licenses/by-nc-nd/4.0/).

Keyword:

0-1 knapsack problem

Multidimensional knapsack

Transfer function

Light spectrum optimizer

Swarm and evolutionary

behaviors based improve

ment strategy