국문초록 전자 알고리즘 및 유전자-엔트로피 알고리즘을 이용한 TSP 문제 해결에 관한 연구 공주대학교 대학원 산업정보학과 계산정보전공 김선희 외판원문제(TSP, Traveling Salesman Problem)는 주어진 개의 도시와 각 도시간의 거리나 비용이 주어질 때, 한 도시로부터 출발하여 모든 도시를 단 한 번씩 방문한 다음 출발했던 도시로 다시 돌아오는 여러 경로 중 가장 짧은 거리나 비용을 찾는 문제이다. 일반적으로 개의 도시로 이루어진 TSP문제에서 모든 가능한 경로의 수는 이 되어 이는 수학적인 모델을 세우기는 용이하지만 이 증가함에 따라 해를 찾기 위한 계산시간이 기하급수적으로 증가하여 제한된 시간 내에 이 문제를 해결하기는 실질적으로 불가능하게 된다. 이렇듯, TSP문제는 ...
국문초록 전자 알고리즘 및 유전자-엔트로피 알고리즘을 이용한 TSP 문제 해결에 관한 연구 공주대학교 대학원 산업정보학과 계산정보전공 김선희 외판원문제(TSP, Traveling Salesman Problem)는 주어진 개의 도시와 각 도시간의 거리나 비용이 주어질 때, 한 도시로부터 출발하여 모든 도시를 단 한 번씩 방문한 다음 출발했던 도시로 다시 돌아오는 여러 경로 중 가장 짧은 거리나 비용을 찾는 문제이다. 일반적으로 개의 도시로 이루어진 TSP문제에서 모든 가능한 경로의 수는 이 되어 이는 수학적인 모델을 세우기는 용이하지만 이 증가함에 따라 해를 찾기 위한 계산시간이 기하급수적으로 증가하여 제한된 시간 내에 이 문제를 해결하기는 실질적으로 불가능하게 된다. 이렇듯, TSP문제는 최적해를 찾기에 불가능한 NP-Complete 문제로 잘 알려져 있다. 이러한 최적화 문제를 풀기 위한 알고리즘으로는 담금질(simulated annealing), 신경회로망(neural network), 그리고 유전자 알고리즘(genetic algorithms) 등이 대표적인 방법으로 알려져 있다. J. Holland에 의해 제안된 유전자 알고리즘은 주어진 모집단이 다음 세대의 모집단으로 진화하는 과정에서 자연계의 적자생존의 개념을 모델링한 것으로 주어진 문제의 가능한 해의 영역을 병렬적으로 조사한다는 장점을 갖고 있다. 그러나 유전자 알고리즘도 다른 탐색 알고리즘과 마찬가지로 최적해를 찾아가는 과정에서 국소 최소치(local minimum)에 빠진다는 문제점을 갖고 있다. 즉, 하나의 해가 국소 최소치에 빠지면 다른 해도 그 국소 최소치에 빠지는 경향이 있어, 알고리즘이 전체 해를 찾기 전에 국소 최소치로 해가 수렴하는 조기 수렴 현상(premature convergence)이 나타나는 것이다. 최근에는 이런 조기 수렴하는 현상을 극복하기 위한 연구들이 이루어지고 있다. 그 방법 중에 하나가 유전자-엔트로피 알고리즘이다. 이 방법은 유전자 알고리즘과 엔트로피샘플링을 기본으로 하는 알고리즘으로 기존의 유전자 알고리즘과의 가장 큰 차이는 자손의 선택방법이다. 유전자 알고리즘은 자손의 선택에 있어서 적합도가 높은 개체에 대해서 다음 세대에 살아남을 확률을 높게 부여함으로서 적합도 값에 의해서 자손을 선택한다. 반면에 유전자-엔트로피 알고리즘은 적합도 값뿐만이 아니라 엔트로피라는 개념 여기서 엔트로피는 적합도 값을 일정한 간격으로 나누어서 각 개체들의 적합도 값이 해당하는 빈도로 표현한다. 을 추가시킴으로 자손의 선택은 적합도 값과 엔트로피 값에 의해서 선택된다. 그래서 엔트로피 값은 작을수록, 적합도 값은 클수록 자손을 선택할 확률을 높게 하는 것이다. 따라서 적합도 값이 작다할지라도 엔트로피 값이 클 경우 선택될 확률을 높임으로서 국소 최소치에 빠지는 문제를 극복할 수 있는 것이다. 본 논문에서는 유전자 알고리즘의 단점인 조기 수렴 현상을 해결하기 위해서 유전자-엔트로피 알고리즘을 이용하여 TSP문제를 풀어 보았다. 또한 기존에 연구되어진 유전자 알고리즘으로 TSP문제를 풀어 봄으로서 두 알고리즘간의 성능을 비교, 분석하였다. 유전자-엔트로피 알고리즘은 국소 최소치를 보다 효과적으로 빠져 나올 수 있었으며 유전자 알고리즘과의 성능 테스트를 통해 보다 나은 알고리즘임을 확인 할 수 있었다.
국문초록 전자 알고리즘 및 유전자-엔트로피 알고리즘을 이용한 TSP 문제 해결에 관한 연구 공주대학교 대학원 산업정보학과 계산정보전공 김선희 외판원문제(TSP, Traveling Salesman Problem)는 주어진 개의 도시와 각 도시간의 거리나 비용이 주어질 때, 한 도시로부터 출발하여 모든 도시를 단 한 번씩 방문한 다음 출발했던 도시로 다시 돌아오는 여러 경로 중 가장 짧은 거리나 비용을 찾는 문제이다. 일반적으로 개의 도시로 이루어진 TSP문제에서 모든 가능한 경로의 수는 이 되어 이는 수학적인 모델을 세우기는 용이하지만 이 증가함에 따라 해를 찾기 위한 계산시간이 기하급수적으로 증가하여 제한된 시간 내에 이 문제를 해결하기는 실질적으로 불가능하게 된다. 이렇듯, TSP문제는 최적해를 찾기에 불가능한 NP-Complete 문제로 잘 알려져 있다. 이러한 최적화 문제를 풀기 위한 알고리즘으로는 담금질(simulated annealing), 신경회로망(neural network), 그리고 유전자 알고리즘(genetic algorithms) 등이 대표적인 방법으로 알려져 있다. J. Holland에 의해 제안된 유전자 알고리즘은 주어진 모집단이 다음 세대의 모집단으로 진화하는 과정에서 자연계의 적자생존의 개념을 모델링한 것으로 주어진 문제의 가능한 해의 영역을 병렬적으로 조사한다는 장점을 갖고 있다. 그러나 유전자 알고리즘도 다른 탐색 알고리즘과 마찬가지로 최적해를 찾아가는 과정에서 국소 최소치(local minimum)에 빠진다는 문제점을 갖고 있다. 즉, 하나의 해가 국소 최소치에 빠지면 다른 해도 그 국소 최소치에 빠지는 경향이 있어, 알고리즘이 전체 해를 찾기 전에 국소 최소치로 해가 수렴하는 조기 수렴 현상(premature convergence)이 나타나는 것이다. 최근에는 이런 조기 수렴하는 현상을 극복하기 위한 연구들이 이루어지고 있다. 그 방법 중에 하나가 유전자-엔트로피 알고리즘이다. 이 방법은 유전자 알고리즘과 엔트로피 샘플링을 기본으로 하는 알고리즘으로 기존의 유전자 알고리즘과의 가장 큰 차이는 자손의 선택방법이다. 유전자 알고리즘은 자손의 선택에 있어서 적합도가 높은 개체에 대해서 다음 세대에 살아남을 확률을 높게 부여함으로서 적합도 값에 의해서 자손을 선택한다. 반면에 유전자-엔트로피 알고리즘은 적합도 값뿐만이 아니라 엔트로피라는 개념 여기서 엔트로피는 적합도 값을 일정한 간격으로 나누어서 각 개체들의 적합도 값이 해당하는 빈도로 표현한다. 을 추가시킴으로 자손의 선택은 적합도 값과 엔트로피 값에 의해서 선택된다. 그래서 엔트로피 값은 작을수록, 적합도 값은 클수록 자손을 선택할 확률을 높게 하는 것이다. 따라서 적합도 값이 작다할지라도 엔트로피 값이 클 경우 선택될 확률을 높임으로서 국소 최소치에 빠지는 문제를 극복할 수 있는 것이다. 본 논문에서는 유전자 알고리즘의 단점인 조기 수렴 현상을 해결하기 위해서 유전자-엔트로피 알고리즘을 이용하여 TSP문제를 풀어 보았다. 또한 기존에 연구되어진 유전자 알고리즘으로 TSP문제를 풀어 봄으로서 두 알고리즘간의 성능을 비교, 분석하였다. 유전자-엔트로피 알고리즘은 국소 최소치를 보다 효과적으로 빠져 나올 수 있었으며 유전자 알고리즘과의 성능 테스트를 통해 보다 나은 알고리즘임을 확인 할 수 있었다.
ABSTRACT A study on TSP using genetic algorithms and genetic-entropy algorithms Sun Hee, Kim Department of Industrial Information, Graduate School, Kong Ju National University Kong Ju. Korea (Supervised by Professor Lee, Chang-Yong) The Traveling Salesman Problem (TSP) is to find a route of visiting...
ABSTRACT A study on TSP using genetic algorithms and genetic-entropy algorithms Sun Hee, Kim Department of Industrial Information, Graduate School, Kong Ju National University Kong Ju. Korea (Supervised by Professor Lee, Chang-Yong) The Traveling Salesman Problem (TSP) is to find a route of visiting each city exactly once and returning to the starting city for a given number of cites, in such a way that the cost or length of the traveling cities is minimized. The number of configuration for visiting each city is an order of , where is the number of cities. Thus TSP is best known as a NP-complete problem. During past a few decades, there have been several attempts to solve TSP approximately, if not exactly, by using various optimization algorithms, such as simulated annealing, taboo search, and genetic algorithms(GAs). GAs are one of the evolutionary algorithms that mimic the biological evolution and natural selection in terms of the survival of the fittest. GAs also have been applied successfully in the variety of different optimization problems. As is true for all known optimization algorithms, it is hard to for optimization algorithms to find the true or nearly optimized solution for problems with many local minima. GAs are not an exception to it, and suffers so called premature convergence problem. This is mainly due to falling into one of local minima before finding a true or nearly true optimum. To solve this premature convergence problem, we adapt the entropy-Boltzmann selection to GAs. This selection is based on the entropic sampling and importance sampling in the Monte Carlo simulation. In the conventional GAs, chromosomes having better fitness always have higher probability to survive and being selected. In contrast, however, the entropy-Boltzmann selection selects chromosomes according to not only their fitness but their relative entropy. This enables systematically to escape from being falling into local minima. In this paper, we solve TSP using both conventional GAs and GAs with the entropy-Boltzmann selection. We compare and analyze the performance of both algorithms in terms of numerical simulations. It is found that GAs with the entropy-Boltzmann selection outperforms the conventional GAs, and the new selection method helps to escape local minima.
ABSTRACT A study on TSP using genetic algorithms and genetic-entropy algorithms Sun Hee, Kim Department of Industrial Information, Graduate School, Kong Ju National University Kong Ju. Korea (Supervised by Professor Lee, Chang-Yong) The Traveling Salesman Problem (TSP) is to find a route of visiting each city exactly once and returning to the starting city for a given number of cites, in such a way that the cost or length of the traveling cities is minimized. The number of configuration for visiting each city is an order of , where is the number of cities. Thus TSP is best known as a NP-complete problem. During past a few decades, there have been several attempts to solve TSP approximately, if not exactly, by using various optimization algorithms, such as simulated annealing, taboo search, and genetic algorithms(GAs). GAs are one of the evolutionary algorithms that mimic the biological evolution and natural selection in terms of the survival of the fittest. GAs also have been applied successfully in the variety of different optimization problems. As is true for all known optimization algorithms, it is hard to for optimization algorithms to find the true or nearly optimized solution for problems with many local minima. GAs are not an exception to it, and suffers so called premature convergence problem. This is mainly due to falling into one of local minima before finding a true or nearly true optimum. To solve this premature convergence problem, we adapt the entropy-Boltzmann selection to GAs. This selection is based on the entropic sampling and importance sampling in the Monte Carlo simulation. In the conventional GAs, chromosomes having better fitness always have higher probability to survive and being selected. In contrast, however, the entropy-Boltzmann selection selects chromosomes according to not only their fitness but their relative entropy. This enables systematically to escape from being falling into local minima. In this paper, we solve TSP using both conventional GAs and GAs with the entropy-Boltzmann selection. We compare and analyze the performance of both algorithms in terms of numerical simulations. It is found that GAs with the entropy-Boltzmann selection outperforms the conventional GAs, and the new selection method helps to escape local minima.
AI-Helper
※ AI-Helper는 부적절한 답변을 할 수 있습니다.