Binary Mountain Gazelle Optimizer and Binary Enhanced Mountain Gazelle Optimizer for 0-1 Knapsack Problems and Uncapacitated Facility Location Problems

Abstract

Binary optimization problems, in which decision variables assume binary values (0 or 1), remain critical in addressing real-world tasks such as resource allocation, feature selection, scheduling, and facility location planning. Two prominent NP-hard examples are the 0-1 Knapsack Problems (KPs), which seeks to maximize the total value of selected items under a weight constraint, and the Uncapacitated Facility Location Problems (UFLPs), which aims to minimize the total cost associated with facility openings and customer assignments. This study introduces advancements to the Binary Mountain Gazelle Optimizer (BinMGO), a population-based metaheuristic algorithm inspired by the hierarchical and social behavior of gazelles. The proposed Enhanced BinMGO (EBinMGO) incorporates multiple mutation strategies to enhance convergence speed and solution robustness. Additionally, the Zigzag BinMGO (ZBinMGO) integrates a zigzag mutation mechanism to improve search space diversity and reduce the likelihood of premature convergence.Furthermore, both algorithms are extended with S-shaped and X-shaped transfer functions, enabling a more effective transformation of continuous search values into binary decisions and further balancing exploration and exploitation.The proposed algorithms are evaluated on standard benchmark datasets for both 0-1 KPs and UFLPs. Performance assessments consider statistical metrics such as best, worst, mean, standard deviation, CPU time, and average relative percentage deviation (ARPD). BinMGO, EBinMGO, and ZBinMGO are compared against competitive binary optimizers, including Snake Optimizer (SO), Prairie Dog Optimization (PDO), Pelican Optimization Algorithm (POA), Ali Baba and the Forty Thieves (AFT), Binary Particle Swarm Optimization (BPSO), and Chaotic PSO (CPSO).