Come può un puma digitale risolvere il problema dello zaino?

Un gruppo di ricercatori ha lanciato il Binary Puma Optimizer (BPO), una nuova metaeuristica pensata per trasformare problemi di ottimizzazione in versione binaria. Il puma, ispirato al comportamento predatore, esplora lo spazio di ricerca con otto funzioni di trasferimento: quattro a forma di S e quattro a forma di V. Queste funzioni convertono le soluzioni continue del Puma Optimizer originale in sequenze di 0 e 1, perfette per problemi dove le scelte sono “sì” o “no”.

Il BPO è stato testato su due classici: il problema 0‑1 Knapsack (KP) e il problema di Localizzazione di Facility non capienti (UFLP). Per il KP è stato creato BPO1, che combina le funzioni di trasferimento con strategie greedy, crossover, penalità, riparazione e miglioramento. Invece, BPO2, dedicato all'UFLP, si affida solo alle funzioni di trasferimento, perché il modello non prevede vincoli di capacità e quindi non genera soluzioni infeasibili.

I risultati mostrano che BPO1 e BPO2 competono con gli algoritmi binari più noti, spesso superandoli in qualità delle soluzioni e in velocità di convergenza. La versatilità del BPO dimostra che una singola struttura di ricerca può adattarsi a problemi molto diversi, semplicemente cambiando le funzioni di trasferimento e aggiungendo (o meno) meccanismi di supporto. Questo apre la porta a nuove applicazioni in logistica, pianificazione e persino nella progettazione di reti neurali binarie.

Il Binary Puma Optimizer (BPO) si basa sul concetto di "puma" come agente di ricerca che combina esplorazione globale e sfruttamento locale. Le otto funzioni di trasferimento (TF) sono cruciali: le quattro S‑shaped (S1‑S4) mappano valori continui in probabilità di attivazione con una curva sigmoide, favorendo transizioni graduali; le quattro V‑shaped (V1‑V4) utilizzano una funzione a forma di V per enfatizzare cambiamenti bruschi, utile quando la soluzione richiede rapide variazioni di bit.

Nel caso del 0‑1 Knapsack, BPO1 integra le TF con un meccanismo greedy che ordina gli oggetti per rapporto valore/peso, generando una popolazione iniziale più promettente. Il crossover scambia segmenti di bit tra due soluzioni genitori, aumentando la diversità genetica. La penalità assegna un costo aggiuntivo alle soluzioni che violano il vincolo di capacità, mentre l'algoritmo di riparazione corregge tali violazioni sostituendo oggetti a basso valore. L'algoritmo di miglioramento applica una ricerca locale su bit singoli per affinare ulteriormente la soluzione.

Per l'UFLP, BPO2 non necessita di questi meccanismi aggiuntivi poiché il modello è privo di vincoli di capacità: ogni combinazione di aperture di strutture è fattibile. Qui le TF sono sufficienti a guidare la ricerca verso configurazioni che minimizzano la somma dei costi di apertura e dei costi di trasporto.

Le performance sono valutate mediante benchmark standard (ad esempio, dataset di CPLEX per KP e dataset di OR‑Library per UFLP). Metriche chiave includono il valore medio della soluzione, la deviazione percentuale dalla soluzione ottima nota e il tempo di esecuzione. I risultati indicano che BPO1 ottiene una deviazione media inferiore al 2% rispetto all'ottimo, con tempi di convergenza ridotti del 15‑20% rispetto a GA, PSO e altri meta‑algoritmi binari. BPO2 mostra una robustezza superiore in scenari con grandi numeri di potenziali strutture, mantenendo una qualità della soluzione costante anche con popolazioni più piccole.

Dal punto di vista teorico, l'uso combinato di TF S‑shaped e V‑shaped permette al BPO di bilanciare l'esplorazione (via V‑shaped, più aggressiva) e lo sfruttamento (via S‑shaped, più graduale). Questo approccio ibrido è stato poco esplorato nella letteratura delle metaeuristiche binarie, suggerendo potenziali estensioni future verso problemi di scheduling, routing e ottimizzazione di reti neurali binarie.