Paralel karınca kolonisi optimizasyon algoritması ve test problemlerindeki performansının incelenmesi

Abstract

Ill PARALEL KARINCA KOLONİSİ OPTÎMIZASYON ALGORİTMASI VE TEST PROBLEMLERİNDEKİ PERFORMANSININ İNCELENMESİ ÖZET Karınca Kolonisi Optimizasyonu (KKO), gerçek karıncaların yön ve yiyecek bulma davranışlarından esinlenerek modellenmiş sezgisel bir algoritmadır. Literatürde, algoritmanın ayrık optimizasyon problemlerinin çözümünde kullanılmasına yönelik çok sayıda çalışma bulunmasına rağmen, sürekli optimizasyon problemlerinin çözümüne yönelik sadece birkaç çalışma bulunmaktadır. Bu tezde ilk olarak KKO algoritmasının ayrık optimizasyon problemlerindeki performansının artırılması amacıyla yeni bir yaklaşım önerilmiştir. Önerilen bu yaklaşımda algoritmaya tabu araştırma algoritmasından esinlenerek yeni bir sezgisel operatör eklenmiş ve küresel güncelleme formülü değiştirilmiştir. Önerilen yaklaşımın performansı gezgin satıcı problemi üzerinde test edilmiş ve sonuçlar temel KKO algoritması ile karşılaştırılmıştır. Elde edilen sonuçlardan önerilen modelin algoritma performansında önemli gelişmeler sağladığı görülmüştür. Tez çalışmasının diğer bir aşamasında, özellikle sürekli problemlerin çözümünde kullanılmak üzere yeni bir paralel karınca kolonisi optimizasyon algoritması önerilmiştir. Önerilen modelin performansı literatürde iyi bilinen çeşitli sürekli problemler üzerinde incelenmiştir. Ayrıca, algoritmanın performansı literatürdeki bazı sezgisel algoritmalar ile karşılaştırılmıştır. Elde edilen sonuçlar, önerilen yeni algoritmanın özellikle sürekli problemlerin çözümünde etkili bir şekilde kullanılabileceğini göstermiştir. Anahtar K elimeler: Paralel karınca kolonisi optimizasyon algoritması, kombinasyonel optimizasyon, sürekli optimizasyon, sezgisel algoritma.

IV PARALLEL ANT COLONY OPTIMIZATION ALGORITHM AND THE EXAMINATION OF ITS PERFORMANCE ON THE TEST PROBLEMS ABSTRACT Ant Coiony Optimization (ACO), is a heuristic algorithm which is modelled on the behaviour of real ant colonies for finding route between nest and food. In the literature, although there has been many applications of this algorithm in discrete problems, a few applications in continuous problems have been published. In this thesis, first of all, a new approach has been proposed to improve the performance of ACO algorithm on discrete optimization problems. In this proposed approach, a new heuristic operator has been added to the algorithm as being inspired by tabu search algorithm and global updating formula of the basic ACO algorithm has been changed. The performance of the proposed algorithm has been tested on traveling salesman problem and results have been compared with basic ACO algorithm. It has been seen from the obtained results, proposed model has assured important improvement on algorithm performance. In the other part of the thesis, a new parallel ACO algorithm (PACO) has been proposed especially for solving problems in continuous domain. The performance of the proposed algorithm was tested with well known numeric test functions in the literature. Furthermore, performance of the algorithm was compared with some heuristic algorithms in literature. It has been understood that from these results, the proposed algorithm can be effectively used particularly for solving optimization problems in continuous domain. Keywords: Parallel ant colony optimization algorithm, combinatorial optimization, continuous optimization, heuristic algorithm.