One-way mutation: an efficient strategy to improve the performance of evolutionary algorithms for solving 0-1 knapsack problem

In order to more effectively solve the 0-1 knapsack problem (0-1KP) using evolutionary algorithms, this paper proposes a one-way mutation strategy (OWMS) to improve the performance by analyzing the shortcomings of existing methods for handling infeasible solutions. In addition, a new algorithm rRGOA is proposed to eliminate infeasible solutions of 0-1KP based on OWMS. To verify the effectiveness of OWMS and rRGOA, four evolutionary algorithms are used to solve 108 large-scale 0-1KP instances. The calculation results indicate that combining OWMS with existing methods can greatly improve the performance of evolutionary algorithms for solving 0-1KP. Meanwhile, rRGOA is also an effective algorithm for handling infeasible solutions. The comparison with five state-of-the-art algorithms and deterministic algorithms shows that genetic algorithm is the best for solving 0-1KP when combining OWMS with existing methods to handle infeasible solutions. Finally, it is pointed out that the inverse strongly correlated 0-1KP instances are the easiest for evolutionary algorithms.