Demetleme problemi için paralel karınca yaklaşımı
Parallel ant based clustering for clustering problem
Yazar: ÖZLEM GEMİCİ
Danışman: Y.DOÇ.DR. ŞİMA ETANER UYAR
İstanbul Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Yüksek Lisans, 2007
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control

Özet:
Bu çalısmada, öncelikle demetleme problemi çözümü için karınca demetlemeyöntemi ardısıl olarak gerçeklenmistir. Gerçeklenen algoritma seçilen paralelkütüphane kullanılarak iteratif bir yaklasım ile paralellestirilmistir. Demetlenecekveriler ve demetleme ortamını olusturan 2 boyutlu ortam ve toplam adım sayısıislemciler arasında paylastırılır. slemcilerden biri master islemci olarak belirlenir.Master islemci dahil her islemci kendine atanan alanda ardısıl demetlemeçözümünü çalıstırır ve çalısmasının sonlandıgını master islemciye bildirir. Masterislemci ardısıl demetleme çözümünü bütün verileri ve 2 boyutlu alanın tamamınıkullanarak tekrar çalıstırır. Demetleme algoritmasının daha iyi bir noktadanbaslayabilmesi amaçlanmaktadır. Yapılan çalısmada gerçeklenen iteratif ve kısmiparalellestirme isleminin özellikle algoritma sonlanma zamanında iyilestirmeyesebep olup olmayacagı arastırılmıstır. Yapılan testlerde iki ve dört islemi için seçilenveritabanları için performans ölçüm sonuçları elde edilmistir. Algoritmanın daha iyibir noktadan baslamasını saglamak ve atılacak toplam adım sayısının digerislemcilerle paylasmasını saglamak algoritma çalısma zamanlarında iyilesmeyisaglamıstır. Haberlesme maliyetinin diger paralellestirme yöntemine göre çokdüsük olması da algoritmanın avantajlarından biridir.Anahtar Kelimeler: Demetleme, Karınca, Paralel, C#, MPI

Abstract:
In this study sequential ant based clustering is implemented. The implementation isparallelized using an iterative approach through the chosen parallelization library,which is MPI. All the processors share the dataset to cluster and the 2-dimensionalclustering environment. One of the processors is marked as master. Each of theprocessors, including the one denoted as master, runs the sequential algorithm andinforms the master processor when the run ends. After all processors finish clusteringthe data assigned to them, the master processor runs the sequential algorithm again, butthis time it uses all the items in the dataset and the whole 2-dimensional clusteringenvironment. The aim of the first stage is to provide a better start point for theclustering algorithm performed by the master in the second stage. It is analyzed if theimplemented iterative and partially parallel clustering method causes a better timeperformance then its fully sequential version. Tests are executed for 2 and 4 processorson selected example datasets. As stated above, the aim is to make the second stage of thealgorithm to start from a better initial situation for clustering by dividing the grid andthe number of iterations among the processors. The aim of this study is to speed up theant clustering method, which is normally very time consuming. Thus, no steps are takento improve the clustering solution. As a result of the experiments, it is seen that theproposed algorithm performs better based on time measurements, however it does notimprove other clustering performance measures. This is an expected outcome. Thecommunication cost is very small compared to other ant clustering parallelizationtechniques found in literature.Keywords: Clustering, Ant, Parallel, C#, MPI