최적의 TSP 해결을 위한 유전자 알고리즘의 새로운 집단 초기화 및 순차변환 기법 제안과 구현

Abstract

As information and telecommunication (IT) becomes ever-developed, the shortest distance setting in GIS, mass transit network design, network optimization and logistic system has begun to have firsthand effects on cost of distance and time in more cases of our daily life than before. Most of problems with shortest distance setting are based on TSP (Traveling Salesman Problem). Given certain number of cities and certain distance between cities, TSP refers to a problem of finding shortest distance across all turnaround routes from a city, starting point, via all other cities visited once only to the original city. However, as the number of cities gets increasing, the load of calculation to find optimal solution tends to increase exponentially, so such calculation has been typically classified as an NP-hard problem. In order to resolve this problem, the Genetic Algorithm proposed by John Holland has been used as the most representative algorithm to calculate the optimal solution of TSP. The Genetic Algorithm, which is modeled conceptually after the survival of the fittest dominating in the natural world, has an advantage of investigating in parallel the domain of combinable solutions for a given problem. This study proposed two major ways to more effectively find out an optimal TSP solution using Genetic Algorithm: One refers to a new initialization method that uses a combination of random initialization method and induced initialization method, which belong to population initialization method, one of Genetic Algorithm procedures. The other refers to algorithmic implementation and experiment using sequential transformation method for applying an alternative operator, so as to enhance probability of selecting a combination of dominant factors and thereby find out an optimal TSP solution. In order to verify potential performance of algorithm proposed herein, this study conducted experiments with 50 cities and 100 cities set as variables. As a result, 50 cities showed 3.86% higher performance on the average, and 100 cities showed 6.97% higher performance on the average. That is, it was found that group initialization method using information on known distance among cities and a method for higher probability of selecting a combination of dominant factors by rearranging subjects could be effective in improving performance to find out an optimal TSP solution. And it was found that the larger number of cities was directly associated with the higher effectiveness in improving performance. As demonstrated by findings hereof, it is expected that the algorithm proposed in a field based on TSP will be useful in various ways and will be helpful to find out an optimal solution in quicker and more correct ways.