Game Theory Based Co-evolutionary Algorithm (GCEA) for Solving Multiobjective Optimization Problems

Kwee-Bo SIM  Ji-Yoon KIM  Dong-Wook LEE  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E87-D   No.10   pp.2419-2425
Publication Date: 2004/10/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Artificial Intelligence and Cognitive Science
Keyword: 
multiobjective optimization problems (MOPs),  Pareto optimal set,  game theory,  evolutionary stable strategy (ESS),  co-evolutionary algorithm,  

Full Text: PDF(385.6KB)>>
Buy this Article




Summary: 
When we try to solve Multiobjective Optimization Problems (MOPs) using an evolutionary algorithm, the Pareto Genetic Algorithm (Pareto GA) introduced by Goldberg in 1989 has now become a sort of standard. After the first introduction, this approach was further developed and lead to many applications. All of these approaches are based on Pareto ranking and use the fitness sharing function to maintain diversity. On the other hand in the early 50's another scheme was presented by Nash. This approach introduced the notion of Nash Equilibrium and aimed at solving optimization problems having multiobjective functions that are originated from Game Theory and Economics. Since the concept of Nash Equilibrium as a solution of these problems was introduced, game theorists have attempted to formalize aspects of the equilibrium solution. The Nash Genetic Algorithm (Nash GA), which is introduced by Sefrioui, is the idea to bring together genetic algorithms and Nash strategy. The aim of this algorithm is to find the Nash Equilibrium of MOPs through the genetic process. Another central achievement of evolutionary game theory is the introduction of a method 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 in 1982. In this paper, we propose Game theory based Co-Evolutionary Algorithm (GCEA) and try to find the ESS as a solution of MOPs. By applying newly designed co-evolutionary algorithm to several MOPs, the first we will confirm that evolutionary game can be embodied by co-evolutionary algorithm and this co-evolutionary algorithm can find ESSs as a solutions of MOPs. The second, we show optimization performance of GCEA by applying this model to several test MOPs and comparing with the solutions of previously introduced evolutionary optimization algorithms.