게임 이론은 의사 결정 문제와 관련 된 연구와 함께 정립 된 수학적 분석법으로써 1928년 Von Neumann이 유한개의 순수전략이 존재하는 2인 영합게임은 결정적(deterministic)이라는 것을 증명함으로써 수학적 기반을 정립하였고 50년대 초, Nash는 Von Neumann의 이론을 일반화하는 개념을 제안함으로써 현대적 게임이론의 장을 열었다. 이후 진화 생물학 연구자들에 의해 고전적인 게임 이론의 가정에 해당하는 참가자들의 합리성(rationality) 대신 다윈 선택(Darwinian selection)에 의해 게임의 해를 탐색하는 것이 가능하다는 것이 밝혀지게 되었고 진화 생물학자 Maynard Smith에 의해 진화적 안정 전략(Evolutionary Stable Strategy: ESS)의 개념이 정립되면서 현대적 게임 이론으로써 진화적 게임 이론이 체계화 되었다. 한편 이와 같은 진화적 게임 이론에 관한 연구와 함께 생태계의 공진화를 이용한 컴퓨터 시뮬레이션이 1991년 Hillis에 의해 처음으로 시도되었으며 Kauffman은 다른 종들 간의 공진화적 동역학(dynamics)을 분석하기 위한 NK 모델을 제안하였다. Kauffman은 이 모델을 이용하여 공진화 현상이 어떻게 정적 상태(static state)에 이르며 이 상태들은 게임 이론에서 소개되어진 내쉬 균형이나 ESS에 해당한다는 것을 보여주었다. 이후, 몇몇 연구자들 게임 이론과 진화 알고리즘에 기반한 연산 모델들을 제시해 왔으나 실용적인 문제의 적용에 대한 연구는 아직 미흡한 편이다. 이에 본 논문에서는 게임 이론에 기반 한 공진화 알고리즘을(Game theory based Co-Evolutionary Algorithm: GCEA) 제안하고 이 알고리즘을 이용하여 공진화적인 문제들을 효과적으로 해결할 수 있음을 확인하는 것을 목표로 한다.
게임 이론은 의사 결정 문제와 관련 된 연구와 함께 정립 된 수학적 분석법으로써 1928년 Von Neumann이 유한개의 순수전략이 존재하는 2인 영합게임은 결정적(deterministic)이라는 것을 증명함으로써 수학적 기반을 정립하였고 50년대 초, Nash는 Von Neumann의 이론을 일반화하는 개념을 제안함으로써 현대적 게임이론의 장을 열었다. 이후 진화 생물학 연구자들에 의해 고전적인 게임 이론의 가정에 해당하는 참가자들의 합리성(rationality) 대신 다윈 선택(Darwinian selection)에 의해 게임의 해를 탐색하는 것이 가능하다는 것이 밝혀지게 되었고 진화 생물학자 Maynard Smith에 의해 진화적 안정 전략(Evolutionary Stable Strategy: ESS)의 개념이 정립되면서 현대적 게임 이론으로써 진화적 게임 이론이 체계화 되었다. 한편 이와 같은 진화적 게임 이론에 관한 연구와 함께 생태계의 공진화를 이용한 컴퓨터 시뮬레이션이 1991년 Hillis에 의해 처음으로 시도되었으며 Kauffman은 다른 종들 간의 공진화적 동역학(dynamics)을 분석하기 위한 NK 모델을 제안하였다. Kauffman은 이 모델을 이용하여 공진화 현상이 어떻게 정적 상태(static state)에 이르며 이 상태들은 게임 이론에서 소개되어진 내쉬 균형이나 ESS에 해당한다는 것을 보여주었다. 이후, 몇몇 연구자들 게임 이론과 진화 알고리즘에 기반한 연산 모델들을 제시해 왔으나 실용적인 문제의 적용에 대한 연구는 아직 미흡한 편이다. 이에 본 논문에서는 게임 이론에 기반 한 공진화 알고리즘을(Game theory based Co-Evolutionary Algorithm: GCEA) 제안하고 이 알고리즘을 이용하여 공진화적인 문제들을 효과적으로 해결할 수 있음을 확인하는 것을 목표로 한다.
Game theory is mathematical analysis developed to study involved in making decisions. In 1928, Von Neumann proved that every two-person, zero-sum game with finitely many pure strategies for each player is deterministic. As well, in the early 50's, Nash presented another concept as the basis for a ge...
Game theory is mathematical analysis developed to study involved in making decisions. In 1928, Von Neumann proved that every two-person, zero-sum game with finitely many pure strategies for each player is deterministic. As well, in the early 50's, Nash presented another concept as the basis for a generalization of Von Neumann's theorem. Another central achievement of game theory is the introduction of evolutionary game theory, by which agents can play optimal strategies in the absence of rationality. Not the rationality but through the process of Darwinian selection, a population of agents can evolve to an Evolutionary Stable Strategy (ESS) introduced by Maynard Smith. Keeping pace with these game theoretical studies, the first computer simulation of co-evolution was tried out by Hillis in 1991. Moreover, Kauffman proposed NK model to analyze co-evolutionary dynamics between different species. He showed how co-evolutionary phenomenon reaches static states and that these states are Nash equilibrium or ESS introduced in game theory. Since the studies about co-evolutionary phenomenon were started, however many other researchers have developed co-evolutionary algorithms, in this paper we propose Game theory based Co-Evolutionary Algorithm (GCEA) and confirm that this algorithm can be a solution of evolutionary problems by searching the ESS.To evaluate newly designed GCEA approach, we solve several test Multi-objective Optimization Problems (MOPs). From the results of these evaluations, we confirm that evolutionary game can be embodied by co-evolutionary algorithm and analyze optimization performance of GCEA by comparing experimental results using GCEA with the results using other evolutionary optimization algorithms.
Game theory is mathematical analysis developed to study involved in making decisions. In 1928, Von Neumann proved that every two-person, zero-sum game with finitely many pure strategies for each player is deterministic. As well, in the early 50's, Nash presented another concept as the basis for a generalization of Von Neumann's theorem. Another central achievement of game theory is the introduction of evolutionary game theory, by which agents can play optimal strategies in the absence of rationality. Not the rationality but through the process of Darwinian selection, a population of agents can evolve to an Evolutionary Stable Strategy (ESS) introduced by Maynard Smith. Keeping pace with these game theoretical studies, the first computer simulation of co-evolution was tried out by Hillis in 1991. Moreover, Kauffman proposed NK model to analyze co-evolutionary dynamics between different species. He showed how co-evolutionary phenomenon reaches static states and that these states are Nash equilibrium or ESS introduced in game theory. Since the studies about co-evolutionary phenomenon were started, however many other researchers have developed co-evolutionary algorithms, in this paper we propose Game theory based Co-Evolutionary Algorithm (GCEA) and confirm that this algorithm can be a solution of evolutionary problems by searching the ESS.To evaluate newly designed GCEA approach, we solve several test Multi-objective Optimization Problems (MOPs). From the results of these evaluations, we confirm that evolutionary game can be embodied by co-evolutionary algorithm and analyze optimization performance of GCEA by comparing experimental results using GCEA with the results using other evolutionary optimization algorithms.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
Goldberg[17]는 다목적 함수 최적화 문제의 표준적인 진화 알고리즘적 해법으로 인정받고 있는 Pareto Genetic Algorithm (Pareto GA)이라 불리는 파레토에 기반 한 적합도 할당 기법을 제안하였는데 이 알고리즘의 기본 아이 디어는 개체군 내의 비 지배적인 개체들에게 높은 선택확 률을 할당하는 것으로써 비지배적인 해의 순서에 따라 파레토 랭킹이라고 불리는 랭킹을 할당하고 이를 적합도로 할당하는 방식을 이용한다. Pareto GA가 소개되어진 후 여러 연구자들에 의하여 최적화 성능을 더욱 향상시키는 기법들[18][19]이 소개되어져 왔으나 본 논문에서는 GCEA를 이용하여 다목적 함수 최적화 문제의 해를 탐색하는 기법을 제안하고자 한다.
본 논문에서는 게임 이론의 간략한 몇 가지 개념의 간략한 소개와 더불어 생태계의 진화 메커니즘을 공학적으로 응용한 공진화 알고리즘에 대해 소개하고 이러한 두 연구 분야를 이어주는 차원에서 진행된 몇 가지 연구들을 소개하였다.
또 몇몇 다른 공진화 알고리즘 연구자들은 공진화적 현상을 게임이론의 관점에서 연구하였는데 그 중 Kauffman은 통계학적 모델인 NK 클래스에 기반 한 공진화를 소개하였다. 이 연구를 통하여 그는 공진 화하는 생태계가 어떻게 내쉬 균형이나 진화적 안정 전략과 같은 균형상태를 이루며 안정된 상태를 유지할 수 있는 지를 보여주었다[6].
앞서 밝힌 바와 같이 진화적 게임의 형태를 가지는 공진 화는 적정 세대가 지나면 안정된 균형 상태에 도달하고 이상태는 ‘지배 특성(dominance property)’ 관점에서 게임의 최적해에 해당하므로 수학적 관점에서 이러한 공진화는 게임 이론적인 특성과 다이나믹스를 가진다. 이러한 특성들로부터 공진화 알고리즘을 게임 행렬을 통하여 구성하고 진화적 게임의 형태를 가지는 문제들에 대한 해법으로 제시될 수 있음을 알 수 있는데 본 논문에서는 이러한 공진화 알고리즘의 개념에 진화적 게임 이론을 결합한 새로운 구조의 공진화 알고리즘인 ‘게임 이론에 기반 한 공진화 알고리즘(GCEA)’을 제안하고 여러 가지 난제를 포함한 최적화 문제에 적용하여 다른 진화 알고리즘의 최적화 결과와 성능을 비교 평가하는 것을 목표로 한다. 물론 제안된 알고리즘은 로봇의 제어기나 분산 로봇에서 환경의 변화에 따라 전략의 종류에 따른 로봇의 비율을 진화시킴으로써 전체 시스템의 효율을 높이는 데에도 적용 가능 할 것으로 생각되나 이는 차후 연구 주제로 남기고 본 논문에서는 ‘다목적 함수 최적화 문제 (Multi-objective Optimization Problems: MOPs)’의 풀이를 통한 최적화 성능을 평가한다.
이에 본 논문에서는 게임 이론과 공진화 알고리즘의 몇가지 주요한 개념들을 간략하게 소개하고 앞서 소개된 관점에서 새로이 구성된 ‘게임 이론에 기반 한 공진화 알고리즘(Game Theory based Co-evolutionary Algorithm: GCEA)’을 제안하고 이를 여러 가지 실험적 문제들에 적용하여 다른 진화 알고리즘의 적용결과들과 비교함으로써 본 논문에서 제안된 GCEA의 성능을 평가한다.
비협조적 게임의 해로써 내쉬 균형이 제안된 후 게임의 균형해를 찾는 연구가 활발해졌는데 이 중 Lewontin[3]은 진화 생물학의 분석에 게임이론을 도입하여 게임의 균형해를 찾고자 하였으나 그의 접근법은 기존의 게임과는 달리 각 종들이 환경을 상대로 게임을 하여 게임의 참가자가 소멸될 확률을 최소화 하는 전략을 찾는 것이었다. 또, Hamilton은 Maynard Smith 와 Price[4]에 의해 소개되어진 ‘진화적 안정 전략(Evolutionary Stable Strategy)’과 유사한 개념의 ‘Unbeatable Strategy’를 제안하였다.
제안 방법
또 이러한 관점에서 이 두 가지 분야를 결합하여 진화적인 접근법으로 해결하는 문제들의 새로운 해법으로써 진화적 게임 이론을 적용한 공진화 알고리즘인 GCEA를 제안하였다.
이러한 특성들로부터 공진화 알고리즘을 게임 행렬을 통하여 구성하고 진화적 게임의 형태를 가지는 문제들에 대한 해법으로 제시될 수 있음을 알 수 있는데 본 논문에서는 이러한 공진화 알고리즘의 개념에 진화적 게임 이론을 결합한 새로운 구조의 공진화 알고리즘인 ‘게임 이론에 기반 한 공진화 알고리즘(GCEA)’을 제안하고 여러 가지 난제를 포함한 최적화 문제에 적용하여 다른 진화 알고리즘의 최적화 결과와 성능을 비교 평가하는 것을 목표로 한다. 물론 제안된 알고리즘은 로봇의 제어기나 분산 로봇에서 환경의 변화에 따라 전략의 종류에 따른 로봇의 비율을 진화시킴으로써 전체 시스템의 효율을 높이는 데에도 적용 가능 할 것으로 생각되나 이는 차후 연구 주제로 남기고 본 논문에서는 ‘다목적 함수 최적화 문제 (Multi-objective Optimization Problems: MOPs)’의 풀이를 통한 최적화 성능을 평가한다. 공학자들이 접하는 실세계 최적화 문제의 대부분은 서로 경합하는 두개 이상의 목적함수를 동시에 최적화해야 하는 문제를 포함하게 되는데 하나의 목적함수를 가진 ‘단목적 함수 최적화 문제(Single-objective Optimization Problems: SOPs)’의 경우에는 명확한 최적해가 존재하지만 다목적 함수의 최적화 문제의 경우는 그렇지가 않다.
앞서 소개한 바와 같이 기존의 다목적 함수 최적화 문제 풀이법들은 매우 다양하게 연구되어 왔고 실제적인 문제에도 성공적으로 적용되어왔음에도 불구하고 각 알고리즘의 성능 이나 특징들을 구별지어주기에 적합한 평가 방법에 대한 연구는 부족한 실정이었으나 Deb[23]와 Zitzler[24]에 의해 진화 알고리즘에서 해결하기 어려운 문제에 대한 성능 평가를 위한 함수들이 제시되었다. 이에 본 논문에서도 Zitzler의 논문에서 제시되어진 6개의 테스트용 다목적함수 최적화 문제를 이용하여 성능을 평가하였다.
이러한 경쟁적 공진화와는 달리 한편으로 Potter, De Jong 그리고 Grefenstette와 같은 연구자들에 의해 협조적 공진화에 대한 연구도 진행되었는데 그들에 의해 제안된 협조적 공진화 알고리즘(Cooperative Co-evolutionary Algorithm)[9]은 유전적으로 독립된 각 개체군들을 대표하는 개체를 선택하고 이를 하나의 개체로 결합하여 상위 레벨의 일을 수행하기에 유리한 개체로써 평가 받을 수 있는 개체(agent)를 생성한다. 이처럼 생태계의 개체군 사이의 진화에 대한 연구로부터 시작된 공진화 알고리즘은 지금까지 학계에 많은 응용 알고리즘과 적용 사례들이 보고되어 왔으나 본 논문에서는 게임 이론과의 유사성에 착안하여 고안 한 ‘게임 이론에 기반 한 공진화 알고리즘(Game Theory based Co-evolutionary Algorithm: GCEA)’을 제안한다.
최근 몇 년 동안 Tic-Tac-Toe (TTT) 게임[20]이나 디지털 생태계의 적응[21]이나 경쟁적인 환경 속에서 인공적인 유기체의 구현[22]과 같은 문제를 풀기위하여 게임 이론에 기반 한 공진화적인 해법에 관한 연구들이 수행되어 왔으나본 논문에서는 MOPs를 풀기위한 GCEA의 제안과 성능 평가를 다룬다. 다목적 함수의 최소화 문제를 생각 할 경우 ?, ? 두 개의 결정 변수를 가지고 두 개의 목적 함수 ? ? ?,
대상 데이터
여기서 ? , ? ? ? 이다.
이론/모형
다음의 그림들은 Zitzler의 논문에 소개된 진화 알고리즘 들과 GCEA를 이용하여 최적화 된 MOP들의 해를 나타내고 있다. GCEA를 이용하여 최적화 된 해를 Zitzler의 논문[24] 에서 8개의 진화 알고리즘을 이용하여 최적화 된 실험 결과와 비교하여 GCEA의 성능을 평가하였는데 Zitzler가 실험한 8개의 진화 알고리즘은 다음과 같다.
성능/효과
GCEA를 이용하여 최적화 한 경우의 결과가 NSGA를 사용 하여 개체수 500에 엘리티즘을 적용하여 1000세대 동안 최적화 한 결과보다는 못하지만 나머지 경우보다는 비교적 우수한 해를 찾는 것을 알 수 있는데 이는 적은 개체수와 짧은 세대수 동안 다른 유전적 기법을 필요로 하지 않고도 더 최적화 된 해를 찾아 낼 수 있다는 것을 의미한다.
구별 해내지 못하는 것을 볼 수 있는데 Zitzler는 그의 논문 에서 이 함수의 해탐색에 있어서의 난점을 지적하면서 증가된 개체군 크기와 엘리티즘을 이용하여 이러한 문제를 해결 하고자 하였다. 그러나 본 논문에서 제안하는 GCEA의 경우 이러한 부가적인 기법이 없이 단지 개체군 크기만 증가시키는 방법으로도 최적해 탐색 성능을 향상시킬 수 있다. 그림 14는 Zitzler의 논문에서 이처럼 개체수를 늘리고 엘리티즘을 적용해 가면서 NSGA를 이용하여 ? 평가 함수의 최적해를
또한 이렇게 제안된 GCEA의 최적화 성능을 평가하기 위하여 다목적 함수 최적화 문제를 사용하였는데 실험 결과를 통하여 비록 ESS는 수학과 경제학 분야와 관련된 진화적 게임 문제들의 균형해로 간주되고 있으나 GCEA를 이용하여 다목적 함수 최적화 문제의 해를 탐색하는 방법으로도 이용 될수 있음을 확인하였다. 따라서 본 논문에서 제안된 GCEA는 차후 상충하는 여러 개의 목적함수를 가진 환경에서 최적의 전략을 결정하는 에이전트들의 제어기 설계에도 적용이 가능할 것으로 보이며 향후 GCEA를 이용한 에이전트의 제어기 설계를 연구를 수행할 예정이다.
후속연구
또한 이렇게 제안된 GCEA의 최적화 성능을 평가하기 위하여 다목적 함수 최적화 문제를 사용하였는데 실험 결과를 통하여 비록 ESS는 수학과 경제학 분야와 관련된 진화적 게임 문제들의 균형해로 간주되고 있으나 GCEA를 이용하여 다목적 함수 최적화 문제의 해를 탐색하는 방법으로도 이용 될수 있음을 확인하였다. 따라서 본 논문에서 제안된 GCEA는 차후 상충하는 여러 개의 목적함수를 가진 환경에서 최적의 전략을 결정하는 에이전트들의 제어기 설계에도 적용이 가능할 것으로 보이며 향후 GCEA를 이용한 에이전트의 제어기 설계를 연구를 수행할 예정이다.
질의응답
핵심어
질문
논문에서 추출한 답변
내쉬 균형이란?
1952년, Nash는 비협조적 게임의 해를 찾기 위해 유한한 수의 순수전략을 가진 모든 2인 영합 혹은 비영합 게임은 적어도 하나 이상의 내쉬 균형이라 불리는 균형쌍을 가진다는 게임 이론의 새로운 개념을 제안하였으며 이를 수학적으로 증명하였다. 또 그의 증명에 의하면 게임의 각 참가자들은 자신의 전략집합과 목적함수를 가지고 있으며 게임을 하는 동안 상대 참가자의 전략이 고정된 상태에서 자신의 보상값을 최적화하는 전략을 선택하는 방식으로 번갈아 게임을 수행 할 경우 모든 참가자가 자신의 보상값을 더 이상 향상시킬 수 있는 전략을 찾지 못하는 상태에 이르게 되는데 이러한 상태를 내쉬 균형이라고 불리는 이러한 균형 상태를 비협 조적 게임의 해로 제시하였다.
게임 이론이란?
게임 이론은 의사 결정 문제와 관련 된 연구와 함께 정립 된 수학적 분석법으로써 1928년 Von Neumann이 유한개의 순수전략이 존재하는 2인 영합게임은 결정적(deterministic)이라는 것을 증명함으로써 수학적 기반을 정립하였고 50년대 초, Nash는 Von Neumann의 이론을 일반화하는 개념을 제안함으로써 현대적 게임이론의 장을 열었다. 이후 진화 생물학 연구자들에 의해 고전적인 게임 이론의 가정에 해당하는 참가자들의 합리성(rationality) 대신 다윈 선택(Darwinian selection)에 의해 게임의 해를 탐색하는 것이 가능하다는 것이 밝혀지게 되었고 진화 생물학자 Maynard Smith에 의해 진화적 안정 전략(Evolutionary Stable Strategy: ESS)의 개념이 정립되면서 현대적 게임 이론으로써 진화적 게임 이론이 체계화 되었다.
공진화 GA에서 유전적 장점의 혼합을 꾀한 방법은 무엇인가?
또 1994년에는 Paredis[8]가 공진화 GA(Co-evolutionary Genetic Algorithms: CGAs)을 제안 하였는데 이것은 전형적인 유전자 알고리즘의 all-at-once fitness evaluation과는 달리 부분적이면서도 연속적인 적합도 평가를 이용한다. 상호 작용 하는 다수의 하위 개체군들은 섬 모델(island model)이라 불리는 공진화하는 niche들을 탐색할 수 있도록 설계하였 으며 각 개체들은 하나의 하위 개체군으로부터 다른 하위 개체군으로 이주하는 것을 허용함으로써 유전적 장점의 혼합을 꾀하였다. 이러한 경쟁적 공진화와는 달리 한편으로 Potter, De Jong 그리고 Grefenstette와 같은 연구자들에 의해 협조적 공진화에 대한 연구도 진행되었는데 그들에 의해 제안된 협조적 공진화 알고리즘(Cooperative Co-evolutionary Algorithm)[9]은 유전적으로 독립된 각 개체군들을 대표하는 개체를 선택하고 이를 하나의 개체로 결합하여 상위 레벨의 일을 수행하기에 유리한 개체로써 평가 받을 수 있는 개체(agent)를 생성한다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.