JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2020, Vol. 55 ›› Issue (11): 87-95.doi: 10.6040/j.issn.1671-9352.4.2020.109

Previous Articles    

Discrete sine cosine algorithm for solving large-scale 0-1 knapsack problems

ZHENG Jian   

  1. Meizhouwan Vocational Technology College, Putian 351119, Fujian, China
  • Published:2020-11-17

PDF (PC)

518

Abstract: According to the mathematical characteristics of the 0-1 knapsack problem(0-1 KP), this paper redesigns a discrete version of SCA(DSCA)for 0-1 KP. Within the framework of basic SCA, DSCA uses the real code to generate initial individuals, a new nonlinear exponential decreasing function is applied to adjust the individual update step size. A greedy-based repair operator is included to fix and optimize the infeasible solution. The performance of the improved algorithm was tested on two sets of large-scale 0-1 KP. The comparison with some state-of-arts algorithms confirms that DSCA is efficient and concise, not only can it provide an effective solution for 0-1 KP, but also it expands the application fields of SCA.

Key words: 0-1 knapsack problem, sine cosine algorithm, swarm intelligence, combination optimization

CLC Number: 

  • TP391
[1] SEYEDALI M. SCA: a sine cosine algorithm for solving optimization problems[J]. Knowledge-Based Systems, 2016, 96:120-133.
[2] 雍龙泉. 基于正弦余弦算法的非线性方程组求根[J].陕西理工大学学报(自然科学版),2019, 35(6):64-69. YONG Longquan. Solving roots of nonlinear equations based on sine and cosine algorithm[J]. Journal of Shaanxi University of Technology(Natural Science Edition), 2019, 35(6):64-69.
[3] 于坤, 焦青亮, 刘子龙,等. 基于改进正弦余弦算法的光谱特征峰定位方法[J]. 光学学报,2019, 39(9):0930008. YU Kun, JIAO Qingliang, LIU Zilong, et al. Positioning of characteristic spectral peaks based on improved sine cosine algorithm[J]. Acta Optica Sinci, 2019, 39(9):0930008.
[4] MAJHI S K. An efficient feed foreword network model with sine cosine algorithm for breast cancer classification[J]. International Journal of System Dynamics Applications, 2018, 7(2):1-14.
[5] RAJESH K S, DASH S S. Load frequency control of autonomous power system using adaptive fuzzy based PID controller optimized on improved sine cosine algorithm[J]. Journal of Ambient Intelligence and Humanized Computing, 2018. DOI: 10.1007/s12652-018-0834-z.
[6] SINGH P P, BAINS R, SINGH G, et al. Comparative analysis on economic load dispatch problem optimization using moth flame optimization and sine cosine algorithms[J]. International Journal of Advance Research and Innovative Ideas in Education, 2017, 3(2):65-75.
[7] HANS K, DAVID P, ULRICH P. Basic algorithm concepts[M] //Knapsack Problems. Berlin: Springer, 2003: 15-62.
[8] TRUONG T K, LI K, XU Y. Chemical reaction optimization with greedy strategy for the 0-1 knapsack problem[J]. Applied Soft Computing Journal, 2013, 13(4):1774-1780.
[9] CHU P C, BEASLEY J E. A genetic algorithm for the multidimensional knapsack problem[J]. Journal of heuristics, 1998, 4(1):63-86.
[10] LI N, LI G, DENG Z L. An improved sine cosine algorithm based on levy flight[C] //Ninth International Conference on Digital Image Processing. Chengdu:International Society for Optics and Photonics, 2017.
[11] ELAZIZ M A, OLIVA D, XIONG S. An improved opposition-based sine cosine algorithm for global optimization[J]. Expert Systems with Applications, 2017, 90:484-500.
[12] 郭文艳,王远,戴芳,等. 基于精英混沌搜索策略的交替正余弦算法[J]. 控制与决策,2019,34(8):1654-1662. GUO Wenyan, WANG Yuan, DAI Fang, et al. Alternating sine cosine algorithm based on elite chaotic search strategy[J]. Control and Decision, 2019, 34(8):1654-1662.
[13] 陈聪,马良,刘勇. 函数优化的量子正弦余弦算法[J]. 计算机应用研究, 2017,34(11):3214-3218. CHEN Cong, MA Liang, LIU Yong. Quantum sine cosine algorithm for function optimization[J]. Application Research of Computers, 2017, 34(11):3214-3218.
[14] PASANDIDEH S H R, KHALILPOURAZARI S. Sine cosine crow search algorithm: a powerful hybrid meta heuristic for global optimization[J]. arXiv: Neural and Evolutionary Computing, 2018. arXiv preprint arXiv:1801.08485.
[15] NENAVATH H, JATOTH R K. Hybridizing sine cosine algorithm with differential evolution for global optimization and object tracking[J]. Applied Soft Computing, 2018, 62:1019-1043.
[16] LI C, LOU Z, SONG Z, et al. An enhanced brain storm sine cosine algorithm for global optimization problems[J]. IEEE Access, 2019, 7:28211-28229.
[17] 张校非,白艳萍,郝岩,等. 改进的正弦余弦算法在函数优化问题中的研究[J]. 重庆理工大学学报(自然科学版), 2017,31(2):146-152. ZHANG Jiaofei, BAI Yanping, HAO Yan, et al. Research of improved sine cosine algorithm in function optimization[J]. Journal of Chongqing University of Technology(Natural Science), 2017, 31(2):146-152.
[18] 徐松金,龙文. 求解高维优化问题的改进正弦余弦算法[J]. 计算机应用研究,2018,35(9):2574-2577. XU Songjin, LONG Wen. Improved sine cosine algorithm for solving high-dimensional optimization problems[J]. Application Research of Computers, 2018, 35(9):2574-2577.
[19] NENAVATH H, JATOTH R K. Hybrid SCATLBO: a novel optimization algorithm for global optimization and visual tracking[J]. Neural Computing and Applications, 2019, 31:5497-5526.
[20] 王蕾,丁正生. 融合正弦余弦算法和精英算子的花授粉算法[J]. 计算机工程与应用, 2020, 56(6):159-164. WANG Lei, DING Zhengsheng. Improved flower pollination algorithm combining sine cosine algorithm and elite operator[J]. Computer Engineering and Application, 2020, 56(6):159-164.
[21] 肖子雅,刘升,韩斐斐,等. 正弦余弦指引的乌鸦搜索算法研究[J]. 计算机工程与应用, 2019, 55(21):52-59. XIAO Ziya, LIU Sheng, HAN Feifei, et al. Crow search algorithm based on directing of sine cosine algorithm[J]. Computer Engineering and Application, 2019, 55(21):52-59.
[22] YADAV R K, GUPTA H, JHINGRAN H, et al. An enhanced genetic algorithm to solve 0/1 knapsack problem[J]. International Journal of Computer Science and Information Security, 2017, 15(5):1-15.
[23] ALZAQEBAH A, ABU-SHAREHA A A. Ant colony system algorithm with dynamic pheromone updating for 0/1 knapsack problem[J]. International Journal of Intelligent Systems and Applications, 2019, 11(2):9-18.
[24] HADDAR B, KHEMAKHEM M, HANAFI S, et al. A hybrid heuristic for the 0-1 knapsack sharing problem[J]. Expert Systems with Applications, 2015, 42(10):4653-4666.
[25] ZHAN S, ZHANG Z, WANG L, et al. List-based simulated annealing algorithm with hybrid greedy repair and optimization operator for 0-1 knapsack problem[J]. IEEE Access, 2018. DOI: 10.1109/ACCESS.2018.2872533.
[26] FENG Y, WANG G G, GAO X Z. A novel hybrid cuckoo search algorithm with global harmony search for 0-1 knapsack problems[J]. International Journal of Computational Intelligence Systems, 2016, 9(6):1174-1190.
[27] HAN M, LIU S. An improved binary chicken swarm optimization algorithm for solving 0-1 knapsack problem[C] //13th International Conference on Computational Intelligence and Security. Hong Kong:IEEE Computer Society, 2017: 207-210.
[28] GAO Y G,ZHANG F M, ZHAO Y, et al. Quantum-inspired wolf pack algorithm to solve the 0-1 knapsack problem[J]. Mathematical Problems in Engineering, 2018. DOI: 10.1155/2018/5327056.
[29] FENG Y, WANG G G, DEB S, et al. Solving 0-1 knapsack problem by a novel binary monarch butterfly optimization[J]. Neural Computing and Applications, 2015, 28(7):1619-1634.
[30] FENG Y, YANG J, WU C, et al. Solving 0-1 knapsack problems by chaotic monarch butterfly optimization algorithm with gaussian mutation[J]. Memetic Computing, 2016, 10(2):135-150.
[31] FENG Y, WANG G G, DONG J, et al. Opposition-based learning monarch butterfly optimization with Gaussian perturbation for large-scale 0-1 knapsack problem[J]. Computers & Electrical Engineering, 2018, 67:454-468.
[32] 万晓琼,张惠珍. 求解0-1背包问题的混合蝙蝠算法[J]. 计算机应用研究,2019,36(9):2579-2583. WANG Xiaoqiong, ZHANG Huizhen. Hybrid bat algorithm for solving 0-1 knapsack problem[J]. Application Research of Computers, 2019, 36(9):2579-2583.
[33] RIZK-ALLAH R M, HASSANIEN A E. New binary bat algorithm for solving 0-1 knapsack problem[J]. Complex & Intelligent Systems, 2018, 4:31-53.
[34] KONG X, GAO L, OUYANG H, et al. A simplified binary harmony search algorithm for large scale 0-1 knapsack problems[J]. Expert Systems with Applications, 2015, 42(12):5337-5355.
[35] ZOU D X, GAO L Q, LI S, et al. Solving 0-1 knapsack problem by a novel global harmony search algorithm[J]. Applied Soft Computing, 2011, 11(2):1556-1564.
[36] CHEN J, PAN Q, LI J. Harmony search algorithm with dynamic control parameters[J]. Applied Mathematics and Computation, 2012, 219(2):592-604.
[37] KULKARMI A J, SHABIR H. Solving 0-1 knapsack problem using cobort intelligence algorithm[J]. International Journal of Machine Learning and Cybernetics, 2016, 7:427-441.
[1] ZHANG Ling, REN Xue-fang. Intelligent data classification and intelligent retrieval-recognition of class [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2020, 55(10): 7-14.
[2] Ming-xing LIN. Low-light image enhancement algorithm based on variational structure [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2020, 55(9): 72-80.
[3] Jia-qi WANG,Mu-yun YANG,Tie-jun ZHAO,Zhen-yu ZHAO. Construction of retrieval dataset of procuratorate legal documents [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2020, 55(7): 81-87.
[4] Ying YU,Xin-nian WU,Le-wei WANG,Ying-long ZHANG. A multi-label three-way classification algorithm based on label correlation [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2020, 55(3): 81-88.
[5] Liu-ying WEN,Wei YUAN. Clustering method for multi-label symbolic value partition [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2020, 55(3): 58-69.
[6] Min-qing ZHANG,Neng ZHOU,Meng-meng LIU,Han WANG,Yan KE. Reversible data hiding in homomorphic encrypted domain based on Paillier [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2020, 55(3): 1-8,18.
[7] Xin-le WANG,Wen-feng YANG,Hua-ming LIAO,Yong-qing WANG,Yue LIU,Xiao-ming YU,Xue-qi CHENG. Topic tag popularity prediction based on multi-dimensional features [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2020, 55(1): 94-101.
[8] Ni LI,Huan-mei GUAN,Piao YANG,Wen-yong DONG. BERT-IDCNN-CRF for named entity recognition in Chinese [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2020, 55(1): 102-109.
[9] YANG Ya-ru, WANG Yong-qing, ZHANG Zhi-bin, LIU Yue, CHENG Xue-qi. Social network user identity linkage model based on comprehensive information [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2019, 54(9): 105-113.
[10] ZHANG Di, ZHA Dong-dong, LIU Hua-yong. Construction of the cubic λμ-α-DP curve with two kinds of shape parameters [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2019, 54(9): 114-126.
[11] Chang-ying HAO,Yan-yan LAN,Hai-nan ZHANG,Jia-feng GUO,Jun XU,Liang PANG,Xue-qi CHENG. Dialogue generation model based on extended keywords information [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2019, 54(7): 68-76.
[12] Xiang-wen LIAO,Yang XU,Jing-jing WEI,Ding-da YANG,Guo-long CHEN. Review spam detection based on the two-level stacking classification model [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2019, 54(7): 57-67.
[13] Yang XU,Jian-zhong SUN,Lei HUANG,Xiao-yao XIE. Trajectory model of area crowd based on WiFi positioning [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2019, 54(5): 8-20.
[14] Zhe-jin DONG,Jian WANG,Ling-fei QIAN,Hong-fei LIN. A modeling method of user growth profile [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2019, 54(3): 38-45.
[15] Xue-mei WANG,Xing-shu CHEN,Hai-zhou WANG,Wen-xian WANG. Automatic extraction of key information for news web pages based on tag and block features [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2019, 54(3): 67-74.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd