《山东大学学报(理学版)》 ›› 2020, Vol. 55 ›› Issue (11): 87-95.

• •

### 离散正弦余弦算法求解大规模0-1背包问题

1. 湄洲湾职业技术学院, 福建 莆田 351119
• 发布日期:2020-11-17
• 作者简介:郑健(1980— ),男,硕士,副教授,研究方向为计算机算法、物联网技术应用.E-mail:zj@mzwu.edu.cn
• 基金资助:
福建省莆田市科技计划项目(2019GM003)

### 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

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.

• 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] 张凌,任雪芳. 数据智能分类与分类智能检索-识别[J]. 《山东大学学报(理学版)》, 2020, 55(10): 7-14. [2] 林明星. 基于变分结构引导滤波的低照度图像增强算法[J]. 《山东大学学报(理学版)》, 2020, 55(9): 72-80. [3] 王佳麒,杨沐昀,赵铁军,赵臻宇. 检务文书检索数据集的构建[J]. 《山东大学学报(理学版)》, 2020, 55(7): 81-87. [4] 余鹰,吴新念,王乐为,张应龙. 基于标记相关性的多标记三支分类算法[J]. 《山东大学学报(理学版)》, 2020, 55(3): 81-88. [5] 温柳英,袁伟. 多标签符号型属性值划分的聚类方法[J]. 《山东大学学报(理学版)》, 2020, 55(3): 58-69. [6] 张敏情,周能,刘蒙蒙,王涵,柯彦. 基于Paillier的同态加密域可逆信息隐藏[J]. 《山东大学学报(理学版)》, 2020, 55(3): 1-8,18. [7] 王新乐,杨文峰,廖华明,王永庆,刘悦,俞晓明,程学旗. 基于多维度特征的主题标签流行度预测[J]. 《山东大学学报(理学版)》, 2020, 55(1): 94-101. [8] 李妮,关焕梅,杨飘,董文永. 基于BERT-IDCNN-CRF的中文命名实体识别方法[J]. 《山东大学学报(理学版)》, 2020, 55(1): 102-109. [9] 杨亚茹, 王永庆, 张志斌, 刘悦, 程学旗. 基于多元信息融合的用户关联模型[J]. 《山东大学学报(理学版)》, 2019, 54(9): 105-113. [10] 张迪,查东东,刘华勇. 带两类形状参数的三次λμ-α-DP曲线的构造[J]. 《山东大学学报(理学版)》, 2019, 54(9): 114-126. [11] 郝长盈,兰艳艳,张海楠,郭嘉丰,徐君,庞亮,程学旗. 基于拓展关键词信息的对话生成模型[J]. 《山东大学学报(理学版)》, 2019, 54(7): 68-76. [12] 廖祥文,徐阳,魏晶晶,杨定达,陈国龙. 基于双层堆叠分类模型的水军评论检测[J]. 《山东大学学报(理学版)》, 2019, 54(7): 57-67. [13] 徐洋,孙建忠,黄磊,谢晓尧. 基于WiFi定位的区域人群轨迹模型[J]. 《山东大学学报(理学版)》, 2019, 54(5): 8-20. [14] 董哲瑾,王健,钱凌飞,林鸿飞. 一种用户成长性画像的建模方法[J]. 《山东大学学报(理学版)》, 2019, 54(3): 38-45. [15] 王雪梅,陈兴蜀,王海舟,王文贤. 基于标签和分块特征的新闻网页关键信息自动抽取[J]. 《山东大学学报(理学版)》, 2019, 54(3): 67-74.
Viewed
Full text

Abstract

Cited

Shared
Discussed