利用改进萤火虫算法求解0―1背包问题

1、利用改进萤火虫算法求解01背包问题DOIDO：I10.11907/rjdk.15111650引言背包问题最早由Dantzing于20世纪50年代提出，它是一种组合优化的NP完全问题。可以描述为：给定N种物品和一个背包，该背包的最大承受重量为W，每种物品均包含重量、数量、价值3个属性，如何取舍这些物品，使得背包中物品的总价值最高。如果每一种物品只有一件，可以选择放或不放，则转为0-1背包问题。目前，求解背包问题的方法主要分为精确算法和近似算法两类。精确算法包括回溯法、分支定界法和动态规划法等1；近似算法有蚁群算法、粒子群算法、蜂群优化算法等。随着智能优化算法的不断发展，智能算法在求解复杂问题方面

2、的优势日益凸显，本文将改进的萤火虫算法(Fireflyalgorithm,FA)应用在0-1背包问题中，取得了较好的效果。10-1背包问题将0-1背包问题描述为：已知有n件物品和一个最大承受重量为V的背包，每件物品的重量为wi(i=1,2,，n),价值为pi，如何选取这些物品，使得总重量在背包承受范围内，且总价值最大。定义一个变量xi，当物品i被放入背包时，xi=1，否则xi=0；则0-1背包问题的数学模型可以表示为：maxz=£ni=1pixi(1)5 .t.I2ni=1wixi<V.(2)6 萤火虫算法萤火虫算法是由剑桥大学YangXinshe于2008年提出的一种模拟自然

3、界萤火虫发光行为的仿生算法。尽管人们对于萤火虫发光行为的意义还存有争议，但是有两点是确定的，即吸引配偶和吸引潜在猎物。为了将萤火虫的生物行为抽象为算法，YangXinshe在文献2中作了如下约束：萤火虫个体之间不存在性别之分，每只萤火虫个体都可以吸引其它的萤火虫，也可以被其它萤火虫吸引；萤火虫的吸引力和它所发出光的亮度成正比。因此，对于任意两只萤火虫来说，亮度较弱的萤火虫个体会朝着亮度较强的萤火虫飞行；如果当前可见光内，没有发现比自己更亮的萤火虫，则该萤火虫实行随机飞行策略；光的亮度一般由求解问题的目标函数决定3。在萤火虫算法中，每只萤火虫个体包含位置、亮度和吸引力7 个属性。萤火虫个体在某个

4、固定位置的亮度I是确定的，该变量一般取决于问题的目标函数。其它个体看到该个体的亮度随着它们之间距离的增大而减小，此外，还要考虑传播介质对光线的吸收作用。因此，个体在距离当前位置r处的亮度可以表示为：I(r)=I0e-Tr2(3)式(3)中，I0为个体在当前位置的亮度，丫为介质的吸收率。每个个体对其它个体的吸引力B也是相对的，随着两个个体之间距离的增大而减小。此外，吸引力还和介质吸收率有关2。因此，个体在距离该个体r位置时对其它个体的吸引力定义为：B(r)=B0e-丫r2式(4)中，B0表示两个个体距离为0时，当前个体对另一个体的吸引力，丫为介质吸收率。在该算法中，距离采用欧式距离公式计算。个体

5、i朝着比它更亮的个体j飞行的距离为：xi=xi+B0e-丫r2ij(xj-xi)+arand-12(5)式(5)中，xi和xj分别表示个体i和个体j的位置，B0e-Yr2ij表示个体i和个体j的距离为r时，个体j对个体i的吸引力。a是一个随机参数，rand是一个随机数产生函数，它产生的数字均匀分布于0，1区间。萤火虫算法步骤为：初始化种群及各参数；计算种群中所有个体的亮度值；根据公式(5)更新种群中的所有个体；对所有个体按照亮度值进行排序，找出最优个体；如果达到最大迭代次数或找到最优解，算法结束；否则，转步骤继续执行。3改进萤火虫算法应用于0-1背包问题求解在用萤火虫算法求解0-1背包问题时，

6、算法可行解采用离散0、1序列表示；然而，每个萤火虫个体均用0，1区间内随机生成的n维向量X(x1,x2,，xn)实数编码表示。因此，在每次计算萤火虫个体的亮度值之前，需要将个体的实数编码离散化，本文采用四舍五入的方法将实数编码转换成离散的0、1序列。在0-1背包问题的数学模型中，还存在一个约束条件：物品的总重量不能超过背包的容量。由于萤火虫算法的个体实数编码全部随机生成，因此，可能存在不满足这一约束的个体。对于那些不满足约束的个体，本文采用一种贪心策略：按照价值密度(价值和重量的比值)从小到大的顺序，依次将物品取出背包，直至满足问题的约束条件为止。这种方法保证了所有个体都能满足问题的约束条件。

7、为了增加种群的多样性，本文设计了一种变异策略，使得算法随迭代次数的增加依然可以保持种群个体的差异性。在每次迭代后，对于种群中除最优解之外的所有个体，从中随机选择一个个体，随机选择该个体的某一位进行变异操作，即由0变1或者由1变0。这种方法有效增加了种群个体的差异性，避免随迭代次数增加，种群陷入局部收敛。本文将背包中物品的总价值作为萤火虫个体的亮度值，利用改进萤火虫算法(ImprovedFireflyAlgorithm，IFA)求解0-1背包问题的算法步骤为：随机生成初始化种群，并初始化算法的各参数；对种群中所有个体的实数编码进行离散化；根据的个体，按照贪心策略对其进行修正；对所有个体的亮度进行

8、排序，根据亮度选出最优个体；随机从非最优个体中选择一个个体进行变异操作；种群中的个体按照公式（5）进行更新；如果达到最大迭代次数或者找到最优解，算法结束。否则，转步骤继续执行。4实验仿真实验所用PC机的操作系统为Windows8,处理器为2.94GHz,2G内存；所有实验基于matlab7.0仿真环境。实验中，乜取0.25,B取1,丫取1。对于每个算例均进行了50次独立实验。本文选取了3个测试算例，并将实验结果和现有实验结果进行对比分析。算例1：n=10，V=269，weight=95，4，60，32，23，72，80，62，65，46，price=55，10，47，5，4，50，8，61，85，87。运用回溯算法得到最优解为295。文献4采用蚂蚁优化算法在100次迭代后，可得最优解295；文献5采用蜂群算法在10次迭代后可得最优解295；文献6采用人工萤火虫群优化算法（Artificialglowwormswarmoptimizationalgorithm,GSQ在20次迭代后可得最优解295；本文采用改进的萤火虫算法在10次迭代内可得最优解295，其中，种群数目设置为20，最大迭代次数为100。收敛过程如图1所示。5结语本文针对0-1背包问题的自身特点，设计了一种改进的萤火散化编码，引入变异策略，有效地对背包问题进行求解。此外，引入贪心策略修正萤火虫算法的不可行解