关键词: 纳什均衡, 多极值, Memetic 算法, 几何变换

Abstract:

Concerning the premature convergence problem of particle swarm optimization (PSO) and the shortage of finding only one minimum, we propose a geometrictransform based Memetic algorithm (MA) for detecting multiminima, which is applied in Nash Equilibria (NE) computing in game theory. The basic MA consists of PSO and Tabu Search (TS), which improves PSO in two ways: loosing constraint on particle movements and incorporating the genetic algorithm (GA) to maintain particle diversity. TS iterates through the neighborhood to get a local optimum. Furthermore, the deflectionrepulsion geometric transformation is incorporated to tune the search for multi minima. The performance is evaluated on a series of NE detecting examples. The results show that the proposed MA has a notable ability to detect multi minima while yielding high accuracy and performance.

Key words: Nash Equilibrium;multi minima;Memetic algorithm (MA);geometric transformation