:::: MENU ::::
İncelemeler

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.


Particle Swarm Optimization within the CUDA Architecture

“Particle Swarm Optimization within the CUDA Architecture” Luca Mussi ve Stefano Cagnoni tarafından yazılan makale 2009 yılında GPU’lar Genetik ve Evrimsel Hesaplama çalışması(GECCO 2009) çerçevesinde hazırlanmıştır. Aşağıdaki bağlantıdan makaleyi indirebilirsiniz:
Particle_Swarm_Optimization_within_the_CUDA_Architecture

Çalışmada 100 boyutlu bir sürü ile 22 kat hızlanma elde ettiklerini belirtmişlerdir. Lakin bir sürü içerisinde kaç parçacık olduğu ile ilgili çok açık bir bilgi vermemişlerdir veya ben göremedim 🙂
Çalışmada kullandıkları GPU’nun 14 SM’si olduğundan daha fazla SM’ye sahip kartlarda daha fazla hızlanma elde edilebileceğini belirtmişlerdir.
Rastgele sayı üretmek için Mersenne Twister metodunu kullandıkları belirtmişler, bu metod şu an için MATLAB’ın varsayılan rastgele sayı üretme metodudur.
Kıyaslama fonksiyonlarından Rastrigin’in global optimumunu bulmaya çalıştıklarını belirtmişler, ancak sonuçlarla ilgili ayrıntılı bilgi vermemişlerdir.
Çalışmada asıl zaman alıcı kısmın rastgele sayıların üretildiği ve kullanıldığı kısım olduğu açıklanmıştır.


Sayfalar:1...1213141516171819