Parçacık Sürü Optimizasyonu Üzerine…

Parçacık sürü optimizasyonu (PSO) sürülerle ilgili problemleri çözmek için yaygın olarak kullanılan bir algoritmadır. 1995 yılında James Kennedy ve Russell C. Eberhart tarafından bir olasılıksal arama süreci olarak geliştirilmiş ve ilk olarak sürü halinde hareket eden kuş ve balık türlerinin yiyecek bulmak, avcılardan kaçmak gibi temel ihtiyaçlarını ne şekilde yaptıklarını, sürü içindeki sosyal davranışlarını ve sürünün bir bütün olarak koreografisini izlemeleri sonucu yapılan simülasyonları matematik olarak açıklamak amacıyla kullanılmıştır[1].

Problemlere maliyeti düşük tutarak en optimal çözümleri arayan optimizasyon algoritmalarından birisi olan PSO yönteminin esinlenme kaynağı doğada sürü halinde yaşayan hayvan türleri olmuştur.

Sürü içindeki bireyler hem bireysel tecrübelerinden hem de sürünün tecrübelerinden öğrenerek amaca göre en optimal bir sonraki gidecekleri yeri ve yönü seçmektedirler. PSO algoritması ile çözüm modelleri üretmek diğer optimizasyon algoritmalarıyla karşılaştırıldığında ayarlanması gereken parametre sayısının az olması, doğrulanmasının daha mümkün olması gibi sebepler dolayısıyla daha kolaydır[2].

PSO arama algoritmaları, fonksiyon optimizasyonları, yapay sinir ağı modellerinin eğitimi, bulanık mantık sistemleri ve görüntü işleme gibi birçok alanda kullanılmaktadır[3].


Doğayı gözlemlememiz sonucu öğrenilen bir öğreti olarak bakabileceğimiz PSO algoritmasını çıkış örneklerinden birini inceleyerek daha yakından ele alalım; doğada bir kuş sürüsünün nerede sabit kalmaları gerektiğini bir optimizasyon problemi olarak düşünebiliriz. Kuş sürüsü, kuşların hayatta kalma oranını maksimize etmek adına dikey ve yatay ölçülerde en optimize yere gitmek zorundadır. Bunu başarmak için sürüdeki her bir kuş farklı yön ve yerlere uçarak en optimal noktayı bulmaya çalışır. Kuşlar için hayatta kalma kriteri su içmek veya yemek yemek şeklinde değişse de sürü bütün problemleri için aynı arama algoritmasını kullanır.


PSO algoritmasının genel olarak çalışmasının ilk adımı bir rasgele çözüm kümesi üretilmesidir. Bu çözüm kümesine parçacık adı verilir, PSO bu çözüm kümesinden yola çıkarak optimum bir çözüm bulmaya çalışır. Her iterasyonda parçacık konumları parçacığın bireysel en iyi değere ve sürünün bulduğu en iyi değere göre güncellenir. Parçacığın bireysel olarak en iyi bulduğu değere “pbest”, sürünün bulduğu en iyi değere ise “gbest” denilir. Parçacık popülasyon matrisinde D adet özelliğe sahip i. parçacık xi = [xi1,xi2,,,,xiD] olarak gösterilir. Her iterasyon için pbest ve gbest değerleri bulunduktan sonra parçacığın hızı ve konumu aşağıda verilen vik hız vektörü ve xik konum vektörlerinin bir sonraki değerlerinin hesaplanması aşağıdaki denklemlere göre yapılır;


1. denklem; vik+1 = w . vik + c1 . rand1k . (pbestik – xik) + c2 . rand2k . (gbestk – xik)


2. denklem; xik+1 = xik + vik+1


Öğrenme faktörleri olan c1 ve c2, her parçacığı pbest ve gbest değerlerine doğru çeker. Denklemdeki rand1k ve rand2k ise 0-1 arasında seçilmiş rasgele sayılardır, k iterasyon sayısını göstermektedir.

Eylemsizlik ağırlığı olan w, her iterasyonda doğrusal olarak azaltılmalı ve 1’den küçük olmalıdır. Hız vektörünün ilk terimi olan “w . vik“, aslında “w” parametresi ve parçacığın eski hızının bir ürünüdür. Açıklamak adına “w = 1değerini bir önceki durumdan bir sonraki duruma geçildiğinde azaltılmazsa, parçacığın farklı bir yöne gitmesi olayı ya azalır ya da düşer. Bu sebeple eylemsizlik ağırlığı parametresi olan “w” her iterasyonda düşürülür ve bunun sayesinde sürü daha fazla yeri keşfedebilir. “w” parametresini düşürmek ise model ve simülasyonların sonuç verirken daha çok vakit harcadığını göstermiştir[7].

Bireysel ilerlemeyi açıklayan, birinci denklemin ikinci terimi ise parçacığın en iyi bireysel değeri olan “pbestik” ve parçacığın o anki değeri olan “xik” değerlerinin birbirinden çıkarılmasıyla bulunur. Bu terimin arkasındaki ide ise parçacığın “pbestik” değerinden uzaklaştıkça, (pbestik – xik) değerinin yükselmesi, bundan dolayı formüldeki bu kısmın değerinin artması ve parçacığın en iyi noktaya daha da yaklaşmasıdır.

c1 parametresi ise pozitif bir sabittir ve parçacığın bireysel hareketiyle ilgilenir. rand1k , 0 ve 1 arasında olan rastgele değer parametresidir. Bu rastgele belirlenen parametrenin önemli olma sebebi ise parçacıkların hız farklılıklarından dolayı erken yakınsama gibi yerel engellere takılma sorunu yaşamalarını önler, global optimayı yükseltir.

Eşitlikteki üçüncü kısım ise “sosyal öğrenen” terimdir. Bu kısım sayesinde parçacıklar öğrendikleri bilgileri popülasyonun parçacıklarıyla paylaşarak sürü genelinde ulaşılan en iyi değeri bulmaya yardımcı olur. (gbestk – xik), herhangi bir k iterasyonunda parçacıklar için en iyi noktaya çekilmelerine yardımcı olur. c2 de diğer bir sosyal öğrenim parametresidir ve sürünün global öğrenme ağırlık katsayısını belirler. rand2k ise rand1k‘nin göreviyle aynı görevi taşımaktadır.


Parçacık Sürü Optimizasyonun nasıl çalıştığına adım adım göz atmak istersek PSO’nun aşağıdaki yapay kodunu inceleyebiliriz:


PSO Yapay Kodu:
Adım 1. Probleme göre parametreleri, amaç fonksiyonunu, çözüm uzayını ve popülasyon büyüklüğünü türet,
Adım 2. Sürüdeki parçacıkların hızı ve konumunu rastgele üret, kişisel en iyi değeri pbestik = xik olarak al, hafızaya kaydet,
Adım 3. Her iterasyon için;
Adım 3.1. Her parçacık için;
-Değeri amaç fonksiyonuyla karşılaştır,
pbest’i güncelle,
Bitir.
Adım 3.2. Hafızayı güncelle,
Adım 3.3. Her parçacık için;
-Hafızaya kayıtlı en iyi değeri bulan parçacığa git(gbestk),
-Hızı güncelle,
-Konumu güncelle,
Bitir.
Adım 4. Algoritmayı bitirme kriterlerinin karşılanıp karşılanmadığını kontrol et,
-Eğer kriterler karşılanıyorsa bitir,
-Eğer kriterler karşılanmıyorsa Adım 3’e geri dön.

PSO’nun günümüzde arama algoritmaları içerisinde daha çok kullanılan bir algoritma olmasının başlıca sebeplerinden birisi olan parametrelerinin azlığı ve ayarlanılabilir olması özelliklerinden bahsetmiştik, PSO’nun avantajlarından bir başkası ise kullanım alanlarının sınırlı olmamasıdır.

Çözüm yelpazesi bir hayli geniş olan PSO algoritmasının gerçek hayat kullanımlarından bazılarına örnek olarak, lösemi kanserinde erken ve kolay tanı imkanı sağlaması[13], termo-dinamik alanı[14] ve kompakt doğrusal Fresnel reflektör optikal geometrik optimizasyonunu[15] söyleyebiliriz.

Kullanım alanı geniş ve potansiyeli bir hayli yüksek olan PSO algoritmasının başarıya ulaşmasının zor bir yanı ise ancak ve ancak problemin amaç fonksiyonunu algoritmanın güzel bir şekilde soruyu çözecek hale getirilmesiyle mümkün olmasıdır. Bu görevin zorluğu bir gerçek hayat problemini matematiksel olarak denklemlerle açıklamanın zorluğundan da gelmektedir.

Algoritmanın bir başka dezavantajı ise sorunu çözdükten sonra çok yüksek ihtimal global optimayı bulmuş olsak bile aslında çok nadiren global optimayı bulduğuna emin olmamızdır. Optimal verinin elimizde olmadığı zamanlarda bu sorunun önüne geçmek adına diğer optimizasyon algoritmalarını da sorunun çözümünde kullanmamız bize global değerler için daha iyi fikirler verecektir.

Kaynakça;

  • [1] Sürü davranışı. https://tr.wikipedia.org/wiki/S%C3%BCr%C3%BC_davran%C4%B1%C5%9F%C4%B1.
  • [2] Cavuslu, M. Ali & Karakuzu, Cihan & Sahin, Suhap. (2010). Parçacık Sürü Optimizasyonu Algoritması ile Yapay Sinir Ağı Eğitiminin FPGA Üzerinde Donanımsal Gerçeklenmesi. Journal of Polytechnic. 13. 83-92.
  • [3]https://web.archive.org/web/20110716231935/http://cswww.essex.ac.uk/technical-reports/2007/tr-csm469.pdf
  • [4]Pektas, M. Parçacık Sürü Optimizasyonu (PSO). https://medium.com/deep-learning-turkiye/par%C3%A7ac%C4%B1k-s%C3%BCr%C3%BC-optimizasyonu-pso-1402d4fe924a.
  • [5]http://web.firat.edu.tr/iaydin/bmu579/bmu_579_bolum3.pdf
  • [6]Cavuslu, M. Ali & Karakuzu, Cihan & Sahin, Suhap. (2010). Parçacık Sürü Optimizasyonu Algoritması ile Yapay Sinir Ağı Eğitiminin FPGA Üzerinde Donanımsal Gerçeklenmesi. Journal of Polytechnic. 13. 83-92.
  • [7]Kennedy J, Eberhart RC. “Particle Swarm Optimization: Proceedings of the International Conference on Neural Networks; Institute of Electrical and Electronics Engineers. Vol:4 – 1995 pp. 1942-1948. DOI: 10.1108/ICNN.1995.488968”
  • [8]Kennedy J, Eberhart RC. “Particle Swarm Optimization: Proceedings of the International Conference on Neural Networks; Institute of Electrical and Electronics Engineers. Vol:4 – 1995 pp. 1942-1948. DOI: 10.1108/ICNN.1995.488968”
  • [9]Der, O., Vural, R. A., & Yıldırım, T. Parçacık Sürü Optimizasyonu Tabanlı Evirici Tasarımı Inverter Design Based on Particle Swarm Optimization . https://www.emo.org.tr/ekler/235f3310045b155_ek.pdf.
  • [10]Parçacık Sürü Optimizasyonu. Mühendis Beyinler. https://www.muhendisbeyinler.net/parcacik-suru-optimizasyonu/.
  • [11]http://downloads.hindawi.com/archive/2008/685175.pdf
  • [12]Almeida, B. S. G. de, & Leite, V. C. (2019, December 3). Particle Swarm Optimization: A Powerful Technique for Solving Engineering Problems. https://www.intechopen.com/books/swarm-intelligence-recent-advances-new-perspectives-and-applications/particle-swarm-optimization-a-powerful-technique-for-solving-engineering-problems.
  • [13]Srisukkham, W., Zhang, L., Neoh, S. C., Todryk, S., & Lim, C. P. (2017, March 29). Intelligent leukaemia diagnosis with bare-bones PSO based feature optimization. https://www.sciencedirect.com/science/article/pii/S1568494617301485.
  • [14]Azimifar, A., & Payan, S. (2016, February 2). Enhancement of heat transfer of confined enclosures with free convection using blocks with PSO algorithm. https://www.sciencedirect.com/science/article/abs/pii/S1359431115013721?via=ihub.
  • [15]Ajdad, H., Baba, Y. F., Mers, A. A., Merroun, O., Bouatem, A., & Boutammachte, N. (2018, July 3). Particle swarm optimization algorithm for optical-geometric optimization of linear fresnel solar concentrators. https://www.sciencedirect.com/science/article/abs/pii/S0960148118307869.
  • Görsel; Background photo created by nikitabuida – www.freepik.com

Data Science Earth

Data Science Earth ekibi, üst düzey Veri Bilim çözümleri üretmek amacı ile toplanmış akademisyenler ve uzmanlardan oluşmaktadır. Öncelikli olarak veri bilincini geliştirmeyi ve küreselleşen rekabet ortamında verinin gücünün doğru kullanılmasını sağlamayı amaçlamaktadır.

Sponsor

QuestionPro 35 farklı soru seçim özelliği ile anket çalışmalarımıza güç katmaktadır.