An Evolutionary Game-Theoretical Approach to Particle Swarm Optimisation
This work merges ideas from two very different areas: Particle Swarm Optimisation and Evolutionary Game Theory. In particular, we are looking to integrate strategies from the Prisoner Dilemma, namely cooperate and defect, into the Particle Swarm Optimisat
- PDF / 407,260 Bytes
- 10 Pages / 430 x 660 pts Page_size
- 42 Downloads / 249 Views
2
Department of Computer Science, University of Essex, UK [email protected] Dipartimento di Sistemi e Istituzioni per l’Economia, University of L’Aquila, Italy [email protected] 3 Department of Animal Production, Epidemiology and Ecology and Molecular Biotechnology Center, University of Torino, Italy [email protected]
Abstract. This work merges ideas from two very different areas: Particle Swarm Optimisation and Evolutionary Game Theory. In particular, we are looking to integrate strategies from the Prisoner Dilemma, namely cooperate and defect, into the Particle Swarm Optimisation algorithm. These strategies represent different methods to evaluate each particle’s next position. At each iteration, a particle chooses to use one or the other strategy according to the outcome at the previous iteration (variation in its fitness). We compare some variations of the newly introduced algorithm with the standard Particle Swarm Optimiser on five benchmark problems.
1
Introduction
Particle Swarm Optimisation (PSO) is a method for optimisation of continuous nonlinear functions, discovered through the simulation of a simplified social model (particle swarm) [1,2]. PSO has its roots in two main methodologies: artificial life (in particular flocking, schooling and swarming theory), and evolutionary computation. PSOs use a population of interacting particles (i.e., candidate solutions) that “fly” over the landscape searching for the optimum. Each particle is placed in the parameter space of some problem and evaluates its fitness at the current location. It then determines its movement through the space by combining some aspect of the history of its own fitness values with those of one or more other members of the swarm. Finally, the particle moves through the parameter space with a velocity determined by the locations and processed fitness values of those other members, possibly together with some random perturbations. More formally, the update equations for force, velocity and position of a particle i are as follows: φ2 R2 (xpi − xi ) fi = φ1 R1 (xsi − xi ) + social component individual component M. Giacobini et al. (Eds.): EvoWorkshops 2008, LNCS 4974, pp. 575–584, 2008. c Springer-Verlag Berlin Heidelberg 2008
(1)
576
C. Di Chio, P. Di Chio, and M. Giacobini
vi (t) = vi (t − 1) + fi
xi (t) = xi (t − 1) + vi
where xi is the current particle’s position, vi is the particle’s velocity, xsi is the swarm’s best position, xpi is the particle’s best position, and with φ1 = φ2 = 2.05. The next iteration takes place after all particles have been moved. Eventually the swarm as a whole is likely to move close to the best location. As with many other search heuristics, PSO has also been used in the context of game theory. Amongst others, Franken and Engelbrecht [3] employed coevolutionary particle swarm optimisation for the generation of feature evaluation scores for the Seega game. Closer to Evolutionary Game Thoery (EGT), Abdelba and co-authors [4] investigated the application of co-evolutionary training techniques
Data Loading...
