Parçacık Sürü Optimizasyonunun(PSO) OneMax Problemindeki Performansı

Parçacık Sürü Optimizasyonu (PSO), genellikle kuş ve balık sürülerinin sosyal davranışları gözlemleyerek geliştirilen popülasyon temelli bir optimizasyon algoritmasıdır 🐦🐟 [1]. 

Bu optimizasyon algoritması genellikle literatürde çok sık kullanılan bir algoritmadır.

Bu yazımda sizlere One Maximization probleminin çözülmesinde PSO (Particle Swarm Optimization) algoritmasının kullanılışını ve performansını açıklayacağım.

Ama öncelikle sizler için topladığım farklı kaynaklardan bilgileri öğrenerek pekiştirelim ki algoritma mantığını kavrayabilelim.

Metasezgisel optimizasyon yöntemlerinden olan PSO algoritmasının geliştirilmesinde en çok kullanılan kuş sürüleri ele alındığında bilgi paylaşımı yaklaşımı kullanılarak çevreye adapte olabilme, zengin yiyecek kaynağı arama ve avcılardan kaçabilme yetenekleri baz alınmıştır 🌽🥗 [2].

sürü mantığıyla uçan kuş resmi

Sürü Mantığı [3]

Parçacık Sürü Optimizasyonu, sürü halinde hareket eden 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 [4].

Diğer optimizasyon algoritmalarında da genellikle görüldüğü gibi PSO algoritmasında da parçacıklar en iyiyi takip etme eğiliminde olmaktadır. Bu sebepten dolayı, bir süre sonra tüm parçacıklar bir yerde kümelenmiş halde çözümü arıyor olarak bulunmaktadır [4].

PSO algoritmasının kodunu çalıştırdığınızda ise bir süre sonra parçacıkların gerçekten bir yerde kümelenmiş olduğunu gözlemleyeceksiniz 👀

Parçacıklar, bu hız formülüne dayanarak hız değişimi ile farklı konumlara giderek en iyi konumu bulmaya çalışmaktadır. Sürü mantığı ile çalışıldığı için en iyi pozisyonda olan parçacık takip edilmektedir. Bu şekilde bir kümelenme görülmektedir.

One Max Probleminin Kullanımındaki Hesaplama Aşaması

One Max Problemi, basit bir optimizasyon problemidir. Problemin amacı, uygulanabilir bir çözümde olanların sayısını en üst düzeye çıkarmaktır. Problemin formülü aşağıda verilmiştir. Bu formülde yer alan D, problemin boyutunu belirtmektedir 🔖

Yukarıda formülünü görmekte olduğunuz maksimizasyon problemi için PSO algoritmasında kullanılacak maliyet fonksiyonu Sigmoid olarak belirlenmiştir.

Sigmoid fonksiyonu ise içerisine aldığı değerleri 0.5 ile kontrol etmektedir. Bu fonksiyon ile parçacıkların sahip olduğu Dimension içerisindeki tüm parçacıkların Sigmoid’ den gelen çıktısını 0.5 değerinin üzerine çıkarmaktır.

Böylelikle 0.5 değerinin üzerindeki çıktılar 1’e eşitlenecektir. Literatürdeki bu algoritma üzerinde çalışılmış diğer araştırmalar incelendiğinde parçacıkların hız değişim formülünde bulunan w, c1 ve c2 değerleri farklı alınmaktadır 💡

Sigmoid Fonksiyonu Çalışma Grafiği [5]

Wilcoxon ile İstatistiksel Sonuçlar

Öncelikle w değeri 0.005, c1 değeri 0.005 ve c2 değeri ise 0.009 seçilmiştir. Toplamda 40 adet parçacığın bulunduğu popülasyonda çalışılmaktadır. Bu değerler baz alındığında sırasıyla D=100, 500 ve 1000 boyutları için 30 kez çalıştırılmıştır. D olarak belirtilen değer problem boyutunu belirtmektedir. Buna göre aşağıdaki tabloda Wilcoxon ile hesaplanan sonuç değerleri yazdırılmıştır 📝

D problemin boyutu: 100 , iterasyon sayısı : 100.000 ve toplam 30 kez çalıştırma

Ortalama Medyan En iyi değer En kötü değer Standart Sapma
0.0031551897084034007 0.0025380204697822194 0.00023797210224091314 0.008994153476226206 0.0020874904616420636

D problemin boyutu: 500 , iterasyon sayısı : 100.000 ve toplam 30 kez çalıştırma

Ortalama Medyan En iyi değer En kötü değer Standart Sapma
0.0024457287103268333 0.002274384447498488 0.0001588232061854383 0.0001588232061854383 0.0016983186907986983

D problemin boyutu: 1000 , iterasyon sayısı : 100.000 ve toplam 30 kez çalıştırma

Ortalama Medyan En iyi değer En kötü değer Standart Sapma
0.0014781328189136006 0.0010733144689043976 7.397751636520865e-05 0.004376988570160589 0.0010840516145429367

Ardından w değeri 0.4, c1 değeri 1.5 ve c2 değeri ise 2 seçilmiştir. Toplamda 40 adet parçacığın bulunduğu popülasyonda çalışılmaktadır. Bu değerler baz alındığında sırasıyla D=100, 500 ve 1000 boyutları için 30 kez çalıştırılmıştır. D olarak belirtilen değer problem boyutunu belirtmektedir. Buna göre aşağıdaki tabloda Wilcoxon ile hesaplanan sonuç değerleri yazdırılmıştır 📝

D problemin boyutu: 100 , iterasyon sayısı : 100.000 ve toplam 30 kez çalıştırma

Ortalama Medyan En iyi değer En kötü değer Standart Sapma
0.10290449068126414 0.06354761821949564 0.001496700649763677 0.4405023200617695 0.11308392205322863

D problemin boyutu: 500 , iterasyon sayısı : 100.000 ve toplam 30 kez çalıştırma

Ortalama Medyan En iyi değer En kötü değer Standart Sapma
0.11090339649603935 0.07350043038100676 0.0010117064651082308 0.5125380033802425 0.11343766955639699

D problemin boyutu: 1000 , iterasyon sayısı : 100.000 ve toplam 30 kez çalıştırma

Ortalama Medyan En iyi değer En kötü değer Standart Sapma
0.1276016324307818 0.048701691139323475 0.0005810872467598704 0.7015965709030323 0.15191292927119768

🕵Bu değerler karşılaştırıldığında w, c1, c2 değerleri büyütüldükçe ortalama, medyan ve standart sapmanın büyüdüğü fark edilmektedir. Standart sapmanın büyük olması aynı zamanda serideki yani popülasyondaki parçacıkların ortalamadan saptığı anlamına gelir. Yukarıda tercih edilen değerler ile en iyi sonuç yani minimum değere daha kolay ulaşılmıştır.

🏋 İlk alınan değerlerdeki w değeri 0.005, c1 değeri 0.005 ve c2 değeri ise 0.009 olduğunda istenilen sonuca daha kolay ulaştığı gözlemlenmiştir. D=100,500 ve 1000. boyuta kadar artırıldığında en iyi konumun değerinin gittikçe küçüldüğü görülmüştür ve bu istenen bir durumdur.

NOT 🌠

PSO algoritması için geçerli olan best_globalbest değeri bir numpy dizisinde tutulmuş ve daha sonra Wilcoxon istatistiği uygulanarak aşağıdaki değerlere ulaşılmıştır.

📌Kodu incelemek isterseniz Github Reposu olarak sizlere yayınlıyorum. İyi çalışmalar dilerim 🐞

Diğer yazılarıma buradan ulaşabilirsiniz.

REFERANSLAR

[1] M. Yasin ÖZSAĞLAM, Mehmet ÇUNKAŞ, Optimizasyon Problemlerinin Çözümü için Parçacık Sürü Optimizasyonu Algoritması, Politeknik, Cilt:11 Sayı: 4 s.299-305, 2008.

[2] Fırat Üniversitesi, BMÜ-579 Metasezgisel Yöntemler, Parçacık Sürü Optimizasyonu.

[3] Pablo J. Villacorta, Swarm Intelligence Metaheuristics, part 2: Particle Swarm Optimization, https://www.stratio.com/blog/swarm-intelligence-metaheuristics-part-2-particle-swarm-optimization/.

[4] Muhammed Pektaş, Nisan 2019, Parçacık Sürü Optimizasyonu (PSO) Medium yazısından alınmıştır.

[5] https://en.wikipedia.org/wiki/Sigmoid_function adresinden alınmıştır.

Leave a Reply

Your email address will not be published. Required fields are marked *