How Can a Digital Puma Solve the Knapsack Problem?

A research team has introduced the Binary Puma Optimizer (BPO), a new metaheuristic designed to turn optimization problems into binary form. Inspired by a predator's behavior, the puma explores the search space using eight transfer functions: four S‑shaped and four V‑shaped. These functions convert continuous solutions of the original Puma Optimizer into 0‑1 strings, ideal for “yes” or “no” decision problems.

The BPO was tested on two classics: the 0‑1 Knapsack Problem (KP) and the Uncapacitated Facility Location Problem (UFLP). For KP, BPO1 combines transfer functions with greedy strategies, crossover, penalty, repair, and improvement mechanisms. In contrast, BPO2, dedicated to UFLP, relies solely on transfer functions because the model has no capacity constraints and thus never produces infeasible solutions.

Results show that BPO1 and BPO2 compete with the most popular binary algorithms, often outperforming them in solution quality and convergence speed. The BPO’s versatility demonstrates that a single search framework can adapt to very different problems simply by switching transfer functions and adding (or not) auxiliary mechanisms. This opens the door to new applications in logistics, planning, and even binary neural network design.

The Binary Puma Optimizer (BPO) is grounded in the concept of a "puma" as a search agent that blends global exploration with local exploitation. Its eight transfer functions (TF) are pivotal: the four S‑shaped (S1‑S4) map continuous values to activation probabilities using a sigmoid curve, promoting gradual transitions; the four V‑shaped (V1‑V4) employ a V‑shaped function to emphasize abrupt changes, useful when solutions require rapid bit flips.

For the 0‑1 Knapsack, BPO1 incorporates TFs with a greedy mechanism that sorts items by value‑to‑weight ratio, generating a more promising initial population. Crossover swaps bit segments between two parent solutions, increasing genetic diversity. Penalty assigns an extra cost to solutions violating the capacity constraint, while the repair algorithm fixes such violations by replacing low‑value items. The improvement algorithm performs a local search on single bits to further refine the solution.

In the Uncapacitated Facility Location Problem, BPO2 does not need these additional mechanisms because the model lacks capacity constraints: any combination of facility openings is feasible. Here, TFs alone guide the search toward configurations that minimize the sum of opening and transportation costs.

Performance is assessed using standard benchmarks (e.g., CPLEX datasets for KP and OR‑Library datasets for UFLP). Key metrics include average solution value, percentage deviation from the known optimum, and execution time. Results show BPO1 achieving an average deviation below 2% from the optimum, with convergence times reduced by 15‑20% compared to GA, PSO, and other binary meta‑algorithms. BPO2 demonstrates superior robustness in scenarios with many potential facilities, maintaining consistent solution quality even with smaller populations.

Theoretically, the combined use of S‑shaped and V‑shaped TFs enables BPO to balance exploration (via V‑shaped, more aggressive) and exploitation (via S‑shaped, more gradual). This hybrid approach has been scarcely explored in binary meta‑heuristic literature, suggesting future extensions to scheduling, routing, and binary neural network optimization problems.