【背包问题】基于matlab萤火虫算法求解背包问题【含Matlab源码 1440期】

【背包问题】基于matlab萤火虫算法求解背包问题【含Matlab源码 1440期】一、背包问题简介 1【背包问题】 背包问题(Knapsack problem)是一种组合优化的NP完全问题。 问题描述为:给定一组物品,每种物品都有自己的重量weight和价格value,在限定的总重

一、背包问题简介

1【背包问题】 背包问题(Knapsack problem)是一种组合优化的NP完全问题。 问题描述为:给定一组物品,每种物品都有自己的重量weight和价格value,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。 2【0-1背包问题】 对每个物品i 只有 装入/不装入背包 两种情况。 我们有n种物品,物品j的重量为wj,价格为pj。 我们假定所有物品的重量和价格都是非负的。背包所能承受的最大重量为W。 如果限定每种物品只能选择0个或1个,则问题称为0-1背包问题。 令V(i,j)表示前i个物品中能够装入容量为j的背包中的物品价值最大值,则可得到动态规划函数: V(i,0) = V(0,j)=0; //把前i个物品装入容量为0的背包 和 把0个物品装入容量为j的背包,价值均为0 V(i,j) = V(i-1,j) j<wi //如果第i个物品的重量大于背包容量wi>j,则装入前i个物品得到的最大价值和装入前i-1个物品得到的最大价值相同,即物品i不装入背包 V(i,j) = max{ V(i-1,j),V(i-1,j-wi)+vi } j>wi // 1.如果把第i个物品装入背包,则背包中物品的价值=把前i-1个物品装入容量为j-wi背包中的价值加上第i个物品的价值vi; 2. 如果第i个物品没有装入背包,则背包中价值=前i-1个物品装入容量为j的背包中所取得的价值。 取二者中价值较大者。 step 1:只装入前1个物品,确定各种情况下的背包能够得到的最大价值; step 2:只装人前2个物品,确定各种情况下的背包能够得到的最大价值;. step n:… 最后V(n,C)便是容量为C的背包中装入n个物品时取得的最大价值。 为了得到V(n,C) 需想前推到V(n-1,C)。如果V(n,C)>V(n-1,C),则第n个物品装入背包,前n-1个物品装入容量为C-wn的背包中;否则,第n个物品没有被装入背包,前n-1个物品被装入容量为C的背包中。 直到确定第一个物品是否被装入背包中。 得到: 当 V(i,j)= V(i-1,j), xi = 0; 当 V(i,j) > V(i-1,j), xi = 1,j = j-wi;

二、萤火虫优化算法(FA)简介

1 介绍 萤火虫(firefly)种类繁多,主要分布在热带地区。大多数萤火虫在短时间内产生有节奏的闪光。这种闪光是由于生物发光的一种化学反应,萤火虫的闪光模式因种类而异。萤火虫算法(FA)是基于萤火虫的闪光行为,它是一种用于全局优化问题的智能随机算法,由Yang Xin-She(2009)[1]提出。萤火虫通过下腹的一种化学反应-生物发(bioluminescence)发光。这种生物发光是萤火虫求偶仪式的重要组成部分,也是雄性萤火虫和雌性萤火虫交流的主要媒介,发出光也可用来引诱配偶或猎物,同时这种闪光也有助于保护萤火虫的领地,并警告捕食者远离栖息地。在FA中,认为所有的萤火虫都是雌雄同体的,无论性别如何,它们都互相吸引。该算法的建立基于两个关键的概念:发出的光的强度和两个萤火虫之间产生的吸引力的程度。

2 天然萤火虫的行为 天然萤火虫在寻找猎物、吸引配偶和保护领地时表现出惊人的闪光行为,萤火虫大多生活在热带环境中。一般来说,它们产生冷光,如绿色、黄色或淡红色。萤火虫的吸引力取决于它的光照强度,对于任何一对萤火虫来说,较亮的萤火虫会吸引另一只萤火虫。所以,亮度较低的个体移向较亮的个体,同时光的亮度随着距离的增加而降低。萤火虫的闪光模式可能因物种而异,在一些萤火虫物种中,雌性会利用这种现象猎食其他物种;有些萤火虫在一大群萤火虫中表现出同步闪光的行为来吸引猎物,雌萤火虫从静止的位置观察雄萤火虫发出的闪光,在发现一个感兴趣趣的闪光后,雌性萤火虫会做出反应,发出闪光,求偶仪式就这样开始了。一些雌性萤火虫会产生其他种类萤火虫的闪光模式,来诱捕雄性萤火虫并吃掉它们。

3 萤火虫算法 萤火虫算法模拟了萤火虫的自然现象。真实的萤火虫自然地呈现出一种离散的闪烁模式,而萤火虫算法假设它们总是在发光。为了模拟萤火虫的这种闪烁行为,Yang Xin-She提出了了三条规则(Yang,2009): (1)假设所有萤火虫都是雌雄同体的,因此一只萤火虫可能会被其他任何萤火虫吸引。 (2)萤火虫的亮度决定其吸引力的大小,较亮的萤火虫吸引较暗的萤火虫。如果没有萤火虫比被考虑的萤火虫更亮,它就会随机移动。 (3)函数的最优值与萤火虫的亮度成正比。 光强(I)与光源距离(r)服从平方反比定律,因此由于空气的吸收,光的强度(I)随着与光源距离的增加而减小,这种现象将萤火虫的可见性限定在了非常有限的半径内: 在这里插入图片描述 萤火虫算法的主要实现步骤如下: 在这里插入图片描述 其中I0为距离r=0时的光强(最亮),即自身亮度,与目标函数值有关,目标值越优,亮度越亮;γ为吸收系数,因为荧光会随着距离的增加和传播媒介的吸收逐渐减弱,所以设置光强吸收系数以体现此特性,可设置为常数;r表示两个萤火虫之间的距离。有时也使用单调递减函数,如下式所示。 在这里插入图片描述 第二步为种群初始化: 在这里插入图片描述 其中t表示代数,xt表示个体的当前位置,β0exp(-γr2)是吸引度,αε是随机项。下一步将会计算萤火虫之间的吸引度: 在这里插入图片描述 其中β0表示r=0时的最大吸引度。 下一步,低亮度萤火虫向较亮萤火虫运动: 在这里插入图片描述 最后一个阶段,更新光照强度,并对所有萤火虫进行排序,以确定当前的最佳解决方案。萤火虫算法的主要步骤如下所示。

Begin
	初始化算法基本参数:设置萤火虫数目n,最大吸引度β0,光强吸收系数γ,步长因子α,最大迭代次数MaxGeneration或搜索精度ε;
	初始化:随机初始化萤火虫的位置,计算萤火虫的目标函数值作为各自最大荧光亮度I0;
	t=1
	while(t<=MaxGeneration || 精度>ε)
		计算群体中萤火虫的相对亮度I(式2)和吸引度β(式5),根据相对亮度决定萤火虫的移动方向;
		更新萤火虫的空间位置,对处在最佳位置的萤火虫进行随机移动(式6);
		根据更新后萤火虫的位置,重新计算萤火虫的亮度I0;
		t=t+1
	end while
	输出全局极值点和最优个体值。
end

萤火虫算法与粒子群算法(PSO)和细菌觅食算法(BFA)有相似之处。在位置更新方程中,FA和PSO都有两个主要分量:一个是确定性的,另一个是随机性的。在FA中,吸引力由两个组成部分决定:目标函数和距离,而在BFA中,细菌之间的吸引力也有两个组成部分:适应度和距离。萤火虫算法实现时,整个种群(如n)需要两个内循环,特定迭代需要一个外循环(如I),因此最坏情况下FA的计算复杂度为O(n2I)。

三、部分源代码

%求解0-1背包问题的改进萤火虫群算法(WGFA)
%设置参数:步长因子alpha=0.5,吸引度beta0=1,介质吸收因子gama=1,
%萤火虫的亮度即目标函数值
clc
clear all
close all
%% 
%初始化参数
alpha=0.2;      % 步长因子Randomness 0--1
gamma=1.0;      % 介质吸收因子
beta0=1.0;       %最大吸引度
wmax=1;wmin=0.05;%权重,用于计算线性递减惯性权重
Pm=0.1;%变异概率
%%
%对当前解用改进贪心算法修复,使不可行解变为可行解,并使可行解尽量增加其价值
function [xn]=f_GA(xn,M,n,V,P,W)
[fn,index]=sort(P./W,'ascend');
coresV=sum((W.*xn)');%当前背包重量 for i=1:M if coresV(i)>V for j=1:n if xn(i,index(j))==1 coresV(i)=coresV(i)-W(index(j)); if coresV(i)>V xn(i,index(j)) = 0; else xn(i,index(j)) = 0; break end end end end rest=[];index2=[]; for k=1:n if xn(i,index(k))==0 rest(end+1)=fn(index(k)); index2(end+1)=index(k); end end rest=fliplr(rest);index2=fliplr(index2); for j=1:size(rest,2) coresV(i)=coresV(i)+W(index2(j)); if coresV(i)<V xn(i,index2(j))=1; continue else coresV(i)=coresV(i)-W(index2(j)); end end end end 

四、运行结果

在这里插入图片描述

五、matlab版本及参考文献

1 matlab版本 2014a

2 参考文献 [1] 包子阳,余继周,杨杉.智能优化算法及其MATLAB实例(第2版)[M].电子工业出版社,2016. [2]张岩,吴水根.MATLAB优化算法源代码[M].清华大学出版社,2017.

今天的文章【背包问题】基于matlab萤火虫算法求解背包问题【含Matlab源码 1440期】分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/15989.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注