가상 경기 이론에 기초한 연속형 최적화 알고리즘 = A Continuos Optimization Algorithm based on Fictitious Play Theory

국문 초록 (Abstract)

본 논문에서는 가상 경기 이론에 기초한 연속형 최적화 알고리즘을 제안하였다. 진화 게임 이론에 속하는 가상 경기는 각 경기자가 자신의 효용치를 최대로 하는 전략을 선택한다는 가정 하에서, 상대 경기자들이 가지고 있는 특성을 모두 알고 있지 않아도 반복적으로 경기를 수행하는 과정에서 상호 만족하는 상태로 수렴하도록 고안된 이론이다. 특히 모든 경기자가 동일한 효용치를 가질 때 가상 경기 이론은 최적화 모델에 적용될 수 있다는 점에 착안하여, 본 연구에서는 가상 경기에 기초한 연속형 최적화 모델을 제안하고 이 모델을 연속형 최적화 알고리즘으로 구현하였다. 제안한 알고리즘의 특성과 성능을 분석하기 위하여 분리 가능한 함수와 분리가 가능하지 않는 함수 등, 두 가지 유형의 벤치마킹 함수에 적용하여 실험을 수행하였다. 실험 결과를 통해 볼 때, 분리 가능한 함수의 경우에는 제안한 알고리즘이 경기자의 최상 전략을 비교적 용이하게 찾아가기 때문에 보다 효율적인 최적치를 구할 수 있었다. 분리가 가능하지 않는 함수의 경우에는 경기가 진행되는 과정에서 경기자가 선택한 전략에 변화가 있음을 알 수 있었으며, 최적화 성능은 벤치마킹 함수에 의존하였다.

다국어 초록 (Multilingual Abstract)

In this paper, we proposed a continuous optimization algorithm based on the fictitious play theory. As an evolutionary game theory, the fictitious play is a theory in which each player, under the assumption that each player selects a strategy maximizing his/her utility, can evolve into a mutually satisfactory state through a repeated play without having all information about opponents' characteristics. In particular, inspired by the fact that the fictitious play can be used a model for an optimization when all players have an identical utility, we proposed a model for a continuous optimization model and embodied the model as an algorithm. In order to analyze the characteristics and performance of the proposed algorithm, we applied the algorithm to the two types of benchmarking functions: separable and inseparable functions. From the experimental results, we can infer that, in the case of the separable functions, the proposed algorithm yields a better optimal solution because it can find a best strategy with relative ease. In the case of inseparable functions, on the contrary, the selected strategy of a player varied as a play proceeds and the performance of the optimization depended on the benchmarking functions.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 가상 경기 이론과 연속형 최적화 문제
• 3. 실험 결과 및 토론
• 4. 요약 및 결론
• 참고문헌

참고문헌 (Reference)

1 D. Fudenberg, "The Theory of Learning in Games" MIT Press 1998

2 D. Fogel, "System Identification through Simulated Evolution: A Machine Learning Approach to Modeling" Ginn 1991

3 I. Rezek, "On similarities between Inference in Game Theory and Machine Learning" 33 : 259-283, 2008

4 장치안, "Non-cooperative power control for wireless ad hoc networks with repeated games" Institute of Electrical and Electronics Engineers 25 (25): 1101-1112, 200708

5 J. Nash, "Non-Cooperative Games" 54 : 286-295, 1951

6 E-G. Talbi, "Metaheuristics: from design to implementation" Wiley 2009

7 D. Fudenberg, "Learning mixed equilibria" 5 : 320-367, 1993

8 G. Brown, "Iterative Solutions of Games by Fictitious Play, In Activity Analysis of Production and Allocation" Wiley 1951

9 D. Monderer, "Fictitious play property for games with identical interests" 68 : 258-265, 1996

10 A. Garcia, "Fictitious play for finding system optimal routings in dynamic traffic networks" 34 : 147-156, 2000

11 C. Lee, "Evolutionary programming using mutations based on the L´evy probability distribution" 8 : 1-13, 2004

12 J. Weibull, "Evolutionary Game Theory" The MIT Press 1998

13 D. Fogel, "Evolutionary Computation: Toward a New Philosophy of Machine Intelligence" IEEE Press 1995

14 J. Nash, "Equilibrium points in n-person games" 36 : 48-49, 1950

15 M. R. Garey, "Computers and Intractability: A Guide to the Theory of NP- Completeness" W. H. Freeman 1979

16 J. Schaffer, "A study of control parameters affecting online performance of genetic algorithms for function optimization" 51-60, 1989

17 T. Lambert, "A fictitious play approach to large-scale optimization" 53 : 477-489, 2005