Scholarlink

<p>The discounted {0–1} knapsack problem (D{0–1}KP) extends the classical 0–1 knapsack problem (0–1 KP) by introducing discount relationships among all grouped items. It serves as a model for commodity trading activities in economies of scale and finds applications in investment decision-making, project selection, and budget control. To solve the D{0–1}KP more efficiently, an improved group theory-based optimization algorithm with directed mutation (bIGTOA-DMO) is proposed. Firstly, a modified random linear combination operator (MbRLCO) inspired by the crossover operator of the differential evolution algorithm is proposed, and a binary version of local mutation operator (bIRMO) is presented. Secondly, a structural characteristic is proved by analyzing the profit-density relationships of the items, indicating that each group in the optimal solution tends to select the discounted item. Based on this characteristic, a directed mutation operator (DMO) is proposed, which loads the discounted items with a probability for groups without selected items. To evaluate the performance of bIGTOA-DMO, it is used to calculate 80 benchmark instances and 40 harder instances, and compared with eight existing state-of-the-art algorithms for solving D{0–1}KP. Experimental results show that the key operators of bIGTOA-DMO significantly improve its optimization-seeking ability, average performance, convergence ability, and robustness. Furthermore, bIGTOA-DMO exhibits more competitiveness over the comparison algorithms.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

An efficient improved group theory-based optimization algorithm with directed mutation operator for the discounted {0–1} knapsack problem

  • 期刊论文

  • 发表日期：

    2026年2月16日

查看全文
  • Hansong Zhang,
  • Yichao He,
  • Jinghong Wang,
  • Bianfang Chai,
  • Seyedali Mirjalili

摘要

The discounted {0–1} knapsack problem (D{0–1}KP) extends the classical 0–1 knapsack problem (0–1 KP) by introducing discount relationships among all grouped items. It serves as a model for commodity trading activities in economies of scale and finds applications in investment decision-making, project selection, and budget control. To solve the D{0–1}KP more efficiently, an improved group theory-based optimization algorithm with directed mutation (bIGTOA-DMO) is proposed. Firstly, a modified random linear combination operator (MbRLCO) inspired by the crossover operator of the differential evolution algorithm is proposed, and a binary version of local mutation operator (bIRMO) is presented. Secondly, a structural characteristic is proved by analyzing the profit-density relationships of the items, indicating that each group in the optimal solution tends to select the discounted item. Based on this characteristic, a directed mutation operator (DMO) is proposed, which loads the discounted items with a probability for groups without selected items. To evaluate the performance of bIGTOA-DMO, it is used to calculate 80 benchmark instances and 40 harder instances, and compared with eight existing state-of-the-art algorithms for solving D{0–1}KP. Experimental results show that the key operators of bIGTOA-DMO significantly improve its optimization-seeking ability, average performance, convergence ability, and robustness. Furthermore, bIGTOA-DMO exhibits more competitiveness over the comparison algorithms.