[논문]자기 적응형 교배기법을 이용한 반복적 죄수 딜레마 게임의 진화적 협동 수렴 분석

김찬중; 이종현; 안창욱

자기 적응형 교배기법을 이용한 반복적 죄수 딜레마 게임의 진화적 협동 수렴 분석
Analysis on the a Self Adaptive Crossover for Iterated Prisoner's Dilemma Game of Evolutionary Convergence 원문보기

한국정보처리학회 2010년도 추계학술발표대회, 2010 Nov. 12, 2010년, pp.478 - 481

김찬중 (성균관대학교 정보통신공학부) , 이종현 (성균관대학교 정보통신공학부) , 안창욱 (성균관대학교 정보통신공학부)

초록
AI-Helper

본 논문에서는 경제학, 사회학, 수학 분야에서 수십년 전부터 연구해오던 죄수의 딜레마 게임의 협동진화에 대해 고찰해보고자 한다. 반복적 죄수의 딜레마 게임은 게임이론의 가장 기본적인 이론으로써, 사회적 상호작용, 경제활동, 국제관계 등 다양한 현상들을 모델링 하기 위한 하나의 방법이다. 그 중에 N명이 참가하는 반복적 죄수 딜레마 게임의 전략은 유전 알고리즘(Genetic Algorithms, GAs)을 통해 진화적으로 만들어 낼 수 있으며, 이 경우에 그 결과를 일반적인 내쉬 균형 이 아닌, 모든 개체들이 유전알고리즘을 통해 협동으로 수렴하도록 유도할 수 있다는 사실은 상당히 시사하는 바가 크다. 기존에 주로 연구되어오던 죄수의 딜레마 게임은 협동으로의 수렴과정에서 일반적으로 순위기반선택(Rank-based selection)과 1점 교배기법(1point crossover)을 사용한다. 그러나 순위기반선택은 모든 개체에 순위을 매겨야 하기 때문에, 개체수가 커질수록 성능이 저하되며, 1점 교배기법은 개체 값이 분산되어있을 경우, 최적해(Optimal solution)을 찾기 힘들다는 단점이 있어, 개체수가 많은 경우에 적용하기에는 비효율적이다. 본 논문에서는 토너먼트 선택기법(Tournament selection)과 자기 적응형 교배기법(Self-adaptive crossover)을 적용한 새로운 기법을 제안한다. 또한 기존 기법과 비교 실험을 통해 제안기법이 기존기법에 비해 평균 수렴시간과 수렴 횟수에서 뛰어난 성능을 보이고 있음을 확인하였다.

AI 본문요약
AI-Helper

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

문제 정의

본 논문에서는 게임이론 중에서도 가장 널리 알려진 죄수의 딜레마, 그 중에서도 반복적인 죄수의 딜레마 게임(NIPD)에서 공진화를 통해 개체군들이 협동으로 수렴할 수 있음을 보여주는 기존 실험에서 사용된 순위기반선택기법(Rank-based selection)과 1점 교배기법(1 point crossover)의 문제점을 분석하는 한편, 보다 효율적인 기법을 도출하기 위해 토너먼트 선택기법(Tournament selection)과 자기 적응형 교배기법(Self-Adative Crossover)을 고찰하고 이들 기법의 비교분석을 통해 보다 제안 기법의 성능향상을 얻고자 하였다.

가설 설정

본 논문에서는 함수 C와 D를 수식 1과 같이 가정하였다.

제안 방법

우선, 기존 기법을 소개한 논문을 바탕으로 본 논문에서 제안한 새로운 기법을 적용한 실험을 수행하였고 각 기법간의 수렴시간과 횟수를 측정하였다.

이론/모형

이 매개변수의 결정은 일반적으로 매개변수 조율에 의해 이루어지는데, 이는 시간과 노력을 소모하게 만들고 효율적이지 않다. 이 점을 개선하기 위해 본 논문에서는 자기 적응형 교배기법을 적용하였다. 이 기법은 속도엔 영향을 끼치지 않고 결과가 우수한 교배기법을 판단하기 위해 교배교차점 간의 경쟁기법을 적용한다.

성능/효과

실험 결과, 기존 기법이 20번의 게임 횟수 중에 4IPD, 즉 4인이 참가하는 경우는 협동으로의 수렴율이 50%에도 못 미치는 9회에 불과했으며, 가장 높은 수렴율을 보인 2IPD게임의 경우에도 80%의 수렴율을 나타냈다. 그에 반해, 본 논문에서 제안한 기법을 활용한 경우, 모든 경우에서, 100%의 협동 수렴율을 나타냈다.
반복적 죄수의 딜레마 게임에서 협동 수렴율 및 수렴 시간을 단축하기 위해, 공진화 분야에서 많은 기법들이 연구되어 왔다. 본 논문에서는 죄수의 딜레마 게임에서 수렴시간(Convergence time)이 긴 순위기반 선택기법과 탐색효율이 낮은 1점 교배기법을 사용하는 대신, 토너먼트 선택기법(Tournament selection)과 자기적응형 교배기법(Self-adaptive crossover)을 적용함으로써 일반화 성능이 향상된다는 것을 실험 결과로서 확인하였다.
실험 결과, 기존 기법이 20번의 게임 횟수 중에 4IPD, 즉 4인이 참가하는 경우는 협동으로의 수렴율이 50%에도 못 미치는 9회에 불과했으며, 가장 높은 수렴율을 보인 2IPD게임의 경우에도 80%의 수렴율을 나타냈다. 그에 반해, 본 논문에서 제안한 기법을 활용한 경우, 모든 경우에서, 100%의 협동 수렴율을 나타냈다.
위 실험결과를 통해 논문의 제안 기법이 기본 기법에 비해, 성능 우위와 더불어 시간적 효율성 측면에서도 우수함을 확인할 수 있었다.
위의 실험(개체수 100, 교차율 0.3, 돌연변이율 0.001, 2점 교차방식)은 순위기반 선택방법과 토너먼트 방법으로 2IPD 게임을 진행한 것으로, 협동율을 나타내는 세로축의 pay-off값이 순위기반 선택에 비해 토너먼트 기법일 때 더욱 높은 값으로 수렴하고 있음을 확인할 수 있다 [2].
평균 수렴시간에서도 기존 기법에 비해 우수한 성능을 나타내었다. 총 1000세대 중에 기존기법은 130~230세대 정도의 평균수렴시간을 나타낸 반면, 제안 기법의 경우, 2인 게임이 액 49세대, 4인 게임이 58세대, 8인 게임이 약 24세대, 16인 게임이 약 19세대로 기본기법 대비 최소 10%에서 최대 43% 정도의 시간이 소모되었다.
평균 수렴시간에서도 기존 기법에 비해 우수한 성능을 나타내었다. 총 1000세대 중에 기존기법은 130~230세대 정도의 평균수렴시간을 나타낸 반면, 제안 기법의 경우, 2인 게임이 액 49세대, 4인 게임이 58세대, 8인 게임이 약 24세대, 16인 게임이 약 19세대로 기본기법 대비 최소 10%에서 최대 43% 정도의 시간이 소모되었다.
평균 협동 수렴율과 세대수(Generation)에 기초한 평균 수렴시간간의 직접적인 결과 값의 비교를 통해, 최적해로의 수렴율과 시간적 효율성 양쪽 측면에서 제안 기법이 기존 기법에 비해 훨씬 우수하였다.

후속연구

본 논문에서 제안한 기법은 보다 복잡하고 다각도로 변화하는 사회적, 경제적 현상들에 NIPD 모형을 적용함에 있어 유용한 역할을 할 수 있을 것이다. 또한 기존 연구의 경우, 실제 현실에 접목하기에는 일부 한계성을 안고있었으나, 본 연구를 통해 반복적 죄수의 딜레마 게임을 보다 현실적인 사회, 정치, 경제 현상들에 유용하게 접목시킬 수 있을 것으로 예상된다.
본 논문에서 제안한 기법은 보다 복잡하고 다각도로 변화하는 사회적, 경제적 현상들에 NIPD 모형을 적용함에 있어 유용한 역할을 할 수 있을 것이다. 또한 기존 연구의 경우, 실제 현실에 접목하기에는 일부 한계성을 안고있었으나, 본 연구를 통해 반복적 죄수의 딜레마 게임을 보다 현실적인 사회, 정치, 경제 현상들에 유용하게 접목시킬 수 있을 것으로 예상된다.

질의응답

핵심어	질문	논문에서 추출한 답변
	교배의 교차점(Crossover Point) 수는 어떤 매개변수인가?	교배의 교차점(Crossover Point) 수는 교배 기법을 결정 짓는 중요한 매개변수이다. 이 매개변수의 결정은 일반적으로 매개변수 조율에 의해 이루어지는데, 이는 시간과 노력을 소모하게 만들고 효율적이지 않다.
	순위기반 선택기법은 무엇인가?	순위기반 선택기법은 각 개체들의 적합도(최적해에 근접한 정도를 나타내는 값)의 순서에 맞춰서 순위를 매기는 기법이다. 개체수가 적을 경우에는 효과적일 수 있으나, 개체수가 많아질 경우, 매 세대(Generation)마다 일일이 모든 개체들의 순위를 매기는 데 걸리는 시간이 지나치게 커져 비효율적인 기법이다.
	매개변수의 결정은 일반적으로 매개변수 조율에 의해 이루어지는데, 이는 시간과 노력을 소모하게 만들고 효율적이지 않은 점을 개선하기 위해 무엇을 적용하였는가?	이 매개변수의 결정은 일반적으로 매개변수 조율에 의해 이루어지는데, 이는 시간과 노력을 소모하게 만들고 효율적이지 않다. 이 점을 개선하기 위해 본 논문에서는 자기 적응형 교배기법을 적용하였다. 이 기법은 속도엔 영향을 끼치지 않고 결과가 우수한 교배기법을 판단하기 위해 교배교차점 간의 경쟁기법을 적용한다.

원문 보기

ScienceON 원문보기

*원문 PDF 파일 및 링크정보가 존재하지 않을 경우 KISTI DDS 시스템에서 제공하는 원문복사서비스를 사용할 수 있습니다.

이 논문과 함께 이용한 콘텐츠

[논문] 퍼지 논리를 이용한 병렬 유전 알고리즘

저작권 관리 안내

내보내기 메뉴

내보내기 구분

파일저장
인쇄
메일전송

구성항목

기본정보
상세정보

관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관

저장형식

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

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

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

AI-Helper ※ AI-Helper는 을 사용합니다.

AI-Helper

안녕하세요, AI-Helper입니다. 좌측 "선택된 텍스트"에서 텍스트를 선택하여 요약, 번역, 용어설명을 실행하세요.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.

연합인증