강화학습을 이용한 n-Queen 문제의 수렴속도 향상

국문 초록 (Abstract)

강화학습(Reinforcement-Learning)의 목적은 환경으로부터 주어지는 보상(reward)을 최대화하는 것이며, 강화학습 에이전트는 외부에 존재하는 환경과 시행착오를 통하여 상호작용하면서 학습한다. 대표적인 강화학습 알고리즘인 Q-Learning은 시간 변화에 따른 적합도의 차이를 학습에 이용하는 TD-Learning의 한 종류로서 상태공간의 모든 상태-행동 쌍에 대한 평가 값을 반복 경험하여 최적의 전략을 얻는 방법이다. 본 논문에서는 강화학습을 적용하기 위한 예를 n-Queen 문제로 정하고, 문제풀이 알고리즘으로 Q-Learning을 사용하였다. n-Queen 문제를 해결하는 기존의 방법들과 제안한 방법을 비교 실험한 결과, 강화학습을 이용한 방법이 목표에 도달하기 위한 상태전이의 수를 줄여줌으로써 최적 해에 수렴하는 속도가 더욱 빠름을 알 수 있었다.

다국어 초록 (Multilingual Abstract)

The purpose of reinforcement learning is to maximize rewards from environment, and reinforcement learning agents learn by interacting with external environment through trial and error. Q-Learning, a representative reinforcement learning algorithm, is a type of TD-learning that exploits difference in suitability according to the change of time in learning. The method obtains the optimal policy through repeated experience of evaluation of all state-action pairs in the state space. This study chose n-Queen problem as an example, to which we apply reinforcement learning, and used Q-Learning as a problem solving algorithm. This study compared the proposed method using reinforcement learning with existing methods for solving n-Queen problem and found that the proposed method improves the convergence rate to the optimal solution by reducing the number of state transitions to reach the goal.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 관련연구
• 3. 강화학습(reinforcement learning)
• 4. Q-Learning을 이용한 n-Queen알고리즘
• 5. 실험 및 평가
• 6. 결론
• 참고문헌
• 저자소개

참고문헌 (Reference)

1 "함수근사와 규칙추출을 위한 클러스터링을 이용한 강화학습" 30 (30): 1054-1061, 2003.

2 "학습 에이전트" 18 (18): 26-35, 2003.

3 "탐색 강화 계층적 강화 학습" 28 (28): 2001-, 2001

4 "강화 학습에서의 탐색과 이용의 균형을 통한 범용적 온라인 Q-학습이 적용된 에이전트의 구현" 30 : 672-680, 2003.

5 "Using Reinforcement Learning to Spider the Web Efficiently In proceedings of the 16th International Conference on Machine Learning" 335-343, 1999.

6 "Q- Learning" Machine Learning" 279-292, 1992.

7 "Personalized Web-Document Filtering Using Reinforcement Learning" 15 : 665-685, 2001.

8 "Neural Network" Prentice- Ha ll 1999.

9 "Machine Learning" McGraw-Hill 1997.

10 "Foundations of Algorithms" Jones and Bartlett Publisher 1998.

11 "Building domain-specific search engines with machine learning techniques" In AAAI-99 Spring Symposium on Intelligent Agents in Cyberspace 135-141, 1999.

12 "An Introduction. The MIT Press" 1998.