1__author__ = ('Julian Togelius, julian@idsia.ch',
2              'Justin S Bayer, bayer.justin@googlemail.com')
3
4import scipy
5import logging
6
7from pybrain.optimization.optimizer import ContinuousOptimizer
8
9
10def fullyConnected(lst):
11    return dict((i, lst) for i in lst)
12
13def ring(lst):
14    leftist = lst[1:] + lst[0:1]
15    rightist = lst[-1:] + lst[:-1]
16    return dict((i, (j, k)) for i, j, k in zip(lst, leftist, rightist))
17
18# TODO: implement some better neighborhoods
19
20
21class ParticleSwarmOptimizer(ContinuousOptimizer):
22    """ Particle Swarm Optimization
23
24    `size` determines the number of particles.
25
26    `boundaries` should be a list of (min, max) pairs with the length of the
27    dimensionality of the vector to be optimized (default: +-10). Particles will be
28    initialized with a position drawn uniformly in that interval.
29
30    `memory` indicates how much the velocity of a particle is affected by
31    its previous best position.
32
33    `sociality` indicates how much the velocity of a particle is affected by
34    its neighbours best position.
35
36    `inertia` is a damping factor.
37    """
38
39    size = 20
40    boundaries = None
41
42    memory = 2.0
43    sociality = 2.0
44    inertia = 0.9
45
46    neighbourfunction = None
47
48    mustMaximize = True
49
50    def _setInitEvaluable(self, evaluable):
51        if evaluable is not None:
52            logging.warning("Initial point provided was ignored.")
53        ContinuousOptimizer._setInitEvaluable(self, evaluable)
54
55    def _additionalInit(self):
56        self.dim = self.numParameters
57        if self.neighbourfunction is None:
58            self.neighbourfunction = fullyConnected
59
60        if self.boundaries is None:
61            maxs = scipy.array([10] * self.dim)
62            mins = scipy.array([-10] * self.dim)
63        else:
64            mins = scipy.array([min_ for min_, max_ in self.boundaries])
65            maxs = scipy.array([max_ for min_, max_ in self.boundaries])
66
67        self.particles = []
68        for _ in range(self.size):
69            startingPosition = scipy.random.random(self.dim)
70            startingPosition *= (maxs - mins)
71            startingPosition += mins
72            self.particles.append(Particle(startingPosition, self.minimize))
73
74        # Global neighborhood
75        self.neighbours = self.neighbourfunction(self.particles)
76
77    def best(self, particlelist):
78        """Return the particle with the best fitness from a list of particles.
79        """
80        picker = min if self.minimize else max
81        return picker(particlelist, key=lambda p: p.fitness)
82
83    def _learnStep(self):
84        for particle in self.particles:
85            particle.fitness = self._oneEvaluation(particle.position.copy())
86
87        for particle in self.particles:
88            bestPosition = self.best(self.neighbours[particle]).position
89            diff_social = self.sociality \
90                          * scipy.random.random() \
91                          * (bestPosition - particle.position)
92
93            diff_memory = self.memory \
94                          * scipy.random.random() \
95                          * (particle.bestPosition - particle.position)
96
97            particle.velocity *= self.inertia
98            particle.velocity += diff_memory + diff_social
99            particle.move()
100
101    @property
102    def batchSize(self):
103        return self.size
104
105
106class Particle(object):
107    def __init__(self, start, minimize):
108        """Initialize a Particle at the given start vector."""
109        self.minimize = minimize
110        self.dim = scipy.size(start)
111        self.position = start
112        self.velocity = scipy.zeros(scipy.size(start))
113        self.bestPosition = scipy.zeros(scipy.size(start))
114        self._fitness = None
115        if self.minimize:
116            self.bestFitness = scipy.inf
117        else:
118            self.bestFitness = -scipy.inf
119
120    def _setFitness(self, value):
121        self._fitness = value
122        if ((self.minimize and value < self.bestFitness)
123            or (not self.minimize and value > self.bestFitness)):
124            self.bestFitness = value
125            self.bestPosition = self.position.copy()
126
127    def _getFitness(self):
128        return self._fitness
129
130    fitness = property(_getFitness, _setFitness)
131
132    def move(self):
133        self.position += self.velocity
134
135