Parçacık Sürü Optimizasyonu -PSO-NEDİR?

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. 

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ü. 

ALGORİTMA

 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ü  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 PARAMETRELERİ

 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.

Öğ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.

SAYISAL ÇÖZÜM ÖRNEĞİ

 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  ve  olmak üzere toplamda iki bilinmeyenden oluşmaktadır. Yani  boyutludur.  Algoritmanın 10 parçacıkla ve  öğrenme faktörü sabitleriyle arama uzayında çalıştırılacağı varsayılmıştır.

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	pbest
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
			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.

 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;}

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.