검색 상세

자동 마이그레이션 조절을 이용한 분산 유전자 알고리즘

Distributed Genetic Algorithm using Automatic Migration Control

초록/요약

오늘날 데이터는 네트워크에 의해 연결된 여러 사이트들에 분포되어 있으며 그 양이 방대하다. 따라서 기존의 머신 러닝 기법들이 분산화 된 환경에서도 효과적으로 적용될 수 있도록 하기 위한 여러 가지 방법들이 연구되고 있다. 특히 생태계 기반의 휴리스틱 탐색 알고리즘인 유전자 알고리즘은 성능 면에서 높은 효율성을 보이지만, 일반적으로 하나의 사이트에 있는 데이터에서 수행되며 시간과 공간에서 높은 복잡도를 보인다. 따라서 유전자 알고리즘의 계산적인 오버헤드를 줄이고, 나아가 분산되어있는 데이터에 적용이 가능한 분산 유전자 알고리즘에 대한 연구가 활성화되고 있다. 분산 유전자 알고리즘은 부분 개체군 사이에 개체들의 이동을 허용하므로 기존의 단일 유전자 알고리즘보다 더 많은 수의 파라미터를 필요로 한다. 특히 어떤 개체들을 얼마나 많이 이주시킬 것인가에 따라 그 성능이 달라질 수 있기 때문에 적절한 파라미터의 선택이 중요하다고 하겠다. 따라서 본 논문은 부분 개체군 사이의 개체들의 이동에 필요한 파라미터들을 적응적으로 결정하는 알고리즘을 제안한다. 이에 더하여, 이동된 개체들이 새로운 부분 개체군에서 도태되지 않고 잘 적응할 수 있도록 하기 위한 장치를 제안한다. 제안된 분산 유전자 알고리즘을 머신 러닝의 주요한 연구 주제 중 하나인 특징 부분 선택에 적용하여 실험하였다. 분산 유전자 알고리즘을 적용하여 생성된 특징들을 이용한 분류 정확도를 평가한 결과, 단일 유전자 알고리즘을 적용한 경우에 비해 상대적으로 좋은 성능을 얻을 수 있었다.

more

초록/요약

Nowadays, huge data are distributed in different sites connected on the networks. Therefore, many approaches to make existing machine learning methods be effectively applied to distributed environments have been researched. The Genetic Algorithm is one of global search heuristics inspired from biology. It is highly efficient in performance, but generally, it runs with data at a single site, which incurs high complexity in both time and space. Therefore, the research on Distributed Genetic Algorithm has been conducted actively in a bid to handle distributed data and to mitigate the computational overhead. In addition to standard parameters of Genetic Algorithm, Distributed Genetic Algorithm needs extra parameters, as it allows individuals to move between subpopulations. Especially, it is important to select proper parameters, because the performance is sensitive according to how many and which individuals move. Motivated by these, a new algorithm is proposed in this thesis to determine how many and which individuals move between subpopulations at each site adaptively. In addition, we present a method to help individuals from other subpopulations not be weeded out but adapt to a new subpopulation. We apply our Distributed Genetic Algorithm to the feature subset selection task which has been one of the active research topics in machine learning. As a result, the proposed algorithm produced better performance than the single genetic algorithm in terms of the classification accuracy with the feature subsets.

more

목차

제 1 장 서론 = 1
1.1 연구 배경 = 1
1.2 논문의 구성 = 3
제 2 장 관 련 연 구 = 4
2.1 유전자 알고리즘(Genetic Algorithm) = 4
2.2 유전자 알고리즘의 병렬 모델들(Parallel Models) = 7
2.3 분산 유전자 알고리즘(Distributed Genetic Algorithm) = 11
2.4 특징 선택(Feature Selection) = 13
제 3 장 자동 마이그레이션 조절을 이용한 분산 유전자 알고리즘 = 16
3.1 자동 마이그레이션 조절을 이용한 분산 유전자 알고리즘 = 17
3.1.1 알고리즘의 개요 = 17
3.1.2 자동 마이그레이션 조절 프로세스 = 21
3.1.3 노화(Aging) = 22
3.2 알고리즘을 이용한 특징부분 선택 = 23
제 4 장 실험 및 결과 = 26
4.1 실험 방법 = 26
4.2 데이터 셋 설명 = 27
4.3 실험 결과 = 28
4.3.1 CGA와 DGA의 비교 = 28
4.3.2 DGA의 평균 학습 곡선 = 32
4.3.3 DGA와 독립적인 실행 모델의 비교 = 34
제 5 장 결론 및 향후 과제 = 35
5.1 결론 = 35
5.2 향후 과제 = 37
참고문헌 = 39
그림목차
[그림 1] 이진 데이터에 대한 유전자 연산자들의 연산과정 = 5
[그림 2] 독립적인 실행 모델 = 7
[그림 3] 지배-종속 모델 = 8
[그림 4] 분산 모델 = 9
[그림 5] 셀 방식의 모델 = 9
[그림 6] 여러 가지 혼성 모델 = 10
[그림 7] 특징 선택의 일반적인 진행 과정 = 14
[그림 8] 알고리즘의 흐름도 = 17
[그림 9] 자동 마이그레이션 조절 프로세스 = 22
[그림 10] 특징 부분 집합의 이진 문자열 표현 = 24
[그림 11] 분산 유전자 알고리즘을 이용한 특징 부분 선택 = 25
[그림 12] DGA에서 가장 좋은 특징 부분 집합들의 학습 곡선 = 33
표목차
[표 1] 데이터 셋 = 27
[표 2] CGA와 DGA 사이의 분류 정확도의 비교 = 29
[표 3] 훈련 정확도와 테스트 정확도 사이의 차 = 30
[표 4] 각 테스트 정확도의 표준편차 = 31
[표 5] 독립적인 실행모델과 자동 마이그레이션 조절을 이용한 DGA의 분류 정확도 비교 = 34

more