求解0-1背包问题的烟花算法
|
摘要
为了克服现有方法在求解0-1背包问题时存在的缺陷,提出了一种改进的烟花算法.在给出0-1背包问题的数学模型后,利用Kent混沌映射对基本烟花算法的解初始化以使初始位置分布更加均匀,同时引入Sigmoid函数得到渐变的爆炸半径使得算法的求解精度与搜索速度达到某种平衡,用改进的烟花算法来对其进行求解.通过对典型测试函数和0-1背包问题的求解结果说明了所提出的改进烟花算法求解精度更高,性能更加稳定.
To overcome the shortcomings of the existing method in solving the 0-1 knapsack problems, an improved fireworks algorithm is proposed. After a mathematical model of the 0-1 knapsack problem is given, an improved fireworks algorithm is proposed to solve it. The main idea of the improved algorithm is as follows. The initialization of the basic fireworks algorithm is solved by using Kent chaotic map to make the initial position more uniform. The Sigmoid function is also introduced to get the gradual explosion radius to make the solution accurate and the search speed reach a certain balance. The resolving results of the typical test function and the 0-1 knapsack problem show that the improved fireworks algorithm has higher precision and more stable performance.
To overcome the shortcomings of the existing method in solving the 0-1 knapsack problems, an improved fireworks algorithm is proposed. After a mathematical model of the 0-1 knapsack problem is given, an improved fireworks algorithm is proposed to solve it. The main idea of the improved algorithm is as follows. The initialization of the basic fireworks algorithm is solved by using Kent chaotic map to make the initial position more uniform. The Sigmoid function is also introduced to get the gradual explosion radius to make the solution accurate and the search speed reach a certain balance. The resolving results of the typical test function and the 0-1 knapsack problem show that the improved fireworks algorithm has higher precision and more stable performance.
引文
1 Merkle R,Hellman M.Hiding information and signatures in trapdoor knapsacks.IEEE Transactions on Information Theory,1978,24(5):525-530.[doi:10.1109/TIT.19781055927]
2 Caprara A,Pisinger D,Toth P.Exact solution of the quadratic knapsack problem.Informs Journal on Computing1999,11(1):125-139.
3李鸣山,郑海虹.0-1背包问题的多重分枝-限界算法.武汉测绘科技大学学报,1995,20(1):84-85.
4王梦竹.求解0-1背包问题算法研究.软件导刊,201312(8):59-61.
5王乐,王世卿,张静乐.基于Matlab的0-1背包问题的动态规划方法求解.计算机技术与发展,2006,16(4):88-89,92.[doi:10.3969/j.issn.1673-629X.2006.04.031]
6荆源.背包问题的差分进化算法.才智,2011,12(7):92-93.
7赵传信,季一木.粒子群优化算法在0/1背包问题的应用.微机发展,2005,15(10):23-25.[doi:10.3969/j.issn.1673-629X.2005.10.009]
8乐天.遗传算法求解0/1背包问题的综述.浙江海洋学院学报(自然科学版),2013,32(1):71-74.[doi:10.3969/j.issn.1008-830X.2013.01.014]
9 Tan Y,Zhu YC.Fireworks algorithms for optimization.Proceeding of International Conference on Swarm Intelligence(ICSI2010).Beijing,China.2010.355-364.
10 Zhang SQ,Tan Y.A unified distance measure scheme for orientation coding in identification.2013 International Conference on Information Science and Technology.Yangzhou,China.2013.979-985.
11 Imran AM,Kowsalya M.A new power system reconfiguration scheme for power loss minimization and voltage profile enhancement using fireworks algorithm.International Journal of Electrical Power&Energy Systems,2014,62:312-322.
12 Janecek A,Tan Y.Swarm intelligence for non-negative matrix factorization.International Journal of Swarm Intelligence Research,2011,2(4):12-34.[doi:10.4018/IJSIR]
13 Zheng YJ,Song Q,Chen SY.Multiobjective fireworks optimization for variable-rate fertilization in oil crop production.Applied Soft Computing,2013,13(11):4253-4263.[doi:10.1016/j.asoc.2013.07.004]
14曾德良,邓志光,陈彦桥.改进烟花算法在火电厂负荷优化分配中的应用.应用科学学报,2018,36(3):542-552.[doi:10.3969/j.issn.0255-8297.2018.03.014]
15陈璇,樊永生,余红英,等.自适应烟花算法在重型装备装载中的应用.科学技术与工程,2016,16(25):296-300.[doi:10.3969/j.issn.1671-1815.2016.25.051]
16孙宪坤,陈涛,韩华,等.基于Kent混沌测量矩阵的压缩感知图像重构算法.计算机应用与软件,2017,34(4):213-220.[doi:10.3969/j.issn.1000-386x.2017.04.036]
17吴湘锋,李志军,向林波.可编程双极性Sigmoid函数及其导数发生器.电子测量与仪器学报,2015,29(8):1137-1143.
18杜振鑫.烟花算法中爆炸半径的改进研究.计算机时代,2013,(1):28-29.[doi:10.3969/j.issn.1006-8228.2013.01.011]
19尚亚菲,刘雪英,贾敏南.引入惯性权重的烟花算法.内蒙古工业大学学报,2016,35(3):168-177.[doi:10.3969/j.issn.1001-5167.2016.03.002]
20王秋芬,梁道雷.一种求解0-1背包问题的启发式遗传算法.计算机应用与软件,2013,30(2):33-37,57.[doi:10.3969/j.issn.1000-386x.2013.02.009]
2 Caprara A,Pisinger D,Toth P.Exact solution of the quadratic knapsack problem.Informs Journal on Computing1999,11(1):125-139.
3李鸣山,郑海虹.0-1背包问题的多重分枝-限界算法.武汉测绘科技大学学报,1995,20(1):84-85.
4王梦竹.求解0-1背包问题算法研究.软件导刊,201312(8):59-61.
5王乐,王世卿,张静乐.基于Matlab的0-1背包问题的动态规划方法求解.计算机技术与发展,2006,16(4):88-89,92.[doi:10.3969/j.issn.1673-629X.2006.04.031]
6荆源.背包问题的差分进化算法.才智,2011,12(7):92-93.
7赵传信,季一木.粒子群优化算法在0/1背包问题的应用.微机发展,2005,15(10):23-25.[doi:10.3969/j.issn.1673-629X.2005.10.009]
8乐天.遗传算法求解0/1背包问题的综述.浙江海洋学院学报(自然科学版),2013,32(1):71-74.[doi:10.3969/j.issn.1008-830X.2013.01.014]
9 Tan Y,Zhu YC.Fireworks algorithms for optimization.Proceeding of International Conference on Swarm Intelligence(ICSI2010).Beijing,China.2010.355-364.
10 Zhang SQ,Tan Y.A unified distance measure scheme for orientation coding in identification.2013 International Conference on Information Science and Technology.Yangzhou,China.2013.979-985.
11 Imran AM,Kowsalya M.A new power system reconfiguration scheme for power loss minimization and voltage profile enhancement using fireworks algorithm.International Journal of Electrical Power&Energy Systems,2014,62:312-322.
12 Janecek A,Tan Y.Swarm intelligence for non-negative matrix factorization.International Journal of Swarm Intelligence Research,2011,2(4):12-34.[doi:10.4018/IJSIR]
13 Zheng YJ,Song Q,Chen SY.Multiobjective fireworks optimization for variable-rate fertilization in oil crop production.Applied Soft Computing,2013,13(11):4253-4263.[doi:10.1016/j.asoc.2013.07.004]
14曾德良,邓志光,陈彦桥.改进烟花算法在火电厂负荷优化分配中的应用.应用科学学报,2018,36(3):542-552.[doi:10.3969/j.issn.0255-8297.2018.03.014]
15陈璇,樊永生,余红英,等.自适应烟花算法在重型装备装载中的应用.科学技术与工程,2016,16(25):296-300.[doi:10.3969/j.issn.1671-1815.2016.25.051]
16孙宪坤,陈涛,韩华,等.基于Kent混沌测量矩阵的压缩感知图像重构算法.计算机应用与软件,2017,34(4):213-220.[doi:10.3969/j.issn.1000-386x.2017.04.036]
17吴湘锋,李志军,向林波.可编程双极性Sigmoid函数及其导数发生器.电子测量与仪器学报,2015,29(8):1137-1143.
18杜振鑫.烟花算法中爆炸半径的改进研究.计算机时代,2013,(1):28-29.[doi:10.3969/j.issn.1006-8228.2013.01.011]
19尚亚菲,刘雪英,贾敏南.引入惯性权重的烟花算法.内蒙古工业大学学报,2016,35(3):168-177.[doi:10.3969/j.issn.1001-5167.2016.03.002]
20王秋芬,梁道雷.一种求解0-1背包问题的启发式遗传算法.计算机应用与软件,2013,30(2):33-37,57.[doi:10.3969/j.issn.1000-386x.2013.02.009]