您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（理学版）》

《山东大学学报(理学版)》 ›› 2020, Vol. 55 ›› Issue (11): 87-95.doi: 10.6040/j.issn.1671-9352.4.2020.109

• • 上一篇    

离散正弦余弦算法求解大规模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

PDF (PC)

664

摘要： 针对0-1背包问题的数学特征,设计了相应离散算法进行求解。算法在基本正弦余弦算法的框架内,首先采用实数编码进行个体初始化,并设计非线性指数递减函数根据迭代深度调节个体更新步长,借用贪婪修复算子对不可行解进行修复及优化。算法性能采用2组大规模的0-1背包问题进行测试,并通过与同类新兴算法的对比表明,本算法高效、简洁,不仅为0-1背包问题提供了高效率的解决方案,还拓展了正弦余弦算法的应用领域。

关键词: 0-1背包问题, 正弦余弦算法, 群智能, 组合优化

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

中图分类号: 

  • 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   
No Suggested Reading articles found!
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发