Discrete Preference-Based Stepping Ahead Firefly Algorithm for Solving Multidimensional Knapsack Problems

Abstract

Complex optimization problems, especially those encountered in real-life scenarios, pose significant challenges due to their multifaceted nature and the involvement of numerous variables. In such contexts, the application of intelligent optimization algorithms emerges as a valuable tool for effectively tackling these intricate problems. Firefly Algorithm (FA) is a popular meta-heuristic algorithm for continuous domain and lacks application in discrete domain. While there are a few applications but hardly on combinatorial optimization problems. Combinatorial optimization problem, which consist of selecting an optimal object from a finite number of objects is a challenging domain. In this study, a novel discrete version of stepping ahead FA together with its hybridization with another algorithm are proposed to solve the Multidimensional Knapsack Problem (MKP). The proposed algorithms are called discrete stepping ahead Firefly Algorithm (FA-Step) and hybridization of discrete stepping ahead Firefly Algorithm with Covariance Matrix Adaptation Evolution Strategy (FA-CMAES). The proposed algorithms make full use of the problem-solving expertise while also incorporating diversity to improve exploitation with stepping ahead mechanism and preference operator. The proposed algorithms are tested on 38 well-known knapsack instances and compared with some novel works from the literature. The proposed methods allow researchers to utilize discretization techniques in other state-of-the-art techniques to solve discrete domain problems with ease.

Keywords

• Firefly algorithm
• covariance matrix adaptation evolution strategy
• multidimensional knapsack problem
• optimization
• stepping ahead mechanism