Chaotic Niche Firefly Algorithm Solving Bounded Knapsack Problem

REN Jing-min; PAN Da-zhi

doi:10.13718/j.cnki.xsxb.2020.11.009

To solve the Bounded Knapsack Problem, a chaotic niche firefly algorithm has been proposed. The chaotic theory has been used to initialize the firefly population. In order to increase the diversity of the population, the niche technology has been used to calculate the individual shared fitness. The similar individuals in the shared radius have been excluded by a certain probability, and the Levy flight operation has been performed on all the excluded individuals. Excellent individuals perform local searches, and the precocious individuals have re-randomly been generated to update their positions using chaos theory. The simulation results show that the improved algorithm can effectively solve the Bounded Knapsack Problem.

HTML

针对实际问题，背包问题^[1]可构造出一系列子问题，如0-1背包问题^[2]、有界背包问题^[3]、折扣{0-1}背包问题^[4]等.目前求解有界背包问题(BKP)的方法有精确算法和近似算法^[5-7].

本文在标准萤火虫算法的基础上结合混沌理论和小生境技术提出混沌小生境萤火虫算法(NCFA)用于求解有界背包问题，并与小生境萤火虫算法(ULFA)、带权重的贪心萤火虫算法(WGFA)^[8]进行对比实验，结果表明本文算法能有效解决有界背包问题.

1. 有界背包问题

有界背包问题^[3]是组合优化中经典的NP问题之一，其具体描述如下：

考虑背包问题中的背包容量为C，使用n项特定的物品来填充它，其中第i项物品价值为p_i，对应重量为w_i，可选择物品个数最多为b_i，现选择若干个物品，在保证总重量不超过背包容量C的情况下使得背包内物品的价值总和最大.有界背包问题的数学模型如下：

其中：系数p_i，w_i，b_i(i=1，2，…，n)和C均为正整数.

2. 算法思想

2.1. 标准萤火虫算法

萤火虫算法^[9]是基于萤火虫闪光行为的一种启发式算法.萤火虫的吸引度取决于它的亮度，亮度越强吸引度就越强，因而可以将萤火虫亮度与有界背包问题的目标函数相关联，可将目标函数值直接作为萤火虫x_i(i=1，2，…，n)的亮度：

同时萤火虫的一部分亮度在传输过程中会被介质吸收.在最大化问题中，萤火虫相对亮度较低者会被相对亮度较高者吸引，相对亮度受萤火虫自身亮度和距离影响，其描述如下：

其中：γ为光强吸收因子，r为两萤火虫之间的欧式距离.两只萤火虫间的吸引度也将随着萤火虫i和萤火虫j之间的距离r_ij变化而变化.因此，可以定义萤火虫的吸引度β为

其中：β₀为萤火虫在距离为r=0时的吸引度，γ为光强吸收因子，r为两萤火虫之间的欧氏距离.若萤火虫i向萤火虫j的方向移动，移动公式如下：

其中：x_i^t，x_j^t为萤火虫i和萤火虫j在第t代时所处的位置；α为步长因子，rand为一个从0到1均匀分布的随机数，αrand-12为随机搜索项.

2.2. 混沌思想

混沌是自然界广泛存在的一种非线性现象，具有随机性、遍历性、初始条件敏感性等特点^[10]，本文采用的混沌映射是立方映射^[11]，其表达式为：

实际问题中，在初始值不为0的情况下都会产生混沌，对比logistic映射，立方映射产生的混沌序列均匀性较好，这里将其用于萤火虫种群的初始化.

2.3. Levy飞行

Levy飞行^[12]是一种随机漫步，其步长服从于一个重尾的概率分布，使用Levy飞行的位置更新如下所示：

其中：x_i^t表示个体i在第t代的位置，⊕为点对点乘法，α为步长控制量，d_Levy(λ)为随机步长，i=1，2，…，n.由于Levy飞行具有快速增长且方差无限的特点，于是运用于大规模搜索时，其搜索效果比较好^[13].由于Levy飞行是短距离的探索和偶尔长距离的飞行相结合，所以若对更新后的萤火虫全部进行Levy飞行将不能保护优秀个体.本文为了使较差萤火虫得到充分利用，于是选取惩罚个体的$\frac{1}{5}$进行Levy飞行.目的是种群在增加全局搜索能力的同时避免破坏较优个体.

2.4. 小生境技术

小生境技术^[14]包含了共享机制与排挤机制.传统的小生境共享机制采用单一的共享半径与两个个体的距离进行比较，虽然能判断多个子群内的拥挤程度，但是并不能判断子群内个体的优劣.本文提出计算小生境内个体的共享函数如下

其中：f_ibest和f_iavg分别表示个体i与最好个体的适应度差异和个体i与其他个体的平均适应度差异，e₁和e₂表示个体i的两种共享半径

种群内个体的共享适应度为

其中：n为种群内的个体数，d_ij为小生境内个体间的欧氏距离.为了保证种群多样性，本文根据共享适应度对所有个体进行排序，并对较差的部分个体进行惩罚：

其中penalty为惩罚系数.

2.5. 局部搜索

为了使算法快速找到问题的最优解，本文利用每次迭代产生的除最优个体外前k个较优个体产生新的位置，并将其用于替换相等数量的最差个体，位置更新公式如下

其中：x_new为更新后的个体，x_best为最优个体，λ为一个属于(0，1)的随机数，x_i为除最优个体外的前k个较优个体i=2，3，…，k+1.

2.6. 编码方式

由于有界背包问题是离散化问题，而萤火虫算法针对连续型问题求解，于是需要一种编码方式将问题中的连续解离散化，本文采用如下编码方式：

其中：bound(k)为背包内第k项物品的可选择数上限，x_ik为第i个个体的第k个分量，i=1，2，…n.

2.7. 对不可行解的修复处理

由于萤火虫算法在求解有界背包问题过程中会产生大量不可行解，本文采用文献[6]提出的一种改进贪心算法对不可行解进行修复.

3. 算法实现的具体流程

改进后的萤火虫算法(NCFA)用于求解有界背包问题实施步骤具体如下：

Step1 初始化参数，利用混沌理论对萤火虫种群初始化.

Step2 根据式(4)-(7)更新萤火虫位置，利用改进贪心算法修复不可行解.

Step3 根据式(10)-(13)计算Step2中解的共享适应度并排序，对共享半径内的较差个体进行惩罚.

Step4 对种群内被惩罚个体选取一定比例进行Levy飞行，并计算种群内萤火虫适应度.

Step5 利用局部搜索得到的新解替换较差解，利用改进贪心算法修复不可行解.

Step6 计算种群内个体适应度，更新全局最优值及最优解.

Step7 判断是否达到结束条件，若是，转Step8；若否，转Step2.

Step8 输出全局最优值.

5. 总结

本文在萤火虫算法基础上加入改进的小生境技术，在一定程度上增加了全局搜索能力，在算法初期利用混沌初始化得到的解均匀分布在解空间，并利用改进贪心算法增加了有效个体的数量，为后期寻找全局最优奠定了基础，基于萤火虫算法的改进算法NCFA可以有效求解BKP.

Figure (6) Table (4) Reference (14)

Name
	Name cannot be empty!
E-mail
	Mailbox cannot be empty! Mailbox cannot be empty!
Telephone
	Mobile number cannot be empty! Please enter a valid mobile number!
Title

Content
Verification Code

[1]	CONNOLLY D, MARTELLO S, TOTH P. Knapsack Problems: Algorithms and Computer Implementations[J]. The Journal of the Operational Research Society, 1991, 42(6): 513. doi: 10.1057/jors.1991.99 CrossRef Google Scholar
[2]	徐小平, 庞润娟, 王峰, 等.求解0-1背包问题的烟花算法[J].计算机系统应用, 2019, 28(2): 166-172. Google Scholar
[3]	KELLERER H, PFERSCHY U, PISINGER D. The Bounded Knapsack Problem[M]//Knapsack Problems. Berlin: Springer, 2004: 185-209. Google Scholar
[4]	贺毅朝, 王熙照, 李文斌, 等.基于遗传算法求解折扣{0-1}背包问题的研究[J].计算机学报, 2016, 39(12): 2614-2630. Google Scholar
[5]	PISINGER D. A Minimal Algorithm for the Bounded Knapsack Problem[M]//Integer Programming and Combinatorial Optimization. Berlin: Springer, 1995: 95-109. Google Scholar
[6]	贺毅朝, 李泽文, 李焕哲, 等.离散灰狼优化算法求解有界背包问题[J].计算机工程与设计, 2019, 40(4): 1008-1015. Google Scholar
[7]	LI Y, HE Y C, LI H Z, et al. A Binary Particle Swarm Optimization for Solving the Bounded Knapsack Problem[M]//Communications in Computer and Information Science. Berlin: Springer, 2019: 50-60. Google Scholar
[8]	任静敏, 潘大志.带权重的贪心萤火虫算法求解0-1背包问题[J].计算机与现代化, 2019(5): 86-91. Google Scholar
[9]	YANG X S. Firefly Algorithm, Stochastic Test Functions and Design Optimisation[J]. International Journal of Bio-Inspired Computation, 2010, 2(2): 78-84. doi: 10.1504/IJBIC.2010.032124 CrossRef Google Scholar
[10]	THIÉTART R A, FORGUES B. Chaos Theory and Organization[J]. Organization Science, 1995, 6(1): 19-31. doi: 10.1287/orsc.6.1.19 CrossRef Google Scholar
[11]	桂传志.混沌序列在优化理论中的应用[D].南京: 南京理工大学, 2006. Google Scholar
[12]	YANG X S, DEB S. Cuckoo Search via Levy Flights[C]//Proceeding of World Congress on Nature & Biologically Inspired Computing 2009. New York: IEEE Publications, 2009. Google Scholar
[13]	YANG X S. Nature-Inspired Metaheuristic Algorithms[M]. 2nd ed. Frome: Luniver Press, 2010. Google Scholar
[14]	LI M, CHEN T H. A Study of Genetic Algorithm Based on Niche Technique[J]. Advanced Materials Research, 2012, 1670: 152-155. Google Scholar

Message Board

Chaotic Niche Firefly Algorithm Solving Bounded Knapsack Problem

Abstract

References

Access History

通讯作者: 陈斌, bchen63@163.com

Article Metrics

Access History

Other Articles By Authors

Chaotic Niche Firefly Algorithm Solving Bounded Knapsack Problem

Corresponding author: PAN Da-zhi