Parçacık Sürü Optimizasyonu (PSO)
Günlük hayatta bazı problemleri çözerken en iyi çözümü bulabilmeniz için çok sayıda seçeneği denemeniz gerekebilir. Örneğin; bir deniz taşımacılığı şirketinizin olduğunu ve bir yük geminize 100 farklı ürün seçeneğinden 50 farklı ürün yükleyebileceğinizi varsayalım. Bu durumda maksimum karı elde etmek için gemiye olabildiğince değerli olacak şekilde 50 farklı ürün yüklemeniz gerekmektedir. Bu aşamada en iyi durumu belirlemek için her ihtimali denemeye kalkarsak karşımıza 100'ün 50'li kombinasyonu çıkar. Bu da tam olarak 100 891 344 545 564 149 295 156 822 016 sayısına karşılık gelmektedir. 😅 Bu kadar ihtimali denemenin maliyeti çok ama çok fazla olacağından biz de optimizasyon algoritmaları ile makul sürede en iyi çözümü aramaktayız.
O halde bir optimizasyon algoritmasından beklentimiz kısaca; problemin makul sürede en iyi çözümünü bulmaya çalışmasıdır, diyebiliriz.
Gelin şimdi yazımızın konusu olan Parçacık Sürü Optimizasyonu’na bir göz atalım!
Bakalım beklentimizi karşılayabiliyor mu ?
Parçacık Sürü Optimizasyonu nedir ?
Parçacık Sürü Optimizasyonu, sürü halinde hareket eden bazı hayvanların yiyecek bulmak gibi temel ihtiyaçlarını giderirken sergiledikleri hareketlerin, sürüdeki diğer bireyleri etkilediğinin ve sürünün amacına daha kolay ulaştığının gözlemlenmesinden esinlenilerek Dr. Kennedy ve Dr. Eberhart tarafından 1995 yılında geliştirilmiş bir optimizasyon algoritmasıdır.
Yazının devamında Parçacık Sürü Optimizasyonundan bahsederken PSO kısaltmasını kullanacağız.
Şimdi biraz da terminolojisinden bahsedelim !
PSO’da çözümü bulmak adına arama yapan her bir bireye parçacık adı verilirken, parçacıkların bulunduğu popülasyona ise sürü adı verilir.
Bir bireyin çözüme ne kadar yakın olduğunu anlamak için uygunluk fonksiyonu kullanılır. Bu fonksiyon, yük gemisi örneğimiz ele alınırsa, seçilen yüklerin toplam değerini dikkate alarak çözümün uygunluğunu değerlendiren bir fonksiyon olabilir. Bu fonksiyonun asıl amacı gerçek çözüme ne kadar yaklaştığımızı ölçmektir.
Bir parçacığın çözümü aradığı süre boyunca kendisinin çözüme en çok yaklaştığı, o andaki en iyi durumuna pbest* denirken, tüm sürüde tüm arama boyunca çözüme en çok yaklaşan parçacığın o andaki durumuna ise gbest** denir.
Simdi biraz işin teorisine bakalım ve ardından uygulamamızı yapalım!
Teoride PSO
Akış şemasında da gösterildiği gibi;
PSO’da öncelikle çözümü arayacak sürü ve gerekli parametreler belirlenir. Uygunluk fonksiyonu yardımıyla parçacıkların çözüme yakınlığı ölçülür ve bu değerlere göre pbest ve gbest değerleri güncellenir. Daha sonra değişim hızı fonksiyonu ile her parçacığın yapacağı hareket belirlenir ve yeni durumları ayarlanır. Tekrar uygunluk fonksiyonu ile çözüme ne kadar yaklaşıldığı kontrol edilir. Bu döngü istenilen şartlara ulaşılıncaya kadar tekrarlanır.
Şimdi parçacıkların değişim hızlarını hesapladığımız formüle bir göz atalım.
Parçacık Sürü Optimizasyonunda parçacıkların değişim hızları ;
x: parçacık değeri
v : parçacığın değişim hızı,
c1,c2 : sabit değerler,
rand1, rand2 : rastgele üretilen değerler,
pbest : parçacığın çözüme en çok yaklaştığı durum
gbest : tüm parçacıklar arasında çözüme en çok yaklaşılan durum olmak üzere aşağıdaki formül ile hesaplanır.
Bu formül sayesinde parçacık kendi en iyi çözümüne ve global en iyi çözüme yönelir. Bu da parçacığı çözümü en iyi parçacığın ve kendi en iyi durumunun yakınlarında aramaya iter.
Parçacıkların bu hareketini görselde kolayca gözlemleyebilirsiniz.
Bu kadar bilginin ardından gelin şimdi bir uygulama yaparak öğrendiklerimizi pekiştirelim ve PSO’nun doğru çözüme nasıl yaklaştığına şahit olalım!
PSO Uygulaması
Örnek problemimiz verilen denklemin sonucunu 0 yapacak x değerini bulmak olsun. Burada denklemi bir işin maliyet fonksiyonu olarak düşünebilirsiniz.
- Öncelikle kaç adet parçacık ile çözümü arayacağımızı belirliyoruz.
Bu sayı arama uzayının genişliğine ve sizin isteğinize bağlı olarak belirlenir. Biz bu örneğimizde 3 belirleyelim.
Parçacıklar rastgele belirlenir. Parçacıkları aşağıda verildiği gibi sırasıyla 3, 7, 5 olarak belirledik.
- Her parçacığın uygunluk değeri hesaplanır.
Bu örnekte amacımız problemin denklemini 0’a yaklaştırmak olduğundan uygunluk fonksiyonumuz problemin denkleminin ta kendisidir.
Görüldüğü üzere belirlediğimiz x değerlerini denklemde yerine koyarak uygunluk değerlerini kolayca elde ettik. Tekrar hatırlatmak gerekirse; amacımız uygunluk değeri 0 olan x değerini bulmaktı.
- pbest ve gbest değerleri hesaplanır.
Şuan ilk iterasyonda olduğumuzdan parçacıkların kendileri zaten pbest’leridir. gbest ise 0'a en yakın olan P1 parçacığıdir.
- c1, c2 değerleri ve rastgele olarak rand1, rand2 değerleri belirlenir.
c1 ve c2 değerleri genellikle 2 belirlenir ben de bu parametreleri 2 olarak belirliyorum.
rand1 ve rand2 değerini de hesaplama kolaylığı açısından 2 belirliyorum.
Ayrıca daha ilk iterasyonda olduğumuzdan parçacıklar herhangi bir hıza sahip değildir. Bu nedenle ilk değişim hızı V0'ı 0 kabul ediyoruz.
Nihayet sıra değişim fonksiyonumuzu kullanarak parçacıkların değişimini hesaplamaya geldi 😃
- Parçacıkların değişim hızları hesaplanır.
Böylece formülümüzü kullanarak parçacıkların değişimi hesaplanmış oldu.
- Parçacıkların yeni değerleri belirlenir.
Bu aşamada parçacıklar, değişim değerleri ile toplanarak yeni parçacıklar belirlenir.
Şimdiki görevimiz bu parçacıklar ile çözüme ne kadar yaklaştığımızı değerlendirmek.
- Yeni parçacıkların uygunluk değerleri bulunur.
Tebrikler. 🍧 Daha ilk iterasyonda bırakın problemin çözümüne yaklaşmayı çözdünüz bile 😃
Denklemimizi 0 yapan değer -3 olarak bulunmuş oldu.
Eğer çözüme ulaşamamış olsaydık; yeni parçacıklar da göz ününe alınarak yeniden pbest değeri ve bu zamana kadar gelmiş tüm pbest’lerin en iyisi olan gbest değeri belirlenecekti. Ek olarak rand1 ve rand2 değerleri tekrar belirlenip parçacıkların değişimi hesaplanacak ve yeni parçacıklar bulunacaktı. Ve bir kez daha uygunluk değerini bulup çözüme ne kadar yaklaştığımızı değerlendirecektik.
Sonuç
PSO algoritmasını baz istasyonların en az maliyetle en uygun yerlere yerleştirilmesi, tasarımsal ürünlerin en verimli halinin belirlenmesi gibi herhangi bir optimizasyon problemine uygularken genellikle kaç iterasyon çalışacağını belirlemeniz gerekir. Örneğin; “1000 iterasyon çalış ve bana bulduğun en iyi çözümü ver” diyebilirsiniz. Aksi halde tam çözümü bulana kadar aramaya devam edecektir.
Algoritmanın avantaj ve dezavantajlarından bahsetmek gerekirse; hatırlayacağınız üzere gbest olan parçacığın değişim hızı 0 bulunmuştu. Bu durum PSO’nun dezavantajlarından biridir. Çözüme en yakın olan parçacık belki de kolayca çözüme ulaşabilecek iken adeta diğer parçacıkların onu yakalayıp geçmesini beklemektedir.
Ayrıca PSO algoritmasında parçacıklar en iyiyi takip etme eğiliminde olduğundan dolayı, bir süre sonra tüm parçacıkları bir yerde kümelenmiş halde çözümü arıyor olarak bulabilirsiniz. Bu durum çözümün arandığı uzayın detaylı taranması adına olumsuz bir durum oluşturur. Fakat kümelenme geçekten çözümün bulunduğu yerde ise çözüme de daha çabuk ulaşılacağından bir avantaj anlamına gelir.
Soru ve görüşleriniz için benimle twitter ve linkedin üzerinden iletişime geçebilirsiniz.
İyi çalışmalar.
*pbest terimi ingilizcede “Personel Best” ifadesinin kısaltmasıdır. Türkçede “kişisel en iyi” anlamına gelir.
**gbest terimi ingilizcede “Global Best” ifadesinin kısaltmasıdır. Türkçede “küresel en iyi” anlamına gelir.
Kaynaklar
1- Particle Swarm Optimization — James Kennedy and Russell Eberhart
2- Particle Swarm Optimization — Scholarpedia
