Parçacik süRÜ optiMİzasyonu genel Bilgiler

PARÇACIK SÜRÜ OPTİMİZASYONU

Genel Bilgiler

• 1995 yılında Dr.Eberhart ve Dr.Kennedy tarafından geliştirilmiş popülasyon temelli sezgisel bir optimizasyon tekniğidir.

• Kuş veya balık sürülerinin sosyal davranışlarından esinlenerek geliştirilmiştir.

Genel Bilgiler

• Birbirleriyle ve çevresiyle etkileşim içerisinde olan bireylerin davranışları incelenerek geliştirilmiştir. Bu kavram parçacık zekası olarak da isimlendirilmektedir.

• PSO’da parçacık olarak isimlendirilen potansiyel çözümler, mevcut en iyi çözümleri takip ederek problem uzayında gezinirler.

Genel Bilgiler

• PSO, fonksiyon optimizasyonu, çizelgeleme, yapay sinir ağlarının eğitimi, bulanık mantık sistemleri, görüntü işleme vb. pek çok alanda yaygın olarak kullanılmaktadır.

Algoritma

• Belirli bir alanda, sadece bir bölgede yiyecek olduğu, bir kuş grubunun bu alanda yiyecek aradığı ve başlangıçta yiyeceğin nerede olduğunu bilmediği kabul edilir ise, yiyecek bulmak için en iyi çözüm ne olabilir?

Algoritma

• PSO’da her bir parçacık bir kuşu ifade eder ve her parçacık bir çözüm sunar.

• Tüm parçacıkların uygunluk fonksiyonu ile bulanan uygunluk değerleri vardır.

• Parçacıklar, kuşların uçuşlarını yönlendiren hız bilgisine benzer bir bilgiye sahiptir.

Algoritma

• PSO rastgele üretilmiş belirli sayıda çözümle (parçacıkla) başlatılır ve parçacıklar güncellenerek en uygun çözüm değeri araştırılır.

• Parçacıkların her biri, parçacığın en iyi kendi çözümü (pbest) ve tüm parçacıkların en iyi çözümü (gbest) kullanılarak güncellenir. Bu değerler hafızada saklanır.

Algoritma

Algoritma

• D adet parametreden oluşan n parçacık göz önüne alındığında i. Parçacık,

• xi = [ xi1, xi2, ….xiD]

• pbesti=[pi1,pi2,…piD]

• gbest=[p1,p2,….pD]

• x11 x12 x1D

• x= x21 x22 x2D x: popülasyon matrisi

• xn1 xn2 xnD

Algoritma

• Parçacığın her konumdaki değişim miktarını gösteren hız vektörü:

• vi= [vi1, vi2, …viD ]

• Parçacık hızı ve konumunun güncellenmesi;

• Vik+1 = Vik + c1rand1k(pbestik-xik)+ c2rand2k(gbestk-xik)

• Xik+1 = xik + Vik+1

Algoritma

• Rand:(0,1) aralığında rastgele bir değer

• k: iterasyon sayısı

• c1,c2: öğrenme faktörüdür. Parçacıkları pbest ve gbest konumlarına doğru yönlendirir. Genellikle 2 olarak seçilir.

PSO parametreleri

• f(x)= x12 + x22 + x32

• Göz önene alınırsa;

• Bilinmeyen sayısı 3 olup parçacık D=3 boyutludur.

• PSO reel sayıları kullanarak çalışabilir.

PSO parametreleri

• Parçacık sayısı: genelde 20-40 arasındadır.

• Parçacık boyutu: probleme göre değişkenlik gösterir.

• Vmax= bir iterasyonda, bir parçacıkta meydana gelebilecek maksimum değişikliği (hız) belirler.

• Parçacık aralığı: örneğin x1 için(-5,5)

• Öğrenme faktörleri: c1, c2 olup [0,4] aralığında seçilebilir.

• Sonlandırma kriteri: minimum hata veya iterasyon sayısı olabilir.

Sayısal örnek

• İkisi küresel olmak üzere toplamda 6 yerel minimuma sahip bir fonksiyon

• f(x)=4x12 -2,1x14 + 1/3 (x16) + x1x2 – 4x22 + 4x24

• Fonksiyonun minimum olduğu nokta araştırılacaktır.

Sayısal örnek

• Boyut=D=2 (x1,x2)

• Parçacık sayısı=10

• Öğrenme faktörü=c1,c2=2

• Parçacıklar parametre aralıklarına uygun olarak seçilerek, her parçacık için uygunluk değeri hesaplanır.

• İlk iterasyon için her parçacığın pbest değeri kendisine eşittir. Başlangıç hızı 0 olarak alınmıştır.

Sayısal örnek

Sayısal örnek

Sayısal örnek

Sayısal örnek

• Parçacıkların yeni konumları;

• x1k+1= x1k + v1k+1

• x1,11= x1,10 + v1,11 ;

• x1,11 =(-3,7060195)+2,035288=-1,6707315

• x1,21= x1,20 + v1,21 ;

• x1,21 =2,81307351+(-1,44282)=1,37025351

• x11 = [-1,6707315, 1.37025351]

Sayısal örnek