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

*此作品的通信作者

研究成果: Article同行評審

2 引文 斯高帕斯(Scopus)

摘要

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.

原文English
頁(從 - 到)12691-12713
頁數23
期刊Neural Computing and Applications
35
發行號17
DOIs
出版狀態Published - 6月 2023

指紋

深入研究「TMHSCA: a novel hybrid two-stage mutation with a sine cosine algorithm for discounted {0-1} knapsack problems」主題。共同形成了獨特的指紋。

引用此