Ring Theory-based Evolutionary Algorithm with Repair-Optimization Algorithm for Solving the Unbouned Knapsack Problem

The Unbounded Knapsack Problem (UKP), as an important extension of the classical 0-1 knapsack problem, is an NP-hard combinatorial optimization problem characterized by its allowance for unlimited item selection, which leads to higher computational complexity. To efficiently solve UKP using the Ring Theory-based Evolutionary Algorithm (RTEA), we first establish an Improved Threshold Unbounded Knapsack Problem (IT-UKP) model based on maximum selection constraints. Building upon an effective algorithm for handling infeasible solutions, we then propose a hybrid algorithm, RTEA-ROA, which combines RTEA with a Repair -Optimization Algorithm (ROA) to solve IT-UKP. Finally, we evaluate RTEA-ROA on three classes of large-scale UKP instances. Comparative experiments with classical algorithms (GA, DisPSO, and GTOA) demonstrate that RTEAROA is particularly well-suited for solving large-scale UKP instances both rapidly and efficiently.