基于混合VNS（变邻域搜索算法）的PSO（粒子群优化算法）的任务分配问题（Matlab代码实现）

💥💥💞💞欢迎来到本博客❤️❤️💥💥

🏆博主优势：🌞🌞🌞博客内容尽量做到思维缜密，逻辑清晰，为了方便读者。

⛳️座右铭：行百里者，半于九十。

目录

💥1 概述

📚2 运行结果

🎉3 参考文献

👨‍💻4 Matlab代码实现

💥1 概述

    PSO算法最早是由Kennedy和Eberhart提出的;它的基本原理源于对鸟群捕食行为的仿真.目前对PSO算法的研究主要集中在连续型的PSO算法,即描述粒子状态及其运动规律的量都是连续型的.而对离散粒子群优化(Discrete Particle Swarm ()ptimization,DPSO)算法的研究甚少.只有ClerC提出用于求解TSP问题的DPSO算法,但其性能与其它算法(如蚁群算法)相比仍有一定差距.

     独立任务的分配问题不仅存在于计算机并行计算、操作系统等计算机技术领域,而且还广泛存在于工农业生产、交通运输及服务行业.它通常以总完成时间最短为目标函数,是一个NP-困难的组合优化问题,不存在多项式时间复杂性的算法以找到全局最优解.尽管文献中已有许多启发式算法试图去获取优质解,但是解的质量还是不能令人满意.本文基于一种混合VNS(变邻域搜索算法)的PSO(粒子群优化算法)用以解决拦截对抗中的任务分配问题，新的算法能够有效地避免粒子群陷入局部收敛，并且解决离散优化问题。

📚2 运行结果

ultimate distribute matrix:
         0         0         0         0         0         0    0.0806    0.9194
         0         0    1.0000         0         0         0         0         0
         0         0         0         0         0         0    1.0000         0
         0         0         0         0         0    1.0000         0         0
         0         0         0    1.0000         0         0         0         0
    1.0000         0         0         0         0         0         0         0
         0    1.0000         0         0         0         0         0         0
         0         0         0         0         0    1.0000         0         0
    1.0000         0         0         0         0         0         0         0
         0         0         0         0    1.0000         0         0         0
 
ultimate fitness value:
  146.8842
 
时间已过 4.112748 秒。

部分代码：

maxgen = 100;   % number of iterations
sizepop = 50;   % Population size
Vmax = 1;  % limits of velocity
Vmin = -1;
popmax = 1;   % limits of position
popmin = 0;

% original population
for i = 1:sizepop
    % obtain a particle swarm randomly
    popi = popmin + (popmax - popmin)*rand(numP, numE);
    for k = 1:numP
        popi(k,:) = popi(k,:)/sum(popi(k,:));
    end
    pop(i,:,:) = popi;   % original postion
    V(i,:,:) = Vmin + (Vmax - Vmin)*rand(numP, numE);   % original velocity
    % caculate fitness value
    fitness(i) = fitnessf(squeeze(pop(i,:,:)), P, E);
end

% Individual and global extremums of the initial population
[bestfitness bestindex] = max(fitness);
zbest = pop(bestindex,:,:);   % global extremums
gbest = pop;    % Individual extremums
fitnessgbest = fitness;   % Individual extremums fitness value
fitnesszbest = bestfitness;   % global extremums fitness value

% iterations
for i = 1:maxgen
    for j = 1:sizepop
        % velocity update
        V(j,:,:) = omg*V(j,:,:) + c1*rand*(gbest(j,:,:) - pop(j,:,:)) + c2*rand*(zbest - pop(j,:,:));
        
        % position update
        pop(j,:,:) = pop(j,:,:) + V(j,:,:);
        pop(j,find(pop(j,:,:)<0)) = 0;
        popj = squeeze(pop(j,:,:));
        for k = 1:numP
            popj(k,:) = popj(k,:)/sum(popj(k,:));
        end
        pop(j,:,:) = popj;
        
        % caculate fitness value
        fitness(j) = fitnessf(squeeze(pop(j,:,:)), P, E);
        
        Fhistory(i, j) = fitness(j);
        
        
    end
    for j = 1:sizepop
        % individual extremum update
        if fitness(j) > fitnessgbest(j)
            gbest(j,:,:) = pop(j,:,:);
            fitnessgbest(j) = fitness(j);
        end
        
        % global extremum update
        if fitness(j) > fitnesszbest
            zbest = pop(j,:,:);
            fitnesszbest = fitness(j);
        end
    end
    % vns strategy
    for j = 1:sizepop
        popj = squeeze(pop(j,:,:));
        if i > 3
            if (Fhistory(i, j) - Fhistory(i-1, j)) < 1e-4
                if (Fhistory(i, j) - Fhistory(i-2, j)) < 1e-4
                    if mod(i, 15) == 0
                        if j == 1
                            disp('vns going');
                        end
                        omg = 0.4;
                        % vns strategy
                        [popjn, isupdate] = vns(popj, P, E);
                        pop(j,:,:) = popjn;
                        tmptfitness = fitnessf(popjn, P, E);
                        % individual extremum update
                        if isupdate
                            gbest(j,:,:) = popjn;
                            fitnessgbest(j) = tmptfitness;
                        end
                        % global extremum update
                        if tmptfitness > fitnesszbest
                            zbest = pop(j,:,:);
                            fitnesszbest = tmptfitness;
                        end
                    end
                end
            end
        end
        
    end
    
    yy(i) = fitnesszbest; % fitness value each iteration
    disp(i);
    disp(squeeze(pop(1, :, :)));
end
 

 

 

🎉3 参考文献

[1]钟一文,杨建刚.独立任务分配问题的离散粒子群优化算法[J].模式识别与人工智能,2006,19(03):399-405.

👨‍💻4 Matlab代码实现