:::: MENU ::::
Particle Swarm Optimization

Binary Particle Swarm Optimization: Challenges and New Solutions

“Binary Particle Swarm Optimization: Challenges and New Solutions” başlıklı çalışma Hossein Nezamabadi-pour , Majid Rostami-sharbabaki , Malihe Maghfoori-Farsangi tarafından yapılmış olup CSI J Comput Sci Eng dergisinin 2008 yılındaki 6.1 cildinin 21-32.sayfaları arasında basılmıştır.

Sigmoid fonksiyonu yerine:

s

fonksiyonu kullanılmıştır.

Ayrıca;

rands

kullanılmıştır.

Sigmoid yerine önerilen fonksiyonun grafiği:

proposed

Çalışmayı indirmek için:

Binary_Particle_Swarm_Optimization_Challenges_and_New_Solutions


A Discrete Particle Swarm Optimization Algorithm for Uncapacitated Facility Location Problem

“A Discrete Particle Swarm Optimization Algorithm for Uncapacitated Facility Location Problem” başlıklı çalışma Ali R. Guner ve Mehmet Sevkli tarafından yapılmış olup Journal of Artificial Evolution and Applications dergisinde 2008 yılında yayınlanmıştır.

Sürekli değerler mod işlemi ile ikili hale çevrilmiştir. Mutasyon ve Crossover işlemi uygulanmıştır. Local search modülü eklenmiştir. Çalışmada PSO parçacık sayısını kaç aldıklarını yazmamışlar veya ben göremedim 🙂

Çalışmayı indirmek için:

A_Discrete_Particle_Swarm_Optimization_Algorithm_for_Uncapacitated_Facility_Location_Problem


A Modified Continuous Particle Swarm Optimization Algorithm for Uncapacitated Facility Location Problem

“A Modified Continuous Particle Swarm Optimization Algorithm for Uncapacitated Facility Location Problem” başlıklı çalışma Sujay Saha, Arnab Kole ve Kashinath Dey tarafından yapılmış olup 2011 yılında Information Technology and Mobile Communication (pp. 305-311). Springer Berlin Heidelberg’de basılmıştır.

İkilileştirme işlemi sürekli değerlerinin 2’ye göre modunun alınması ile gerçekleştirilmiştir.
Çalışmada üretilen rastgele r1 sayısı 0.5 olduğu zaman parçacık=0 ve r2 sayısı 0.5 olduğu zaman hız=0 alınmıştır. Aksi durumlarda mod alma ile değerler oluşturulmuştur.

inertia weight 0.9 – 0.4 aralığında iterasyon sayısına bağlı olarak azalan şekilde ayarlanmıştır.

Sürekli değerlerle işlem yaptığı için hedeflenen optimal costlara yakın değerler üretilebilmiştir.

optimaller

Çalışmayı indirmek için:

A_Modified_Continuous_Particle_Swarm_Optimization_Algorithm_for_Uncapacitated_Facility_Location_Problem


GPU based parallel cooperative particle swarm optimization using C-CUDA: a case study

“GPU based parallel cooperative particle swarm optimization using C-CUDA: a case study.” başlıklı çalışma Kumar, Jitendra, Lotika Singh ve Sandeep Paul tarafından yapılmış olup Fuzzy Systems (FUZZ), 2013 IEEE International Conference on. IEEE konferansında 2013 yılında sunulmuştur.

Evrimsel algoritmaları CUDA üzerinde gerçeklemenin hızlanmaya katkısı olduğu gibi, yakınsama zamanında iyileşme(improvement in convergence time) yaptığı da görülmektedir.

Çalışmada CUDA üzerinde Cooperative Particle Swarm Optimization (CPSO) algoritması gerçeklenmiştir.

Çalışmada CUDA’nın randomize sınıfının popülasyon çeşitliliğini daha iyi ürettiği belirtilmiştir.

CPSO çalışması: van den Bergh, Frans, Andries P. Engelbrecht, and A. P. Engelbrecht. “Cooperative learning in neural networks using particle swarm optimizers.” South African Computer Journal. 2000. APA

CUDA(COMPUTE UNIFIED DEVICE ARCHITECTURE)

CUDA, NVIDIA tarafından geliştirilmiş bir yazılım ve donanım mimarisidir. CUDA, SIMD (Single Instruction Multiple Data) programlama modeline uygun çalışma gösterir. CPU ve GPU birlikte işleme yapar. Aynı anda çok sayıda thread çalıştığından SIMT (Single Instruction Multiple Threads) programlama modeli şeklinde isimlendirilmiştir.

GPU’da çalışan koda kernel ismi verilmektedir. Kodun bir de CPU’da çalışan kısmı mevcuttur.

CUDA grid, block ve thread yapısı

grid-block-thread

GPU bellek hiyerarşisi aşağıda görülmektedir.

gpu-memory-hierarchy-model

Evrimsel algoritmaların fitness değerlendirme işlemi GPU’da yapılarak zaman kazanımı sağlanmaktadır.

Cooperative Particle Swarm Optimization (CPSO)

Kooperatif PSO’da parçacıklar arasında bir yarıştan ziyade yardımlaşma fikri ön plana çıkarılmıştır. Popülasyon n farklı alt popülasyona bölünür ve her bir alt bölüm ayrı ayrı çözüme ulaşmaya çalışır.

CPSO’nun bölünmüş sürü yaklaşımı:

pseudo-code-for-split-swarm-approach-assuming-m-particles-per-swarm

n=5 ve D=1000 için düşünelim.
M=Parçacık Sayısı

n adet D boyutlu S1..Sn arasında sürü oluşturulur. {5 adet 1000 boyutlu sürü oluşturulur}
Durdurma kriteri sağlanıncaya kadar:
—S1–Sn sürülerinin her birinden en iyi parçacıkları seç(b1–bn)
—— For k:1-M, i:1:n
———- p=Si sürüsünün k.parçacığı
———- v =(b1;b2;:;p;:;bn) – Bir vektör oluşturulur
———- E(v)= error function at v
———- E(v)’yi kullanarak Si sürüsündeki k parçacığının fitnesini ayarla
———- b1–bn deki en iyi fitnessleri gerekliyse güncelle
—— S1–Sn sürülerinin normal PSO güncellemelerini yap
—Durdurma kriteri.

CPSO’da her bir jenerasyonda 4ns yani (2 pBest hesabı, 2 gBest hesabı)xBoyut SayısıXPopülasyon Sayısı kadar fonksiyon değerlemesi yapmaktadır. 1000 boyutlu 20 parçacıklı bir sistemde 80000 FEs yapılır. Çok fonksiyon değerlemesi yapıldığından paralel programlama çözümü uygun bir yaklaşımdır.

GPU destekli CPSO algoritmasının sözde kodu:

parallel_implementation_using_gpu

Paralel olarak fitness değerlemesi aşağıdaki şekilde yapılmaktadır:

parallel-implementation-of-fitness-evaluation

Hesaplama işlemi atomic operations ile yapılmaktadır. Böylece aynı anda aynı bölgeye tek bir yazma işlemi gerçekleştirilmektedir. Sonuçlar shared memory’ye yazılmaktadır.

context vector oluşumu aşağıdaki şekilde yapılmaktadır:

context-vector-generation

Tüm adımlar aşağıdaki şekilde görselleştirilmiştir:

implementation-diagram-of-cpso-on-gpu-using-c-cuda

İşlemler GPU’da yapılırken organizasyon CPU tarafından yürütülmektedir.

Çalışmada 𝑐1 = 𝑐2 = 2.05 ve 𝑤 = 0.25 alınmıştır.

Çalışmanın yapıldığı makinanın özellikleri:
pc

Test fonksiyonları:

test-fonksiyonlari

CUDA’da thread/block sayısını belirlemek de önemli bir karardır. Sonuca etki etmektedir. Aşağıda farklı boyutlarda farklı thread/block sayısın etkisi görülmektedir.

hizlanma-threads-block

100 jenerasyonda 500,1000,1500 boyutta farklı threads/block sayısına göre sonuçlar:

100-generations

Her thread bir boyutta işlem yapmaktadır ve her blokta ⌈𝑛/𝑘⌉ Boyut/Block’taki Thread Sayısı kadar eleman işlenmektedir.

Farklı fonksiyonlarda farklı hızlanmaların elde edilmesinin nedeni fonksiyonun hesaplama karmaşıklığı ile alakalıdır.

1000 jenerasyonda ulaşılan sonuçlar:

1000-jenerasyon

Yakınsama analizi ve popülasyon çeşitliliğini izleme adına yapılan çalışmada:

std

Paralel versiyonun daha iyi yakınsadığı ve daha erken istenen sonuca ulaştığı görülmektedir. Bunun nedeni olarak CUDA’nın rastgele sayı üretme tekniğinin daha iyi olduğu sonucuna varılmıştır. Ayrıca CPU’da tek noktalı bir rastgele sayı üretme durumu var iken, burada her bir GPU çekirdeği için ayrı bir rastgele sayı üretme çekirdeği vardır.

Çalışmayı indirmek için:
gpu_based_parallel_cooperative_particle_swarm_optimization_using_c_cuda_a_case_study


Sayfalar:12