PARÇACIK SÜRÜ OPTIMIZASYONU (PARTICLE SWARM OPTIMIZATION) 

GIRIS

 

Parçacik Sürü Optimizasyonu (Particle Swarm Optimization) (PSO) 1995’te Dr. Eberhart ve Dr. Kennedy tarafindan gelistirilmis popülasyon temelli sezgisel bir optimizasyon teknigidir. Kus veya balik sürülerinin sosyal davranislarindan esinlenilerek gelistirilmistir.

PSO, Genetik Algoritmalar gibi evrimsel hesaplama teknikleri ile birçok benzerlikler gösterir. Sistem random çözümlerden olusan bir popülasyonla baslatilir ve en iyi çözüm için jenerasyonlari güncelleyerek arama yapar. Buna karsin, GA’nin tersine, PSO’da çaprazlama ve mutasyon gibi evrimsel operatörler yoktur. PSO’da parçacik(particles)denilen potansiyel çözümler, mevcut en iyi çözümleri takip ederek problem uzayinda gezinirler (uçus yaparlar).

GA ile karsilastirilirsa; PSO’nun avantaji gerçeklestirilmesinin kolay olmasidir ve ayarlanmasi gereken çok az parametresi vardir. PSO pek çok alanda basarili bir sekilde uygulanmistir. Bunlardan bazilari; fonksiyon optimizasyonu, yapay sinir aglari egitimi, bulanik sistem kontrolü ve GA’nin uygulanabildigi diger alanlardir.

Biyolojik sistemlerden esinlenen birçok hesaplama teknigi mevcuttur. Örnegin yapay sinir aglari insan beyninin basitlestirilmis bir modelidir. Genetik algoritmalar biyolojideki evrimsel süreçten esinlenir. Burada ise ele alinan konu biyolojik sistemlerin farkli bir türü olan sosyal sistemlerdir. Özellikle birbiriyle ve çevresiyle etkilesim içinde olan basit bireylerin birliktelik davranislari incelenmektedir. Bu kavram parçacik zekâsi olarak isimlendirilir.

Sayisal zekâ alaninda parçaciklardan esinlenen iki popüler metot vardir:  Karinca Koloni Optimizasyonu (ACO) ve Parçacik Sürü Optimizasyonu (PSO). ACO karincalarin davranislarindan esinlenir ve ayrik optimizasyon problemlerinde birçok basarili uygulamasi vardir. (http://iridia.ulb.ac.be/~mdorigo/ACO/ACO.html)

Parçacik sürüsü kavrami basitlestirilmis sosyal sistemin benzetimi olarak olusturuldu. Asil amaç bir kus veya balik sürüsü koreografisinin grafiksel olarak benzetimini yapmakti. Ancak parçacik sürüsü modelinin bir optimizasyon araci olarak kullanilabilecegi düsünüldü. (http://www.engr.iupui.edu/~shi/Coference/psopap4.html)

.

ALGORITMA

 Daha önce de açiklandigi gibi, PSO kus veya balik sürüsünün davranislarini benzetir. Bir alanda rasgele yiyecek arayan bir kus grubunun oldugunu ve arama yapilan alanda yalnizca bir parça yiyecek oldugunu varsayalim. Kuslarin hiçbiri yiyecegin nerede oldugunu bilmesin. Fakat her bir iterasyon sonunda yiyecegin ne kadar uzakta oldugunu bilsinler. Bu durumda en iyi strateji nedir?  En etkili olani yiyecege en yakin olan kusu takip etmektir.

PSO bu senaryoya göre çalisir ve optimizasyon problemlerini çözmek için kullanilir. PSO’da her bir çözüm arama uzayindaki bir kustur ve bunlar bir “parçacik” olarak isimlendirilir. Tüm parçacilarin, optimize edilecek uygunluk fonksiyonu tarafindan degerlendirilen bir uygunluk degeri ve uçuslarini yönlendiren hiz bilgileri vardir. Parçaciklar problem uzayinda mevcut optimum parçaciklari takip ederek uçarlar.

PSO bir grup rasgele üretilmis çözümle (parçacikla) baslatilir ve jenerasyonlar güncellenerek en uygun deger arastirilir. Her iterasyonda, her bir parçacik iki “en iyi” degere göre güncellenir. Bunlardan birincisi bir parçacigin o ana kadar buldugu en iyi uygunluk degeridir. Ayrica bu deger daha sonra kullanilmak üzere hafiza tutulur ve “pbest” yani parçacigin en iyi degeri olarak isimlendirilir.  Diger en iyi deger ise popülâsyondaki herhangi bir parçacik tarafindan o ana kadar elde edilmis en iyi uygunluk degerine sahip çözümdür. Bu deger popülasyon için global en iyi degerdir ve “gbest” olarak isimlendirilir.

 D adet parametreden olusan n adet parçacik için popülasyon matrisi yandaki gibi ifade edilir. Matrise göre, i. parçacik ve , seklinde gösterilir. i’ninci parçacigin her konumdaki degisim miktarini göster hiz vektörü  olarak ifade edilir.  Bu iki en iyi deger bulunduktan sonra; parçacik, hizini ve konumu sirasiyla asagidaki (1) ve (2) denklemlerine göre günceller.

 

                                                 (1)

                                                                                                        (2)

 

Burada (0,1) arasinda üretilen rasgele bir degeri, i parçacik numarasi, k ise iterasyon sayisini gösterir. C1 ve C2 ögrenme faktörleridir. Bunlar parçaciklari  ve  konumlarina dogru yönlendiren sabitlerdir. C1 parçacigin kendi tecrübelerine göre, C2 ise sürüdeki diger parçaciklarin tecrübelerine göre hareketi yönlendirir. Düsük degerler seçilmesi parçaciklarin hedef bölgeye dogru çekilmeden önce, bu bölgeden uzak yerlerde dolasmalarina imkân verir. Ancak hedefe ulasma süresi uzayabilir. Diger yandan, yüksek degerler seçilmesi, hedefe ulasmayi hizlandirirken, beklenmedik hareketlerin olusmasina ve hedef bölgenin es geçilmesine sebep olabilir. Genellikle C1=C2=2 olarak almanin iyi sonuçlar verdigi belirtilmistir.

.

Asagida PSO algoritmasinin Pseudocode’u verilmistir.

 

 

 

 

 

 

 

 

 

 

 

PSO PARAMETRELERI

 PSO’nun avantajlarindan birisi reel sayilarla çalisiyor olmasidir. Genetik algoritmalardaki gibi hesaplama yapabilmek için ikili kodlamadan dönüstürme yapilmasi ya da bazi özel kullanilmasi zorunlu operatörlere ihtiyaç duyulmaz. Örnegin  fonksiyonu için çözümü bulmayi deneyelim. Burada 3 bilinmeyen oldugundan dolayi D=3 boyutludur ve parçacik seklinde ayarlanir.  fonksiyonu da uygunluk fonksiyonu olarak kullanilir. Daha sonra yukarida verilen standart prosedür optimumu bulmak için uygulanir. Sonlanma kriteri olarak maksimum iterasyon sayisi veya minimum hata kosulu saglanmasi kullanilir. Görüldügü gibi PSO’da ihtiyaç duyulan çok az sayida parametre vardir. Bu parametrelerin listesi ve tipik olarak aldiklari degerler asagida verilmektedir.

Parçacik Sayisi; genellikle 20 ila 40 arasinda alinir. Aslinda çogu problem için sayiyi 10 almak iyi çözümler elde etmek için yeterlidir. Bazi zor veya özel problemler için 100 veya 200 parçacik kullanilmasi gerekebilir.

Parçacik boyutu; Optimize edilecek probleme göre degismektedir.

Parçacik araligi; Optimize edilecek probleme göre degismekle birlikte farkli boyutlarda ve araliklarda parçaciklar tanimlanabilir.

Vmax: Bir iterasyonda, bir parçacikta meydana gelecek maksimum degisikligi (hiz) belirler. Genellikle parçacik araligina göre belirlenir. Örnegin X1 parçacigi (-10,10) araliginda ise Vmax=20 sinirlandirilabilir.

Ögrenme Faktörleri: c1 ve c2 genellikle 2 olarak seçilir. Fakat farkli da seçilebilir. Genellikle c1, c2 ye esit ve [0, 4] araliginda seçilir.

Durma Kosulu: Maksimum iterasyon sayisina ulasildiginda veya deger fonksiyonu istenilen seviyeye ulastiginda algoritma durdurulabilir.

 

SAYISAL ÇÖZÜM ÖRNEGI

 Bu bölümde PSO algoritmasinin çalisma mantiginin daha somut bir sekilde anlasilabilmesi için bir örnek üzerinden hesaplamalar incelenecektir. Bu amaçla literatürde “Six-hump Camel-back (alti-kamburlu deve-sirti)” fonksiyonu olarak bilinen test fonksiyonu ele alinmaktadir. Problemin bu sekilde isimlendirilmesinin sebebi ikisi küresel minimum olmak üzere toplamda 6 yerel minimuma sahip olmasidir. Fonksiyon asagida verildigi gibidir:

Six-Hump Camel-Back Test Fonksiyonu

 

Fonksiyonunun minimum oldugu nokta PSO ile arastirilacaktir. Buna göre ele alinan problem  ve  olmak üzere toplamda iki bilinmeyenden olusmaktadir. Yani  boyutludur.  Algoritmanin 10 parçacikla ve  ögrenme faktörü sabitleriyle arama uzayinda çalistirilacagi varsayilmistir.

Adim-1:           Parçaciklar parametrelerin aralik degerlerine uygun bir sekilde rasgele olusturulur ve uygunluk degerleri uygunluk fonksiyonu kullanilarak hesaplanir. Ilk iterasyon için her bir parçacigin pbest degeri kendisine esittir. Buradan elde edilen en iyi degere karsilik gelen parçacik gbest olarak seçilir. Buna göre olusturulmus 10 parçacik Tablo-1’de görülmektedir.

Tablo 1: Birinci iterasyonda rasgele olusturulan parçacik degerleri

 

Adim-2: Her bir parçacik için denklem (2)’ye göre parçacik hizlari hesaplanir. Burada yalniz P1 için hesaplama yapilmakta ve diger parçaciklarin sonuçlari Tablo-2’de verilmektedir.

 

 Buna göre;

 

 

Tablo 2: Birinci iterasyon için hesaplanan hiz degerleri

 

 

NOT: Tablo-2’de verilen rand1 ve rand2 degerleri [0,1] araliginda seçile rasgele degerlerdir. Bu degerler normalde program için çalisma zamaninda üretilir.

Adim-3: Her bir parçacik için denklem (3)’e göre parçacik konumunu güncellenir. Burada yalniz P1 için hesaplama yapilmakta ve diger parçaciklarin sonuçlari Tablo-3’de verilmektedir.

 

_{Buna göre;}

 

Tablo 3: Birinci iterasyon için hesaplanan konum degerleri

 

Yeni konum degerleri elde edildikten sonra bu degerler kullanilarak tekrar basa dönülür uygunluk degerleri hesaplanir, ve degerleri güncellenir. Sonlanma kriteri saglanincaya kadar islemlere devam edilir.

KAYNAKLAR 

[1]	http://www.swarmintelligence.org/tutorials.php
[2]	http://www.engr.iupui.edu/~eberhart/
[3]	http://users.erols.com/cathyk/jimk.html
[4]	http://www.alife.org
[5]	http://www.aridolan.com
[6]	http://www.red3d.com/cwr/boids/
[7]	http://iridia.ulb.ac.be/~mdorigo/ACO/ACO.html
[8]	http://www.engr.iupui.edu/~shi/Coference/psopap4.html
[9]	Kennedy, J. and Eberhart, R. C. Particle swarm optimization. Proc. IEEE int'l conf. on neural networks Vol. IV, pp. 1942-1948. IEEE service center, Piscataway, NJ, 1995.
[10]	Eberhart, R. C. and Kennedy, J. A new optimizer using particle swarm theory. Proceedings of the sixth international symposium on micro machine and human science pp. 39-43. IEEE service center, Piscataway, NJ, Nagoya, Japan, 1995.
[11]	Eberhart, R. C. and Shi, Y. Particle swarm optimization: developments, applications and resources. Proc. congress on evolutionary computation 2001 IEEE service center, Piscataway, NJ., Seoul, Korea., 2001.
[12]	Eberhart, R. C. and Shi, Y. Evolving artificial neural networks. Proc. 1998 Int'l Conf. on neural networks and brain pp. PL5-PL13. Beijing, P. R. China, 1998.
[13]	Eberhart, R. C. and Shi, Y. Comparison between genetic algorithms and particle swarm optimization. Evolutionary programming vii: proc. 7th ann. conf. on evolutionary conf., Springer-Verlag, Berlin, San Diego, CA., 1998.
[14]	Shi, Y. and Eberhart, R. C. Parameter selection in particle swarm optimization. Evolutionary Programming VII: Proc. EP 98 pp. 591-600. Springer-Verlag, New York, 1998.
[15]	Shi, Y. and Eberhart, R. C. A modified particle swarm optimizer. Proceedings of the IEEE International Conference on Evolutionary Computation pp. 69-73. IEEE Press, Piscataway, NJ, 1998