Chaotic binary crow search algorithm for 0-1 knapsack problem

doi:10.3778/j.issn.1002-8331.1710-0086

Computer Engineering and Applications ›› 2018, Vol. 54 ›› Issue (10): 173-179.DOI: 10.3778/j.issn.1002-8331.1710-0086

Previous Articles Next Articles

Chaotic binary crow search algorithm for 0-1 knapsack problem

LIU Xuejing1, HE Yichao1, WU Congcong1, LI Liang2

1.College of Information Engineering, Hebei GEO University, Shijiazhuang 050031, China
2.Hebei Post Information Technology Bureau, China Post Group Corporation, Shijiazhuang 050011, China

Online:2018-05-15 Published:2018-05-28

求解0-1背包问题的混沌二进制乌鸦算法

刘雪静1，贺毅朝1，吴聪聪1，李靓2

1.河北地质大学信息工程学院，石家庄 050031
2.中国邮政集团公司河北省邮政信息技术局，石家庄 050011

Abstract

Abstract: In order to solve the optimization problem in discrete space, a binary crow algorithm is proposed, and two chaotic sequences by using Chebyshev mapping are generated in the initial solution, so the initial positions of the individuals are distributed throughout the search space; the greedy repair and optimization strategy is used to deal with the invalid individual of 0-1 knapsack problem, and Chaotic Binary Crow Search Algorithm（CBCSA） is proposed. The simulation results show that CBCSA has faster speed and better optimization ability than other algorithms for 0-1KP, and the first mapping method is better than the second mapping method.

Key words: crow search algorithm, chaotic, greedy optimization strategy, Chebyshev mapping, 0-1 knapsack problem

摘要： 针对离散空间的最优化问题，提出了二进制乌鸦算法，并在初始解中利用Chebyshev映射产生两种混沌序列优化乌鸦的初始解，保证个体的初始位置在整个搜索空间均匀分布；然后，为快速有效地求解0-1背包问题，引入贪心修复与优化策略处理非正常编码个体，得到基于混沌理论的二进制乌鸦算法（chaotic binary crow search algorithm，CBCSA）。仿真实验表明，CBCSA具有良好的全局寻优能力和收敛速度，能快速求得最优解，且混沌序列的第一映射方式比第二映射方式性能更佳。

关键词: 乌鸦算法, 混沌, 贪心策略, Chebyshev映射, 0-1背包问题

LIU Xuejing1, HE Yichao1, WU Congcong1, LI Liang2. Chaotic binary crow search algorithm for 0-1 knapsack problem[J]. Computer Engineering and Applications, 2018, 54(10): 173-179.

刘雪静1，贺毅朝1，吴聪聪1，李靓2. 求解0-1背包问题的混沌二进制乌鸦算法[J]. 计算机工程与应用, 2018, 54(10): 173-179.

[1]	XIN Ziyun, ZHANG Damin, CHEN Zhongyun, ZHANG Huijuan, YAN Wei. Shared Crow Algorithm Using Multi-Segment Perturbation [J]. Computer Engineering and Applications, 2020, 56(2): 55-61.
[2]	LI Hongwei, CHEN Liang, BAI Jingbo. Projection Pursuit Threat Target Assessment Model Based on Chaotic Moth-Flame Optimization Algorithm [J]. Computer Engineering and Applications, 2020, 56(2): 152-157.
[3]	CHEN Zhongyun, ZHANG Damin, XIN Ziyun, ZHANG Huijuan, YAN Wei. Salp Swarm Algorithm Using Chaotic and Elite Centroid Stretching Mechanism [J]. Computer Engineering and Applications, 2020, 56(10): 44-50.
[4]	SHAO Liangshan, LI Chenhao. Improved Flower Pollination Algorithm Extreme Learning Machine Classification Model [J]. Computer Engineering and Applications, 2020, 56(1): 172-179.
[5]	CAI Yanguang1, QI Yuanhang1, CAI Hao1，2, CHEN Houren1, OLE Hejlesen2. Chaotic Fireworks Algorithm for Multi-Type Vehicle Routing Problem in Supply Chain [J]. Computer Engineering and Applications, 2019, 55(3): 238-244.
[6]	LIU Mingxia1, YOU Xiaoming1, LIU Sheng2. Adaptive Dynamic Chaotic Ant Colony Algorithm Based on Degree of Aggregation [J]. Computer Engineering and Applications, 2019, 55(3): 15-22.
[7]	HUANG Yuda1, WANG Yiran2, NIU Sijie3. Analysis and Optimization of GSO Algorithm Based on Chaos and Self-Adaptive Search Strategy [J]. Computer Engineering and Applications, 2019, 55(3): 147-153.
[8]	WANG Yong, YANG Jin, WANG Ying. Image Encryption Algorithm Based on Improved Henon Hyperchaotic System Combined with AES Algorithm [J]. Computer Engineering and Applications, 2019, 55(22): 180-186.
[9]	XIAO Ziya, LIU Sheng, HAN Feifei, YU Jianfang. Crow Search Algorithm Based on Directing of Sine Cosine Algorithm [J]. Computer Engineering and Applications, 2019, 55(21): 52-59.
[10]	WANG Liting, ZHANG Jinxin, ZHANG Jinhua. Application of Crow Search Algorithm in SVM Parameter Optimization [J]. Computer Engineering and Applications, 2019, 55(21): 214-219.
[11]	HE Zhiming, LI Wenjing. Flower Pollination Algorithm Based on Dynamic Global Search and Cauchy Mutation [J]. Computer Engineering and Applications, 2019, 55(19): 74-80.
[12]	TANG Shenwei, JIA Ruiyu. [K]-Means Cluster Algorithm Based on Improved PSO [J]. Computer Engineering and Applications, 2019, 55(18): 140-145.
[13]	TIAN Hong, CHEN Guobin, LIU Chao. Research on New Moth-Flame Optimization Algorithm [J]. Computer Engineering and Applications, 2019, 55(16): 138-143.
[14]	XIE Guobo, WU Zhenyu. Chaotic Image Encryption Algorithm Based on Wavelet Transform and Gravity Model [J]. Computer Engineering and Applications, 2019, 55(13): 100-105.
[15]	YANG Chaojie, PEI Yijian, LIU Peng. Research on Three-Dimensional Space Path Planning Based on Improved Particle Swarm Optimization Algorithm [J]. Computer Engineering and Applications, 2019, 55(11): 117-122.

Chaotic binary crow search algorithm for 0-1 knapsack problem

求解0-1背包问题的混沌二进制乌鸦算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics