[논문]An Efficiency Analysis on Mutation Operation with TSP solved in Genetic Algorithm

Yoon, Hoijin

doi:10.9708/jksci.2020.25.12.055

An Efficiency Analysis on Mutation Operation with TSP solved in Genetic Algorithm 원문보기

韓國컴퓨터情報學會論文誌 = Journal of the Korea Society of Computer and Information, v.25 no.12, 2020년, pp.55 - 61

Yoon, Hoijin (Dept. of Computer Engineering, Hyupsung University)

초록
AI-Helper

유전자 알고리즘은 명료한 방식으로 답을 찾기 어려운 문제, 즉 NP 문제의 경우 효과적인 솔루션을 찾을 수 있다. 단 유전자 알고리즘의 실행 비용은 기존 프로그래밍 방식에 비하여 높은 비용을 요구하게 되므로, 높은 성능의 실행환경을 전제로 한다. 이러한 문제를 조금이나마 줄여보기 위하여 본 연구는 유전자 알고리즘의 돌연변이 연산자를 초점을 맞추고, 돌연변이 연산의 복잡한 실행을 위한 비용을 고려하여, 과연 해당 연산자가 모든 문제 영역에서 반드시 요구될까를 분석하기 위한 실험을 진행한다. 우리 실험 주체는 유전자 알고리즘을 적용하는 대표적인 문제 중의 하나인 TSP(Travelling Salesman Problem)으로 하였다. 돌연변이 연산을 적용하는 경우와 적용하지 않는 경우에 대한 결과값들을 세대수와 적합도 값을 수집하여 분석한다. 그 결과 돌연변이 연산자를 적용하는 경우가 세대수 감소와 적합도 향상의 효과적인 결과를 반드시 보이지는 않았다.

Abstract ▼ AI-Helper

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.

주제어

표/그림 (5)

그림 Fig. 1. A Sample Solution from TSP programmed in GA
그림 Fig. 2. A Result of TSP program in the experiment
그림 Fig. 3. Relation of Fitness and the number of generations
그림 Fig. 4. Solutions in the case where mutation_rate is 0
그림 Fig. 5. Solutions in the case where mutation_rate is 0.2

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

GA에서 돌연변이 연산자를 적용하는 목적은 최종결과물이 지역적 최적 솔루션 (local optimum)머무는 것을 방지하여 최종 솔루션의 적합도를 높이기 위함, 즉 혜택을높이고자 함이다. 지역적 최적 솔루션을 피하기 위한 최적화 문제는 매우 큰 볼륨의 가능한 솔루션들 가운데 하나를찾아 최적 솔루션으로 명시한다.
본 연구는 GA의 효과성을 지원하기 위하여 GA의 비용 즉 세대 수와, 혜택 즉 최종결과물의 적합도의 상호관계가 돌연변이 연산자의 적용 여부에 영향을 받는지를 평가하였다. 이때 비용도 함께 평가하여, 돌연변이 연산의 효과성을 분석한다.
본 연구는 유전자 알고리즘이 갖는 돌연변이 연산에 대한 효과성 분석을 하였다. 지역적 최적 솔루션에 머무는 문제를 해결하기 위한 돌연변이 연산자는 프로그램 실행 면에서 또 다른 실행 비용을 발생하게 된다.
본 연구는 유전자 알고리즘이 갖는 돌연변이 연산의 역할에 대한 고찰로부터 시작하였다. 돌연변이 연산은 솔루션이답으로 가지 못하고 정체하는 현상 즉 지역적 최적 솔루션에머물게 되는 것을 막기 위하여 적용되는 연산이다.
Lu의 선택 연산 대신 교배와 돌연변이 연산에 휴리스틱 정보를 적용하여 비용 절감 경로를 빨리 찾도록 하는 연구[11]도 있다. 본 연구는 특히 돌연변이 연산이 GA에서 갖는 의미를 분석하여, 돌연변이 연산을 통하여 얻는 적합도 향상과 세대수 감소를 어느정도 보장받을 수 있을지를 보이고자 한다.
지역적 최적 솔루션에 머무는 문제를 해결하기 위한 돌연변이 연산자는 프로그램 실행 면에서 또 다른 실행 비용을 발생하게 된다. 본 연구에서는 돌연변이 연산을 적용하는 경우와 적용하지 않는 경우의 솔루션을 찾는 세대수와 솔루션의 적합도를 분석하여, “돌연변이 연산을 적용하면 세대수는 짧아지고 적합도는 높아지는가? 즉 비용이익면에서 효과적일까?”에 대한 답을 얻고자 하였다. 유전자 알고리즘을 적용하는 대표적인 문제인 TSP를 파이썬으로 구현하였으며, 돌연변이 연산 비율, 즉 mutation_rate를 독립변수로 하는 실험을 수행하였다.
우리는 실험을 통하여 돌연변이 연산의 적용 여부가 실행 결과에 어떤 영향을 주는지를 분석하고자 한다. 이 분석을 우리는 비용에 대한 이익 분석이라고 하였다.
이렇게 GA를 효과적으로 진행하기 위한 연구들과 같이, 본 연구는 돌연변이 연산으로 인한 GA의 효과성을 평가한다. GA에서 돌연변이 연산자를 적용하는 목적은 최종결과물이 지역적 최적 솔루션 (local optimum)머무는 것을 방지하여 최종 솔루션의 적합도를 높이기 위함, 즉 혜택을높이고자 함이다.

가설 설정

RQ : 돌연변이 연산을 적용하면 세대수는 짧아지고 적합도는 높아지는가? 즉 비용이익면에서 효과적일까?
돌연변이 연산으로 기대했던 가설은 더 좋은 적합도를보이고, 더 짧은 세대수를 나타낼 것이라는 기대였다. 그러나 실험의 결과로는 꼭 그렇지는 않다고 볼 수 있다.
짧아지고 적합도는 높아지는가? 즉 비용이익면에서 효과적일까?”를 RQ(Research Question)으로 하여, (1) 돌연변이 연산을 제거하여 local optimum을 피하기위하여 투입하는 노력을 절감하는 효과와 (2) 솔루션의 fitness값을 비교하여, (1)과 (2)사이의 비용-이익관계 (trade-off)를 분석한다.

제안 방법

RQ에 대한 답을 얻기 위하여 우리는 3장에서 TSP를 유전자 알고리즘으로 구현하여 실험을 설계하였다. 돌연변이연산을 하는 경우와 하지 않는 경우로 나누고, mutation_rate를 ‘독립변수’로 하고, 각 경우에 일정수준이상의 솔루션을 내는 세대 수와 솔루션의 적합도 값을 ‘의존변수’로 설정하여 실험을 진행하였다.
[12]. 그러나 본 실험은 TSP 문제를 해결하는 어플리케이션을 대상으로 하여 돌연변이 연산자를 적용하여, 본 연구의 RQ에 대한 결론을 정리하였다. 본 연구의 RQ는 돌연변이 연산과 솔루션의 비용 이익면에서의 상호관계에 대한 것이다.
돌연변이 연산을 적용하는 경우와 적용하지 않는 경우의 실행 결과를 아래 좌표평면에 분포시키고, 그 분포가 A 분면에 있을수록 비용이익면에서 효과적인 것이므로, 우리가 독립변수로 설정한 돌연변이 연산의 적용 비율, 즉 mutation_rate를 조정하여 실험을 진행한다.
돌연변이연산을 하는 경우와 하지 않는 경우로 나누고, mutation_rate를 ‘독립변수’로 하고, 각 경우에 일정수준이상의 솔루션을 내는 세대 수와 솔루션의 적합도 값을 ‘의존변수’로 설정하여 실험을 진행하였다.
앞서언급한대로 독립변수 mutation_rate를 변경하면서 세대수와 해당 솔루션의 적합도를 구할 때, 임의선택 절차로인하여 그 결과값이 매번 다르게 생성된다. 따라서 이와같은 비일관성을 고려하여 본 실험은 동일한 mutation_rate에 대하여 TSP 프로그램 실행을 반복적으로 실시하여 솔루션을 생성하는 세대수와 해당 솔루션의적합도 값들이 어떤 흐름을 갖는지를 분석한다.
이때 구해진 거리가짧을수록 좋은 적합도, 즉 솔루션으로써 적합하게 되므로, 경로 거리의 합과 적합도는 서로 반비례 관계를 갖는다. 따라서 총 거리의 합을 분모로 하여 적합도를 계산한다.
본 연구는 “돌연변이 연산을 적용하면 솔루션을 얻는세대수는 짧아지고 적합도는 높아지는가? 즉 비용이익면에서 효과적일까?”를 RQ(Research Question)으로 하여, (1) 돌연변이 연산을 제거하여 local optimum을 피하기위하여 투입하는 노력을 절감하는 효과와 (2) 솔루션의 fitness값을 비교하여, (1)과 (2)사이의 비용-이익관계 (trade-off)를 분석한다.
TSP는 NP-complete 문제로서, 기존의 정공법으로는 해결하기 어렵고, 또한 그복잡도가 매우 높은 문제이다. 본 연구에서는 TSP를 유전자 알고리즘으로 해결하기 위한 코드를 파이썬으로 작성하여 실험에 활용하였다[8, 9].
실험을 통하여 산출되는 결과값을 분석하기 위하여, 세대수를 x축으로 하고 적합도를 y축으로 하는 좌표평면으로 만들었다. 이때 각 분면을 크게 4개로 나누어볼 수 있으며, 그림 3과 같다.
실험의 독립변수는 mutation_rate, 즉 돌연변이 연산을 어느 정도로 적용할지를 결정하는 변수이다. 그에 대한 의존변수는 일정수준 이상의 적합도를 갖는 솔루션을 생성하게 되는 세대 수와 그의 적합도 값이다.
즉 실행 비용이 크다고 할 수 있다. 우리는 GA의 비용을줄이기 위한 방법으로 돌연변이 연산의 제거를 고려해보았다. 돌연변이 연산의 의미는 local optimum을 해결하기 위한 것이라고 한다면, 돌연변이 연산을 적용한 경우의솔루션이, 돌연변이 연산을 적용하지 않는 솔루션보다 적합도가 크다는 기대가 가능하다.
이때 세대 수를 ‘비용’으로 보고, 지역적 솔루션을 지나 더 좋은 솔루션을 내는 것을 ‘이익’으로 볼 때, 돌연변이 연산을 적용하면 짧은 세대를 거쳐 높은 적합도를 갖는 솔루션을 갖게 되는 결과를 예상할 수 있다. 우리는 이를 다음의 RQ로 정의하고, 그에 대한 답을 찾기 위한 실험을 설계하였다.
본 연구에서는 돌연변이 연산을 적용하는 경우와 적용하지 않는 경우의 솔루션을 찾는 세대수와 솔루션의 적합도를 분석하여, “돌연변이 연산을 적용하면 세대수는 짧아지고 적합도는 높아지는가? 즉 비용이익면에서 효과적일까?”에 대한 답을 얻고자 하였다. 유전자 알고리즘을 적용하는 대표적인 문제인 TSP를 파이썬으로 구현하였으며, 돌연변이 연산 비율, 즉 mutation_rate를 독립변수로 하는 실험을 수행하였다. 그 결과, 돌연변이 연산을 적용하지 않는 경우에 비하여 돌연변이 연산을 적용하는 경우가 더 높은 적합도 또는 짧은 세대수를 보장하지는 않음을 알 수 있었다.
즉, 처음 세대의 범위에서 벗어나기 위한 변형을 돌연변이 연산자가 맡아서 한다. 이 역할은 어떤 어플리케이션에서도 동일하게 적용되므로, TSP에 대한 평가 결과로 본 실험의 RQ에 대한 답을 유도하였다.
이때 비용도 함께 평가하여, 돌연변이 연산의 효과성을 분석한다.
512인 경우이다. 이와 같은과정을 mutation_rate가 0인 경우와 0.2인 경우로 나누어 실행하고, 확률적 실행에 의한 무작위성을 고려하여 20 회 반복 실행하여 분포를 확인하는 방법으로 프로그램을활용한다.
그리고 Wang[7]은본 연구와 같이 세대 수를 비용으로 정의하고, 보다 짧은세대 수를 거치는 최소비용 경로를 찾을 수 있도록 TSP에적용한 GA을 변형하였다. 즉, 각 세대에서 생성된 솔루션의 경로에서 꼬임이 발생하는 경우에 대하여, 솔루션의 꼬임을 푸는 untwist연산을 개발하여 적용함으로써, TSP 최적 솔루션에 보다 빨리 도달하도록 하였다.
2로 설정한 실행 결과는 그림 4와 같은 분포를 보인다. 첫 번째 분포는 mutation_rate를 0으로 설정하여 TSP의솔루션을 찾았다. 이를 반복적으로 실행하여 얻은 세대수와 적합도 값으로 그린 분포도이다.
한 세대를 구성하는 개체의 규모, 즉 populatione 100 으로 하여, 한 세대에 100개의 후보경로들이 존재하도록 하였다. 100개 개체 가운데 높은 적합도를 갖는 50개를 선정하도록 Selection의 값은 0.

대상 데이터

우리 실험을 위하여 TSP를 파이썬으로 구현하였으며, 도시 50개를 적용하였다. 초기 설정값들은 다음과 같으며, 이때 mutation_rate를 변경하면서 실험을 진행한다.

성능/효과

유전자 알고리즘을 적용하는 대표적인 문제인 TSP를 파이썬으로 구현하였으며, 돌연변이 연산 비율, 즉 mutation_rate를 독립변수로 하는 실험을 수행하였다. 그 결과, 돌연변이 연산을 적용하지 않는 경우에 비하여 돌연변이 연산을 적용하는 경우가 더 높은 적합도 또는 짧은 세대수를 보장하지는 않음을 알 수 있었다. 즉, 돌연변이 연산으로 인한 추가 실행 시간 비용까지 고려한다면, 무조건적인 돌연변이 연산은 반드시 필요하지 않으며, 만일 요구되는 적합도의 수준이 매우 높으며, 시스템의 성능이 높은 경우로서 세대수가 많아지거나 돌연 변이연산 적용의 비용에 영향을 받지 않는다면 솔루션의 질적 향상, 즉 적합도를 높이는 방향으로 돌연변이 연산을 고려할 수 있다.
돌연변이 연산을 적용한 경우가 적용하지 않는 경우에 비하여 더 효과적인 결과를 보일 것으로 기대하였으나, 세대수 면에서는 더 효과적인 결과로 보기 어려운 분포를 보였다. 그렇다면 적합도가 더 높은 솔루션을 얻은 것일까? 돌연변이 연산을 적용하지 않은 mutation_rate를 0으로 설정한 경우의 반복 실행에 대한 적합도 평균은 0.
즉, 돌연변이 연산으로 인한 추가 실행 시간 비용까지 고려한다면, 무조건적인 돌연변이 연산은 반드시 필요하지 않으며, 만일 요구되는 적합도의 수준이 매우 높으며, 시스템의 성능이 높은 경우로서 세대수가 많아지거나 돌연 변이연산 적용의 비용에 영향을 받지 않는다면 솔루션의 질적 향상, 즉 적합도를 높이는 방향으로 돌연변이 연산을 고려할 수 있다. 본 실험은 돌연변이 연산에 대한 기대 가설이 반드시 참이 아님을 보임으로써, 돌연변이 연산을 반드시 적용할 필요가 없음을 보였다.
507로서 더 높은 적합도를 보이지는 않았다. 참고로 세대수의 평균을 비교하면, 돌연 변이연산이 없는 경우 평균 세대수는 9.85이고, 돌연변이 연산을 적용한 경우의 평균 세대수는 16.85로서, 돌연변이 연산이 없는 경우 솔루션을 찾는 세대수가 오히려 더 적게 나타났다.
솔루션으로 찾는다. 후손을 만들어 구성하는 세대의 수가 적을수록, 그리고 솔루션의 적합도가 높을수록 효과적이라고 평가할 수 있다

참고문헌 (12)

Holland, J.H.. "Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence," MIT Press: Cambridge, MA, USA, pp.89-120, 1992.
M. Mitchell, "An Introduction to Genetic Algorithms," MIT Press, pp.128-130, 1999
H. Yoon, "Fitness-Orientated Mutation Operators in Genetic Algorithm," IJITEE, Vol. 9, No. 4, pp.1769-1772, Feb. 2020. doi:10.35940/jijtee.D1692.029420
Alan T Piszcz, Terence Soule, "A Survey of Mutation Techniques in Genetic Programming," Proceedings of the 8th annual conference on Genetic and evolutionary computation, pp. 951-952, Seattle, Washington, USA, July 2006. DOI: 10.1145/1143997.1144165
E. Osaba, R. Carballedo, F. Diaz, E. Onieva, I. de la Iglesia, A. Perallos, "Crossover versus Mutation: A Comparative Analysis of the Evolutionary Strategy of Genetic Algorithms Applied to Combinatorial Optimization Problems", The Scientific World Journal, vol. 2014, Article ID 154676, 22 pages, 2014. DOI: 10.1155/2014/154676

상세보기
Hee-Su Kim and Sung-Bae Cho, "An efficient genetic algorithm with less fitness evaluation by clustering," Proceedings of the 2001 IEEE Congress on Evolutionary Computation, pp.887-894, Seoul, South Korea, May 2001. DOI: 10.1109/CEC.2001.934284.
L. Wang, J. Zhang and H. Li, "An Improved Genetic Algorithm for TSP," Proceedings of 2007 International Conference on Machine Learning and Cybernetics, pp.925-928, Hong Kong, Aug. 2007. DOI: 10.1109/ICMLC.2007.4370274.
Clinton Sheppard, "Genetic Algorithms with Python," CreateSpace Independent Publishing Platform, pp.169-186, 2016
Giancarlo Zaccone, "Natural Computing with Python," bpb publications, pp.85-118, 2019
J. Lu, N. Fang, D. Shao and C. Liu, "An Improved Immune-Genetic Algorithm for the Traveling Salesman Problem," Proceedings of 3rd International Conference on Natural Computation (ICNC 2007), pp. 297-301, Haikou, Aug. 2007. DOI: 10.1109/ICNC.2007.217.
Y. Liu and J. Huang, "A Novel Genetic Algorithm and Its Application in TSP," Proceedings of 2008 IFIP International Conference on Network and Parallel Computing, pp. 263-266, Shanghai, Oct. 2008. DOI: 10.1109/NPC.2008.27
B. H. Hasan and M. S. Mustafa, "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, Kuala Lumpur, Jan. 2011.DOI: 10.1109/ISMS.2011.11.

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증