[논문]입자군집최적화와 차분진화알고리즘 간의 공진화를 활용한 교섭게임 관찰

이상욱

doi:10.5392/jkca.2014.14.11.549

입자군집최적화와 차분진화알고리즘 간의 공진화를 활용한 교섭게임 관찰
Observation of Bargaining Game using Co-evolution between Particle Swarm Optimization and Differential Evolution 원문보기

한국콘텐츠학회논문지 = The Journal of the Korea Contents Association, v.14 no.11, 2014년, pp.549 - 557

초록
AI-Helper

근래에 게임이론 분야에서 진화계산법을 사용한 교섭게임 분석은 중요한 이슈 중에 하나이다. 본 논문에서는 이질적인 두 인공 에이전트 간의 공진화를 활용하여 교섭게임을 관찰한다. 두 인공 에이전트를 모델링하기 위해 사용된 전략은 진화전략의 종류인 입자군집최적화와 차분진화알고리즘이다. 교섭게임에서 각 전략이 최선의 결과를 얻기 위한 알고리즘 모수들을 조사하고 두 전략의 공진화를 관찰하여 어느 알고리즘이 교섭게임에 더 우수한지 관찰한다. 컴퓨터 시뮬레이션 실험 결과 입자군집최적화 전략이 차분진화알고리즘 전략보다 교섭게임에서 더 우수한 성능을 보임을 확인하였다.

Abstract ▼ AI-Helper

Recently, analysis of bargaining game using evolutionary computation is essential issues in field of game theory. In this paper, we observe a bargaining game using co-evolution between two heterogenous artificial agents. In oder to model two artificial agents, we use a particle swarm optimization and a differential evolution. We investigate algorithm parameters for the best performance and observe that which strategy is better in the bargaining game under the co-evolution between two heterogenous artificial agents. Experimental simulation results show that particle swarm optimization outperforms differential evolution in the bargaining game.

주제어

AI 본문요약
AI-Helper

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

문제 정의

관계망 중 가장 많이 사용하는 것은 난수 관계망(Random Topology), 원형 관계망(Circle Topology), 폰노이만 관계망(Von Neumann Topology)이다[17]. 본 논문에서는 난수, 원형, 폰노이면 관계망에 따른 LPSO를 각각 LPSOR, LPSOC, LPSOV라 명명하였다.
Seong[13][14]은 유전알고리즘과 입자군집최적화 기반의 두 이질적인 인공 에이전트 집단 간의 교섭게임을 연구하였으며, 공진화를 통한 경쟁에서 입자군집최적화가 유전알고리즘에 비해 더 우수함을 보였다. 본 논문에서는 입자군집 최적화와 함께 연속문제의 해결에 사용되는 진화계산기법 중에 하나인 차분진화알고리즘을 인공 에이전트 전략으로 소개하고 입자군집최적화와 공진화를 통한 교섭게임을 관찰하였다.
실세계의 교섭게임을 이해하기 위해서 인공 에이전트를 활용한 교섭게임의 관찰한 게임이론 분야의 중요한 이슈이다. 본 논문에서는 입자군집최적화와 차분진화알고리즘을 기반으로 한 인공에이전트들 간의 공진화를 통한 교섭게임을 관찰하였다. 실험의 공정성을 위해 각각의 인공 에이전트가 최적의 성능을 내는 알고리즘 변수 설정을 위한 실험을 먼저 진행하였다.
61Ghz 성능의 옥타코어 CPU와 16GB메모리, Visual studio 2010을 사용하였다. 최적의 환경에서 PSO-agent와 DE-agent의 공진화를 통한 교섭게임을 관찰하기 위해 다음과 같은 실험을 진행하였다.

제안 방법

경쟁자 집단의 해는 고정시킨 상태에서 최적의 DEagent를 위한 변수 F와 cf를 실험을 통해 알아보았다. [그림 8]에서 보는 바와 같이 변수에 대해 결과의 차이는 거의 없는 것으로 나타났다.
경쟁자 집단의 해는 고정시킨 상태에서 최적의 PSOagent를 위한 최대 속도값(Vmax)과 중간 변수(Φ)를 실험을 통해 알아보았다.
본 논문에서는 교섭게임 실험에 총 재화의 양을 10으로, 최대 단계는 4단계로 설정하였다. 교섭게임에서는 거래 첫 단계를 제안자로 시작하는지 응답자로 시작하는지가 매우 중요하므로 [그림 3]과 같이 2개의 열로 해를 표현하였다.
본 논문에서는 입자군집최적화와 차분진화알고리즘을 기반으로 한 인공에이전트들 간의 공진화를 통한 교섭게임을 관찰하였다. 실험의 공정성을 위해 각각의 인공 에이전트가 최적의 성능을 내는 알고리즘 변수 설정을 위한 실험을 먼저 진행하였다. 최적의 알고리즘 환경 하에서 두 인공 에이전트간의 공진화 실험결과 PSO 기반 에이전트는 거래 미성립의 위험을 감수하고 거래 성립시 많은 양의 재화를 얻는 전략으로 진화하고, DE 기반 에이전트는 소량의 재화를 획득하더라도 거래가 성사되는 전략으로 진화하였음을 알수 있었다.
두 인공 에이전트에 대한 변수 설정과 교섭게임의 최대 단계 및 최대 진화 세대 수를 설정한 다음, 두 인공 에이전트 해집단을 초기화 한다. 하나의 인공 에이전트에 대한 평가가 이루어진 후 평가결과를 바탕으로 진화하며, 그 후에 다른 하나의 인공 에이전트가 같은 과정을 수행한다. 해를 평가할 때는 경쟁 인공 에이전트 집단에서 교섭게임에 임할 상대 해를 선발한 후 [그림 1]과 같은 교섭게임을 제안자로 시작할 때와 응답자로 시작할 때로 실행하여 획득한 재화 값을 평균하여 적합도로 사용한다.

대상 데이터

실험에 사용한 해집단의 수는 20, 최대 세대 수는 10,000, 평가시 교섭게임에 임할 상대 해의 수는 전체 해집단 수와 동일한 20, 교섭게임의 최대 단계는 4단계로 설정하였다. 여기서 세대(Generation) 수란 진화계산 알고리즘이 평가 후 연산을 거처 자식해를 생성하거나 해를 업데이트 하는 과정의 반복 수를 뜻한다.

이론/모형

문헌 [14]에 의하면 여러 가지의 PSO버전 중에 토폴로지로 원형 관계망을 사용한 지역 입자군집최적화 (LPSOC)가 성능이 가장 우수함을 보였다. 이에 따라 본 논문에서도 LPSOC를 사용하여 PSO-agent를 모델링 하였다.

성능/효과

PSO-agent는 제안자의 입장일 때는 적은 양의 재화를 상대방에게 제시하며 응답자의 입장일 때는 많은 양의 재화를 상대방으로 바라는 것으로 나타났다. DE-agent는 PSO-agent와는 반대의 성향을 보였다.
특히 마지막 단계에서는 제안자가 0보다는 크지만 아주 적은 양의 재화만 제안 하더라도 응답자 입장에서는 거래를 거절하여 아무것도 얻지 못하는 것보다는 작은 양의 재화라도 획득하는 것이 최선의 선택이므로 제안을 수락할 수밖에 없는데, 이것을 내쉬균형 (Nash equilibriums)의 부분게임완전 균형 (Sub-game perfect equilibrium)이라 한다. 그러나 현실 사회의 사람을 대상으로 한 실험한 교섭게임의 결과는 비록 아무것도 획득하지 못할지라도 응답자가 적은 양의 재화를 제안 받는 경우, 제안을 거부하는 현상이 관찰되었다. 이로 인해 교섭게임에서 마지막 단계 일지라도 60∼80%의 경우, 제안자는 총 재화의 4∼5할 정도를 응답자에게 제안하였으며, 단지 3%의 경우만이 2할 이하의 재화를 상대방에게 제안하는 경향이 관찰되었다[7].
최적의 알고리즘 환경 하에서 두 인공 에이전트간의 공진화 실험결과 PSO 기반 에이전트는 거래 미성립의 위험을 감수하고 거래 성립시 많은 양의 재화를 얻는 전략으로 진화하고, DE 기반 에이전트는 소량의 재화를 획득하더라도 거래가 성사되는 전략으로 진화하였음을 알수 있었다. 이로 인해 PSO 기반 인공에이전트가 DE 기반 인공에이전트에 비해 항상 재화를 많이 얻는 것을 살펴볼 수 있었다. 향후 연구로 다양한 진화계산 기법들을 기반으로 한 인공 에이전트를 활용한 교섭게임을 관찰 할 계획이다.
실험의 공정성을 위해 각각의 인공 에이전트가 최적의 성능을 내는 알고리즘 변수 설정을 위한 실험을 먼저 진행하였다. 최적의 알고리즘 환경 하에서 두 인공 에이전트간의 공진화 실험결과 PSO 기반 에이전트는 거래 미성립의 위험을 감수하고 거래 성립시 많은 양의 재화를 얻는 전략으로 진화하고, DE 기반 에이전트는 소량의 재화를 획득하더라도 거래가 성사되는 전략으로 진화하였음을 알수 있었다. 이로 인해 PSO 기반 인공에이전트가 DE 기반 인공에이전트에 비해 항상 재화를 많이 얻는 것을 살펴볼 수 있었다.

후속연구

이로 인해 PSO 기반 인공에이전트가 DE 기반 인공에이전트에 비해 항상 재화를 많이 얻는 것을 살펴볼 수 있었다. 향후 연구로 다양한 진화계산 기법들을 기반으로 한 인공 에이전트를 활용한 교섭게임을 관찰 할 계획이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	게임이론이란?	게임이론이란 상충적인 조건에서 경쟁자간의 경쟁상태를 모형화하여 게임의 참여자 행동을 분석하여 최적의 전략을 수립하는 것을 연구하는 학문이다. 폰 노이만[1]에 의해 처음 게임이론이 소개되었을 때는 주로 군사학에 많이 적용되었으나, 근래에는 경제학, 경영학, 정치학, 심리학 분야 등에도 널리 적용되고 있다.
	교섭게임이론에서 가상의 인공 에이전트를 만들기 위해 어떠한 것들이 사용되어 왔는가?	초기에는 사람이 직접 실험에 참여한 결과를 바탕으로 분석이 이루어졌지만 근래에는 컴퓨터의 발전으로 인해 가상의 인공 에이전트(Artificial agent)를 만들어 컴퓨터 시뮬레이션 실험을 통해 교섭게임을 분석하려는 시도가 이루어지고 있다. 가상의 인공 에이전트를 생성하기 위하여 유전알고리즘[6], 진화전략[7], 유한 오토마타[8], 강화학습이론[9][10] 등이 사용되어 왔다.
	게임이론은 어느 분야에서 적용되고 있는가?	게임이론이란 상충적인 조건에서 경쟁자간의 경쟁상태를 모형화하여 게임의 참여자 행동을 분석하여 최적의 전략을 수립하는 것을 연구하는 학문이다. 폰 노이만[1]에 의해 처음 게임이론이 소개되었을 때는 주로 군사학에 많이 적용되었으나, 근래에는 경제학, 경영학, 정치학, 심리학 분야 등에도 널리 적용되고 있다. 게임 이론에 있어서 참여자가 취하는 행동을 전략이라고 하며, 어떤 전략을 선택했을 때, 게임의 결과로 참여자가 얻는 것을 이익이라고 한다.

참고문헌 (19)

John von Neumann and Oskar Morgenstern, Theory of games and economic behavior, Princeton University Press, 1944.
I. Stahl, Bargaining Theory, Stockholm, Stockholm School of Economics, 1971.
T. Omoto, K. Kobayashi, and M. Onishi, "Bargaining model of construction dispute resolution," IEEE International Conference on Systems, Man and Cybernetics, Vol.7, pp.7-12, 2002.
S. Berninghaus, W. Guth, R. Lechler, and H. J. Ramser, "Decentralized versus collective bargaining - An experimental study," International journal of game theory, Vol.7, No.3, pp.437-448, 2002.
M. Nakayama, "E-commerce and firm bargaining power shift in grocery marketing channels: A case of wholesalers' structured document exchanges," Journal of information technology(JIT), Vol.15, No.3, pp.195-210, 2000.

상세보기
S. Matwin, T. Szapiro, and K. Haigh, "Genetic algorithms approach to a negotiation support system," IEEE Trans. Systems, Man and Cybernetics, Vol.21, No.1, pp.102-114, 1991.

상세보기
K. M. Page, M. A. Nowak, and K. Sigmund, "The spatial ultimatum game," Proceedings, Biological sciences, Vol.267, No.1458, pp.2177-2182, 2000.

상세보기
D. D. B. Van Bragt and J. A. La Poutre, "Co-evolving automata negotiate with a variety of opponents," Proceedings of the 2002 Congress on Evolutionary Computation, Vol.2, pp.1426-1431, 2002.
Fang Zhong, Steven O. Kimbrough, and D. J. Wu, "Cooperative agent systems: artificial agents play the ultimatum game," Proceedings of the 35th Annual Hawaii International Conference on System Sciences, pp.2169-2177, 2002.
D. J. Cooper, Nick Feltovich, E. Alvin. Roth, and Rami Zwick, "Relative versus Absolute Speed of Adjustment in Strategic Environments; Responder Behavior in Ultimatum Games," Experimental economics, a journal of the Economic Science Association, Vol.6, No.2, pp.181-207, 2003.
S. C. Chang, J. I. Yun, J. S. Lee, S. U. Lee, N. P. Mahalik, and B. H. Ahn, "Analysis on the Parameters of the Evolving Artificial Agents in Sequential Bargaining Game," The special issue on Software Agent and its Applications, IEICE, Vol.E88-D, No.9, 2005.
장석철, 석상문, 윤정일, 윤정원, 안병하, "인공에이전트를 이용한 교섭게임에 관한 연구", 대한산업공학회지, 제32권, 제3호, pp.172-179, 2006.
M. H. Seong and S. Y. Lee, "A Bargaining game design using co-evolution analysis between artificial agents," Advanced Science and Technology Letters, Vol.46, pp.10-14, 2014.
M. H. Seong and S. Y. Lee, "A Bargaining game using artificial agents based on genetic algorithms and particle swarm optimization," International Journal of Software Engineering and Its Applications, Vol.8, No.5, pp.205-218, 2014.
J. Kennedy and R. C. Eberhart, "Particle swarm optimization," Proceedings of IEEE international conference on neural networks, pp.1942-1948, 1995.
M. Clerc and J. Kenney, "The particle swarm-explosion, stability, and convergence in a multidimensional complex space," IEEE Trans Evol Comput, Vol.6, pp.58-73, 2002.

상세보기
M. Clerc, Particle swarm optimization, ISTE, 2006.
J. Kennedy and R. Mendes, "Population structure and particle swarm performance," Proc 2002 Congress Evol Comput., Vol.2, pp.1671-1676, 2002.
R. Strorn and K. Price, "Differential evolution - a simple and efficient heuristic for global optimization over continuous spaces," Journal of Global Optimization, Vol.11, No.4, pp.341-359, 1997.

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

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

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	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

연합인증