Hybrid method for the generalized minimum spanning tree problem

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