Parçacık Sürü Optimizasyonu Algoritması (PSO)

 

Sezgisel algoritmalar, büyük boyutlu optimizasyon problemleri için, kabul edilebilir sürede optimuma yakın çözümler verebilen algoritmalardır. Genel amaçlı sezgisel optimizasyon algoritmaları, biyoloji tabanlı, fizik tabanlı, sürü tabanlı, sosyal tabanlı, müzik tabanlı ve kimya tabanlı olmak üzere altı farklı grupta değerlendirilmektedir. Sürü zekâsı tabanlı optimizasyon algoritmaları kuş, balık, kedi ve arı gibi canlı sürülerinin hareketlerinin incelenmesiyle geliştirilmiştir [1].

Sezgisel optimizasyon yöntemlerine örnek olarak;

  • Genetik Algoritma (Genetic Algorithm)(GA)
  • Karınca Kolonisi Optimizasyonu (Ant Colony Optimization)(ACO)
  • Parçacık Sürü Optimizasyonu (Particle Swarm Optimization)(PSO)
  • Yapay Arı Kolonisi (Artificial Bee Colony)(ABC)
  • Diferansiyel Gelişim Algoritması (Differential Evolution Algorithm) (DEA)

.

.

.

Bu yazımızda PSO ile ilgileneceğiz ve PSO algoritması kullanarak parçacıkların x-y koordinat sisteminde bir noktada toplanmalarını sağlayacağız.

 

Parçacık sürü optimizasyonu, 1995 yılında Dr.Eberhart ve Dr.Kennedy tarafından geliştirilmiş popülasyon temelli sezgisel bir optimizasyon tekniğidir. Genel olarak PSO, her parçacığa rastgele konum atar ve her tekrarda belirli formüllerle konumları değiştirir. Aralarındaki en iyi konumu genel (global) olarak tanımlar ve diğer parçacıkların her tekrarda bu global değere yaklaşmasını sağlar. Aşağıdaki PSO algoritmasının akış diyagramı ile işleyiş daha iyi anlaşılabilir.

PSO ALGORİTMASI

flowchart

extra

 

PSO algoritmasını incelemek için, parçacıkların koordinat sisteminde istediğimiz bir noktada toplanmalarını ele alacağız. Bu sorunu Matlab’da çözümledik.

Matlab Kodu =>

%%% FONKSİYON KODU %%%
function z = distance(x,target)
 
z = sqrt(sum(((x(1,1)-target(1,1)).^2) + ((x(1,2)-target(1,2)).^2)));
 
 
end

 

%%% PSO ALGORİTMA KODU %%%
clc;
clear;
close all;
 
while 1
%Bu satırları kullanarak komut penceresinden input alınabilir.   
% prompt = 'Target=? '; 
% target = input(prompt);
 
figure(1)
xlabel('x coordinate ');
ylabel('y coordinate ');
grid on
axis([-50 50 -50 50])
title('Click on a coordinate as the target')
target = ginput(1); % Grafik üzerinden bir kordinata tıklanarak input alınacak.
 
distanceFunction = @(x,target) distance(x,target);  % Fonksiyon tanımlandı.
 
nVar = 2; 
VarSize = [1 nVar]; % Her parçacığın x ve y kordinatlarını tanımlamak için
VarMin = -10; % Her parçacığın ilk konumu rastegele seçilirken sınırlandırma için min. ve max. değerleri
VarMax = 10;
MaxIt = 140; % Her parçacığın hedefe gitmesi için tekrarlanma sayısı
nPop = 200; % parçacık sayısı
w = 1; % inertia coefficient
c1 = 2; % cognitive coefficient 
c2 = 2; % social coefficient
Positions = zeros(nPop,nVar); % (parçacık sayısı,pozisyon değer sayısı)
BestPos = zeros(MaxIt, 2);
% Her parçacığa pozisyon, hız, mesafe, en iyi pozisyon ve en iyi mesafe
% şeklinde başta boş olmak üzere tanımlamalar yapıldı.
empty_particle.Position = [];
empty_particle.Velocity = [];
empty_particle.distance = [];
empty_particle.Best.Position = [];
empty_particle.Best.distance = [];
particle = repmat(empty_particle,nPop,1);
GlobalBest.distance = Inf;
 
 for i=1:nPop % Her parçacık için tekrar et 
 
 particle(i).Position = unifrnd(VarMin, VarMax, VarSize); % İlk konumu rastgele belirle
 particle(i).Velocity = zeros(VarSize); % İlk hızı sıfır olarak belirle
 particle(i).distance = distanceFunction(particle(i).Position,target); % İlk mesafe değerini belirle
 particle(i).Best.Position = particle(i).Position; % Her poziyonu en iyi pozisyon olarak belirle
 particle(i).Best.distance = particle(i).distance; % Her mesafe değerini en iyi mesafe olarak belirle
 
    if particle(i).Best.distance < GlobalBest.distance % İlk pozisyonlar için global en iyi değerleri belirle (global en iyi pozisyon ve global en iyi mesafe)
       GlobalBest = particle(i).Best; 
    end   
 end
 
 for it=1:MaxIt % Tekrarlanma sayısı kadar tekrarla
 
    for i=1:nPop % Her parçacık için tekrar et 
 
        for a=1:nPop  
        Positions(a, :) = [particle(a).Position]; % Her parçacığın pozisyon değerlerini 'Positions' matrisine sırayla ata.
        end
 
  % PSO sonucu belirlenen bir sonraki hız ve pozisyon bulma formülleri  
    particle(i).Velocity = w*particle(i).Velocity...
    + c1*rand(VarSize).*(particle(i).Best.Position - particle(i).Position)...
    + c2*rand(VarSize).*(GlobalBest.Position - particle(i).Position);
 
    particle(i).Position = particle(i).Position + particle(i).Velocity;
    particle(i).distance = distanceFunction(particle(i).Position,target);
 
         if particle(i).distance < particle(i).Best.distance % Eğer yeni mesafe, bir önceki en iyi mesafesinden daha küçük ise;
         particle(i).Best.Position = particle(i).Position;   % Yeni pozisyon, en iyi pozisyonu olsun. 
         particle(i).Best.distance = particle(i).distance;   % Yeni mesafe, en iyi mesafesi olsun.
 
            if particle(i).Best.distance < GlobalBest.distance % Eğer yeni en iyi mesafe, global en iyi mesafeden küçük ise;
            GlobalBest = particle(i).Best;                     % O parçacığın en iyi değerleri global olarak atansın.
            end
         end
    end
    BestPos(it,:) = GlobalBest.Position; % Her tekrarlanma aşamasının global en iyi pozisyon değerini 'BestPos' matrisine kaydet
 
    w = w - w*it/MaxIt; % inertia coefficient değerini her tekrarlanmada azalt 
 
 
    %%% HER TEKRARLANMADA PARÇACIKLARIN KONUMLARINI GRAFİKTE GÖSTER %%%
    figure(1);
    plot(Positions(:, 1), Positions(:, 2), 'x')
    xlabel('x coordinate ');
    ylabel('y coordinate ');
    title(['Iteration = ' num2str(it) ',    Target = ' num2str(target) ',    Best Position = ' num2str(BestPos(it,:))])
    grid on
    axis([-50 50 -50 50])
 
 
    %%% BU GRAFİKLE DE TEK BİR PARÇACIĞIN HEDEFE VARANA KADAR HAREKETİ GÖZLEMLENEBİLİR
%     figure(2);
%     plot(Positions(1, 1), Positions(1, 2), 'x')
%     xlabel('x coordinate ');
%     ylabel('y coordinate ');
%     grid on
%     axis([-50 50 -50 50])
 
    pause(.1) % Her tekrarda parçacıkların hareketini gözlemleyebilmek için, her tekrarda .1 saniye bekle
 
 end
 
 
 
end

Grafik Üzerinde simülasyonu =>

Kodu indirmek için => https://drive.google.com/drive/folders/1Y4VdOMyrUAgUOVgzp3QyiKmnBSC0huL-?usp=sharing

Algoritma Hakkında Daha detaylı Bağlantılar =>

https://www.cs.tufts.edu/comp/150GA/homeworks/hw3/_reading6%201995%20particle%20swarming.pdf

http://dergipark.gov.tr/download/article-file/384717

http://web.firat.edu.tr/iaydin/bmu579/bmu_579_bolum3.pdf

https://www.bilalsaim.com/pso-parcacik-suru-algorimtasi-particle-swarm-optimization-h1634

http://dergipark.gov.tr/download/article-file/519231

http://dergipark.gov.tr/download/article-file/94944

http://www.alicavuslu.gen.tr/2019/03/21/parcacik-suru-optimizasyon-algoritmasi-ile-yapay-sinir-agi-egitimi/

 

Formüllerin çıkışını anlamak için yararlı bir YouTube videosu =>

 

 

 

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir

This site uses Akismet to reduce spam. Learn how your comment data is processed.