Genelleştirilmiş yayılma problemi için karma çözüm yöntemi

Abstract

ÖZGENELLEŞTİRİLMİŞ YAYILMA PROBLEMİ İÇİN KARMA ÇÖZÜM YÖNTEMİYiğit Koray GençBaşkent Üniversitesi Fen Bilimleri EnstitüsüEndüstri Mühendisliği Anabilim DalıBu çalışmada, günümüzde şebeke tasarım problemlerinde kullanılanGenelleştirilmiş Yayılma Problemi için yeni sezgisel çözüm yöntemleri geliştirilmiştir.Genetik Algoritma, Tavlama Benzetimi ve Kuş Sürüsü Algoritmasına dayalı yenisezgisel çözüm yöntemleri geliştirilmiştir. Geliştirilen Algoritmalar, literatürde yer alantest problemleri üzerinde denenmiş ve performansları incelenmiştir.Geliştirilen Kuş Sürüsü Algoritması, Genelleştirilmiş Yayılma Problemi için ilkkez bu çalışmada önerilmiştir. Geliştirilen Genetik Algoritmanın performansınıniyileştirilmesi amacıyla, yerel arama algoritmalarından biri olan Tavlama Benzetimi ilebirlikte kullanılabileceği bir melez algoritma önerilmiştir.Geliştirilen algoritmaların parametre değerlerinin en iyi kombinasyonununbelirlenmesi için Cevap Yüzeyi metodu kullanılmıştır.ANAHTAR SÖZCÜKLER: Genelleştirilmiş Yayılma Problemi, Genetik Algoritma, KuşSürüsü Algoritması.Danışman: Prof.Dr. Berna DENGİZ, Başkent Üniversitesi, Endüstri MühendisliğiBölümü.i

ABSTRACTHYBRID METHOD FOR THE GENERALIZED MINIMUM SPANNING TREEPROBLEMYiğit Koray GençBaşkent University, Instıtute of ScienceDepartment of Industrial EngineeringIn this study, new heuristic methods based Genetic Algorithms, SimulatedAnnealing and Particle Swarm Optimization Algorithm are developed for GeneralizedMinimum Spanning Tree Problem. The performances of algorithms have beenevaluated on the test problems given in the literature.Particle Swarm Optimization Algorithm is firstly used for the GeneralizedMinimum Spanning Tree Problem in this study. In addition, a hybrid algorithm basedon Genetic Algorithms and Simulated Annealing is proposed to improve theperformance of the Genetic Algorithm.To determine the best combination of the parameter values of the developedalgorithms, response surface method is applied.KEY WORDS: Generalized Minimum Spanning Tree Problem, Genetic Algorithm,Particle Swarm Optimization AlgorithmAdviser: Prof.Dr. Berna DENGİZ, Başkent University, Department of IndustrialEngineering.i