Akademik Veri Yönetim Sistemi
Tezin Türü: Doktora
Tezin Yürütüldüğü Kurum: Ankara Üniversitesi, Fen Bilimleri Enstitüsü, Türkiye
Tezin Onay Tarihi: 2015
Tezin Dili: Türkçe
Öğrenci: ÖKKEŞ TOLGA ALTINÖZ
Danışman: ASIM EGEMEN YILMAZ
Özet:Çok amaçlı optimizasyon algoritmasının ürettiği çözümler, elde edilebilecek en iyi çözüm kümesinin amaç uzayında oluşturduğu şekil olan Pareto Cephesi üzerinde olması beklenir. Problem zorluğu, amaç sayısı ve karar uzayı boyutu arttıkça istenilen çözüm yakınsallığına ve dağılımına ulaşılması için gerekli olan hesaplama maliyeti artmaktadır. Maliyetin düşürülmesi için iki temel işlem uygulanabilir. Bunlardan ilkinde hesaplama birimindeki geçirilen hesaplama zamanın azaltılması ile sağlanır. Tez kapsamında kullanılan yöntem ise hesaplama birimini arttırırken çalışma zamanının azaltılmasıdır. Bu amaçla iki temel yöntem olan efendi-köle yöntemi ve ada yöntemi incelenecektir. Efendi-köle yönteminde algoritma parçalara ayrılır ve her bir parça farklı bir hesaplama biriminde çalıştırılır. Algoritmada ve/veya problemde yapısal büyük bir değişiklik yapılmadığı için elde edilen çözüm kalitesi değişmez. Bu yöntemde üç farklı işlem gerçekleştirilir. Bu işlemler i) sadece amaç fonksiyonlarının farklı mimarilerde çalıştırılması ii) optimizasyon algoritmasının farklı mimarilerde çalıştırılacak hale getirilmesi ve iii) her bir mimaride bir optimizasyon algoritmasının çalıştırılmasıdır. Çalışmalar CPU ve GPU donanım birimlerinde gerçekleştirilmiştir. Elde edilen sonuçlardan çalışma zamanının azaltıldığı fakat kullanılan hesaplama birimi sayısı göz önüne alındığında efendi-köle yönteminin verimli olmadığı görülmüştür. Ada yönteminde ise farklı mimariler amaç ve/veya karar uzayının farklı bölgelerini aramaktadır. Bu nedenle optimizasyon algoritması performansı değişmektedir. Tez kapsamında referans nokta tabanlı ada yöntemi önerilmiştir. Bu yöntemde referans noktalar farklı hesaplama birimlerine dağıtılması prensine dayanır. Yapılan ilk çalışmalarda hızlanma sağlanmasına rağmen doğrusal hızlanma, bir başka değişle hesaplama birim sayısına eş hızlanma sağlanamamıştır. Önerilen yöntemin performansını arttırmak için göç ve çaprazlama yöntemi önerilmiştir. Yapılan çalışmalarda iki amaçlı problemler için doğrusal hızlanma yakalandığı gibi bu değer aşılmıştır. Problem zorluğunu arttırmak amacı ile yine literatürde ilk defa hibrid test problemleri tanımlanmıştır. Bu zor problemler içinde aynı hızlanma elde edilmiştir. Aynı testler üç amaçlı problemlere uygulanmıştır. Amaç sayısının artması çözüm elde edilmesini zorlaştırmıştır. Yapılan uygulamalar sonucunda doğrusal hızlanmaya yakın sonuçlar üç amaçlı problemler için elde edilmiştir.AbstractThe solutions produced by the multi-objective optimization algorithm are expected to be on the Pareto front which is the shape of the available best solution set at the objective space. As the problem difficulty, objective and decision space dimension is increased, the necessity computational cost for reaching desired convergence and distribution is increased. Two fundamental processes can be applied to reduce the cost. From the first of these, it is succeeded by reducing the computation time at the computation unit. The method used within the thesis is based on increasing the number of computation unit by decreasing the computation time. By this purpose two fundamental models which are master-slave and island models will investigate. At the master-slave model, algorithm is divided into pieces and each of these pieces and they are evaluated at the different computational unit. Since there isn't any big changes at the structure of algorithm and/or problem, solution quality doesn't change. Three processes are evaluated in this model. These processes are i) only objective functions are evaluated at different architectures ii) optimization algorithm is modified to be implemented on different architectures and iii) optimization algorithms are implemented at each of the architectures. Implementations are made both CPU and GPU hardware units. From the obtained results, computation time is decreased but when considered the number of computation unit, it is observed that master-slave model isn't effective. In case of island model, different architectures search different areas of the objective and/or decision space. That's why the performance of the algorithm changes. In thesis, reference point based island model is proposed. This method depends on the distribution of the reference points to different computational units. Although speeding is provided, the linear speed-up in other words same speed decreasing with the number of computation unit isn't supplied. To increase the performance of the proposed method, migration and crossover method is introduced. From the implementations for two objective problems linear speed-up is reached as well as surpasses this speed. To increase the problem difficulty, at the first time in literature hybrid test problems are defined. Same speedup is obtained for these hard problems. Same tests are evaluated for three objective problems. Increasing the number of objective is made difficult to obtain solution. As results of implementations, almost linear speed-up is observed for three objective problems.