Parçacık Sürü Algoritması

Karabük Üniversitesi, Mühendislik Fakültesi.........................................................................................................www.ibrahimcayiroglu.com
İLERİ ALGORİTMA ANALİZİ
PARÇACIK SÜRÜ ALGORİTMASI (Particle Swarm)
Giriş
Parçacık Sürü Optimizasyonu (Particle Swarm Optimization) (PSO) 1995’te 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
esinlenilerek geliştirilmiştir.
PSO, Genetik Algoritmalar gibi evrimsel hesaplama teknikleri ile birçok benzerlikler gösterir. Sistem random çözümlerden
oluşan bir popülasyonla başlatılır ve en iyi çözüm için jenerasyonları güncelleyerek arama yapar. Buna karşın, GA’nın
tersine, PSO’da çaprazlama ve mutasyon gibi evrimsel operatörler yoktur. PSO’da parçacık(particles)denilen potansiyel
çözümler, mevcut en iyi çözümleri takip ederek problem uzayında gezinirler (uçuş yaparlar).
GA ile karşılaştırılırsa; PSO’nun avantajı gerçekleştirilmesinin kolay olmasıdır ve ayarlanması gereken çok az parametresi
vardır. PSO pek çok alanda başarılı bir şekilde uygulanmıştır. Bunlardan bazıları; fonksiyon optimizasyonu, yapay sinir ağları
eğitimi, bulanık sistem kontrolü ve GA’nın uygulanabildiği diğer alanlardır.
Biyolojik sistemlerden esinlenen birçok hesaplama tekniği mevcuttur. Örneğin yapay sinir ağları insan beyninin
basitleştirilmiş bir modelidir. Genetik algoritmalar biyolojideki evrimsel süreçten esinlenir. Burada ise ele alınan konu
biyolojik sistemlerin farklı bir türü olan sosyal sistemlerdir. Özellikle birbiriyle ve çevresiyle etkileşim içinde olan basit
bireylerin birliktelik davranışları incelenmektedir. Bu kavram parçacık zekâsı olarak isimlendirilir.
Sayısal zekâ alanında parçacıklardan esinlenen iki popüler metot vardır: Karınca Koloni Optimizasyonu (ACO) ve Parçacık
Sürü Optimizasyonu (PSO). ACO karıncaların davranışlarından esinlenir ve ayrık optimizasyon problemlerinde birçok başarılı
uygulaması vardır. (http://iridia.ulb.ac.be/~mdorigo/ACO/ACO.html)
Parçacık sürüsü kavramı basitleştirilmiş sosyal sistemin benzetimi olarak oluşturuldu. Asıl amaç bir kuş veya balık sürüsü
koreografisinin grafiksel olarak benzetimini yapmaktı. Ancak parçacık sürüsü modelinin bir optimizasyon aracı olarak
kullanılabileceği düşünüldü. (http://www.engr.iupui.edu/~shi/Coference/psopap4.html)
Algoritma
Daha önce de açıklandığı gibi, PSO kuş veya balık sürüsünün davranışlarını benzetir. Bir alanda rasgele yiyecek arayan bir
kuş grubunun olduğunu ve arama yapılan alanda yalnızca bir parça yiyecek olduğunu varsayalım. Kuşların hiçbiri yiyeceğin
nerede olduğunu bilmesin. Fakat her bir iterasyon sonunda yiyeceğin ne kadar uzakta olduğunu bilsinler. Bu durumda en iyi
strateji nedir? En etkili olanı yiyeceğe en yakın olan kuşu takip etmektir.
PSO bu senaryoya göre çalışır ve optimizasyon problemlerini çözmek için kullanılır. PSO’da her bir çözüm arama uzayındaki
bir kuştur ve bunlar bir “parçacık” olarak isimlendirilir. Tüm parçacıların, optimize edilecek uygunluk fonksiyonu tarafından
değerlendirilen bir uygunluk değeri ve uçuşlarını yönlendiren hız bilgileri vardır. Parçacıklar problem uzayında mevcut
optimum parçacıkları takip ederek uçarlar.
PSO bir grup rasgele üretilmiş çözümle (parçacıkla) başlatılır ve jenerasyonlar güncellenerek en uygun değer araştırılır. Her
iterasyonda, her bir parçacık iki “en iyi” değere göre güncellenir. Bunlardan birincisi bir parçacığın o ana kadar bulduğu en iyi
uygunluk değeridir. Ayrıca bu değer daha sonra kullanılmak üzere hafıza tutulur ve “pbest” yani parçacığın en iyi değeri
olarak isimlendirilir. Diğer en iyi değer ise popülâsyondaki herhangi bir parçacık tarafından o ana kadar elde edilmiş en iyi
uygunluk değerine sahip çözümdür. Bu değer popülasyon için global en iyi değerdir ve “gbest” olarak isimlendirilir.
D adet parametreden oluşan n adet parçacık için popülasyon matrisi yandaki gibi ifade edilir. Matrise göre, i. parçacık
ve
,
şeklinde gösterilir. i’ninci parçacığın her konumdaki değişim miktarını göster hız vektörü
Karabük Üniversitesi, Mühendislik Fakültesi.........................................................................................................www.ibrahimcayiroglu.com
olarak ifade edilir. Bu iki en iyi değer bulunduktan sonra; parçacık, hızını ve konumu sırasıyla aşağıdaki (1) ve (2)
denklemlerine göre günceller.
(1)
(2)
Burada
(0,1) arasında üretilen rasgele bir değeri, i parçacık numarası, k ise iterasyon sayısını gösterir. C1 ve C2
öğrenme faktörleridir. Bunlar parçacıkları
ve
konumlarına doğru yönlendiren sabitlerdir. C1 parçacığın kendi
tecrübelerine göre, C2 ise sürüdeki diğer parçacıkların tecrübelerine göre hareketi yönlendirir. Düşük değerler seçilmesi
parçacıkların hedef bölgeye doğru çekilmeden önce, bu bölgeden uzak yerlerde dolaşmalarına imkân verir. Ancak hedefe
ulaşma süresi uzayabilir. Diğer yandan, yüksek değerler seçilmesi, hedefe ulaşmayı hızlandırırken, beklenmedik hareketlerin
oluşmasına ve hedef bölgenin es geçilmesine sebep olabilir. Genellikle C1=C2=2 olarak almanın iyi sonuçlar verdiği
belirtilmiştir.
Aşağıda PSO algoritmasının Pseudocode’u verilmiştir.
PSO Parametreleri
PSO’nun avantajlarından birisi reel sayılarla çalışıyor olmasıdır. Genetik algoritmalardaki gibi hesaplama yapabilmek için ikili
kodlamadan dönüştürme yapılması ya da bazı özel kullanılması zorunlu operatörlere ihtiyaç duyulmaz. Örneğin
fonksiyonu için çözümü bulmayı deneyelim. Burada 3 bilinmeyen olduğundan dolayı D=3 boyutludur ve
parçacık
şeklinde ayarlanır.
fonksiyonu da uygunluk fonksiyonu olarak kullanılır. Daha sonra yukarıda verilen
standart prosedür optimumu bulmak için uygulanır. Sonlanma kriteri olarak maksimum iterasyon sayısı veya minimum hata
koşulu sağlanması kullanılır. Görüldüğü gibi PSO’da ihtiyaç duyulan çok az sayıda parametre vardır. Bu parametrelerin listesi
ve tipik olarak aldıkları değerler aşağıda verilmektedir.
Parçacık Sayısı; genellikle 20 ila 40 arasında alınır. Aslında çoğu problem için sayıyı 10 almak iyi çözümler elde etmek için
yeterlidir. Bazı zor veya özel problemler için 100 veya 200 parçacık kullanılması gerekebilir.
Parçacık boyutu; Optimize edilecek probleme göre değişmektedir.
Parçacık aralığı; Optimize edilecek probleme göre değişmekle birlikte farklı boyutlarda ve aralıklarda parçacıklar
tanımlanabilir.
Vmax: Bir iterasyonda, bir parçacıkta meydana gelecek maksimum değişikliği (hız) belirler. Genellikle parçacık aralığına göre
belirlenir. Örneğin X1 parçacığı (-10,10) aralığında ise Vmax=20 sınırlandırılabilir.
Karabük Üniversitesi, Mühendislik Fakültesi.........................................................................................................www.ibrahimcayiroglu.com
Öğrenme Faktörleri: c1 ve c2 genellikle 2 olarak seçilir. Fakat farklı da seçilebilir. Genellikle c1, c2 ye eşit ve [0, 4] aralığında
seçilir.
Durma Koşulu: Maksimum iterasyon sayısına ulaşıldığında veya değer fonksiyonu istenilen seviyeye ulaştığında algoritma
durdurulabilir.
Sayısal Çözüm Örneği
Bu bölümde PSO algoritmasının çalışma mantığının daha somut bir şekilde anlaşılabilmesi için bir örnek üzerinden
hesaplamalar incelenecektir. Bu amaçla literatürde “Six-hump Camel-back (altı-kamburlu deve-sırtı)” fonksiyonu olarak bilinen test
fonksiyonu ele alınmaktadır. Problemin bu şekilde isimlendirilmesinin sebebi ikisi küresel minimum olmak üzere toplamda 6
yerel minimuma sahip olmasıdır. Fonksiyon aşağıda verildiği gibidir:
Six-Hump Camel-Back Test Fonksiyonu
Fonksiyonunun minimum olduğu nokta PSO ile araştırılacaktır. Buna göre ele alınan problem
toplamda iki bilinmeyenden oluşmaktadır. Yani
boyutludur. Algoritmanın 10 parçacıkla ve
faktörü sabitleriyle arama uzayında çalıştırılacağı varsayılmıştır.
ve
olmak üzere
öğrenme
Adım-1: Parçacıklar parametrelerin aralık değerlerine uygun bir şekilde rasgele oluşturulur ve uygunluk değerleri uygunluk
fonksiyonu kullanılarak hesaplanır. İlk iterasyon için her bir parçacığın pbest değeri kendisine eşittir. Buradan elde edilen en
iyi değere karşılık gelen parçacık gbest olarak seçilir. Buna göre oluşturulmuş 10 parçacık Tablo-1’de görülmektedir.
Tablo 1: Birinci iterasyonda rasgele oluşturulan parçacık değerleri
Parçacık
Uygunluk Değeri
P1
-3,7060195
2,81307351
707,5444175
P2
1,30101908
-1,6908636
24,47949005
P3
3,5723814
-3,3609453
156,3683986
P4
1,2363086
2,8388213
258,3875547
P5
-2,0099463
1,61072044
-10,58678451
P6
-2,6013287
0,75244956
-96,83639806
P7
-1,5921306
2,24163608
83,9370077
P8
-4,9807337
-4,3846604
207,8923222
P9
-3,5026999
-2,6985498
-94,5324658
P10
-3,3496718
4,677583
1634,851374
pbest
gbest =
Adım-2: Her bir parçacık için denklem (2)’ye göre parçacık hızları hesaplanır. Burada yalnız P1 için hesaplama yapılmakta ve
diğer parçacıkların sonuçları Tablo-2’de verilmektedir.
Karabük Üniversitesi, Mühendislik Fakültesi.........................................................................................................www.ibrahimcayiroglu.com
Buna göre;
Tablo 2: Birinci iterasyon için hesaplanan hız değerleri
Parçacık
rand1
rand2
P1
2,035288
-1,44282
0,4
0,6
P2
-5,29754
5,282534
0,3
0,8
P3
-8,57238
8,360945
0,1
0,9
P4
-5,19401
-1,96496
0,7
0,8
P5
0
0
0,5
0,1
P6
0,473106
0,686617
0,4
0,4
P7
-0,25069
-0,37855
0,9
0,3
P8
0
0
0,3
0
P9
0,597101
1,723708
0,1
0,2
P10
1,339726
-3,06686
0,6
0,5
NOT: Tablo-2’de verilen rand1 ve rand2 değerleri [0,1] aralığında seçile rasgele değerlerdir. Bu değerler normalde program
için çalışma zamanında üretilir.
Adım-3: Her bir parçacık için denklem (3)’e göre parçacık konumunu güncellenir. Burada yalnız P1 için hesaplama
yapılmakta ve diğer parçacıkların sonuçları Tablo-3’de verilmektedir.
Buna göre;
Karabük Üniversitesi, Mühendislik Fakültesi.........................................................................................................www.ibrahimcayiroglu.com
Tablo 3: Birinci iterasyon için hesaplanan konum değerleri
Parçacık
P1
-3,70602
2,035288
2,813074
-1,44282
-1,67073
1,37025
P2
1,301019
-5,29754
-1,69086
5,282534
-3,99653
3,591671
P3
3,572381
-8,57238
-3,36095
8,360945
-5
5
P4
1,236309
-5,19401
2,838821
-1,96496
-3,9577
0,87386
P5
-2,00995
0
1,61072
0
-2,00995
1,61072
P6
-2,60133
0,473106
0,75245
0,686617
-2,12822
1,439066
P7
-1,59213
-0,25069
2,241636
-0,37855
-1,84282
1,863087
P8
-4,98073
0
-4,38466
0
-4,98073
-4,38466
P9
-3,5027
0,597101
-2,69855
1,723708
-2,9056
-0,97484
P10
-3,34967
1,339726
4,677583
-3,06686
-2,00995
1,61072
Yeni konum değerleri elde edildikten sonra bu değerler kullanılarak tekrar başa dönülür uygunluk değerleri hesaplanır,
ve
değerleri güncellenir. Sonlanma kriteri sağlanıncaya kadar işlemlere devam edilir.
Kaynaklar
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
http://www.swarmintelligence.org/tutorials.php
http://www.engr.iupui.edu/~eberhart/
http://users.erols.com/cathyk/jimk.html
http://www.alife.org
http://www.aridolan.com
http://www.red3d.com/cwr/boids/
http://iridia.ulb.ac.be/~mdorigo/ACO/ACO.html
http://www.engr.iupui.edu/~shi/Coference/psopap4.html
Kennedy, J. and Eberhart, R. C. Particle swarm optimization. Proc. IEEE int'l conf. on neural networks Vol. IV, pp. 19421948. IEEE service center, Piscataway, NJ, 1995.
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.
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.
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.
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.
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.
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
http://www.yazilimmutfagi.com
Videolar
1.
2.
http://www.youtube.com/watch?v=RLIA1EKfSys
BU NOTLAR DÜZENLENECEK..!