Improved Discrete Fireworks Algorithm for Large Scale Knapsack Problem

The Knapsack Problem (KP) is a renowned combinatorial optimization challenge, recognized for its NP-hard complexity. This characteristic renders large-scale KP instances resistant to resolution through exact algorithms. In our research, we introduce an enhanced version of the discrete fireworks algorithm, specifically tailored to address various large-scale KP instances. This advancement involves a re-encoding of the original fireworks algorithm and its adaptation into a discrete format, thereby equipping it to effectively tackle discrete KP challenges. Furthermore, we have integrated a probability mechanism and a historical information learning mechanism into the algorithm. These innovations enable the algorithm to assimilate and utilize historical data, significantly augmenting its capability to explore solutions. This enhancement not only accelerates the algorithm's convergence but also improves its proficiency in identifying optimal solutions. Additionally, we have developed a dual-population strategy to optimize the balance between exploration and exploitation performances of the algorithm. Comparative experimental analyses demonstrate that our modified algorithm exhibits rapid convergence, successfully avoids entrapment in local optima, and efficiently resolves large-scale KPs within a reasonable time, outperforming other evolutionary algorithms.