DETERMINING THE INITIAL POPULATION OF SOLVING THE TRAVELING SALESMAN PROBLEM WITH GENETIC ALGORITHMS

Authors : Meryem PULAT, İpek DEVECİ KOCAKOÇ

Pages : 95-123

View : 21 | Download : 8

Publication Date : 2017-07-01

Article Type : Research Paper

Abstract :Gezgin satıcı probleminde aralarındaki uzaklıkları bilinen şehirlerin her birinden yalnız bir kez geçen en az maliyetli turu bulmayı hedeflemektedir. Gezgin satıcı problemi tanımlanması kolay olmasına rağmen optimal çözümü elde etmek çok zordur ve NP-zor problemdir. Bu problemin temel zorluğu olası tur sayısının şehir sayısı arttıkça büyük oranda artmasıdır bu da problemi kesin yöntemlerle çözümünü imkânsız hale getirmektedir bu yüzden problemi çözebilen farklı yöntemler öne sürülmüştür. Bu yöntemlerden biri de genetik algoritmalardır. Genetik algoritmalar özellikle geleneksel optimizasyon yöntemlerinin daha az etkin olduğu zor optimizasyon problemlerini çözmek için uygundur. Genetik Algoritmanın çözüm performansını önemli ölçüde etkileyen başlangıç popülasyonun nasıl oluşturulacağı ve popülasyon büyüklüğünün belirlenmesidir. Başlangıç popülasyonu çoğunlukla rasgele seçilir ama genetik algoritmaların performansını geliştirmek için farklı sezgisellerde kullanılmaktadır. Çalışmada başlangıç popülasyonu en yakın komşuluk sezgiseli ve rasgele bir şekilde oluşturularak farklı popülasyon büyüklükleri de dikkate alınarak karşılaştırılmıştır
Keywords : Gezgin Satıcı Problemi, Genetik Algoritmalar, En Yakın Komşuluk, Başlangıç Popülasyonu