Jisuanji kexue yu tansuo (Jun 2024)
Enhanced Group Theory-Based Optimization Algorithm for Solving Discounted {0-1} Knapsack Problem
Abstract
The group theory-based optimization algorithm (GTOA) is a discrete evolutionary algorithm designed by group theory methods, which is very suitable for solving combinatorial optimization problems with integer vectors as feasible solutions. In order to further improve the performance of GTOA for solving the discounted {0-1}knapsack problem (D{0-1}KP), firstly, this paper points out the deficiency of its random linear combination operator (RLCO) which fails to fully consider the current individual position information, and improves it based on the individual gene retention strategy. Then, the enhanced 0-component mutation strategy is introduced into the random inverse mutation operator (IRMO), which is used to deal with problems such as the decline in the quality of the solution and the decrease of population diversity caused by the failure of the individual 0-component to mutate in time. Based on the improvement of the two operators mentioned above, an enhanced GTOA (EGTOA) is proposed, and a new method for solving D{0-1}KP is proposed based on it. Subsequently, the improved strategies are applied to binary GTOA (GTOA-2), and an enhanced GTOA-2 (EGTOA-2) and a new method for solving D{0-1}KP are proposed. In order to verify the degree of performance improvement and superiority of EGTOA and EGTOA-2, they are used to solve four types of large-scale D{0-1}KP instances. The comparison with GTOA, GTOA-2, and 8 state-of-the-art algorithms of solving D{0-1}KP shows that the ability of EGTOA and EGTOA-2 to obtain optimal solutions is at least 1.14 times higher than that of GTOA and GTOA-2, and 5% to 60% higher than that of the existing 8 state-of-the-art algorithms. At the same time, their average performance is also better than GTOA, GTOA-2, and the 8 advanced algorithms. Therefore, EGTOA and EGTOA-2 are currently the best algorithms for solving D{0-1}KP.
Keywords
