基于混合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 參考文獻

👨‍💻4 Matlab代碼實作