Dynamic characteristics of a continuous optimization method based on fictitious play theory

作     者：Lee, Chang-Yong 

作者机构：Kongju Natl Univ Dept Ind & Syst Engn Cheonan 31080 South Korea 

出 版 物：《JOURNAL OF THE KOREAN PHYSICAL SOCIETY》 (韩国物理学会志)

年 卷 期：2017年第70卷第9期

页      面：880-890页

核心收录：

学科分类：07[理学] 0702[理学-物理学] 

基　　金：Korea Research Foundation - Korean Government (MOEHRD) [NRF-2015R1D1A3A01918708] 

主　　题：Continuous optimization algorithm Fictitious play theory Bayesian estimate 1/f noise Multifractal 

摘      要：In this paper, we propose a continuous optimization algorithm based on fictitious play theory and investigate the dynamic characteristics of the proposed algorithm. Fictitious play is a model for a learning rule in evolutionary game theory, and it can be used as an optimization method when all players have an identical utility function. In order to apply fictitious play to a continuous optimization algorithm, we consider two methods, equal width and equal frequency, of discretizing continuous values into a finite set of a player s strategies. The equal-frequency method turns out to outperform the equal-width method in terms of minimizing inseparable functions. To understand the mechanism of the equal-frequency method, we investigate two important quantities, the mixed strategy and the best response, in the algorithm from the statistical physics viewpoint. We find that the dynamics of the mixed strategies can be described as a 1/f noise. In addition, we adopt the set of best responses as the probability measure and find that the probability distribution of the set can be best characterized by a multifractal;moreover, the support of the measure has a fractal dimension. The dynamics of the proposed algorithm with equal-frequency discretization contains a complex and rich structure that can be related to the optimization mechanism.