Bilal Saim

PSO (Parçacık Sürü Algorimtası – Particle Swarm Optimization)

Parçacık sürü algoritması bir sürü tabanlı sezgisel optimizasyon algoritmasıdır. Dr.Eberhart ve Dr.Kennedy tarafından 1995 yılında geliştirilmiştir.

Parçacık sürü algoritması bir sürü tabanlı sezgisel optimizasyon algoritmasıdır. Dr.Eberhart ve Dr.Kennedy tarafından 1995 yılında geliştirilmiştir. Sürülerin özellikle kuş sürülerinin hareketlerinden esinlenilerek geliştirilmiştir. Kuşların sürü içerisinde besine yakın olan kuşların konumlarına göre hareket etmeleri algoritmanın temelini oluşturur. Feribotta bir martıya simit attığınızda 2-3 martının daha geldiğini biraz geçtiği zaman bir sürü martının etrafınıza toplandığını görürsünüz. PSO’da en uygun çözüm etrafında toplanmayı hedef alarak çözüme gider.

PSO, sosyolojik ve coğrafi koşulları bir kuş sürüsünde inceler. Belli bir alanda bulunan kuş süründe her bir kuş bulunduğu coğrafik konumuna sahiptir. Her bir kuşun bulunduğu coğrafik konum besin kaynağına ne kadar yakınsa o kadar iyidir. Kuşlar bulundukları en iyi konumu hafızada tutarlar. Sürüdeki kuşlar coğrafik konumu iyi olan kuşların ve kendi en iyi konumuna doğru bellirli bir hızda hareket ederler. Yani olayı matematiksel olarak anlatacak olursak kuşların bulunduğu coğrafya bizim çözüm uzayımızı temsil eder. Her bir kuşun konumu ise çözüm kümemizi temsil eder. Besin kaynağına olan yakınlık ise uygunluk değerimizdir. En iyi uygunluk değerine doğru yapılan yönelimin miktarı ise hızımızı temsil eder. PSO çok az değişken içeren basit bir sezgisel optimizasyon algoritmadır. Algoritma çalışma sistemi bu yöndedir gelin daha detaylı bir şekilde adım adım açıklayalım.

Özet Adımlar

Adımları sürüden esinlenildiği davranışlara karşılık gelen algoritmadaki işlemleriyle destekledim. Böylece algoritmanın orijinalini okuduğunuzda ve aşağıda algoritmanın detaylı örneklendirilmesinde kafa karışıklığı yaşamayacağınızı umuyorum.

Esinlenen davranışlar

Algoritmada karşılık gelen eylem

  1. Kuşlara rastgele konumları ve hızları bilirlenir. Bu konumların besin kaynaklarına yakınlığı hesap edilir.
  1. Rastgele çözüm kümeleri oluştur. Her çözüm kümesi parametre sayısı kadar eleman içerir. Oluşturulan çözüm kümelerinin uygunluk değerleri bulunur.

 

  1. Kuşlar konumlarını sürüde en iyi konuma sahip kuşa ve geçmişteki kendi en iyi konumlarına bir hız belirlerler. Belirlenen hızla birlikte kuş konumunu yeniler.
  1. Tüm çözüm kümelerine sırayla iyileştirilme formülü uygulanır.
  1. Belirlenen tekrar sayısına ulaşıncaya kadar 2. Aşamaya geri dönülür.
  1. Maksimum iterasyona ulaşıncaya kadar 2. Aşamaya geri dönülür.

 

Algoritmada Tanımlar ve Detaylı Çözüm

Bu bölümde algoritmadaki önemli değişkenlerden bahsedeceğim. Ayrıca paragrafa noktayla başlayan yer alan değerler aşağıda örneklerde kullanacağım değer olacak. Uygunluk fonksiyonu için Optimizasyon Test Fonksiyonlarından Sphere Fonksiyonu örnek olarak kullanılacaktır. Optimizasyon için Test Fonksiyonları makalemden test fonksiyonlarının ne olduğunu ve Sphere Fonksiyonu ile ilgili detayları bulabilirsiniz.

Problem : Algoritmada çözüm aradığımız problemdir ve genellikle bir matematiksel formülle belirtilir.

  • x12 + x22 için en küçük değeri arayacağız. Kolay ve basit olması için Sphere Test Fonksiyonunu seçtik. Biz burada x1 ve x2 parametre değerlerini algoritmada arayacağız. Örnek olması açısından basit bir problem seçtim. Sphere Formülü: 

Uygunluk fonksiyonu : Algoritmada problem için bulduğumuz çözüm kümelerinin iyilik derecesini bulmamıza yarayan formül. Sizin probleminize göre matematik modelinizi kendiniz belirlemeniz gerekir. Bu bölüm için sezgisel optimizasyon algoritmaları adlı makaleyi tekrar okumanızı tavsiye ediyorum.  Biz yukarıdaki test problemimiz Sphere’nin fonksiyonunu uygunluk fonksiyonu olarak kullanacağız.

Popülasyon Boyutu: Popülasyondaki kuş sayısının toplamıdır. Her bir popoülasyondaki kuşa parçacık adı verilir. Bende parçacık adını aşağıdaki örneklerde kullanacağım. Gerçek dünya problemlerinde 20 popülasyon boyutuna sahip PSO algoritmasının iyi çalıştığı gözlemlenilmiş

  • 5

Paremetre Boyutu: Uygunluk fonksiyonumuzda bilinmeyen değişkenlerin sayısını ifade eder.

  • Görüldüğü üzere bizim problemimizde x1 , x2 olmak üzere 2 parametremiz var.

Paremetre Aralığı: Parametrelerin alabileceği en büyük ve en küçük değerlerdir. Sizin probleminize göre parametre aralığını kendiniz belirlemeniz gerekir. Ne kadar nokta atışı parametre değer aralığı ayarlarsanız. Algoritmanızdan o kadar iyi sonuçlar elde edebilirsiniz.

  • En  küçük = -5.2, En büyük = 5.2 yani -5.2 ≤ xi ≤ 5.2. Ayrıca isterseniz her parametrenin en küçük ve en büyük değerlerini ayrı olarak belirleyebilirsiniz. Ben bu problemde iki parametre içinde aynı değer aralıkları belirledim.

Maksimum İterasyon: Algoritmanın çalışacağı maksimum döngü sayısını belirtir. Her bir iterasyonda tüm işlemler tekrar eder. Maksimum iterasyonu ne kadar büyük tutarsanız algoritmanın en uygun değeri bulma olasılığı artacaktır. Fakat buda size zaman ve hız kaybı yaşatacaktır. Bu yüzden en uygun maksimum iterasyonu ihtiyaçlarınıza göre belirleyiniz.

  • 100

Hız Limitleri: Algoritmanın çözüm kümelerinin değişim mesafesini belirleyen değişkenlerdendir. Ufak değerler için parametrelerin iyileştirmelerdeki değişmeleri küçük, büyük değerleri içinse büyük olacaktır.  

  • 0 ≤ Hız ≤ 1

C1 ve C2 değişkenleri: Geliştirme formülünde kullanılan sabit değişkenler. Altta detaylı açıklamayı bulabilirsiniz.

  • C1 = 2, C2 = 2
     

 

1- a) Kuşlara rastgele konumlar belirlenmesi : İlk aşama olarak her çözüm kümesi için parametre boyutu kadar en küçük ve en büyük parametre değerlerine göre rastgele çözüm kümesi oluşturulur. Uygunluk değerleri uygunluk fonksiyonu ile hesaplanır.

Parametre değeri atama formülü [f.1]:

Xik = lb+ rand(0,1) x (ub- lbj)

 

i  = Seçilen çözüm kümesinin indeks numarası

k = i seçilen çözüm kümesinde seçilen parametrenin indeks numarası

Xik = Seçilen çözüm kümesinin geçerli parametre numarası

rand(0,1) = 0 ile 1 arasında rastgele sayı

lbj = Parametrenin alabileceği minimum sayı

ubj = Parametrenin alabileceği maksimum sayı

Besin kaynağımızın sayısı 2 parametre sayımız 2 ydi. Xi =[ Xi1 , Xi2  ]

X11 = 1.0 + rand(0,1) x (5.0 – 1.0)  = 3.8 -> Birinci çözüm kümesi 1. parametre için

X12 = 1.0 + rand(0,1) x (5.0 – 1.0)  = 2.5 -> İkinci çözüm kümesi 2. parametre için

X1 = [3.8, 2.5]

Bu yöntem ile 2 rastgele çözüm kümesi oluşturulur.  Örnek olarak:

X2 = [-1.1, 1.2]

X3 = [-1.5, -2.2]

X4 = [3.5, -4.2]

X5 = [3.1, 1.2]

Şimdi bir çözüm kümesinin örnek olarak bizim uygunluk değerini hesaplayalım.

X1 = [3.8, 2.5] à U1 = 3.82 + 2.52 = 20.69

U1 = 20.69, U2 = 2.65, U3 = 7.09, U4 = 29.89, U5 = 11,05

1- b) Kuşların rastgele hızlarının belirlenmesi: Belirlenen hız aralığında her bir kuşun hızı bu değer aralıklarında rastgele atanır. Bizim hız aralığımız 0 ile 1 aralığında belirledik:

V11 = 0.15 , V21 = 0.50

V21 = 0.75 , V22 = 0.30

V31 = 0.31 , V32 = 0.55

V41 = 0.66 , V42 = 0.10

V51 = 0.95 , V52 = 0.27

 

 

BAŞLA

2-) Kuşların konumlarının iyileştirilmesi : Oluşturulan çözüm kümelerinin her birinin her bir parametresine sırayla geliştirilme formülü uygulanır.

Hız Formülü [f.2]:

Vik = vik + c1rand1k (pbestk – xik ) + c2rand2k(gbestk – xik)

i = Seçilen çözüm kümesinin indeks numarası

k = Seçilen parametre indeks numarası

Vik = Formül sonu oluşan çözüm kümesine ait yeni hız değeri

xik = Seçilen çözüm kümesinin k. parametre değeri

pbestk = k parçacığına ait geçmişteki en iyi çözüm kümesinin k. parametresi

gbestk = O ana kadar bulunan en iyi çözüm kümesinin k. parametresi

                c1 = Çözüm kümesinin geçmiş en iyi konumuna yaklaşma oranını belirleyen değişken

                c2= Geçmiş en iyi konuma yaklaşma oranını belirleyen değişken

                rand1k = 0-1 arasında rastgele bir sayı

                rand2k = 0-1 arasında rastgele bir sayı

c1 ve  c2 için c1 = c2 = 2 değeri aldığında problemde iyi sonuç aldığı gözlemlenilmiş. Ayrıca yine c1 + c2 = 4 olacak şekilde olması önerilir. Fakat siz kendi probleminizde değerlerini test ederek bir çıkarım yapabilirsiniz. c1 değerinin büyük olması parçacıkların daha geçmişteki en iyi konumları yani pbest’e yakın değerler üretmeleri, c2 değerinin büyük olması parçacıkların o ana kadar ki bulunan en iyi çözüm kümesine yani gbest’e yakın değerler üretmesini sağlar. c1 ve c2 değerlerinin eşit olmasıda gbest ve pbest’e aynı oranda yaklaşım sağlar.

Şimdi geliştirme formülünü örnek olarak uygulayalım:

1.İterasyonda gbest:

U1 = 20.69, U2 = 2.65, U3 = 7.09, U4 = 29.89, U5 = 11,05

 En küçük değere sahip yani iyi uygunluk değerimiz U2 böylece gbest uygunluğumuz 2.65 ve gbest çözüm kümemiz  =  [-1.1, 1.2]

İleriki iterasyonlarda ise gbest uygunluğundan daha iyi olanla gbest değiştirilir. Her iterasyonda iyileştirme formülleri uygulandıktan sonra gbest değeri mevcut uygunluk değerleriyle karşılaştırılır.

                1.İterasyonda pbest:

Her parçacığın kendi geçmişindeki en iyi uygunluk değerine sahip olduğu çözüm kümeleridir. İlk iterasyon olduğu için her parçacığın ilk değeri kendi pbest değeri olur. İleriki iterasyonlarda daha iyi uygunluk değerine ulaşan parçacıklar pbest değerlerini günceller.

Şimdi i=1 için yani 1. Parçacığımız için iyileştirme formülümüzü örnek olması için uygulayalım:

 X1 = [3.8, 2.5]   

gbest = [-1.1, 1.2] (En iyi uygunluk değerine sahip çözüm kümesi)              

pbest = [3.8, 2.5] (Dikkat edilirse ilk iterasyon olduğu için pbest çözüm kümesiyle aynı)

c1 = c2 = 2

Parçacıklarımız 2 parametreli oldukları için her bir parametresine ayrı ayrı formülümüz uygulanır.

k= 1 için yani 1. Parametre için:

rand11 = 0.55 (Rastgele belirlendi)

rand21 = 0.13 (Rastgele belirlendi)

V11 = 0.15 (Algoritma başladığında 1.b. bölümünde rastgele belirlenmişti)

Vik = vik + c1rand1k (pbestk – xik ) + c2rand2k(gbestk – xik)

V11 = 0.15 + 2* 0.55 * (3.8 – 3.8) + 2*0.13*(-1.1 – 3.8) = -1.12

k = 2 için yani 2.Parametre için:

rand12 = 0.85

rand22 = 0.50

V12 = 0.50

Vik = vik + c1rand1k (pbestk – xik ) + c2rand2k(gbestk – xik)

V12 = 0.50 + 2* 0.85 * (2.5 – 2.5) + 2*0.50*(-1.1 – 2.5) = -3.1

Böylece V11 = 1.12 ve V12 = -3.1 bulduk

Konumu güncelle [f.4]:

Xik = Xik + Vik

Parçacığın konumunu güncellemek için görüldüğü üzere bulduğumuz hız ile kendi parametre değerini topluyoruz.

X11 = 3.8 - 1.12 = 2.68

X12 = 2.5 – 3.1 = 0.6

X1 = [2.68, 0.6]

U1 = X112 + X122 = 2.682 + 0.62 = 7.54

Yeni uygunkluk değeri = 7.54, pbest = 20.69

7.54 < 20.69

Yani bulduğumuz değer daha iyi o yüzden yeni pbest değerimiz 7.54 yeni pbest çözüm kümemiz ise [2.68, 0.6]

Yeni uygunkluk değeri = 7.54, gbest = 2.65

gbest bulduğumuz uygunluk değerinden hala iyi olduğu için gbest değişmez.

 

Parametre değeri limit kontrolü [f.4]:

Eğer Xit > ubi -> Xit = ubi

 

Eğer Xit < lbi -> Xit = lbi

i = Seçilen çözüm kümesinin indeks numarası

k = i seçilen çözüm kümesinde seçilen parametrenin indeks numarası

Xik = Seçilen çözüm kümesinin geçerli parametre numarası

lbj = Parametrenin alabileceği minimum sayı

ubj = Parametrenin alabileceği maksimum sayı

                Yukarıdaki işlemler [f.2] ve [f.3]’den sonra parametre değer aralık dışına çıkılmaması için uygulanabilir. İsteğe bağlıdır. Bizim parametre aralığımız -5.12 ile 5.12 aralığındaydı. Örneğin X11 değerini 6.5 bulsaydık 5.2’ye, -6.4 bulsaydık -5.2 ye eşitleyecektik çünkü parametre sınırları aşılmış olacaktı.

Bu makaleyi paylaş

Bilal Saim

Bilal Saim kişisel blog sitesi. Yazılımcı, gençlik çalışanı, gezgin.

Related posts

Yorum yap


Bu sayfa 0,2718 sn de hazırlandı