:::: MENU ::::
İncelemeler

A Particle Swarm Optimizer for Constrained Numerical Optimization

“A Particle Swarm Optimizer for Constrained Numerical Optimization” başlıklı çalışma Leticia C. Cagnina, Susana C. Esquivel, Carlos A. Coello Coello tarafından 2006 yılında “Parallel Problem Solving from Nature” kitabının bir alt bölümü olarak yayınlanmıştır.

Çalışmada Parçacık Sürü Optimizasyonu algoritmasının kısıtlı sayısal optimizasyon için uyarlanması sağlanmıştır.

Bir kısıtlı optimizasyon probleminde;
-Amaç fonksiyonu
-Problemin boyutu
-Kısıtlar(Eşitlikler ve Eşitsizlikler)
bulunur.

Kısıtları sağlayan değerler feasible(olurlu), sağlamayan değerlere infeasible(olanaksız) denir. Kısıtlar arama uzayını feasible ve infeasible alanlara böler. Arama uzayı problemin boyutu ile aynı büyüklükte ve ilgili değişkenlerin alt ve üst sınırlarına göre belirlenen bir alandır.

Çalışmada eşitlik şeklinde olan kısıtların işlenmesinin daha zor olduğu belirtilerek eşitsizliğe çevrilmiştir.

Eşitliği eşitsizliğe dönüştürme nedir?
Eşitlik biçimindeki bir kısıtlayıcı fonksiyon iki eşitsizlikle açıklanabilir.
Örneğin, a11x1 + a12x2 = b1 biçimindeki bir fonksiyon yerine,
a11x1 + a12x2 >= b1 ve a11x1 + a12x2 <= b1 veya a11x1 + a12x2 <= b ve -a11x1 - a12x2 <= -b1 yazılabilir. Çalışmada PSO algoritmasındaki hız(velocity) hesaplama formülü de modifiye edilmiştir. cpso-velocity

Çalışmada komşu olarak anılan parçanın seçimi aşağıdaki sistemle yapılmaktadır. Örneğin komşuluk boyutu=4 ise aralarında en iyi olan seçilmektedir.

Lokal minimumlara takılmayı ve uzun süre gelişememe durumunu ortadan kaldırmak için dinamik bir mutasyon operatörü önerilmiştir. pm olarak isimlendirilen bu operatör aşağıdaki şekilde hesaplanmıştır.

probability-cpso

Çalışmada denemelerde bu metodun iyi sonuçlar vermediğine değinerek, klasik güncelle denklemine müdahale ettiklerini bildirmişler. Verilen olasılık değerlerine göre ya normal güncelleme denklemi kullanılır ya da aşağıdaki denklem kullanılır.

cpso-update-rule

CPSO’nun çözmekte zorlandığı ve iyi sonuçlar üretemediği 2,6 ve 13. kıyas fonksiyonları için yapılan güncellemeler sonucunda aşağıdaki değerler bulunmuştur.

function-2-6-13

CPSO Pseudo Code:

cpso-pseudo-code

Çalışma;
Thomas Philip Runarsson and Xin Yao, Stochastic Ranking for Constrained Evolutionary Optimization. IEEE Transactions on Evolutionary Computation, Vol. 4, No. 3, pp. 284-294, September 2000.
ve
Pulido, Gregorio Toscano, and Carlos A. Coello Coello. “A constraint-handling mechanism for particle swarm optimization.” Evolutionary Computation, 2004. CEC2004. Congress on. Vol. 2. Ieee, 2004.
APA
çalışmalarıyla kıyaslanmıştır.

Parametreler:
cpso-parameters

Kıyaslamalı Sonuçlar:

cpso-results

CPSO’nun Sonuçları:
best-mean-worst

PSOtos Sonuçları:
pso-tos

SR Sonuçları:

sr

Makaleyi indirmek için:
A_Particle_Swarm_Optimizer_for_Constrained_Numerical_Optimization


A parallel Bees Algorithm implementation on GPU

“A parallel Bees Algorithm implementation on GPU” başlıklı makale Journal of Systems Architecture dergisinin 2014 yılında yayınlanan 60.sayısının 271-279.sayfalarında yayınlanmıştır. Makaleyi Guo-Heng Luo, Sheng-Kai Huang, Yue-Shan Chang ve Shyan-Ming Yuan yazmıştır.

Makaleyi indirmek için:
A-parallel-Bees-Algorithm-implementation-on-GPU
Çalışmada Arı Algoritması için paralel bir yaklaşım geliştirilerek CUBA(CUDA based Bees Algorithm) ismi verilmiştir.

Arı Algoritması bal arılarından esinlenen, popülasyon tabanlı bir arama optimizasyon problem çözüm yaklaşımıdır. Hem komşuluk aramasını, hem de rastgele aramayı kullanır. Sürü zekası tabanlı yaklaşımlar optimizasyon problemlerinin çözüm sürelerini hayli düşürmüştür. Bu yaklaşımlar paralelleştirme yöntemiyle çok daha hızlı bir şekilde sonuca ulaşacak şekilde yeniden uyarlanmaktadır. Burada çözüm kalitesini artırma gibi bir hedef yoktur. Arı Algoritmasına için daha önce sunulan paralel yaklaşımda kolonilerin mevcut işlemcilere bölünmesi esasına göre bir yol izlenmiştir. (H. Narasimhan, Parallel artificial bee colony (PABC) algorithm, in: 2009 World
Congress on Nature & Biologically Inspired Computing, 2009, pp. 306–311.)

Konuyla ilgili benzer bir çalışmada(A.K.R. Mohamad Idris, M.W. Mustafa, A Parallel Bees Algorithm for ATC
enhancement in modern electrical network, in: 2010 Fourth Asia International
Conference on Mathematical/Analytical Modelling and Computer, Simulation,
2010, pp. 450–455.) modern elektrik ağlarında mevcut transfer yeteneğini artırmaya yönelik paralel arı algoritması önerilmiştir.

Arı algoritmasının FPGA (Field Programmable Gate Array – Alanda Programlanabilir Kapı Dizileri) ile de uygulamasının yapıldığına dikkat çekilerek şimdiye kadar GPU üzerinde bir çalışma yapılmadığı belirtilmiştir. Çalışmanın ana amacının GPU üzerinde çalışan paralel arı algoritmasını dizayn etmek ve uygulamak olduğu açıklanmıştır.

Arı algoritmasının temel akış diyagramı:

BeesAlgorithm

Parametreler:
n (number of scout bees),
m (number of sites selected out of n visited sites),
e (number of best sites out of m selected sites),
nep (number of bees recruited for best e sites),
nsp (number of bees recruited for the other (m–e) selected sites),
ngh (initial size of patches which includes site and its neighbourhood)
stopping criterion

Komşuluk Daraltma(Neighbourhood shrinking)

Çiçek parçaları : a = {a1. . ., an} olarak tanımlanır ve:
ait

t o anda bulunulan iterasyon sayısını vermektedir.

Yerel bir noktada takılmayı engellemek için gelişimin olmadığı iterasyonlarda değer 0,8 oranında küçültülür.
ngh

Kaynağın Terk Edilmesi

Belirli bir iterasyon sonucunda iyileşme sağlanamadıysa işlem durdurulur. Daha iyi bir sonuç üretecek nokta kalmadıysa rastgele bir noktadan yeni bir arama başlatılabilir. İlgili çalışmada da bu tür modifikasyonların yapıldığı bir çalışmadaki(D.T. Pham, M. Castellani, The Bees Algorithm: modelling foraging behaviour to
solve continuous optimization problems, Proceeding of Institute Mechanical Engineering, C: Journal of Mechanical Engineering and Science 223 (12) (2009) 2919–2938.) Arı algoritması kullanılmıştır.

Esnek AC İletim Sistemleri (FACTS) cihazlarının yerleşimi için yapılan bir ilgili bir çalışma incelenmiştir. Bu çalışmada mevcut transfer yeteneği maksimize edilmek istenmektedir. Çalışmada Bees Algorithm (BA), Genetic Algorithm (GA) ve Parallel Genetic Algorithms (PGA) ile güzel sonuçlar elde edilmiş lakin BCO, GPU ile çalışır vaziyete getirilmemiştir.

Oluşturulan paralel yaklaşımda her bir thread kendi kolonisindeki bir bal arısını temsil etmektedir. Koloniler thread ID’lerine göre farklı bloklara bölünmektedir. Her blokta algoritma bağımsız olarak çalıştırılmaktadır. Her iterasyonda değişen bilgiler shared memory’e eklenerek diğer bloklarla paylaşımı sağlanmaktadır. Global memory ile her iterasyonda erişime geçilmemesi gecikme zamanının azalmasına ve boşa zaman harcanmasının önüne geçilmesine zemin hazırlamıştır. Farklı bloklardaki koloniler birbirleriyle iletişime geçmemektedir çünkü shared memory farklı blocklar tarafından erişilebilir değildir.

cuba

cuba-algoritmasi

Paralel olarak rastgele bir şekilde başlangıç değerleri oluşturulur.
Paralel olarak arıların değerleri ile fitness’lar hesaplanır.
Paralel olarak Odd–Even Sorting algorithm(Tek Çift Sıralama Algoritması) ile sıralamanın yapıldığı belirtilmektedir. Tek Çift Sıralama Algoritması, Bubble Sort temelli paralel bir sıralama algoritmasıdır ve n/2 adımda sıralama işlemini gerçekleştirmektedir.

Bir bloktaki koloni sayısı = Bir bloktaki thread sayısı/ Her kolonideki arı sayısı şeklinde tanımlanmıştır.
BlockDim = 256 ve N = 8 ise her blokta 32 koloni bulunmaktadır.

Çalışmada 9 farklı kıyaslama fonksiyonu kullanılmıştır:
Benchmark-functions

Sonuçlar incelendiğinde paralel yaklaşım kıyas fonksiyonlara bağlı olarak 13-56 kat arasında hızlı çalışmaktadır.
hizlanma


Arı Kolonisi Optimizasyon Algoritması Kullanarak En Kısa Yol Bulma

“Arı Kolonisi Optimizasyon Algoritması Kullanarak En Kısa Yol Bulma” başlıklı makale EMO Bilimsel Dergi’de yayınlanmış olup Mustafa Servet KIRAN, Mesut GÜNDÜZ ve Mehmet Akif ŞAHMAN tarafından yazılmıştır.

Çalışmada Arı Kolonisi Optimizasyon (BCO) Algoritmasının en kısa yol bulma problemleri üzerindeki başarısı araştırılmıştır. Gezgin satıcı problemi için üretilen mevcut çözümler incelenmiş, elde edilen sonuçlar
ile BCO algoritmasının bu probleme uygulanması sonucu elde edilen sonuçlar karşılaştırılmıştır. Kıyaslamalar neticesinde BCO’nun makul zamanlarda iyi sonuçlar verdiği ve düşük hata oranı ile çalıştığı görülmüştür.

“Arı Sistemi” kavramı Tomoya Sato ve Masafumi Hagiwara tarafından ortaya konulmuş gerçek arıların davranışlarından esinlenerek oluşturulan bir bir sezgisel algoritmadır.

BCO’nun sözde kodu aşağıdaki gibidir:
1. Başlatma:
B arıların sayısı,
I çevrim sayısı,
ST={st1,st2,...,stm}aşama sayısı,
x problemin herhangi bir çözümü, bu çözüm başlangıçtaki en iyi çözümdür.
2. i=1, i==I olana kadar aşağıdaki adımları takip et.
3. j=1, j==m olana kadar asağıdaki adımları takip et.
İleri Geçiş: Arıların kovandan uçmalarına izin ver ve stj aşamasındaki Sj kısmi çözümler setinden kısmi çözümlerini tercih et.
stj ‘deki kısmi çözümler kümesi Sj (j=1,2,…,m) tarafından gösterilir.
Geri Geçiş: Tüm arıları kovana geri gönder. Oluşturulan kısmî çözümlerin kalitesi hakkındaki bilgi değişimine izin ver. Terk etme, terk etmeme, isçi alma veya almamaya karar ver.
j = j + 1;
4. i’inci iterasyon sırasında elde edilen xi çözümü bilinen en iyi çözümden daha iyiyse en iyi bilinen çözümü güncelle ( x = xi )
5. i = i + 1

İlgili makaleyi indirmek için:
Ari-Kolonisi-Optimizasyon-Algoritmasi-Kullanarak-En-Kisa-Yol-Bulma


Evaluation of parallel particle swarm optimization algorithms within the CUDA™ architecture

“Evaluation of parallel particle swarm optimization algorithms within the CUDA™ architecture” başlıklı makale Luca Mussi, Fabio Daolio ve Stefano Cagnoni tarafından hazırlanmış olup, Information Sciences dergisinin 2011 yılında yayınlanan 181.sayısının 4642–4657.sayfaları arasında basılmıştır.
Makaleye aşağıdaki bağlantıdan erişebilirsiniz:
Evaluation_of_parallel_particle_swarm_optimization_algorithms_within_the_CUDA_architecture

Makalenin CUDA bölümünde dört madde halinde toplanan paralel programlama önerileri:
1-CPU ve GPU arasındaki veri transferini olabildiğince azaltmak gerekir.
2-Global belleği olabildiğince az kullanmak, mümkünse Shared belleği kullanmak.
3-Global belleği erişimleri olabildiğince birleştirerek yapmak gereklidir.
4-Aynı warp(32 thread) içerisinde farklı uygulamalara yer vermemeye çalışmak.

Optimal sürü boyutu için nd önerilmiştir. Yani D=100 için N=30 seçilebilir.

SyncPSO ismi verilen paralel PSO yaklaşımında her iterasyonun sonunda lbest ve gbest güncellemesi yapılmıştır.
Her parçacık bir thread ile ifade edilmiştir.
Bir sürü bir blok içerisinde simüle edilebilir, birden çok sürü farklı bloklarda eş zamanlı olarak bulunabilir.
SyncPSO tek block içerisinde çalıştırılarak minimum bellek kullanımı hedeflenmiş ama tek SM çalıştığından istenen performans elde edilememiştir.

Aşağıda SyncPSO kernelinin sözde kodu bulunmaktadır:
SyncPSOkernel

SyncPSO 32,64,128 parçacıklı 0-100 arası boyutlarda çalıştırıldığında boyut sayısına paralel bir süre artışı yaşandığı görülmüştür. Parçacıkların sayısının artmasının olumsuz bir etkisi olmamıştır, lakin ideal hızlanma eğrisi(sınırsız iç kaynak kullanıldığı düşünüldüğünde) olarak çizilmiş olan kesik kesik siyah eğriye de yaklaşamaması sebebiyle yaklaşım RingPSO ismiyle farklı bir şekilde yeniden geliştirilmiştir.

Global bellekteki veriler aşağıdaki şekilde yerleştirilmiştir.
global-memory-data-organization

RingPSO’da;
-Her bir parçacık bir blok olarak tanımlanmıştır ve problemin boyutu kadar thread ilgili blokta paralel olarak işlem görmektedir.(PositionUpdateKernel)
-Her bir parçacığın fitness değerini bir blok hesaplamaktadır. Toplam şeklindeki fitness fonksiyonları için her bir thread ilgili boyutun değerini hesaplayıp, son olarak genel toplam alındığından paralel olarak ek bir avantaj daha sağlamış olmaktayız. (FitnessKernel)
-Her bir parçacığın en iyi durumu hafızada tutulur ve her iterasyonda daha iyi bir sonuç var ise değiştirilir.(BestUpdateKernel)
-Kullanılacak rastgele sayıları üretmesi için bir kernel ayarlanır. (Mersenne Twister kernel)

Sonuçlar:
Geliştirilen 2 paralel yaklaşım, seri PSO ile kıyaslanmıştır.
PSO parametreleri olarak w = 0.729844 ve C1 = C2 = 1.49618 alınmıştır.
Veriler float tipinde tutulduğundan her biri 4 byte yer kaplamaktadır.
Çalışmada kullanılan ekran kartları ve özellikleri:
kullanilan-ekran-kartlari

SyncPSO için yapılan teorik testler ve grafikleri aşağıda verilmiştir.
sync-pso-grafikleri

5 boyutlı Rastrigin fonksiyonunu optimize etmeyi amaçlayan çalışmada a grafiğinde görüldüğü üzere iterasyon sayısı arttıkça işlem süresi de artmaktadır. b grafiğinde ise problem boyutunun işlem süresine etkisini araştırmak amacıyla 1-9 arası boyutlarda süreler hesaplanmıştır. Boyut büyüdükçe sürenin arttığı görülse de tam düzgün bir süre artışının olmadığı görülmektedir. Bu da bir blok içerisinde threadlerin dizilimi ve çalışma mantığının çok açık olmamasıyla izah edilebilir. c grafiğinde 14 SM’ye sahip olan kartta sürü sayıları 1-112 arasında değiştirilerek süreler incelenmiş görüleceği üzere 14 ve 14’ün tam kartlarından itibaren 14’lük dilimlerde benzer bir hız olduğu ortada iken ara değerlerde izah edilecek bir durum bulunmamaktadır. Zira bazen daha yüksek, bazen daha düşük hızlar çıktığından kesin bir yoruma izin vermemektedir. Bu durumu da makale yazarları programcılara bu işlem şu şekilde yapılmaktadır demek isterdik lakin biz de bulamadım demişlerdir. O yüzden problemin girdilerine göre oluşturulacak bir thread-block sayısı/yapısı çözüm süresinde ciddi kazanımlar sağlayabilir. d grafiğinde de 32,64,128 parçacıktan oluşmuş sürülerin 1-9 boyuttaki hızlanma katsayıları verilmiştir. Parçacık sayısı ve boyut arttıkça paralel yaklaşımın 30 kata yakın hızlı olduğu ortadadır.

Sphere fonksiyonu 32 parçacık 10000 iterasyon için farklı boyutların ortalama işlem süresi, ortalama sonuç ve hızlanma grafikleri aşağıdadır.
sphere-ringpso

Paralel çözümün boyut artsa bile çok az bir yavaşlama ile sonuca eriştiği görülmektedir.
Optimum çözüme yaklaşma olarak farklı sonuçlar üretildiği görülmektedir. Bu durum izah edilirken her iterasyonda rastgele kullanılan sayılardan dolayı iyileştirme yapılamaması gösterilmiştir.
Boyut arttıkça hızlanmanın artması da yine paralelliğin gücünü ortaya koymaktadır.

Rastrigin fonksiyonundaki trigonometrik ifadelerden dolayı GPU üzerinde daha hızlı çözüm yaptığı(biraz daha düşük doğrulukla ama sorun teşkil etmemektedir) açıklanmıştır. Önemine binaen İngilizce tam ifadesi:(In fact, GPUs have internal fast math functions which can provide good computation speed at the cost of slightly lower accuracy, which causes no problems in this
case.)

Rastrigin fonksiyonu 32 parçacık 10000 iterasyon için 100 çalıştırmanın en iyi 98 tanesinin sonuçları aşağıdadır.

rastrigin-ringpso

Çalışmada en iyi 98 tanesinin alınması çeşitli sebeplerden dolayı farklı çıkan sonuçların elemine edildiğini göstermektedir. Yazarların bu konuyu dürüstçe söylemiş olması hem bu işin doğasındaki rastgelelik ve dış etkenlerin varlığını ortaya koymaktadır, hem de diğer araştırmacılar böyle sonuçlarla karşılaştığında sıkıntıya düşmemesini sağlamaktadır.

Rosenbrock fonksiyonu 32 parçacık 10000 iterasyon için 100 çalıştırmanın en iyi 98 tanesinin sonuçları aşağıdadır.

rosenbrock-ringpso

Yazarlar literatürdeki;
L. de P. Veronese, R.A. Krohling, Swarm’s flight: accelerating the particles using C-CUDA, in: Proceedings of IEEE Congress on Evolutionary Computation
(CEC 2009), 2009, pp. 3264–3270.
ve
Y. Zhou, Y. Tan, GPU-based parallel particle swarm optimization, in: Proceedings of IEEE Congress on Evolutionary Computation (CEC 2009), 2009, pp.
1493–1500.
çalışmalarındaki sonuçlarla kendi ürettikleri RingPSO çözümü kıyaslamışlar ve aşağıdaki sonuçları elde etmişlerdir.

zhou-veronese-ringpso

Çalışmalarda aynı GPU’lar kullanılmasa bile özellikleri detaylı olarak verilerek kıyaslama yapılması istenmiştir. Bu çerçevede Zhou’nunkinden yaklaşık 103 kat, Veronese’ninkinden yaklaşık 11 kat(birbirine yakın özellikteki GPU’ların sonuçlarına göre) hızlı olduğu görülmektedir.

Makalenin son açıklamalar bölümünde genel yapılan işi özü verilerek, gelecekte yapılması düşünülen çalışmalardan bahsedilmiştir.


Sayfalar:1...1011121314151617