« back to all changes in this revision
Viewing changes to eap/toolbox.py
- browse files at revision 1
- compare with another revision
- download diff
- download tarball
- view history from revision 1
- Committer: Bazaar Package Importer
- Author(s): Miriam Ruiz
- Date: 2010-12-09 23:05:47 UTC
- Revision ID: james.westby@ubuntu.com-20101209230547-mrs9lngok0sx6318
Tags: upstream-0.6
Import upstream version 0.6
- files added:
- doc
- doc/_images
- doc/_templates
- eap
- eap/tests
- examples
added
removed
eap/toolbox.py
1
# This file is part of EAP.
2
#
3
# EAP is free software: you can redistribute it and/or modify
4
# it under the terms of the GNU Lesser General Public License as
5
# published by the Free Software Foundation, either version 3 of
6
# the License, or (at your option) any later version.
7
#
8
# EAP is distributed in the hope that it will be useful,
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11
# GNU Lesser General Public License for more details.
12
#
13
# You should have received a copy of the GNU Lesser General Public
14
# License along with EAP. If not, see <http://www.gnu.org/licenses/>.
15
16
"""The :mod:`toolbox` module is intended to contain the operators that you need
17
in your evolutionary algorithms, from initialisation to evaluation. It is
18
always possible to use directly the operators from this module but the toolbox
19
does also contain the default values of the different parameters for each
20
method. More over, it makes your algorithms easier to understand and modify,
21
since once an oprerator is set, it can be reused with a simple keyword that
22
contains all its arguments. Plus, every keyword or argument can be overriden
23
at all time.
24
25
The toolbox is also used in predefined algorithms from the
26
:mod:`~eap.algorithms` module.
27
"""
28
29
import copy
30
import functools
31
import inspect
32
import math
33
import random
34
# Needed by Nondominated sorting
35
from itertools import chain, cycle
36
from operator import attrgetter
37
38
39
class Repeat(object):
40
"""Functional object that repeat a function *func*
41
a number of times *times*, then raise a StopIteration
42
exception. It implements the Python iterator model.
43
44
This class allows to fill a list with objects produced
45
by a function.
46
"""
47
def __init__(self, func, times):
48
self.func = func
49
self.count = cycle(xrange(times+1))
50
self.times = times
51
52
def __iter__(self):
53
return self
54
55
def next(self):
56
"""Function use to iterate."""
57
if self.count.next() == self.times:
58
raise StopIteration
59
return self.func()
60
61
class Iterate(object):
62
"""Class use to cycle on the iterable object
63
returned by a function *func*. The function is
64
called when there is no longer any possible
65
iteration that can be done on the object.
66
"""
67
def __init__(self, func):
68
self.func = func
69
self.iter = None
70
71
def __iter__(self):
72
return self
73
74
def next(self):
75
"""Function use to iterate."""
76
try:
77
return self.iter.next()
78
except StopIteration:
79
self.iter = iter(self.func())
80
raise StopIteration
81
except AttributeError:
82
self.iter = iter(self.func())
83
return self.iter.next()
84
85
class FuncCycle(object):
86
"""Functionnal object use to cycle and call a
87
list of functions.
88
"""
89
def __init__(self, seq_func):
90
self.cycle = cycle(func for func in seq_func)
91
def __call__(self):
92
return self.cycle.next()()
93
94
class Toolbox(object):
95
"""A toolbox for evolution that contains the evolutionary operators.
96
At first the toolbox contains two simple methods. The first method
97
:meth:`~eap.toolbox.clone` duplicates any element it is passed as
98
argument, this method defaults to the :func:`copy.deepcopy` function.
99
The second method :meth:`~eap.toolbox.map` applies the function given
100
as first argument to every items of the iterables given as next
101
arguments, this method defaults to the :func:`map` function. You may
102
populate the toolbox with any other function by using the
103
:meth:`~eap.toolbox.register` method.
104
"""
105
106
def __init__(self):
107
self.register("clone", copy.deepcopy)
108
self.register("map", map)
109
110
def register(self, methodname, method, *args, **kargs):
111
"""Register a *method* in the toolbox under the name *methodname*. You
112
may provide default arguments that will be passed automaticaly when
113
calling the registered method.
114
115
Keyworded arguments *content_init* and *size_init* may be used to
116
simulate iterable initializers. For example, when building objects
117
deriving from :class:`list`, the content argument will provide to
118
the built list its initial content. Depending on what is given to
119
*content_init* and *size_init* the initialization is different. If
120
*content_init* is an iterable, then the iterable is consumed enterily
121
to intialize each object, in that case *size_init* is not used.
122
Otherwise, *content_init* may be a simple function that will be
123
repeated *size_init* times in order to fill the object.
124
"""
125
if "content_init" in kargs:
126
content = kargs["content_init"]
127
del kargs["content_init"]
128
if hasattr(content, "__iter__"):
129
content = FuncCycle(content)
130
if "size_init" in kargs:
131
args = list(args)
132
args.append(Repeat(content, kargs["size_init"]))
133
del kargs["size_init"]
134
else:
135
args = list(args)
136
args.append(Iterate(content))
137
pfunc = functools.partial(method, *args, **kargs)
138
pfunc.__name__ = method
139
setattr(self, methodname, pfunc)
140
141
def unregister(self, methodname):
142
"""Unregister *methodname* from the toolbox."""
143
delattr(self, methodname)
144
145
def decorate(self, methodname, *decorators):
146
"""Decorate *methodname* with the specified *decorators*, *methodname*
147
has to be a registered function in the current toolbox. Decorate uses
148
the signature preserving decoration function
149
:func:`~eap.toolbox.decorate`.
150
"""
151
partial_func = getattr(self, methodname)
152
method = partial_func.func
153
args = partial_func.args
154
kargs = partial_func.keywords
155
for decorator in decorators:
156
method = decorate(decorator)(method)
157
setattr(self, methodname, functools.partial(method, *args, **kargs))
158
159
######################################
160
# GA Crossovers #
161
######################################
162
163
def cxTwoPoints(ind1, ind2):
164
"""Execute a two points crossover on the input individuals. The two
165
individuals are modified in place. This operation apply on an individual
166
composed of a list of attributes and act as follow ::
167
168
>>> ind1 = [A(1), ..., A(i), ..., A(j), ..., A(m)]
169
>>> ind2 = [B(1), ..., B(i), ..., B(j), ..., B(k)]
170
>>> # Crossover with mating points 1 < i < j <= min(m, k) + 1
171
>>> cxTwoPoints(ind1, ind2)
172
>>> print ind1, len(ind1)
173
[A(1), ..., B(i), ..., B(j-1), A(j), ..., A(m)], m
174
>>> print ind2, len(ind2)
175
[B(1), ..., A(i), ..., A(j-1), B(j), ..., B(k)], k
176
177
This function use the :func:`~random.randint` function from the python base
178
:mod:`random` module.
179
"""
180
size = min(len(ind1), len(ind2))
181
cxpoint1 = random.randint(1, size)
182
cxpoint2 = random.randint(1, size - 1)
183
if cxpoint2 >= cxpoint1:
184
cxpoint2 += 1
185
else: # Swap the two cx points
186
cxpoint1, cxpoint2 = cxpoint2, cxpoint1
187
188
ind1[cxpoint1:cxpoint2], ind2[cxpoint1:cxpoint2] \
189
= ind2[cxpoint1:cxpoint2], ind1[cxpoint1:cxpoint2]
190
191
return ind1, ind2
192
193
def cxOnePoint(ind1, ind2):
194
"""Execute a one point crossover on the input individuals.
195
The two individuals are modified in place. This operation apply on an
196
individual composed of a list of attributes
197
and act as follow ::
198
199
>>> ind1 = [A(1), ..., A(n), ..., A(m)]
200
>>> ind2 = [B(1), ..., B(n), ..., B(k)]
201
>>> # Crossover with mating point i, 1 < i <= min(m, k)
202
>>> cxOnePoint(ind1, ind2)
203
>>> print ind1, len(ind1)
204
[A(1), ..., B(i), ..., B(k)], k
205
>>> print ind2, len(ind2)
206
[B(1), ..., A(i), ..., A(m)], m
207
208
This function use the :func:`~random.randint` function from the
209
python base :mod:`random` module.
210
"""
211
size = min(len(ind1), len(ind2))
212
cxpoint = random.randint(1, size - 1)
213
ind1[cxpoint:], ind2[cxpoint:] = ind2[cxpoint:], ind1[cxpoint:]
214
215
return ind1, ind2
216
217
def cxUniform(ind1, ind2, indpb):
218
"""Execute a uniform crossover that modify in place the two individuals.
219
The genes are swapped according to the *indpb* probability.
220
221
This function use the :func:`~random.random` function from the python base
222
:mod:`random` module.
223
"""
224
size = min(len(ind1), len(ind2))
225
for i in xrange(size):
226
if random.random() < indpb:
227
ind1[i], ind2[i] = ind2[i], ind1[i]
228
229
return ind1, ind2
230
231
def cxPartialyMatched(ind1, ind2):
232
"""Execute a partialy matched crossover (PMX) on the input indviduals.
233
The two individuals are modified in place. This crossover expect iterable
234
individuals of indices, the result for any other type of individuals is
235
unpredictable.
236
237
Moreover, this crossover consists of generating two children by matching
238
pairs of values in a certain range of the two parents and swaping the values
239
of those indexes. For more details see Goldberg and Lingel, "Alleles,
240
loci, and the traveling salesman problem", 1985.
241
242
For example, the following parents will produce the two following children
243
when mated with crossover points ``a = 2`` and ``b = 4``. ::
244
245
>>> ind1 = [0, 1, 2, 3, 4]
246
>>> ind2 = [1, 2, 3, 4, 0]
247
>>> cxPartialyMatched(ind1, ind2)
248
>>> print ind1
249
[0, 2, 3, 1, 4]
250
>>> print ind2
251
[2, 3, 1, 4, 0]
252
253
This function use the :func:`~random.randint` function from the python base
254
:mod:`random` module.
255
"""
256
size = min(len(ind1), len(ind2))
257
p1, p2 = [0]*size, [0]*size
258
259
# Initialize the position of each indices in the individuals
260
for i in xrange(size):
261
p1[ind1[i]] = i
262
p2[ind2[i]] = i
263
# Choose crossover points
264
cxpoint1 = random.randint(0, size)
265
cxpoint2 = random.randint(0, size - 1)
266
if cxpoint2 >= cxpoint1:
267
cxpoint2 += 1
268
else: # Swap the two cx points
269
cxpoint1, cxpoint2 = cxpoint2, cxpoint1
270
271
# Apply crossover between cx points
272
for i in xrange(cxpoint1, cxpoint2):
273
# Keep track of the selected values
274
temp1 = ind1[i]
275
temp2 = ind2[i]
276
# Swap the matched value
277
ind1[i], ind1[p1[temp2]] = temp2, temp1
278
ind2[i], ind2[p2[temp1]] = temp1, temp2
279
# Position bookkeeping
280
p1[temp1], p1[temp2] = p1[temp2], p1[temp1]
281
p2[temp1], p2[temp2] = p2[temp2], p2[temp1]
282
283
return ind1, ind2
284
285
def cxUniformPartialyMatched(ind1, ind2, indpb):
286
"""Execute a uniform partialy matched crossover (UPMX) on the input
287
indviduals. The two individuals are modified in place. This crossover
288
expect iterable individuals of indices, the result for any other type of
289
individuals is unpredictable.
290
291
Moreover, this crossover consists of generating two children by matching
292
pairs of values chosen at random with a probability of *indpb* in the two
293
parents and swaping the values of those indexes. For more details see
294
Cicirello and Smith, "Modeling GA performance for control parameter
295
optimization", 2000.
296
297
For example, the following parents will produce the two following children
298
when mated with the chosen points ``[0, 1, 0, 0, 1]``. ::
299
300
>>> ind1 = [0, 1, 2, 3, 4]
301
>>> ind2 = [1, 2, 3, 4, 0]
302
>>> cxUniformPartialyMatched(ind1, ind2)
303
>>> print ind1
304
[4, 2, 1, 3, 0]
305
>>> print ind2
306
[2, 1, 3, 0, 4]
307
308
This function use the :func:`~random.random` and :func:`~random.randint`
309
functions from the python base :mod:`random` module.
310
"""
311
size = min(len(ind1), len(ind2))
312
p1, p2 = [0]*size, [0]*size
313
314
# Initialize the position of each indices in the individuals
315
for i in xrange(size):
316
p1[ind1[i]] = i
317
p2[ind2[i]] = i
318
319
for i in xrange(size):
320
if random.random < indpb:
321
# Keep track of the selected values
322
temp1 = ind1[i]
323
temp2 = ind2[i]
324
# Swap the matched value
325
ind1[i], ind1[p1[temp2]] = temp2, temp1
326
ind2[i], ind2[p2[temp1]] = temp1, temp2
327
# Position bookkeeping
328
p1[temp1], p1[temp2] = p1[temp2], p1[temp1]
329
p2[temp1], p2[temp2] = p2[temp2], p2[temp1]
330
331
return ind1, ind2
332
333
def cxBlend(ind1, ind2, alpha):
334
"""Executes a blend crossover that modify inplace the input individuals.
335
The blend crossover expect individuals formed of a list of floating point
336
numbers.
337
338
This function use the :func:`~random.random` function from the python base
339
:mod:`random` module.
340
"""
341
size = min(len(ind1), len(ind2))
342
343
for i in xrange(size):
344
gamma = (1. + 2. * alpha) * random.random() - alpha
345
x1 = ind1[i]
346
x2 = ind2[i]
347
ind1[i] = (1. - gamma) * x1 + gamma * x2
348
ind2[i] = gamma * x1 + (1. - gamma) * x2
349
350
return ind1, ind2
351
352
def cxSimulatedBinary(ind1, ind2, nu):
353
"""Executes a simulated binary crossover that modify inplace the input
354
individuals. The simulated binary crossover expect individuals formed of
355
a list of floating point numbers.
356
357
This function use the :func:`~random.random` function from the python base
358
:mod:`random` module.
359
"""
360
size = min(len(ind1), len(ind2))
361
362
for i in xrange(size):
363
rand = random.random()
364
if rand <= 0.5:
365
beta = 2. * rand
366
else:
367
beta = 1. / (2. * (1. - rand))
368
beta **= 1. / (nu + 1.)
369
x1 = ind1[i]
370
x2 = ind2[i]
371
ind1[i] = 0.5 * (((1 + beta) * x1) + ((1 - beta) * x2))
372
ind2[i] = 0.5 * (((1 - beta) * x1) + ((1 + beta) * x2))
373
374
return ind1, ind2
375
376
######################################
377
# Messy Crossovers #
378
######################################
379
380
def cxMessyOnePoint(ind1, ind2):
381
"""Execute a one point crossover will mostly change the individuals size.
382
This operation apply on an :class:`Individual` composed of a list of
383
attributes and act as follow ::
384
385
>>> ind1 = [A(1), ..., A(i), ..., A(m)]
386
>>> ind2 = [B(1), ..., B(j), ..., B(n)]
387
>>> # Crossover with mating points i, j, 1 <= i <= m, 1 <= j <= n
388
>>> cxMessyOnePoint(ind1, ind2)
389
>>> print ind1, len(ind1)
390
[A(1), ..., A(i - 1), B(j), ..., B(n)], n + j - i
391
>>> print ind2, len(ind2)
392
[B(1), ..., B(j - 1), A(i), ..., A(m)], m + i - j
393
394
This function use the :func:`~random.randint` function from the python base
395
:mod:`random` module.
396
"""
397
cxpoint1 = random.randint(0, len(ind1))
398
cxpoint2 = random.randint(0, len(ind2))
399
ind1[cxpoint1:], ind2[cxpoint2:] = ind2[cxpoint2:], ind1[cxpoint1:]
400
401
return ind1, ind2
402
403
######################################
404
# ES Crossovers #
405
######################################
406
407
def cxESBlend(ind1, ind2, alpha, minstrategy=None):
408
"""Execute a blend crossover on both, the individual and the strategy.
409
*minstrategy* defaults to None so that if it is not present, the minimal
410
strategy will be minus infinity.
411
"""
412
size = min(len(ind1), len(ind2))
413
414
for indx in xrange(size):
415
# Blend the values
416
gamma = (1. + 2. * alpha) * random.random() - alpha
417
x1 = ind1[indx]
418
x2 = ind2[indx]
419
ind1[indx] = (1. - gamma) * x1 + gamma * x2
420
ind2[indx] = gamma * x1 + (1. - gamma) * x2
421
# Blend the strategies
422
gamma = (1. + 2. * alpha) * random.random() - alpha
423
s1 = ind1.strategy[indx]
424
s2 = ind2.strategy[indx]
425
ind1.strategy[indx] = (1. - gamma) * s1 + gamma * s2
426
ind2.strategy[indx] = gamma * s1 + (1. - gamma) * s2
427
if ind1.strategy[indx] < minstrategy: # 4 < None = False
428
ind1.strategy[indx] = minstrategy
429
if ind2.strategy[indx] < minstrategy:
430
ind2.strategy[indx] = minstrategy
431
432
return ind1, ind2
433
434
def cxESTwoPoints(ind1, ind2):
435
"""Execute a classical two points crossover on both the individual and
436
its strategy. The crossover points for the individual and the strategy
437
are the same.
438
"""
439
size = min(len(ind1), len(ind2))
440
441
pt1 = random.randint(1, size)
442
pt2 = random.randint(1, size - 1)
443
if pt2 >= pt1:
444
pt2 += 1
445
else: # Swap the two cx points
446
pt1, pt2 = pt2, pt1
447
448
ind1[pt1:pt2], ind2[pt1:pt2] = ind2[pt1:pt2], ind1[pt1:pt2]
449
ind1.strategy[pt1:pt2], ind2.strategy[pt1:pt2] = \
450
ind2.strategy[pt1:pt2], ind1.strategy[pt1:pt2]
451
452
return ind1, ind2
453
454
######################################
455
# GA Mutations #
456
######################################
457
458
def mutGaussian(individual, mu, sigma, indpb):
459
"""This function applies a gaussian mutation of mean *mu* and standard
460
deviation *sigma* on the input individual and
461
returns the mutant. The *individual* is left intact and the mutant is an
462
independant copy. This mutation expects an iterable individual composed of
463
real valued attributes. The *mutIndxPb* argument is the probability of each
464
attribute to be mutated.
465
466
.. note::
467
The mutation is not responsible for constraints checking, because
468
there is too many possibilities for
469
resetting the values. Wich way is closer to the representation used
470
is up to you.
471
472
One easy way to add cronstraint checking to an operator is to
473
use the function decoration in the toolbox. See the multi-objective
474
example (moga_kursawefct.py) for an explicit example.
475
476
This function uses the :func:`~random.random` and :func:`~random.gauss`
477
functions from the python base :mod:`random` module.
478
"""
479
for i in xrange(len(individual)):
480
if random.random() < indpb:
481
individual[i] += random.gauss(mu, sigma)
482
483
return individual,
484
485
def mutShuffleIndexes(individual, indpb):
486
"""Shuffle the attributes of the input individual and return the mutant.
487
The *individual* is left intact and the mutant is an independant copy. The
488
*individual* is expected to be iterable. The *shuffleIndxPb* argument is the
489
probability of each attribute to be moved.
490
491
This function uses the :func:`~random.random` and :func:`~random.randint`
492
functions from the python base :mod:`random` module.
493
"""
494
size = len(individual)
495
for i in xrange(size):
496
if random.random() < indpb:
497
swap_indx = random.randint(0, size - 2)
498
if swap_indx >= i:
499
swap_indx += 1
500
individual[i], individual[swap_indx] = \
501
individual[swap_indx], individual[i]
502
503
return individual,
504
505
def mutFlipBit(individual, indpb):
506
"""Flip the value of the attributes of the input individual and return the
507
mutant. The *individual* is left intact and the mutant is an independant
508
copy. The *individual* is expected to be iterable and the values of the
509
attributes shall stay valid after the ``not`` operator is called on them.
510
The *flipIndxPb* argument is the probability of each attribute to be
511
flipped.
512
513
This function uses the :func:`~random.random` function from the python base
514
:mod:`random` module.
515
"""
516
for indx in xrange(len(individual)):
517
if random.random() < indpb:
518
individual[indx] = not individual[indx]
519
520
return individual,
521
522
######################################
523
# ES Mutations #
524
######################################
525
526
def mutES(individual, indpb, minstrategy=None):
527
"""Mutate an evolution strategy according to its :attr:`strategy`
528
attribute. *minstrategy* defaults to None so that if it is not present,
529
the minimal strategy will be minus infinity. The strategy shall be the
530
same size as the individual. This is subject to change.
531
"""
532
size = len(individual)
533
t = 1. / math.sqrt(2. * math.sqrt(size))
534
t0 = 1. / math.sqrt(2. * size)
535
n = random.gauss(0, 1)
536
t0_n = t0 * n
537
538
for indx in xrange(size):
539
if random.random() < indpb:
540
ni = random.gauss(0, 1)
541
individual.strategy[indx] *= math.exp(t0_n + t * ni)
542
if individual.strategy[indx] < minstrategy: # 4 < None = False
543
individual.strategy[indx] = minstrategy
544
individual[indx] += individual.strategy[indx] * ni
545
546
return individual,
547
548
######################################
549
# GP Crossovers #
550
######################################
551
552
def cxTreeUniformOnePoint(ind1, ind2):
553
"""Randomly select in each individual and exchange each subtree with the
554
point as root between each individual.
555
"""
556
try:
557
index1 = random.randint(1, ind1.size-1)
558
index2 = random.randint(1, ind2.size-1)
559
except ValueError:
560
return ind1, ind2
561
562
sub1 = ind1.searchSubtreeDF(index1)
563
sub2 = ind2.searchSubtreeDF(index2)
564
ind1.setSubtreeDF(index1, sub2)
565
ind2.setSubtreeDF(index2, sub1)
566
567
return ind1, ind2
568
569
## Strongly Typed GP crossovers
570
def cxTypedTreeOnePoint(ind1, ind2):
571
"""Randomly select in each individual and exchange each subtree with the
572
point as root between each individual. Since the node are strongly typed,
573
the operator then make sure the type of second node correspond to the type
574
of the first node. If it doesn't, it randomly selects another point in the
575
second individual and try again. It tries up to *5* times before
576
giving up on the crossover.
577
578
.. note::
579
This crossover is subject to change for a more effective method
580
of selecting the crossover points.
581
"""
582
# choose the crossover point in each individual
583
try:
584
index1 = random.randint(1, ind1.size-1)
585
index2 = random.randint(1, ind2.size-1)
586
except ValueError:
587
return ind1, ind2
588
589
subtree1 = ind1.searchSubtreeDF(index1)
590
subtree2 = ind2.searchSubtreeDF(index2)
591
592
type1 = subtree1.root.ret
593
type2 = subtree2.root.ret
594
595
# try to mate the trees
596
# if no crossover point is found after 5 it gives up trying
597
# mating individuals.
598
tries = 0
599
MAX_TRIES = 5
600
while not (type1 == type2) and tries < MAX_TRIES:
601
index2 = random.randint(1, ind2.size-1)
602
subtree2 = ind2.searchSubtreeDF(index2)
603
type2 = subtree2.root.ret
604
tries += 1
605
606
if type1 == type2:
607
sub1 = ind1.searchSubtreeDF(index1)
608
sub2 = ind2.searchSubtreeDF(index2)
609
ind1.setSubtreeDF(index1, sub2)
610
ind2.setSubtreeDF(index2, sub1)
611
612
return ind1, ind2
613
614
######################################
615
# GP Mutations #
616
######################################
617
def mutTreeUniform(individual, expr):
618
"""Randomly select a point in the Tree, then replace the subtree with
619
the point as a root by a randomly generated expression. The expression
620
is generated using the method `expr`.
621
"""
622
index = random.randint(0, individual.size-1)
623
individual.setSubtreeDF(index, expr(pset=individual.pset))
624
625
return individual,
626
627
## Strongly Typed GP mutations
628
def mutTypedTreeUniform(individual, expr):
629
"""The mutation of strongly typed GP expression is pretty easy. First,
630
it finds a subtree. Second, it has to identify the return type of the root
631
of this subtree. Third, it generates a new subtree with a root's type
632
corresponding to the original subtree root's type. Finally, the old
633
subtree is replaced by the new subtree.
634
"""
635
index = random.randint(0, individual.size-1)
636
subtree = individual.searchSubtreeDF(index)
637
individual.setSubtreeDF(index, expr(pset=individual.pset,
638
type_=subtree.root.ret))
639
640
return individual,
641
642
643
def mutTypedTreeNodeReplacement(individual):
644
"""This operator mutates the individual *individual* that are subjected to
645
it. The operator randomly chooses a primitive in the individual
646
and replaces it with a randomly selected primitive in *pset* that takes
647
the same number of arguments.
648
649
This operator works on strongly typed trees as on normal GP trees.
650
"""
651
if individual.size < 2:
652
return individual,
653
654
index = random.randint(1, individual.size-1)
655
node = individual.searchSubtreeDF(index)
656
657
if node.size == 1:
658
subtree = random.choice(individual.pset.terminals[node.root.ret])()
659
individual.setSubtreeDF(index, subtree)
660
661
else:
662
# We're going to replace one of the *node* children
663
index = random.randint(1, len(node) - 1)
664
if node[index].size > 1:
665
prim_set = individual.pset.primitives[node[index].root.ret]
666
repl_node = random.choice(prim_set)
667
while repl_node.args != node[index].root.args:
668
repl_node = random.choice(prim_set)
669
node[index][0] = repl_node
670
else:
671
term_set = individual.pset.terminals[node[index].root.ret]
672
repl_node = random.choice(term_set)()
673
node[index] = repl_node
674
675
return individual,
676
677
def mutTypedTreeEphemeral(individual, mode):
678
"""This operator works on the constants of the tree *ind*.
679
In *mode* ``"one"``, it will change the value of **one**
680
of the individual ephemeral constants by calling its generator function.
681
In *mode* ``"all"``, it will change the value of **all**
682
the ephemeral constants.
683
684
This operator works on strongly typed trees as on normal GP trees.
685
"""
686
if mode not in ["one", "all"]:
687
raise ValueError("Mode must be one of \"one\" or \"all\"")
688
ephemerals = []
689
for i in xrange(1, individual.size):
690
subtree = individual.searchSubtreeDF(i)
691
if hasattr(subtree.root.obj, 'regen'):
692
ephemerals.append(i)
693
694
if len(ephemerals) > 0:
695
if mode == "one":
696
ephemerals = [random.choice(ephemerals)]
697
elif mode == "all":
698
pass
699
700
for i in ephemerals:
701
individual.searchSubtreeDF(i).regen()
702
703
return individual,
704
705
def mutTreeShrink(individual):
706
"""This operator shrinks the individual *individual* that are subjected to
707
it. The operator randomly chooses a branch in the individual and replaces
708
it with one of the branch's arguments (also randomly chosen).
709
710
This operator is not usable with STGP.
711
"""
712
if individual.size < 3 or individual.height <= 2:
713
return individual, # We don't want to "shrink" the root
714
715
index = random.randint(1, individual.size-2)
716
717
# Shrinking a terminal is useless
718
while individual.searchSubtreeDF(index).size == 1:
719
index = random.randint(1, individual.size-2)
720
721
deleted_node = individual.searchSubtreeDF(index)
722
repl_subtree_index = random.randint(1, len(deleted_node)-1)
723
724
individual.setSubtreeDF(index, deleted_node[repl_subtree_index])
725
726
return individual,
727
728
def mutTypedTreeInsert(individual):
729
"""This operator mutate the GP tree of the *individual* passed and the
730
primitive set *expr*, by inserting a new branch at a random position in a
731
tree, using the original subtree at this position as one argument,
732
and if necessary randomly selecting terminal primitives
733
to complete the arguments of the inserted node.
734
Note that the original subtree will become one of the children of the new
735
primitive inserted, but not perforce the first (its position is
736
randomly selected if the new primitive has more than one child)
737
738
This operator works on strongly typed trees as on normal GP trees.
739
"""
740
pset = individual.pset
741
index = random.randint(0, individual.size-1)
742
node = individual.searchSubtreeDF(index)
743
if node.size > 1: # We do not need to deepcopy the leafs
744
node = copy.deepcopy(node)
745
746
new_primitive = random.choice(pset.primitives[node.root.ret])
747
748
inserted_list = [new_primitive]
749
for i in xrange(0, new_primitive.arity):
750
# Why don't we use expr to create the other subtrees?
751
# Bloat control?
752
new_child = random.choice(pset.terminals[new_primitive.args[i]])
753
inserted_list.append(new_child())
754
755
inserted_list[random.randint(1, new_primitive.arity)] = node
756
757
individual.setSubtreeDF(index, inserted_list)
758
return individual,
759
760
761
# In order to use different mutations, wheter build your own algorithms
762
# or define your own mutate function that calls explicitely the needed
763
# methods
764
# def mutTreeRandomMethod(individual, expr):
765
# """This operator performs a mutation over the individual *ind*.
766
# The mutation operator is randomly chosen between the insertion,
767
# the shrink, the node replacement, the subtree replacement (mutTreeUniform)
768
# and the ephemeral constants change.
769
# """
770
# method = random.choice([mutTreeUniform, mutTypedTreeInsert,
771
# mutTreeShrink, mutTypedTreeNodeReplacement,
772
# mutTypedTreeEphemeral])
773
# # Partial?
774
# return functools.partial(method, individual=individual, expr=expr)()
775
776
######################################
777
# Selections #
778
######################################
779
780
def selRandom(individuals, n):
781
"""Select *n* individuals at random from the input *individuals*. The
782
list returned contains references to the input *individuals*.
783
784
This function uses the :func:`~random.choice` function from the
785
python base :mod:`random` module.
786
"""
787
return [random.choice(individuals) for i in xrange(n)]
788
789
790
def selBest(individuals, n):
791
"""Select the *n* best individuals among the input *individuals*. The
792
list returned contains references to the input *individuals*.
793
"""
794
return sorted(individuals, key=attrgetter("fitness"), reverse=True)[:n]
795
796
797
def selWorst(individuals, n):
798
"""Select the *n* worst individuals among the input *individuals*. The
799
list returned contains references to the input *individuals*.
800
"""
801
return sorted(individuals, key=attrgetter("fitness"))[:n]
802
803
804
def selTournament(individuals, n, tournsize):
805
"""Select *n* individuals from the input *individuals* using *n*
806
tournaments of *tournSize* individuals. The list returned contains
807
references to the input *individuals*.
808
809
This function uses the :func:`~random.choice` function from the python base
810
:mod:`random` module.
811
"""
812
chosen = []
813
for i in xrange(n):
814
chosen.append(random.choice(individuals))
815
for j in xrange(tournsize - 1):
816
aspirant = random.choice(individuals)
817
if aspirant.fitness > chosen[i].fitness:
818
chosen[i] = aspirant
819
820
return chosen
821
822
def selRoulette(individuals, n):
823
"""Select *n* individuals from the input *individuals* using *n*
824
spins of a roulette. The selection is made by looking only at the first
825
objective of each individual. The list returned contains references to
826
the input *individuals*.
827
828
This function uses the :func:`~random.random` function from the python base
829
:mod:`random` module.
830
"""
831
s_inds = sorted(individuals, key=attrgetter("fitness"), reverse=True)[:n]
832
sum_fits = sum(map(lambda ind: ind.fitness.values[0], individuals))
833
834
chosen = []
835
for i in xrange(n):
836
u = random.random() * sum_fits
837
sum_ = 0
838
for ind in s_inds:
839
sum_ += ind.fitness.values[0]
840
if sum_ > u:
841
chosen.append(ind)
842
break
843
844
return chosen
845
846
######################################
847
# Non-Dominated Sorting (NSGA-II) #
848
######################################
849
850
def nsga2(individuals, n):
851
"""Apply NSGA-II selection operator on the *individuals*. Usually,
852
the size of *individuals* will be larger than *n* because any individual
853
present in *individuals* will appear in the returned list at most once.
854
Having the size of *individuals* equals to *n* will have no effect other
855
than sorting the population according to a non-domination sheme. The list
856
returned contains references to the input *individuals*.
857
858
For more details on the NSGA-II operator see Deb, Pratab, Agarwal,
859
and Meyarivan, "A fast elitist non-dominated sorting genetic algorithm for
860
multi-objective optimization: NSGA-II", 2002.
861
"""
862
pareto_fronts = sortFastND(individuals, n)
863
chosen = list(chain(*pareto_fronts[:-1]))
864
n = n - len(chosen)
865
if n > 0:
866
chosen.extend(sortCrowdingDist(pareto_fronts[-1], n))
867
return chosen
868
869
870
def sortFastND(individuals, n, first_front_only=False):
871
"""Sort the first *n* *individuals* according the the fast non-dominated
872
sorting algorithm.
873
"""
874
N = len(individuals)
875
pareto_fronts = []
876
877
if n == 0:
878
return pareto_fronts
879
880
pareto_fronts.append([])
881
pareto_sorted = 0
882
dominating_inds = [0] * N
883
dominated_inds = [list() for i in xrange(N)]
884
885
# Rank first Pareto front
886
for i in xrange(N):
887
for j in xrange(i+1, N):
888
if individuals[j].fitness.isDominated(individuals[i].fitness):
889
dominating_inds[j] += 1
890
dominated_inds[i].append(j)
891
elif individuals[i].fitness.isDominated(individuals[j].fitness):
892
dominating_inds[i] += 1
893
dominated_inds[j].append(i)
894
if dominating_inds[i] == 0:
895
pareto_fronts[-1].append(i)
896
pareto_sorted += 1
897
898
if not first_front_only:
899
# Rank the next front until all individuals are sorted or the given
900
# number of individual are sorted
901
N = min(N, n)
902
while pareto_sorted < N:
903
pareto_fronts.append([])
904
for indice_p in pareto_fronts[-2]:
905
for indice_d in dominated_inds[indice_p]:
906
dominating_inds[indice_d] -= 1
907
if dominating_inds[indice_d] == 0:
908
pareto_fronts[-1].append(indice_d)
909
pareto_sorted += 1
910
911
return [[individuals[index] for index in front] for front in pareto_fronts]
912
913
914
def sortCrowdingDist(individuals, n):
915
"""Sort the individuals according to the crowding distance."""
916
if len(individuals) == 0:
917
return []
918
919
distances = [0.0] * len(individuals)
920
crowding = [(ind, i) for i, ind in enumerate(individuals)]
921
922
number_objectives = len(individuals[0].fitness.values)
923
inf = float("inf") # It is four times faster to compare with a local
924
# variable than create the float("inf") each time
925
for i in xrange(number_objectives):
926
crowding.sort(key=lambda element: element[0].fitness.values[i])
927
distances[crowding[0][1]] = float("inf")
928
distances[crowding[-1][1]] = float("inf")
929
for j in xrange(1, len(crowding) - 1):
930
if distances[crowding[j][1]] < inf:
931
distances[crowding[j][1]] += \
932
crowding[j + 1][0].fitness.values[i] - \
933
crowding[j - 1][0].fitness.values[i]
934
sorted_dist = sorted([(dist, i) for i, dist in enumerate(distances)],
935
key=lambda value: value[0], reverse=True)
936
return (individuals[index] for dist, index in sorted_dist[:n])
937
938
939
######################################
940
# Strength Pareto (SPEA-II) #
941
######################################
942
943
def spea2(individuals, n):
944
"""Apply SPEA-II selection operator on the *individuals*. Usually,
945
the size of *individuals* will be larger than *n* because any individual
946
present in *individuals* will appear in the returned list at most once.
947
Having the size of *individuals* equals to *n* will have no effect other
948
than sorting the population according to a strength pareto sheme. The list
949
returned contains references to the input *individuals*.
950
951
For more details on the SPEA-II operator see Zitzler, Laumanns and Thiele,
952
"SPEA 2: Improving the strength pareto evolutionary algorithm", 2001.
953
"""
954
N = len(individuals)
955
L = len(individuals[0].fitness.values)
956
K = math.sqrt(N)
957
strength_fits = [0] * N
958
fits = [0] * N
959
dominating_inds = [list() for i in xrange(N)]
960
961
for i in xrange(N):
962
for j in xrange(i + 1, N):
963
if individuals[i].fitness.isDominated(individuals[j].fitness):
964
strength_fits[j] += 1
965
dominating_inds[i].append(j)
966
elif individuals[j].fitness.isDominated(individuals[i].fitness):
967
strength_fits[i] += 1
968
dominating_inds[j].append(i)
969
970
for i in xrange(N):
971
for j in dominating_inds[i]:
972
fits[i] += strength_fits[j]
973
974
# Choose all non-dominated individuals
975
chosen_indices = [i for i in xrange(N) if fits[i] < 1]
976
977
if len(chosen_indices) < n: # The archive is too small
978
for i in xrange(N):
979
distances = [0.0] * N
980
for j in xrange(i + 1, N):
981
dist = 0.0
982
for k in xrange(L):
983
val = individuals[i].fitness.values[k] - \
984
individuals[j].fitness.values[k]
985
dist += val * val
986
distances[j] = dist
987
kth_dist = _randomizedSelect(distances, 0, N - 1, K)
988
density = 1.0 / (kth_dist + 2.0)
989
fits[i] += density
990
991
next_indices = [(fits[i], i) for i in xrange(N) \
992
if not i in chosen_indices]
993
next_indices.sort()
994
#print next_indices
995
chosen_indices += [i for fit, i in next_indices[:n - len(chosen_indices)]]
996
997
elif len(chosen_indices) > n: # The archive is too large
998
N = len(chosen_indices)
999
distances = [[0.0] * N for i in xrange(N)]
1000
sorted_indices = [[0] * N for i in xrange(N)]
1001
for i in xrange(N):
1002
for j in xrange(i + 1, N):
1003
dist = 0.0
1004
for k in xrange(L):
1005
val = individuals[chosen_indices[i]].fitness.values[k] - \
1006
individuals[chosen_indices[j]].fitness.values[k]
1007
dist += val * val
1008
distances[i][j] = dist
1009
distances[j][i] = dist
1010
distances[i][i] = -1
1011
1012
# Insert sort is faster than quick sort for short arrays
1013
for i in xrange(N):
1014
for j in xrange(1, N):
1015
k = j
1016
while k > 0 and distances[i][j] < distances[i][sorted_indices[i][k - 1]]:
1017
sorted_indices[i][k] = sorted_indices[i][k - 1]
1018
k -= 1
1019
sorted_indices[i][k] = j
1020
1021
size = N
1022
to_remove = []
1023
while size > n:
1024
# Search for minimal distance
1025
min_pos = 0
1026
for i in xrange(1, N):
1027
for j in xrange(1, size):
1028
dist_i_sorted_j = distances[i][sorted_indices[i][j]]
1029
dist_min_sorted_j = distances[min_pos][sorted_indices[min_pos][j]]
1030
1031
if dist_i_sorted_j < dist_min_sorted_j:
1032
min_pos = i
1033
break
1034
elif dist_i_sorted_j > dist_min_sorted_j:
1035
break
1036
1037
# Remove minimal distance from sorted_indices
1038
for i in xrange(N):
1039
distances[i][min_pos] = float("inf")
1040
distances[min_pos][i] = float("inf")
1041
1042
for j in xrange(1, size - 1):
1043
if sorted_indices[i][j] == min_pos:
1044
sorted_indices[i][j] = sorted_indices[i][j + 1]
1045
sorted_indices[i][j + 1] = min_pos
1046
1047
# Remove corresponding individual from chosen_indices
1048
to_remove.append(min_pos)
1049
size -= 1
1050
1051
for index in reversed(sorted(to_remove)):
1052
del chosen_indices[index]
1053
1054
return [individuals[i] for i in chosen_indices]
1055
1056
def _randomizedSelect(array, begin, end, i):
1057
"""Allows to select the ith smallest element from array without sorting it.
1058
Runtime is expected to be O(n).
1059
"""
1060
if begin == end:
1061
return array[begin]
1062
q = _randomizedPartition(array, begin, end)
1063
k = q - begin + 1
1064
if i < k:
1065
return _randomizedSelect(array, begin, q, i)
1066
else:
1067
return _randomizedSelect(array, q + 1, end, i - k)
1068
1069
def _randomizedPartition(array, begin, end):
1070
i = random.randint(begin, end)
1071
array[begin], array[i] = array[i], array[begin]
1072
return _partition(array, begin, end)
1073
1074
def _partition(array, begin, end):
1075
x = array[begin]
1076
i = begin - 1
1077
j = end + 1
1078
while True:
1079
j -= 1
1080
while array[j] > x:
1081
j -= 1
1082
i += 1
1083
while array[i] < x:
1084
i += 1
1085
if i < j:
1086
array[i], array[j] = array[j], array[i]
1087
else:
1088
return j
1089
1090
######################################
1091
# Replacement Strategies (ES) #
1092
######################################
1093
1094
1095
1096
######################################
1097
# Migrations #
1098
######################################
1099
1100
def migRing(populations, n, selection, replacement=None, migarray=None,
1101
sel_kargs=None, repl_kargs=None):
1102
"""Perform a ring migration between the *populations*. The migration first
1103
select *n* emigrants from each population using the specified *selection*
1104
operator and then replace *n* individuals from the associated population in
1105
the *migarray* by the emigrants. If no *replacement*
1106
operator is specified, the immigrants will replace the emigrants of the
1107
population, otherwise, the immigrants will replace the individuals selected
1108
by the *replacement* operator. The migration array, if provided, shall
1109
contain each population's index once and only once. If no migration array
1110
is provided, it defaults to a serial ring migration (1 -- 2 -- ... -- n
1111
-- 1). You may pass keyworded arguments to the two selection operators by
1112
giving a dictionary to *sel_kargs* and *repl_kargs*.
1113
"""
1114
if migarray is None:
1115
migarray = range(1, len(populations)) + [0]
1116
1117
immigrants = [[] for i in xrange(len(migarray))]
1118
emigrants = [[] for i in xrange(len(migarray))]
1119
if sel_kargs is None:
1120
sel_kargs = {}
1121
if repl_kargs is None:
1122
repl_kargs = {}
1123
1124
for from_deme in xrange(len(migarray)):
1125
emigrants[from_deme].extend(selection(populations[from_deme], n=n,
1126
**sel_kargs))
1127
if replacement is None:
1128
# If no replacement strategy is selected, replace those who migrate
1129
immigrants[from_deme] = emigrants[from_deme]
1130
else:
1131
# Else select those who will be replaced
1132
immigrants[from_deme].extend(replacement(populations[from_deme],
1133
n=n, **repl_kargs))
1134
1135
mig_buf = emigrants[0]
1136
for from_deme, to_deme in enumerate(migarray[1:]):
1137
from_deme += 1 # Enumerate starts at 0
1138
1139
for i, immigrant in enumerate(immigrants[to_deme]):
1140
indx = populations[to_deme].index(immigrant)
1141
populations[to_deme][indx] = emigrants[from_deme][i]
1142
1143
to_deme = migarray[0]
1144
for i, immigrant in enumerate(immigrants[to_deme]):
1145
indx = populations[to_deme].index(immigrant)
1146
populations[to_deme][indx] = mig_buf[i]
1147
1148
######################################
1149
# Decoration tool #
1150
######################################
1151
1152
# This function is a simpler version of the decorator module (version 3.2.0)
1153
# from Michele Simionato available at http://pypi.python.org/pypi/decorator.
1154
# Copyright (c) 2005, Michele Simionato
1155
# All rights reserved.
1156
# Modified by Francois-Michel De Rainville, 2010
1157
1158
def decorate(decorator):
1159
"""Decorate a function preserving its signature. There is two way of
1160
using this function, first as a decorator passing the decorator to
1161
use as argument, for example ::
1162
1163
@decorate(a_decorator)
1164
def myFunc(arg1, arg2, arg3="default"):
1165
do_some_work()
1166
return "some_result"
1167
1168
Or as a decorator ::
1169
1170
@decorate
1171
def myDecorator(func):
1172
def wrapFunc(*args, **kargs):
1173
decoration_work()
1174
return func(*args, **kargs)
1175
return wrapFunc
1176
1177
@myDecorator
1178
def myFunc(arg1, arg2, arg3="default"):
1179
do_some_work()
1180
return "some_result"
1181
1182
Using the :mod:`inspect` module, we can retreive the signature of the
1183
decorated function, what is not possible when not using this method. ::
1184
1185
print inspect.getargspec(myFunc)
1186
1187
It shall return something like ::
1188
1189
(["arg1", "arg2", "arg3"], None, None, ("default",))
1190
"""
1191
def wrapDecorate(func):
1192
# From __init__
1193
assert func.__name__
1194
if inspect.isfunction(func):
1195
argspec = inspect.getargspec(func)
1196
defaults = argspec[-1]
1197
signature = inspect.formatargspec(formatvalue=lambda val: "",
1198
*argspec)[1:-1]
1199
elif inspect.isclass(func):
1200
argspec = inspect.getargspec(func.__init__)
1201
defaults = argspec[-1]
1202
signature = inspect.formatargspec(formatvalue=lambda val: "",
1203
*argspec)[1:-1]
1204
if not signature:
1205
raise TypeError("You are decorating a non function: %s" % func)
1206
1207
# From create
1208
src = ("def %(name)s(%(signature)s):\n"
1209
" return _call_(%(signature)s)\n") % dict(name=func.__name__,
1210
signature=signature)
1211
1212
# From make
1213
evaldict = dict(_call_=decorator(func))
1214
reserved_names = set([func.__name__] + \
1215
[arg.strip(' *') for arg in signature.split(',')])
1216
for name in evaldict.iterkeys():
1217
if name in reserved_names:
1218
raise NameError("%s is overridden in\n%s" % (name, src))
1219
try:
1220
# This line does all the dirty work of reassigning the signature
1221
code = compile(src, "<string>", "single")
1222
exec code in evaldict
1223
except:
1224
raise RuntimeError("Error in generated code:\n%s" % src)
1225
new_func = evaldict[func.__name__]
1226
1227
# From update
1228
new_func.__source__ = src
1229
new_func.__name__ = func.__name__
1230
new_func.__doc__ = func.__doc__
1231
new_func.__dict__ = func.__dict__.copy()
1232
new_func.func_defaults = defaults
1233
new_func.__module__ = func.__module__
1234
return new_func
1235
return wrapDecorate
Loggerhead is a web-based interface for Breezy
Version: 2.0.1