【三维装箱】基于matlab粒子群算法求解三维装箱优化问题【含Matlab源码 950期】

一、简介

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

2 粒子群算法分析
2.1基本思想
粒子群算法通过设计一种无质量的粒子来模拟鸟群中的鸟,粒子仅具有两个属性:速度和位置,速度代表移动的快慢,位置代表移动的方向。每个粒子在搜索空间中单独的搜寻最优解,并将其记为当前个体极值,并将个体极值与整个粒子群里的其他粒子共享,找到最优的那个个体极值作为整个粒子群的当前全局最优解,粒子群中的所有粒子根据自己找到的当前个体极值和整个粒子群共享的当前全局最优解来调整自己的速度和位置。下面的动图很形象地展示了PSO算法的过程:
【三维装箱】基于matlab粒子群算法求解三维装箱优化问题【含Matlab源码 950期】
2 更新规则
PSO初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每一次的迭代中,粒子通过跟踪两个“极值”(pbest,gbest)来更新自己。在找到这两个最优值后,粒子通过下面的公式来更新自己的速度和位置。
【三维装箱】基于matlab粒子群算法求解三维装箱优化问题【含Matlab源码 950期】
公式(1)的第一部分称为【记忆项】,表示上次速度大小和方向的影响;公式(1)的第二部分称为【自身认知项】,是从当前点指向粒子自身最好点的一个矢量,表示粒子的动作来源于自己经验的部分;公式(1)的第三部分称为【群体认知项】,是一个从当前点指向种群最好点的矢量,反映了粒子间的协同合作和知识共享。粒子就是通过自己的经验和同伴中最好的经验来决定下一步的运动。以上面两个公式为基础,形成了PSO的标准形式。
【三维装箱】基于matlab粒子群算法求解三维装箱优化问题【含Matlab源码 950期】
公式(2)和 公式(3)被视为标准PSO算法。
3 PSO算法的流程和伪代码
【三维装箱】基于matlab粒子群算法求解三维装箱优化问题【含Matlab源码 950期】

二、源代码

 
clc;clear;close all;
Vmax = 1;%速度限制
Vmin = -1;
nodes=50;%节点数目
links=150;%边数目
dims=nodes*(nodes-1)/2;%种群维数
c1 = 1.49445;
c2 = 1.49445;
maxgen = 300;    %进化次数
sizepop = 100;   %种群规模
% 惯性权重
w=1;
% 线性递减惯性权重
w_max=0.9;
w_min=0.4;
pop=zeros(sizepop,dims);%初始化种群
trans_index=zeros(1,dims);%初始化转换索引
%% 产生初始粒子和速度
for iter = 1:sizepop
    %初始化种群
    xx=randperm(nodes);
    yy=randperm(nodes);
    A=zeros(nodes,nodes);%连通阵,AA的迹为0
    linkscount=1;
    while linkscount<links+1
        edge_a=randi([1,nodes],1,1);%随机产生两个数,表示两个点的序号
        edge_b=randi([1,nodes],1,1);
        if edge_a~=edge_b
             if A(edge_a,edge_b)==0   %保证随机生成的边不重复
                 A(edge_a,edge_b)=1;
                 A(edge_b,edge_a)=1;
                 linkscount=linkscount+1;%表示成功的生成一个link
             end
        else
            A(edge_a,edge_b)=0;
%             linkscount=linkscount+1;%表示成功的生成一个link
        end
    end
    %将邻接矩阵转换为粒子向量
    k=1;
    for i=1:nodes
        for j=1:nodes
            if(i>j)
                index=sub2ind(size(A),i,j); %取出对角线以上索引
                pop(iter,k)=A(index);%按照索引展开为向量
                trans_index(1,k)=index;%保存索引在向量转为邻接矩阵时使用
                k=k+1;
            end
        end
    end
    disp(A);
%     % 将粒子向量转换为邻接矩阵,经验证可以正常恢复
%     G=zeros(nodes,nodes);
%     [row col]=ind2sub(size(A),trans_index);
%     for s=1:length(trans_index)
%         G(row(s),col(s))=pop(iter,s);     
%     end
%     G=G+G';
%     sum(A(:))
    V(iter,:) = (Vmax-Vmin)*rand(1,dims)+Vmin;       %初始化速度
    %计算适应度
    fitness(iter) = fitness_fun(A);   %计算适应度
    
end
%% 个体极值和群体极值
[bestfitness bestindex] = max(fitness); %bestindex:全局最优粒子索引
gbest = pop(bestindex,:);   %全局最佳位置
pbest = pop;    %个体最佳
fitnesspbest = fitness;   %个体最佳适应度值
fitnessgbest = bestfitness;   %全局最佳适应度值
 
%% 迭代寻优
for i = 1:maxgen       %代数更迭
 %    w=-(4/300^2)*i^2+4/300*i+0.4;
    for j = 1:sizepop  %遍历个体
        % 速度更新
        V(j,:) = w*V(j,:) + c1*rand*(pbest(j,:) - pop(j,:)) + c2*rand*(gbest - pop(j,:));
        %速度边界处理
        V(j,find(V(j,:)>Vmax)) = Vmax;
        V(j,find(V(j,:)<Vmin)) = Vmin;
        %统计种群中1的个数
        W=sum(pop(j,:));
        % 种群更新
        pop(j,:) = pop(j,:) + V(j,:);
        %位置边界处理
        pop(j,find(pop(j,:)>=0.5)) = 1;
        pop(j,find(pop(j,:)<0.5)) = 0;
        %比较更新种群与原种群1的个数
        M=sum(pop(j,:));
        if M<W %随机挑选W-M个0变为1
            index0=find(pop(j,:)==0);
            c=1;
            while c<=W-M
                mid=unidrnd(length(index0));
                if pop(j,index0(mid))==0
                    pop(j,index0(mid))=1;
                    c=c+1;
                end
            end
        end
        if M>W %随机挑选M-W个1变为0
            index1=find(pop(j,:)==1);
            k=1;
            while k<=M-W
                mid1=unidrnd(length(index1));
                if pop(j,index1(mid1))==1
                    pop(j,index1(mid1))=0;
                    k=k+1;
                end
            end
        end
        % 将粒子向量转换为邻接矩阵
        G=zeros(nodes,nodes);
        [row col]=ind2sub(size(A),trans_index);
        for s=1:length(trans_index)
            G(row(s),col(s))=pop(j,s);     
        end
        G=G+G';
        % 适应度值更新
        fitness(j) = fitness_fun(G);
    end
    for j = 1:sizepop
        % 个体最优更新
        if fitness(j) > fitnesspbest(j)
            pbest(j,:) = pop(j,:);
            fitnesspbest(j) = fitness(j);
        end
        % 群体最优更新
        if fitness(j) > fitnessgbest
            gbest = pop(j,:);
            fitnessgbest = fitness(j);
        end
    end
    record(1,i)=fitnessgbest;
    fprintf('%d      %f\n',i,fitnessgbest);  %输出结果
%% 适应度值变化绘图
plot(record);
xlabel('gen');
ylabel('fitness');
end

三、运行结果

【三维装箱】基于matlab粒子群算法求解三维装箱优化问题【含Matlab源码 950期】

四、备注

版本:2014a

上一篇:Python爬虫的xpath使用的技巧


下一篇:Leetcode 24:Swap Nodes in Pairs