Particle Swarm Optimization

Çakma Madara' · 20 Nis 2019

Parçacık Sürü Optimizasyonu (PSO), sürü halinde hareket eden balıklar ve böceklerden esinlenerek Kenedy ve Eberhart (1995) tarafından geliştirilmiş bir optimizasyon yöntemidir. Temel olarak sürü zekâsına dayanan bir algoritmadır. Sürü halinde hareket eden hayvanların yiyecek ve güvenlik gibi durumlarda, çoğu zaman rasgele sergiledikleri hareketlerin, amaçlarına daha kolay ulaşmalarını sağladığı görülmüştür. PSO bireyler arasındaki sosyal bilgi paylaşımını esas alır. Arama işlemi genetik algoritmalarda olduğu jenerasyon sayısınca yapılır. Her bireye parçacık denir ve parçacıklardan oluşan popülasyona da sürü (swarm) denir. Her bir parçacık kendi pozisyonunu, bir önceki tecrübesinden yararlanarak sürüdeki en iyi pozisyona doğru ayarlar. PSO, temel olarak sürüde bulunan bireylerin pozisyonunun, sürünün en iyi pozisyona sahip olan bireyine yaklaştırılmasına dayanır. Bu yaklaşma hızı rasgele gelişen durumdur ve çoğu zaman sürü içinde bulunan bireyler yeni hareketlerinde bir önceki konumdan daha iyi konuma gelirler ve bu süreç hedefe ulaşıncaya kadar devam eder. PSO, Sipariş miktarı belirleme, çizelgeleme problemleri, güç ve voltaj kontrolü, motor parametrelerini belirleme, tedarik seçimi ve sıralama problemleri gibi bir çok optimizasyon problemlerinde başarı ile kullanılmıştır. Şekil-1 de PSOnun akış diyagramını sizlere aktarmaya çalıştım.

Algoritma temel olarak aşağıdaki basamaklardan oluşur;

1. Rasgele üretilen başlangıç pozisyonları ve hızları ile başlangıç sürüsü oluşturulur.
2. Sürü içerisindeki tüm parçacıkların uygunluk değerleri hesaplanır.
3. Her bir parçacık için mevcut jenerasyondan yerel en iyi (pbest) bulunur. Sürü içerisinde en iyilerin sayısı parçacık sayısı kadardır.
4. Mevcut jenerasyondaki yerel eniyiler içerisinden küresel en iyi (gbest) seçilir.
5. Pozisyon ve hızlar aşağıdaki gibi yenilenir.

Burada Xid pozisyon ve Vid hız değerlerini verirken, rand1 ve rand2 değerleri rasgele üretilmiş sayılardır. W atalet ağırlık değeri ve C1, C2 ölçeklendirme faktörleridir.

6. Durdurma kriteri sağlanıncaya kadar 2,3,4,5 adımları tekrar edilir.

Bu adımların nasıl uygulanacağını, Python3.7 kullanarak sizlere anlatmaya çalışacağım.

Kod:

# bağımlılıkların yüklenmesi
from __future__ import division
import random
import math

# işlevi optimize etmeye çalışıyoruz
def optimize_function(x):
    total=0
    for i in range(len(x)):
        total+=x[i]**2
    return total

class Particle:
    def __init__(self,x0):
        self.position_i=[]          # parçacık konumu
        self.velocity_i=[]          # parçacık hızı
        self.pos_best_i=[]          # en iyi pozisyonu
        self.err_best_i=-1          # en iyi hata
        self.err_i=-1               # bir parçacığa ait hata

        for i in range(0,num_dimensions):
            self.velocity_i.append(random.uniform(-1,1))
            self.position_i.append(x0[i])

    # mevcut yoğunluğun değerlendirilmesi
    def evaluate(self,costFunc):
        self.err_i=costFunc(self.position_i)

        # bireysel olarak mevcut pozisyonun en iyisi olup olmadığının kontrol edilmesi
        if self.err_i < self.err_best_i or self.err_best_i==-1:
            self.pos_best_i=self.position_i
            self.err_best_i=self.err_i

    # yeni parçacık hızının güncellenmesi
    def update_velocity(self,pos_best_g):
        w=0.5       
        c1=1        
        c2=2        

        for i in range(0,num_dimensions):
            r1=random.random()
            r2=random.random()

            vel_cognitive=c1*r1*(self.pos_best_i[i]-self.position_i[i])
            vel_social=c2*r2*(pos_best_g[i]-self.position_i[i])
            self.velocity_i[i]=w*self.velocity_i[i]+vel_cognitive+vel_social

    # yeni hız güncellemelerine dayanarak parçacık konumunun güncellenmesi
    def update_position(self,bounds):
        for i in range(0,num_dimensions):
            self.position_i[i]=self.position_i[i]+self.velocity_i[i]

            # gerektiğinde maksimum pozisyonun ayarlanması
            if self.position_i[i]>bounds[i][1]:
                self.position_i[i]=bounds[i][1]

            # gerektiğinde minimum pozisyonun ayarlanması
            if self.position_i[i] < bounds[i][0]:
                self.position_i[i]=bounds[i][0]
               
class PSO():
    def __init__(self,costFunc,x0,bounds,num_particles,maxiter):
        global num_dimensions

        num_dimensions=len(x0)
        err_best_g=-1                   # grup için en iyi hata
        pos_best_g=[]                   # grup için en iyi pozisyon


        # sürünün kurulması
        swarm=[]
        for i in range(0,num_particles):
            swarm.append(Particle(x0))

        # optimizasyon döngüsünün başlatılması
        i=0
        while i < maxiter:
            print (i, err_best_g)
            # sürüdeki parçacıklar arasında geçiş yapılarak uygunluğun değerlendirilmesi
            for j in range(0,num_particles):
                swarm[j].evaluate(costFunc)

                # geçerli parçacık ile diğer tüm parçacıklar  en iyi olup olmadığının  
                if swarm[j].err_i < err_best_g or err_best_g == -1:
                    pos_best_g = list(swarm[j].position_i)
                    err_best_g = float(swarm[j].err_i)

            # parçacık pozisyonlarının güncellenmesi
            for j in range(0,num_particles):
                swarm[j].update_velocity(pos_best_g)
                swarm[j].update_position(bounds)
            i+=1

        # sonuçların yazdırılması
        print ('FINAL:')
        print (pos_best_g)
        print (err_best_g)

if __name__ == "PSO":
    main()

# çalıştır
initial=[1,100]            # initial starting ******** [x1,x2...] : başlangıç konumları
bounds=[(-100,100),(-100,100)]  # input bounds [(x1_min,x1_max),(x2_min,x2_max)...] : giriş değerleri
PSO(optimize_function,initial,bounds,num_particles=50,maxiter=100)

Bu şekilde bir çıktı elde edeceksiniz. İterasyonlar ve en iyi değerleri, final olarak da en iyi değerlerimiz karşımıza çıkacaktır.

Particle Swarm Optimization

Çakma Madara'

Katılımcı Üye

Sosyal medya sayfalarımız