粒子群算法求解0-1背包问题

目录

一、粒子群算法的概念

二、粒子群算法分析

三、粒子群算法种类

1.基本粒子群算法

2.标准粒子群算法

3.压缩粒子群算法

4.离散粒子群算法

四、粒子群算法流程

五、例题

---

一、粒子群算法的概念

  粒子群优化算法(PSO：Particle swarm optimization) 是一种进化计算技术（evolutionary computation）。源于对鸟群捕食的行为研究。粒子群优化算法的基本思想：是通过群体中个体之间的协作和信息共享来寻找最优解．
  PSO的优势：在于简单容易实现并且没有许多参数的调节。目前已被广泛应用于函数优化、神经网络训练、模糊系统控制以及其他遗传算法的应用领域。

二、粒子群算法分析

  粒子群算法通过设计一种无质量的粒子来模拟鸟群中的鸟，粒子仅具有两个属性：速度和位置，速度代表移动的快慢，位置代表移动的方向。每个粒子在搜索空间中单独的搜寻最优解，并将其记为当前个体极值，并将个体极值与整个粒子群里的其他粒子共享，找到最优的那个个体极值作为整个粒子群的当前全局最优解，粒子群中的所有粒子根据自己找到的当前个体极值和整个粒子群共享的当前全局最优解来调整自己的速度和位置。下面的动图很形象地展示了PSO算法的过程：

三、粒子群算法种类

1.基本粒子群算法

假设在一个维的目标搜索空间中，有个粒子组成一个群体，其中第i个粒子表示为一个维的向量：

第i个粒子的飞行速度也是一个D维的向量，记为

第i个粒子迄今为止搜索到最优位置称为个体极值，记为

整个粒子群迄今位置搜索到的最优位置为全局极值，记为

在找到这两个最优值是，粒子根据如下公式来更新自己的速度和位置

2.标准粒子群算法

带有惯性权重的改进粒子群算法，该算法能够保证较好 的收敛效果。 

惯性权重表示在多大程度上保留原来的速度：w越大，则全局收敛能力较强，局部收敛能力较弱；在0.8~1.2之间时，粒子群算法有更快收敛速度，当，算法容易陷入局部极值

在算法开始时可给赋予较大正值，随着搜索进行，可以线性地使主键减小。目前，采用较多的动态惯性权重值时Shi提出的线性递减权值策略，其表达式如下 

3.压缩粒子群算法

利用约束因子控制系统行为的最终收敛。压缩因子更新公式。

式中为压缩因子

4.离散粒子群算法

基本粒子群算法时在连续域中搜索函数极值，下面是一种离散二进制版的粒子群算法。在此离散粒子群方法中，将离散问题空间映射到连续粒子运动空间，并适当求改粒子群算法来求解，在计算上仍保留经典粒子群算法速度-位置更新运算规则。

是从产生的随机数。 

四、粒子群算法流程

粒子群算法基于“种群”和“进化”的概念，通过个体间的协作与竞争，实现复杂空间最优解的搜索，其流程如下：

1）初始化粒子群，包括群体规模N，每个粒子的位置x和速度v

2）计算每个粒子的适应度值

3）对每个粒子，用它的适应度值和个体极值比较。如果，则用替换掉

4）对每个粒子，用它的适应度值和全局极值t比较。如果，则用替换

5）迭代更新粒子的速度和位置

6）进行边界条件处理

7）判断算法终止条件是否满足：若是，则结束算法并输出优化结果：否则返回步骤2）

  

五、例题

0-1背包问题。有件物品和一个容量为的背包。第件物品的体积是，价值是。求解将哪些物品放入背包可使物品的体积总和不超过背包的容量，且价值总和最大。假设物品数量为10，背包的容量为300.每件物品的体积为，价值为

仿真过程如下

1）初始化种群粒子个数，粒子维数，最大迭代次数为，学习因子，惯性权重最大值，惯性权重最小值为，速度最大值，速度最小值。

2） 初始化速度和二进制编码的种群粒子位置，其中1表示选择该物品，0表示不选择该物品。取适应度值进行惩罚计算。获得粒子个体最优位置和最优值，以及粒子群全局最优位置和最优值

3）计算动态惯性权重值，更新速度值，并进行边界条件处理，更新二进制编码的位置x，计算适应度值，判断是否替换粒子个体最优位置和最优值，以及粒子群全局最优位置和最优值

4）判断是否满足终止条件：若满足，则结束搜索过程，输出最优值；若不满足，则继续进行迭代优化

%%%%%%%%%%%%%%%%%离散粒子群算法解决0-1背包问题%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%初始化%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
clear all;              %清除所有变量
close all;              %清图
clc;                    %清屏
N=100;                  %群体粒子个数
D=10;                   %粒子维数
T=200;                  %最大迭代次数
c1=1.5;                 %学习因子1
c2=1.5;                 %学习因子2
Wmax=0.8;               %惯性权重最大值
Wmin=0.4;               %惯性权重最小值
Vmax=10;                %速度最大值
Vmin=-10;               %速度最小值
V = 300;                             %背包容量
C = [95,75,23,73,50,22,6,57,89,98];  %物品体积
W = [89,59,19,43,100,72,44,16,7,64]; %物品价值
afa = 2;                             %惩罚函数系数
%%%%%%%%%%%%%%%%初始化种群个体（限定位置和速度）%%%%%%%%%%%%%%%%
x=randi([0,1],N,D);        %随机获得二进制编码的初始种群
v=rand(N,D) * (Vmax-Vmin)+Vmin;
%%%%%%%%%%%%%%%%%%初始化个体最优位置和最优值%%%%%%%%%%%%%%%%%%%
p=x;
pbest=ones(N,1);
for i=1:N
    pbest(i)= func4(x(i,:),C,W,V,afa);
end
%%%%%%%%%%%%%%%%%%%初始化全局最优位置和最优值%%%%%%%%%%%%%%%%%%
g=ones(1,D);
gbest=eps;
for i=1:N
    if(pbest(i)>gbest)
        g=p(i,:);
        gbest=pbest(i);
    end
end
gb=ones(1,T);
%%%%%%%%%%%按照公式依次迭代直到满足精度或者迭代次数%%%%%%%%%%%%%
for i=1:T
    for j=1:N
        %%%%%%%%%%%%%%更新个体最优位置和最优值%%%%%%%%%%%%%%%%%
        if (func4(x(j,:),C,W,V,afa)>pbest(j))
            p(j,:)=x(j,:);
            pbest(j)=func4(x(j,:),C,W,V,afa);
        end
        %%%%%%%%%%%%%%%%更新全局最优位置和最优值%%%%%%%%%%%%%%%
        if(pbest(j)>gbest)
            g=p(j,:);
            gbest=pbest(j);
        end
        %%%%%%%%%%%%%%%%计算动态惯性权重值%%%%%%%%%%%%%%%%%%%%
        w=Wmax-(Wmax-Wmin)*i/T;
        %%%%%%%%%%%%%%%%%跟新位置和速度值%%%%%%%%%%%%%%%%%%%%%
        v(j,:)=w*v(j,:)+c1*rand*(p(j,:)-x(j,:))...
            +c2*rand*(g-x(j,:));
        %%%%%%%%%%%%%%%%%%%%边界条件处理%%%%%%%%%%%%%%%%%%%%%%
        for ii=1:D
            if (v(j,ii)>Vmax)  |  (v(j,ii)< Vmin)
                v(j,ii)=rand * (Vmax-Vmin)+Vmin;
            end
        end    
        vx(j,:)=1./(1+exp(-v(j,:)));
        for jj=1:D
            if vx(j,jj)>rand
                x(j,jj)=1;
            else
                x(j,jj)=0;
            end
        end      
    end
    %%%%%%%%%%%%%%%%%%%%记录历代全局最优值%%%%%%%%%%%%%%%%%%%%%
    gb(i)=gbest;
end
g;                       %最优个体 
figure
plot(gb)
xlabel('迭代次数');
ylabel('适应度值');
title('适应度进化曲线')
%%%%%%%%%%%%%%%%%%适应度函数%%%%%%%%%%%%%%%%%
function result = func4(f,C,W,V,afa)
fit = sum(f.*W);
TotalSize = sum(f.*C);
if TotalSize <= V
    fit = fit;
else
    fit = fit - afa * (TotalSize - V);
end
result = fit;
end