TMHSCA: a novel hybrid two-stage mutation with a sine cosine algorithm for discounted {0-1} knapsack problems

Yan Kang, Haining Wang, Bin Pu*, Jiansong Liu, Shin Jye Lee, Xuekun Yang, Liu Tao

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

The discounted {0-1} knapsack problem (DKP) is an NP-hard problem that is more challenging than the classical knapsack problem. In this paper, an enhanced version of the sine-cosine algorithm (SCA) called TMHSCA is proposed to solve the DKP. The SCA is a novel metaheuristic algorithm based on sine-cosine theory. Three effective improvements are proposed for the SCA to enhance the convergence speed and exploitation capability of the algorithm. First, by dividing the initial population into three subpopulations using random, greedy and opposition-based learning (OBL) strategies, the diversity of the population can be effectively enhanced. Furthermore, a forward-inverse sine-cosine search that expands the search space by utilizing the worst solution as another target is proposed. The proposed forward-inverse sine-cosine search strategy facilitates the algorithm to explore the easily ignored solution space. The last improvement includes the use of an OBL mutation and the mutation operator of differential evolution at a two-stage mutation, which increases the algorithm’s convergence speed and fitness. In our proposed two-stage mutation, the number of mutations can be adaptively adjusted based on the optimization capabilities of the optimal individual. Additionally, a reshuffling repair strategy for repairing infeasible solutions by sorting items into groups to obtain the weight-to-value ratio is proposed. Extensive experiments are conducted on 40 publicly available datasets and are compared to the greedy algorithm, 3 SCAs and 8 competitive baseline methods. The experimental results demonstrate that our method achieves a state-of-the-art performance.

Original languageEnglish
Pages (from-to)12691-12713
Number of pages23
JournalNeural Computing and Applications
Volume35
Issue number17
DOIs
StatePublished - Jun 2023

Keywords

  • Combinatorial optimization
  • Discounted {0-1} knapsack problem
  • Opposition-based learning theory
  • Sine-cosine algorithm

Fingerprint

Dive into the research topics of 'TMHSCA: a novel hybrid two-stage mutation with a sine cosine algorithm for discounted {0-1} knapsack problems'. Together they form a unique fingerprint.

Cite this