粒子群优化算法解决背包问题

粒子群算法解决背包问题的MATLAB程序

%0－1背包问题:对于n个体积为aj、价值分别为cj的物品，如何将它们装入总体积为b的背包中，使得所选物品的总价值最大。
%n＝10
%aj=[95 4 60 32 23 72 80 62 65 46]
%cj=[55 10 47 5 4 50 8 61 85 87]
%b=269
%
%
a=[95 4 60 32 23 72 80 62 65 46];%物品的体积
c=[55 10 47 5 4 50 8 61 85 87];%物品的价值
b=269;%背包的重量限制
%
%
%初始化程序:
Dim=10;%粒子的维数
xSize=20;%种群数  
MaxIt=30;%最大迭代次数
c1=0.7;
c2=0.7;%定义加速因子
w=0.8;%定义惯性因子
%
web -browser http://www.ilovematlab.cn/thread-12680-1-1.html

A=repmat（axSize1）;%将a扩展成一个30*10的矩阵
C=repmat（cxSize1）;%将c扩展成一个30*10的矩阵
x=round（rand（xSizeDim））;%随机取一个30*10的0/1矩阵作为粒子的初始位置
v=rand（xSizeDim）;%粒子的初始速度
xbest=zeros（xSizeDim）;%单个粒子的初始最佳位置
fxbest=zeros（xSize1）;%xbest的适应度
gbest=zeros（1Dim）;%粒子群的初始最佳位置
fgbest=0;%gbest的适应度
%
%
%粒子群最优位置和单个粒子最优位置的选定
%迭代循环算法:
iter=0;
while iter    iter=iter+1;
    fx=sum（（C.*x）‘）;%计算粒子群的适应度即背包内物品的价值
    sx=sum（（A.*x）‘）;%限制函数背包内物品的体积
    for i=1:xSize
        if sx（i）>269
            fx（i）=0;%当被包内物品的体积超过限制时将期适应度设置为1
        end
    end
    for i=1:xSize
        if fxbest（i）            fxbest（i）=fx（i）;
            xbest（i:）=x（i:）;%当粒子的适应度fx（i）大于其最佳适应度时fxbest（i）用其替代原来粒子的最佳适应度并记下此解
        end
    end
    if fgbest        [fgbestg]=max（fxbest）;
        gbest=xbest（g:）;%当存在粒子的最佳适应度fxbest（g）大于种群的最佳适应度时用其替代原来种群的最佳适应度并记下此解
    end
    for i=1:xSize
        if x（i:）==gbest
            x（i:）=round（rand（1Dim））;%为防止算法陷入局部最优，若某个粒子的位置等于种群最佳位置，将对该粒子的位置重新初始化赋值
        end
    end
    R1=rand（xSizeDim）;
    R2=rand（xSizeDim）; 
    v=v*w+c1*R1.*（xbest-x）+c2*R2.*（repmat（gbestxSize1）-x）;%用速度迭代公式产生新的速度
    x=x+v;%更新粒子群的位置
    for i=1:xSize
        for j=1:Dim
            if x（ij）<0.5
                x（ij）=0;
            else x（ij）=1;
            end
        end
    end%由于粒子的位置只有（01）两种状态此处以0.5为分界点对函数值进行离散化
end
%
%
fgbest
sgbest=sum（（a.*gbest）‘）
gbest

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

     文件       2291  2008-07-09 12:59  用PSO算法解决背包问题\beibaoPSO.m

     文件      44544  2008-07-09 13:00  用PSO算法解决背包问题\试验报告.doc

     目录          0  2008-07-09 13:00  用PSO算法解决背包问题

     文件        122  2008-05-14 18:20  Matlab中文论坛--助努力的人完成毕业设计.url

     文件       3434  2008-05-15 08:26  使用帮助：新手必看.htm

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

                50391                    5