초록

용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

최소 걸침 나무는 널리 알려진 순회 판매원 문제와 같이 전통적인 최적화 문제 중에 하나이다. 특히나 최소 걸침 나무와는 달리 차수 제약 최소 걸침 나무의 경우는 일반적으로 NP-hard 문제로 알려져 있다. 이러한 NP-hard 문제를 해결하기 위한 다양한 접근법들이 소개되었는데 유전 알고리즘은 효율적인 방법 중에 하나로 알려져 있다. 유전 알고리즘과 같이 진화에 기반을 둔 알고리즘을 어떤 문제에 적응하기 위해서 가장 우선적으로 고려되어야 하는 것은 해를 어떻게 표현할 것인가 인데 본 논문에서는 차수 제약 최소 걸침 나무를 해결하기 위한 새로운 트리 표현법을 제안한다.

최소 걸침 나무는 널리 알려진 순회 판매원 문제와 같이 전통적인 최적화 문제 중에 하나이다. 특히나 최소 걸침 나무와는 달리 차수 제약 최소 걸침 나무의 경우는 일반적으로 NP-hard 문제로 알려져 있다. 이러한 NP-hard 문제를 해결하기 위한 다양한 접근법들이 소개되었는데 유전 알고리즘은 효율적인 방법 중에 하나로 알려져 있다. 유전 알고리즘과 같이 진화에 기반을 둔 알고리즘을 어떤 문제에 적응하기 위해서 가장 우선적으로 고려되어야 하는 것은 해를 어떻게 표현할 것인가 인데 본 논문에서는 차수 제약 최소 걸침 나무를 해결하기 위한 새로운 트리 표현법을 제안한다.

AI 본문요약

엑셀 다운로드 AI-Helper

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

• 연구 주제
• 연구 방법
• 연구 결과

문제 정의

• 또한 제안하는 표현법에 맞는 새로운 연산자도 제안한다. 따라서 본 논문에서는 기존의 항상 트리를 만들어 내는 두 방법과 제안하는 방법의 비교를 통해 제얀하는 방법의 성능을 입증하도록 한다.
• 본 논문에서는 DCMST를 해결하기 위한 새로운 해 표현 방법을 제안한다. 제안하는 표현법은 기존의 TSP를 해결하기 위한 해표현법을 확장한 개념으로써 PrDfer 수와 NetKey를 이용한 방법처럼 항상 트리를 형성하기 때문에 어떤 repair 과정이 필요 없다는 특징을 지니고 있다.
• 본 논문에서는 TSP 를 EAs 를 이용해서 해결할 경우 사용하는 표현법을 확장한 새로운 트리 표현 방법을 제안한다. 일반적으로, TSP 에서는 각각의 도시가 해 표현에 단지 한번씩만 나타나는데 이를 시작 도시와 종료 도시를 연결하지 않고 남겨두면 degree 가 2 인 하나의 트리가 형성된다.
• 본 논문에서는 제안하는 해 표현법에 맞는 에지-거리 교 차연샨자 (Edge-Distance Crossover : EDX)라는 새로운 교차 연산자를 제안한다.
• 본 논문에서는 진화 알고리즘을 위한 새로운 트리 표현 방법과 이를 위한 새로운 교차 연산자를 제안하였다. 새로운 망법은 기존의 TSP 를 위한 해 표현법의 확장으로 표현이 아주 간단하고 항상 트리를 만들어낸다는 장점을 지니고 있으며 다양한 DCMST 문제로의 확장 또한 간단하다.

제안 방법

• 6, 돌연 변이 확률은 0」로 설정하였고 종료조건은 generation 이 1000 이 될 때까지로 설정하였다. 二I리고 선택전략으로는 토너먼트 크기가 2인 토너먼트 선택전략을 사용하였고, 3가지의 교차연산자 (1~poi.nt, 2-point, uniform crossover)와 제안하는 EDX 연산자 그리고 3 가지의 돌연변이 연산자 (inversion, reciprocal, random pe「hj「bation) 을 이용해서 실험을 하였다. 각 실험은 10번씩 수행하였고 실험 결과는 이를 평균한 값이다.
• 이를 이용하면 모든 경우의 DCMST 문제에 간단하게 적용이 가능하며 또한 트리를 대상으로 하는 모든 문제에 적용이 가능하다. 그리고, 본 논문에서 제안하는 방법은 앞에서 설명한 두 표현법 (PrDfer 수와 NetKey 를 이용한 방법)과 같이 항상 트리를 형성하기 때문에 다른 repair 과정이 필요가 없으며, 각각의 노드가 oH 씩 나타나야 한다는 제약조건만 만족시키면 기존의 어떤 연산자들을 이용해서도 구현이 가능하다. 그리고 encoding 과정과 decoding 과정이 하나의 해 표현으로 가능하기 때문에 부도가 지닌 정보를 이용한 연산자 개발이 용이하다.
• 본 논문에서는 제안하는 방법처럼 항상 트리를 만들어내기 때문에「epair 과정이 필요 없는 PrDer 수와 NetKey 를 이용한 표현법과 비교 실험을 수행하였다. 실험에 사용된 데이터는 500 X 500 크기의 grid 상에서 임으로 노드를 생성하였고, 각 노드간의 거러는 Euclidean distance 룰 이용하였다.
• 유전 알고리즘에 사용된 파라메타로 pop니ation 크기는 100, 교차 확률은 0.6, 돌연 변이 확률은 0」로 설정하였고 종료조건은 generation 이 1000 이 될 때까지로 설정하였다. 二I리고 선택전략으로는 토너먼트 크기가 2인 토너먼트 선택전략을 사용하였고, 3가지의 교차연산자 (1~poi.

데이터처리

• nt, 2-point, uniform crossover)와 제안하는 EDX 연산자 그리고 3 가지의 돌연변이 연산자 (inversion, reciprocal, random pe「hj「bation) 을 이용해서 실험을 하였다. 각 실험은 10번씩 수행하였고 실험 결과는 이를 평균한 값이다.

이론/모형

• 본 논문에서는 제안하는 방법처럼 항상 트리를 만들어내기 때문에「epair 과정이 필요 없는 PrDer 수와 NetKey 를 이용한 표현법과 비교 실험을 수행하였다. 실험에 사용된 데이터는 500 X 500 크기의 grid 상에서 임으로 노드를 생성하였고, 각 노드간의 거러는 Euclidean distance 룰 이용하였다. 그리고 각 노드의 degree 제약은 똑같이 3 으로 제한을 하였다.

성능/효과

• PrDer 수 표현의 경우는 다른 문헌들에서 제안하는 Uniform 교차 연산자와 Random Perturbation 돌연변이 연산자를 이용한 경우가 본 실험에서도 가장 우수한 것으로 나타났다. NetKey 를 이용한 표현의 경우 prOer 수를 이용한 표현보다 결과 값은 좋게 나왔지만 제안하는 방법에 비해서는 상당한 격차를 보임을 확인할 수 있다. 또한 이 방법은 노드 수가 적은 경우에 아주 좋은 결과를 찾아내는 특징을 보였다.
• PrDer 수 표현의 경우는 다른 문헌들에서 제안하는 Uniform 교차 연산자와 Random Perturbation 돌연변이 연산자를 이용한 경우가 본 실험에서도 가장 우수한 것으로 나타났다. NetKey 를 이용한 표현의 경우 prOer 수를 이용한 표현보다 결과 값은 좋게 나왔지만 제안하는 방법에 비해서는 상당한 격차를 보임을 확인할 수 있다.
• 새로운 망법은 기존의 TSP 를 위한 해 표현법의 확장으로 표현이 아주 간단하고 항상 트리를 만들어낸다는 장점을 지니고 있으며 다양한 DCMST 문제로의 확장 또한 간단하다. Z1 리고 제안하는 교차 연산자의 경우 부모가 가지고 있는 유전정보를 이용한다는 점에서 기존의 알고리즘들이 사용하는 일반적인 연산자들과는 차이를 보이며, 기존의 표현법과의 비교 실험을 통해서도 훨씬 더 좋은 결과를 산출해 냄을 확인할 수 있었다.
• 실험결과를 통해 알 수 있듯이 모든 경우에서 제안하는 방법이 기존의 PrDer 수를 이용하는 방법이 나 NetKey 를 이용하는 방법 보다 훨씬 우수한 결과 값을 산출하였고 문제의 크기가 커질수록 해의 차이가 훨씬 커짐을 확인할 수 있다. 그리고 연산자들 간의 비교를 보면 제안하는 EDX 교차 연산자와 Inversion 돌연변이 연산자를 이용한 경우가 가장 좋은 실험결과를 산출하였다.
• NetKey 를 이용한 표현의 경우 prOer 수를 이용한 표현보다 결과 값은 좋게 나왔지만 제안하는 방법에 비해서는 상당한 격차를 보임을 확인할 수 있다. 또한 이 방법은 노드 수가 적은 경우에 아주 좋은 결과를 찾아내는 특징을 보였다.
• 1 은 다른 표현 방법들과의 실험결과를 보여준다. 실험결과를 통해 알 수 있듯이 모든 경우에서 제안하는 방법이 기존의 PrDer 수를 이용하는 방법이 나 NetKey 를 이용하는 방법 보다 훨씬 우수한 결과 값을 산출하였고 문제의 크기가 커질수록 해의 차이가 훨씬 커짐을 확인할 수 있다. 그리고 연산자들 간의 비교를 보면 제안하는 EDX 교차 연산자와 Inversion 돌연변이 연산자를 이용한 경우가 가장 좋은 실험결과를 산출하였다.
• 본 논문에서는 DCMST를 해결하기 위한 새로운 해 표현 방법을 제안한다. 제안하는 표현법은 기존의 TSP를 해결하기 위한 해표현법을 확장한 개념으로써 PrDfer 수와 NetKey를 이용한 방법처럼 항상 트리를 형성하기 때문에 어떤 repair 과정이 필요 없다는 특징을 지니고 있다. 또한 제안하는 표현법에 맞는 새로운 연산자도 제안한다.

본문요약 정보가 도움이 되었나요? 예 아니오 제출

이 논문을 인용한 문헌

더보기