유전자 알고리즘으로 구현한 TSP에서 돌연변이 연산의 효과성 분석
An Efficiency Analysis on Mutation Operation with TSP solved in Genetic Algorithm
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
유전자 알고리즘은 명료한 방식으로 답을 찾기 어려운 문제, 즉 NP 문제의 경우 효과적인 솔루션을 찾을 수 있다. 단 유전자 알고리즘의 실행 비용은 기존 프로그래밍 방식에 비하여 높은 비용을 요구하게 되므로, 높은 성능의 실행환경을 전제로 한다. 이러한 문제를 조금이나마 줄여보기위하여 본 연구는 유전자 알고리즘의 돌연변이 연산자를 초점을 맞추고, 돌연변이 연산의 복잡한실행을 위한 비용을 고려하여, 과연 해당 연산자가 모든 문제 영역에서 반드시 요구될까를 분석하기 위한 실험을 진행한다. 우리 실험 주체는 유전자 알고리즘을 적용하는 대표적인 문제 중의하나인 TSP(Travelling Salesman Problem)으로 하였다. 돌연변이 연산을 적용하는 경우와 적용하지않는 경우에 대한 결과값들을 세대수와 적합도 값을 수집하여 분석한다. 그 결과 돌연변이 연산자를 적용하는 경우가 세대수 감소와 적합도 향상의 효과적인 결과를 반드시 보이지는 않았다.
Abstract
Genetic Algorithm(GA) is applied to a problem that could not figure out its solution in a straightway. It is called as NP-hard problem. GA requires a high-performance system to be run on since the high-cost operations are needed such as crossover, selection, and mutation. Moreover, the scale of the problem domain is normally huge. That is why the straightway cannot be applied. To reduce the drawback of high-cost requirements, we try to answer if all the operations including mutation are necessary for all cases. In the experiment, we set up two cases of with/without mutation operations and gather the number of generations and the fitness of a solution. The subject in the experiment is Travelling Salesman Problem(TSP), which is one of the popular problems solved by GA. As a result, the cases with mutation operation are not faster and the solution is fitter than the case with mutation operation. From the result, the conclusion is that mutation operation does not always need for a better solution in a faster way.
참고문헌 (12)
- Holland, J.H., "Adaptation in Natural and Artificial Systems : An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence", pp.89~120 (1992), MIT Press
- M. Mitchell, "An Introduction to Genetic Algorithms", pp.128~130 (1999), MIT Press
- H. Yoon, "Fitness-Orientated Mutation Operators in Genetic Algorithm", IJITEE, 9(4), pp.1769~1772 (2020)[DOI]
- Alan T Piszcz, "A Survey of Mutation Techniques in Genetic Programming", Proceedings of the 8th annual conference on Genetic and evolutionary computation, pp.951~952 (2006)
- E. Osaba, "Crossover versus Mutation : A Comparative Analysis of the Evolutionary Strategy of Genetic Algorithms Applied to Combinatorial Optimization Problems", The Scientific World Journal, 2014 (2014)[DOI]
- Hee-Su Kim, "An efficient genetic algorithm with less fitness evaluation by clustering", Proceedings of the 2001IEEE Congress on Evolutionary Computation, pp.887~894 (2001)
- L. Wang, "An Improved Genetic Algorithm for TSP", Proceedings of 2007 International Conference on Machine Learning and Cybernetics, pp.925~928 (2007)
- Clinton Sheppard, "Genetic Algorithms with Python", pp.169~186 (2016), CreateSpace Independent Publishing
- Giancarlo Zaccone, "Natural Computing with Python", pp.85~118 (2019), bpb publications
- J. Lu, "An Improved Immune-Genetic Algorithm for the Traveling Salesman Problem", Proceedings of 3rd International Conference on Natural Computation (ICNC 2007), pp.297~301 (2007)
- Y. Liu, "A Novel Genetic Algorithm and Its Application in TSP", Proceedings of 2008 IFIP International Conference on Network and Parallel Computing, pp.263~266 (2008)
- B. H. Hasan, "Comparative Study of Mutation Operators on the Behavior of Genetic Algorithms Applied to Non-deterministic Polynomial (NP) Problems", Proceedings of 2011 Second International Conference on Intelligent Systems, Modelling and Simulation, pp.7~12 (2011)