An Adaptive Fitness-Dependent Optimizer for the One-Dimensional Bin Packing Problem

Abstract

In recent years, the one-dimensional bin packing problem (1D-BPP) has become one of the most famous combinatorial optimization problems. The 1D-BPP is a robust NP-hard problem that can be solved through optimization algorithms. This paper proposes an adaptive procedure using a recently optimized swarm algorithm and fitness-dependent optimizer (FDO), named the AFDO, to solve the BPP. The proposed algorithm is based on the generation of a feasible initial population through a modified well-known first fit (FF) heuristic approach. To obtain a final optimized solution, the most critical parameters of the algorithm are adapted for the problem. To the best of our knowledge, this is the first study to apply the FDO algorithm in a discrete optimization problem, especially for solving the BPP. The adaptive algorithm was tested on 30 instances obtained from benchmark datasets. The performance and evaluation results of this algorithm were compared with those of other popular algorithms, such as the particle swarm optimization (PSO) algorithm, crow search algorithm (CSA), and Jaya algorithm. The AFDO algorithm obtained the smallest fitness values and outperformed the PSO, CS, and Jaya algorithms by 16%, 17%, and 11%, respectively. Moreover, the AFDO shows superiority in terms of execution time with improvements over the execution times of the PSO, CS, and Jaya algorithms by up to 46%, 54%, and 43%, respectively. The experimental results illustrate the effectiveness of the proposed adaptive algorithm for solving the 1D-BPP.

Keywords

• Bin packing
• first fit heuristic
• fitness-dependent optimizer
• swarm intelligent algorithms