DSpace
 

EMU I-REP >
02 Faculty of Engineering >
Department of Computer Engineering >
Theses (Master's and Ph.D) – Computer Engineering >

Please use this identifier to cite or link to this item: http://hdl.handle.net/11129/611

Title: Coevolutionary Memetic Algorithms for Solving Traveling Salesman Problem (TSP)
Authors: Uluçınar, Şerife
Keywords: Computer Engineering
Traveling Salesman Problem - Algorithms
Coevolutionary Algorithms - Algorithms - Memetic Algorithms - Traveling Salesman Problem
Issue Date: 2013
Publisher: Eastern Mediterranean University (EMU)
Citation: Ulucinar, Serife. (2013). Coevolutionary Memetic Algorithms for Solving Traveling Salesman Problem (TSP). Thesis (M.S.), Eastern Mediterranean University, Institute of Graduate Studies and Research, Dept. of Computer Engineering, Famagusta: North Cyprus.
Abstract: ABSTRACT: In this thesis, Coevolutionary Memetic Algorithms are used for solving the well-known Traveling Salesman Problem (TSP). Traveling Salesman Problem is NP-Complete which means no algorithm can solve this problem in a computing time that increases polynomially with respect to the problem size. The proposed solution approach to TSP is the combination of Coevolutionary Algorithms and Memetic Algorithms. The objective solution to TSP is to find the minimum tour length that the Traveling Salesman can make under some restrictions. Coevolutionary Algorithms belong to the class of Evolutionary Algorithms. The main difference of Coevolutionary Algorithms from Evolutionary Algorithms is the way of interaction of individuals in the population. The individuals of the population should interact with each other to form a complete solution to the problem. Moreover, Memetic Algorithms are hybridized algorithms which combine the Evolutionary Algorithms with a local search method. Local search algorithms are the algorithms that refine the solutions by searching within the neighbourhood of promising solutions to find the better ones. In experimental results, the proposed algorithm is tested with several test datas by different parameter values of the algorithm. Keywords: Coevolutionary Algorithms, Memetic Algorithms, Traveling Salesman Problem. …………………………………………………………………………………………………………………………………………………………………………………………………………………… ÖZ: Bu tezde, Birlikte Evrimleşen Memetik Algoritmaları iyi bilinen bir problem olan Gezici Satıcı Problemi’nin çözümü için kullanılmıştır. Gezici Satıcı Problemi, üzerinde çok çalışılan bir problem olması ile birlikte, bu problem hiçbir algoritma tarafından belirli bir hesaplama zamanında çözülebilecek bir problem olmaması ile de bilinir. Gezici Satıcı Problemi’ni çözme yaklaşımımız Birlikte Evrimleşen Algoritmalar ile Memetik Algoritmaları’nın birleşimi ile gerçekleşecektir. Bu problemdeki amacımız Gezici Satıcı’nın dolaşacağı şehirlerden oluşacak olan turdan bazı sınırlamalara uygun olarak en kısa tur mesafesini bulabilmektir. Birlikte Evrimleşen Algoritmalar, Evrimsel Algoritmaların bir sınıfıdır. Birlikte Evrimleşen Algoritmalar ile Evrimsel Algoritmalar arasındaki esas fark, Birlikte Evrimleşen Algoritmaların nüfustaki bireylerin arasındaki etkileşim yoludur. Bu algoritmalarda üzerinde çalışılan problemde bütün bir çözüm elde edebilmek için, nüfustaki bireylerin birbirleriyle bir etkileşim içinde olmaları gerekir. Memetik Algoritmaları ise, Evrimsel Algoritmaların ve bir Bölgesel Arama Algoritması’nın birlikte kullanımı ile oluşan algoritmalardır. Bölgesel Arama Algoritmaları, Evrimsel Algoritmalar tarafından bulunan çözümün etrafında, bu çözümü daha iyi bir çözüm haline getirecek aramalar yapan algoritmalardır. Birlikte Evrimleşen Memetik Algoritmaları, algoritma parametrelerinin farklı değerlerine göre birkaç test verileri ile test edilmiştir. Anahtar Kelimeler: Birlikte Evrimleşen Algoritmalar, Memetik Algoritmaları, Gezici Satıcı Problemi.
Description: Master of Science in Computer Engineering. Thesis (M.S.)--Eastern Mediterranean University, Faculty of Engineering, Dept. of Computer Engineering, 2013. Supervisor: Assist. Prof. Dr. Ahmet Ünveren.
URI: http://hdl.handle.net/11129/611
Appears in Collections:Theses (Master's and Ph.D) – Computer Engineering

Files in This Item:

File Description SizeFormat
Ulucinar.pdf837.47 kBAdobe PDFView/Open


This item is protected by original copyright

Recommend this item
View Statistics

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

 

Valid XHTML 1.0! DSpace Software Copyright © 2002-2010  Duraspace - Feedback