정보처리학회 논문지 B
Current Result Document :
| 한글제목(Korean Title) |
Ant-Q 학습을 이용한 Gale-Shapley 문제 해결에 관한 연구 |
| 영문제목(English Title) |
Solving the Gale-Shapley Problem by Ant-Q learning |
| 저자(Author) |
김현
정태충
Hyun Kim
TaeChoong Chung
|
| 원문수록처(Citation) |
VOL 18-B NO. 03 PP. 0165 ~ 0172 (2011. 06) |
한글내용
(Korean Abstract) |
본 논문에서는 생물학의 개미들이 학습을 통해 목표를 획득하는 방법을 응용한 Ant-Q 알고리즘(Ant Q learning System)[1]을 Gale-Shapley[2]알고리즘을 통해 제시되었던 안정된 결혼문제(SMP: Stable Marriage Problem)[3]의 새로운 해법을 찾기 위해 적용 하였다. SMP는 남성(mi)들과 여성(wj)들은 각자 자신이 좋아하는 이상형에 대한 선호도(PL: preference list)를 바탕으로 안정적이면서도 최선의 짝을 찾는 것을 목표로 하고 있다. Gale-Shapley 알고리즘은 남성(혹은 여성) 위주로 안정적(stability)인 짝(Matching)을 성사시키므로 다양한 조건을 수용하지 못한다.
본 논문에 적용된 Ant-Q는 개미(Ant)의 페로몬을 활용한 학습인 ACS(Ant colony system)에 강화학습의 일종인 Q-학습[9]을 추가한 방법으로, SMP의 새로운 해법을 찾을 수 있었다. |
영문내용
(English Abstract) |
In this paper, we propose Ant-Q learning Algorithm[1], which uses the habits of biological ants, to find a new way to solve Stable Marriage Problem(SMP)[3] presented by Gale-Shapley[2]. The issue of SMP is to find optimum matching for a stable marriage based on their preference lists (PL). The problem of Gale-Shapley algorithm is to get a stable matching for only male (or female). We propose other way to satisfy various requirements for SMP.
ACS(Ant colony system) is an swarm intelligence method to find optimal solution by using phermone of ants. We try to improve ACS technique by adding Q learning[9] concept. This Ant-Q method can solve SMP problem for various requirements. The experiment results shows the proposed method is good for the problem. |
| 키워드(Keyword) |
안정된 결혼문제
개미알고리즘
Q-학습
Ant-Q
TSP
Stable Marriage Problem
Ant Colony System
Q-learning
|
| 파일첨부 |
PDF 다운로드
|
