RL-HGGA: RL-driven genetic algorithm achieves 50x speedup on bin packing

Researchers from Algeria have developed RL-HGGA, a hybrid algorithm that uses reinforcement learning to adaptively control a grouping genetic algorithm for the one-dimensional bin packing problem (1D-BPP). The one-dimensional bin packing problem is a classic NP-hard optimization challenge with applications in logistics, manufacturing, and resource allocation—think efficiently packing items into the fewest bins. Traditional heuristic methods like First-Fit Decreasing (FFD) are fast but suboptimal, while advanced genetic algorithms (like Falkenauer's HGGA) yield near-optimal solutions but take minutes of computation.

The key innovation is replacing fixed operator probabilities with a Q-learning agent that selects among eight macro-actions—including BPCX crossover, light and heavy mutation, Martello-Toth local search, and population restart—based on an eight-dimensional state encoding generation progress, stagnation, optimality gap, average fitness, population variance, and average bin fill rate. Trained with epsilon-greedy over 400 episodes, the agent learned to dynamically choose operators that balance exploration and exploitation. On standard benchmark families (Falkenauer T/U, Scholl 1-3, Hard28), RL-HGGA achieved an average optimality gap of 0.95%—competitive with HGGA's 0.75% and well below FFD's 2.47%—while reducing mean compute time from 64.22 seconds to just 1.29 seconds, a 50x speedup. This demonstrates that learned adaptive operator selection can deliver near-optimal solution quality at a fraction of the cost, opening the door to deploying high-quality optimization in real-time or resource-constrained environments.