GSO package人工萤火虫群背包问题

MATLAB实现的人工萤火虫群优化算法，解决背包问题

%求解0-1背包问题的人工萤火虫群优化算法
clc
clear all

a=[94 4 60 32 23 72 80 62 65 46];%物品的体积
c=[55 10 47 5 4 50 8 61 85 87];%物品的价值
b=269;%背包的容量限制，背包能够装的物品体积或重量的最大值
%a、b、c的数据来自参考文献
%% 
n=10;%萤火虫的个数
Dim=size（a2）;%处理问题的维数，与背包问题中物品的数量相同
iter_max=3;%最大迭代次数
runtime=1;

L0=5;%荧光素初值
R0=3;%动态决策域的初值
beta=0.08;%动态决策域的更新率
nt=5;%邻域个数的阈值
s=0.03;%步长
gama=0.6;%荧光素更新率
rho=0.4;%荧光素消失率
t=2;%迭代次数初值

Rs=5;%可视范围初值，感知范围
Rd=zeros（niter_max）;%生成一个n行iter_max列的矩阵，每一行代表一只萤火虫在每一代的动态决策域
P=zeros（nniter_max）;
L=zeros（niter_max）;%生成一个n行iter_max列的矩阵，每一行代表一只萤火虫在每一代的荧光素值
A=repmat（an1）;%将矩阵a复制n×1块，存储物品的体积
C=repmat（cn1）;%将矩阵c复制n×1块存储物品的价值
Nei=cell（niter_max）;%记录每只萤火虫在每一次迭代时的邻域

%随机分配个体荧光素及动态决策域
for i=1:n
    L（i1）=L0;%所有萤火虫在算法迭代初期的初始荧光素值都是L0
    Rd（i1）=R0;%所有萤火虫在算法迭代初期的初始动态决策域值都是R0
end



for r=1:runtime
%第i个萤火虫在t时刻的位置初始化
X=round（rand（nDim））;%随即取一个n×Dim的0-1矩阵作为萤火虫的初始位置
                     %每一行代表一种背包装物品的状态，1代表对应物品装入背包，0代表不装入
%%  
tic;
final_fxbest=zeros（1t）;
final_X=zeros（tDim）;
while t    
    %for i=1:n
        fX=sum（（C.*X）‘）;%计算每一个萤火虫位置的适应度值，即背包内物品的价值
        sX=sum（（A.*X）‘）;%限制函数，计算一个背包内所有物品的体积
    %end
    for i=1:n
        if sX（i）>b%背包内物品的体积超过最大限制
            fX（i）=0;%当背包内物品的体积超过限制时，将其适应度值设置为1
        end
    end
    for i=1:n
        L（it）=（1-rho）*L（i（t-1））+gama*fX（i）;%荧光素更新公式
    end
    fX
    %位置移动规则
    for i=1:n
        for j=1:n
            %如果X（j:）在X（i:）可视范围内，并且X（j:）的荧光素值大于X（i:），
            %则X（j:）是X（i:）的一个邻居，
            if（norm（X（j:）-X（i:））                Nei{it}=[jNei{it}];%获取邻域Nei
            end
        end
    end
    tempsum=zeros（1n）;
    for i=1:n
        for j=Nei{it}
            j
            %计算每只萤火虫的邻域内所有邻居的荧光素之和
            tempsum（i）=L（jt）-L（it）+tempsum（i）;
        end
    end
    tempsum
    %移动概率的计算
    for i=1:n
        for j=Nei{it}
            %路径选择概率公式，萤火虫i选择萤火虫j并向其移动的概率
            P（ijt）=（L（jt）-L（it））/tempsum（i）;
        end
    end
    for i=1:n
        if isempty（Nei{it}）%如果萤火虫i的邻域为空
            %XX=X（i:）;
            Rd（it+1）=min（Rsmax（0Rd（it）+beta*（nt-length（Nei{it}））））;%决策域更新公式
        else
            for j=Nei{it}
                if P（ijt）==max（P（i:t））&&P（ijt）~=0
                    SeJ=j;%选择最好的移动方向
                    %位置更新
                    X（i:）=X（i:）+s.*（X（SeJ:）-X（i:））/norm（X（SeJ:）-X（i:））;
                    Rd（it+1）=min（Rsmax（0Rd（it）+beta*（nt-length（Nei{it}））））;%决策域更新公式
                end
            end
        end
        sxbest（i）=sum（（a.*X（i:））‘）;%存储每一只萤火虫对应背包内的物品总体积
        fxbest（i）=sum（（c.*X（i:））‘）;%存储每一只萤火虫对应背包内的物品总价值
    end
    jieguo=zeros（1n）;%临时存储运算结果
    for i=1:n
        %如果一只萤火虫对应背包的体积在限制范围之内，则视为有效，存储在矩阵jieguo中
        if sxbest（i）            jieguo（i）=1;
        else
            jieguo（i）=0;
            sxbest（i）=0;
            fxbest（i）=0;
            X（i:）=round（rand（1Dim））;
        end
    end
    %寻找ji

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       4221  2012-10-13 15:14  GSO_package.m

----------- ---------  ---------- -----  ----

                 4221                    1