engleski

Impact of NNA implementation on GA performance for the TSP

Genetic algorithms are a frequently used method for search and optimization problem solving. As such they have also been used to solve the traveling salesman problem. Since they are population-based, the initial population plays a very important role and a ects the algorithm's convergence speed as well as the quality of the nal solution. Commonly, the population is initialized with randomly generated solutions, but in this paper an adapted nearest neighbor algorithm is used for population initialization. Besides that, the algorithm is used during recombination to a lesser extent. Experimental analysis conducted on several instances of the symmetric traveling salesman problem showed that significantly better solution can be achieved with the presented method for the population initialization than with the commonly used random method. Also, the presented method is relatively easy for implementation.

genetic algorithm; initial population; nearest neighbor algorithm; recombination; traveling salesman problem

nije evidentirano