基于改进的萤火虫算法求解0-1背包问题-论文.pdf

《基于改进的萤火虫算法求解0-1背包问题-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基于改进的萤火虫算法求解0—1背包问题孙飞赵学锋西北师范大学计算机科学与工程学院摘要：0-I背包问题是经典的NP¨难题该方案试图用萤火虫优化算法求解0一l背包闸题。考虑到基本人工萤火虫算法存在收敛速度慢、易陷入局部极小和优化精度低等缺点，提曲了基于改进萤必虫算法求解O一1背包问题的计算方法通过仿真实验将改进的萤必虫算法与基本萤火虫算法、动态规划算法、蔼y溯算法、分支限定算法求解O-1¨背．包问题的计算结果进行了比较实验结果表明．改进萤火虫算法在求解0"1背包问题时具有收敛速度快寻优精度高等优点，推广了萤火虫算法的应用领

2、域。关键词：萤炎虫算法O一1¨背包问题收敛速度优化算法一引言程．将求解问题的目标函数度量成个体所处位置的优劣．将个体、0—1背包问题fl1：给定若干种物品和一个背包．每件物品都有的优胜劣汰过程类比为搜索和优化过程中用好的可行解取代较重量和价值，背包容量为C。问应如何选择装入背包中的物品，使差可行解的迭代过程[6117181得在不超过背包容量的情况下，装入背包中的物品总价值最大?(-)算法的数学描述在选择装入背包的物品时．对每种物品两种选择．即装入背包或从数学角度对萤火虫算法的优化机理进行如下定义：不装入不能将物品装入背

3、包多次，也不能将物品分割后装入背定义1萤火虫的相对应光亮度为I=，ne-wr~(1包。0—1背包问题的形式化描述是：给定C>O，wp0，0，i=l，2，．．．其中：／o为萤火虫的最大荧光亮度。即自身(r=0处)荧光亮／1，要求找出一个n元0-1向量(xJ，x2，x⋯一I．x)，∈{0，1l，使度，目标函数值越优自身亮度越高，为光强吸收系数，可设置为常数，为萤火虫i与i之间的欧式距离由于本课题要解决二维得∑

4、一I1=、f(，t一．)(2)T=MaxZ(目标函数)i=1萤火虫i依概率选择邻域范围内萤火虫j并朝其运动．概率．∑c(约束条件)选择公式为：，(n—(nt=lpgt)=‘一_一、而⋯(、3)，∈{0，1)，1≤i0—1背包问题是经典的NP难题之一．目前已有多种方法求其中：为萤火虫在二维空间中第k个分量，ffJ为第t代第解．但是算法的有效性并不高本文将用一种新型的优化算i个萤火虫的亮度，l是萤火虫邻域内邻居萤火虫的个数。定义2萤火虫的吸引度为法——改进人工萤火虫优化算法进行求解．并与已有的动态规划算法、回溯算法及分支限

5、界算法进行比较日。验证改进萤火虫B=B(4)优化算法的有效性其中：80为最大吸引度，即光源处(r=O处)的吸引度，其余参数同上。二、基本人工萤火虫优化算法定义3萤火虫i被吸引向萤火虫i移动的位置更新为萤火虫算法(GSO)是由Krishnanand提出的新型群智能优化算法pJ．模拟了自然界中萤火虫成虫发光的生物学特性。近几年，O+1)=(f)+B(xgt)一(f))(5)其中：Xi和Xi为萤火虫i和i所处的空间位置。人工萤火虫在群智能优化领域引起人们的关注．并成功应用于定义4决策域半径更新：模拟机器人等多个领域H(一)萤

6、火虫算法仿真原理(f+D=min{r~，max{o，(f)+c(一l(f)1)))(6)其中：每个萤火虫都有一个感知范围(o<<‘)在这范围自然界中．萤火虫彼此吸引的原因主要取决于两个要素．即内，是一个比例常数．萤火虫选择光强比自己高的邻居．并向其移自身亮度和吸引度其中．萤火虫发出荧光的亮度取决于自身所在位置的目标值．亮度越高表示所处位置越好，即目标值越佳。动。初始阶段感知范围是．／It是控制邻域范围内邻居萤火虫个吸引度与亮度相关．越亮的萤火虫拥有越高的吸引力．可以吸引数的参数(91I~ol。视野范围(决策与范围)内亮

7、度比其弱的萤火虫往这个方向移在完成算法初始设置以后．GSO算法进入循环迭代过程．主要包括三个过程：吸引度更新、萤火虫位置更新、感知范围更新q响。动亮度和吸引度与萤火虫之间的距离成反比．都随着距离的增算法实现优化的的过程是：先将萤火虫群体随即散布在解空加而减小这相当于模拟了荧光在空间传播时被传播介质吸收而逐渐衰弱的特性目间．每一只萤火虫因为所处位置不同发出的荧光亮度也不同通过公式(1)的比较计算．亮度高的萤火虫可以吸引亮度低的萤火在基本萤火虫群优化算法中．初始有n个萤火虫随机的分散在D维空间这些萤火虫各自携带自身的荧光素

8、．并且拥有各虫向自己移动．移动的距离主要取决于吸引度的大小(公式(2))。初始决策范围根据目标函数的定义域来确定．为了加大搜索区域自的视野范围，称为区域决策范围区域决策范围的大小会受邻决策域半径按公式(6)更新。根据公式(3)、(4)来计算更新后的居数量的影响．当邻居密度较低．萤火虫的决策半径会加大以利位置。这样通过多次移动后．所