GEZGİN SATICI PROBLEMİNİN GENETİK ALGORİTMALARLA ÇÖZÜMÜNDE BAŞLANGIÇ POPÜLASYONUN BELİRLENMESİ

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

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

Abstract

The traveler is aiming to find the least costly tour in the traveling salesman problem, which is only one time out of each of the known cities. Although it is easy to identify the traveling salesman problem, obtaining the optimal solution is very difficult and NP-hard problem. The basic difficulty of this problem is that the number of possible tours increases in large numbers as the number of cities increases, which makes the problem impossible to solve with definite methods, so different methods have been proposed to solve the problem. One of these methods is genetic algorithms. Genetic algorithms are particularly suited to solve difficult optimization problems where traditional optimization methods are less effective. It is determine how to create and the size of the initial population that significantly affect the performance of the Genetic Algorithm solution. The initial population is often randomly selected but is used in different heuristics to improve the performance of genetic algorithms. In the study, the initial population was created with the nearest neighbour intentionally and randomly, and the different population sizes were considered and compared

Keywords

• Traveling Salesman Problem, Genetic Algorithms, Nearest Neighbour, Initial Population.