Journals
  Publication Years
  Keywords
Search within results Open Search
Please wait a minute...
For Selected: Toggle Thumbnails
Improved ring theory-based evolutionary algorithm with new repair optimization operator for solving multi-dimensional knapsack problem
Hansong ZHANG, Yichao HE, Fei SUN, Guoxin CHEN, Ju CHEN
Journal of Computer Applications    2025, 45 (5): 1595-1604.   DOI: 10.11772/j.issn.1001-9081.2024050575
Abstract43)   HTML0)    PDF (1523KB)(12)       Save

To efficiently solve Multi-dimensional Knapsack Problem (MKP) using Ring Theory-based Evolutionary Algorithm (RTEA), after analyzing the inadequacies of existing repair operators: RO1 (based on the pseudo-utility ratio of items’ overall resource consumption) and RO3 (based on the value density across individual resource dimensions), a new weighted repair optimization operator named RO4 was proposed by integrating complementary strategy. Additionally, an inheritance strategy was introduced to improve the global evolutionary operator of RTEA, and a self-adaptive reverse mutation operator suitable for MKP was proposed on the basis of Logistic model, along with a new algorithm IRTEA-RO4 for solving MKP. To validate its efficiency, IRTEA-RO4 was tested on 114 internationally recognized MKP benchmark instances and compared with six state-of-the-art algorithms for solving MKP. Experimental results demonstrate that for small-scale MKP instances, IRTEA-RO4 achieves the highest solution accuracy and fastest computation speed; for large-scale MKP instances, IRTEA-RO4 outperforms the best results of the six existing algorithms by 21% to 125% in solution quality, while also exhibiting superior average performance, enhanced stability, and faster computational speed.

Table and Figures | Reference | Related Articles | Metrics