A Novel Binary Hunger Games Search Algorithm with Data-Driven Repair for the Set Covering Problem
TL;DR
The Binary Hunger Games Search metaheuristic is selected because the relative quality of each individual determines its hunger level, which in turn regulates the movement of the population and the influence of the best solution found.
Abstract
Solving problems associated with the efficient distribution and organization of resources has generated increasing interest in the scientific community. One of the most commonly used approaches consists of approximate solution techniques, which have been able to solve complex covering problems within acceptable computational time and cost. One of the benchmarks used to evaluate these approaches is the Set Covering Problem, which is an NP-hard combinatorial optimization problem. Among the techniques that have been investigated, metaheuristics play an important role. These methods are commonly developed for continuous search spaces and, in order to be applied to covering problems, must be modified to operate in discrete domains. This modification presents an important challenge: finding an appropriate transformation method that translates continuous solutions into binary solutions. This issue has been addressed through two main strategies: binarization using two-step schemes, and, in our proposal, the use of repair operators orchestrated according to their performance through an Adaptive Repair Selection Mechanism based on the multi-armed bandit framework. To evaluate our proposal, we selected the Binary Hunger Games Search metaheuristic because the relative quality of each individual determines its hunger level, which in turn regulates the movement of the population and the influence of the best solution found. Infeasible solutions are handled through a set of Tabu Search-based repair operators. Instead of applying a single repair rule throughout the entire execution, the proposed approach dynamically selects among these operators according to their observed contribution during the search. Each repair operator also incorporates Tabu memory to discourage repetitive decisions during feasibility restoration. The experiments were conducted using the classical Beasley benchmark instances for the Set Covering Problem.