forked from MorphologicalComputations/SpringMassNetworks
-
Notifications
You must be signed in to change notification settings - Fork 2
/
cma.py
executable file
·8802 lines (7734 loc) · 369 KB
/
cma.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
#!/usr/bin/env python
"""Module cma implements the CMA-ES (Covariance Matrix Adaptation
Evolution Strategy).
CMA-ES is a stochastic optimizer for robust non-linear non-convex
derivative- and function-value-free numerical optimization.
This implementation can be used with Python versions >= 2.6, namely
2.6, 2.7, 3.3, 3.4.
CMA-ES searches for a minimizer (a solution x in :math:`R^n`) of an
objective function f (cost function), such that f(x) is minimal.
Regarding f, only a passably reliable ranking of the candidate
solutions in each iteration is necessary. Neither the function values
itself, nor the gradient of f need to be available or do matter (like
in the downhill simplex Nelder-Mead algorithm). Some termination
criteria however depend on actual f-values.
Two interfaces are provided:
- function `fmin(func, x0, sigma0,...)`
runs a complete minimization
of the objective function func with CMA-ES.
- class `CMAEvolutionStrategy`
allows for minimization such that the control of the iteration
loop remains with the user.
Used packages:
- unavoidable: `numpy` (see `barecmaes2.py` if `numpy` is not
available),
- avoidable with small changes: `time`, `sys`
- optional: `matplotlib.pyplot` (for `plot` etc., highly
recommended), `pprint` (pretty print), `pickle` (in class
`Sections`), `doctest`, `inspect`, `pygsl` (never by default)
Install
-------
The file ``cma.py`` only needs to be visible in the python path (e.g. in
the current working directory).
The preferred way of (system-wide) installation is calling
pip install cma
from the command line.
The ``cma.py`` file can also be installed from the
system shell terminal command line by::
python cma.py --install
which solely calls the ``setup`` function from the standard
``distutils.core`` package for installation. If the ``setup.py``
file is been provided with ``cma.py``, the standard call is
python setup.py cma
Both calls need to see ``cma.py`` in the current working directory and
might need to be preceded with ``sudo``.
To upgrade the currently installed version from the Python Package Index,
and also for first time installation, type in the system shell::
pip install --upgrade cma
Testing
-------
From the system shell::
python cma.py --test
or from the Python shell ``ipython``::
run cma.py --test
or from any python shell
import cma
cma.main('--test')
runs ``doctest.testmod(cma)`` showing only exceptions (and not the
tests that fail due to small differences in the output) and should
run without complaints in about between 20 and 100 seconds.
Example
-------
From a python shell::
import cma
help(cma) # "this" help message, use cma? in ipython
help(cma.fmin)
help(cma.CMAEvolutionStrategy)
help(cma.CMAOptions)
cma.CMAOptions('tol') # display 'tolerance' termination options
cma.CMAOptions('verb') # display verbosity options
res = cma.fmin(cma.Fcts.tablet, 15 * [1], 1)
res[0] # best evaluated solution
res[5] # mean solution, presumably better with noise
:See: `fmin()`, `CMAOptions`, `CMAEvolutionStrategy`
:Author: Nikolaus Hansen, 2008-2015
:Contributor: Petr Baudis, 2014
:License: BSD 3-Clause, see below.
"""
# The BSD 3-Clause License
# Copyright (c) 2014 Inria
# Author: Nikolaus Hansen, 2008-2015
#
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions
# are met:
#
# 1. Redistributions of source code must retain the above copyright and
# authors notice, this list of conditions and the following disclaimer.
#
# 2. Redistributions in binary form must reproduce the above copyright
# and authors notice, this list of conditions and the following
# disclaimer in the documentation and/or other materials provided with
# the distribution.
#
# 3. Neither the name of the copyright holder nor the names of its
# contributors nor the authors names may be used to endorse or promote
# products derived from this software without specific prior written
# permission.
#
# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
# "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
# A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
# HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
# INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
# BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
# OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
# AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
# LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY
# WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
# POSSIBILITY OF SUCH DAMAGE.
# (note to self) for testing:
# pyflakes cma.py # finds bugs by static analysis
# pychecker --limit 60 cma.py # also executes, all 60 warnings checked
# or python ~/Downloads/pychecker-0.8.19/pychecker/checker.py cma.py
# python cma.py -t -quiet # executes implemented tests based on doctest
# python -3 cma.py --test 2> out2to3warnings.txt #
# to create a html documentation file:
# pydoc -w cma # edit the header (remove local pointers)
# epydoc cma.py # comes close to javadoc but does not find the
# # links of function references etc
# doxygen needs @package cma as first line in the module docstring
# some things like class attributes are not interpreted correctly
# sphinx: doc style of doc.python.org, could not make it work (yet)
# TODO: implement a (deep enough) copy-constructor for class
# CMAEvolutionStrategy to repeat the same step in different
# configurations for online-adaptation of meta parameters
# TODO: reconsider geno-pheno transformation. Can it be a completely
# separate module that operates inbetween optimizer and objective?
# Can we still propagate a repair of solutions to the optimizer?
# How about gradients (should be fine)?
# TODO: implement bipop in a separate algorithm as meta portfolio
# algorithm of IPOP and a local restart option to be implemented
# in fmin (e.g. option restart_mode in [IPOP, local])
# TODO: self.opts['mindx'] is checked without sigma_vec, which is wrong,
# TODO: project sigma_vec on the smallest eigenvector?
# TODO: class _CMAStopDict implementation looks way too complicated
# TODO: separate display and logging options, those CMAEvolutionStrategy
# instances don't use themselves (probably all?)
# TODO: disp method is implemented in CMAEvolutionStrategy and in
# CMADataLogger separately, OOOptimizer.disp_str should return a str
# which can be used uniformly? Only logger can disp a history.
# TODO: check scitools.easyviz and how big the adaptation would be
# TODO: split tell into a variable transformation part and the "pure"
# functionality
# usecase: es.tell_geno(X, [func(es.pheno(x)) for x in X])
# genotypic repair is not part of tell_geno
# TODO: copy_always optional parameter does not make much sense,
# as one can always copy the input argument first,
# however some calls are simpler
# TODO: generalize input logger in optimize() as after_iteration_handler
# (which is logger.add by default)? One difficulty is that
# the logger object is returned (not anymore when return of optimize
# is change). Another difficulty is the obscure usage of modulo
# for writing a final data line in optimize.
# TODO: separate initialize==reset_state from __init__
# TODO: introduce Ypos == diffC which makes the code more consistent and
# the active update "exact"?
# TODO: dynamically read "signals" from a file, see import ConfigParser
# or myproperties.py (to be called after tell())
#
# typical parameters in scipy.optimize: disp, xtol, ftol, maxiter, maxfun,
# callback=None
# maxfev, diag (A sequency of N positive entries that serve as
# scale factors for the variables.)
# full_output -- non-zero to return all optional outputs.
# If xtol < 0.0, xtol is set to sqrt(machine_precision)
# 'infot -- a dictionary of optional outputs with the keys:
# 'nfev': the number of function calls...
#
# see eg fmin_powell
# typical returns
# x, f, dictionary d
# (xopt, {fopt, gopt, Hopt, func_calls, grad_calls, warnflag},
# <allvecs>)
#
# TODO: keep best ten solutions
# TODO: implement constraints handling
# TODO: extend function unitdoctest, or use unittest?
# TODO: apply style guide
# TODO: eigh(): thorough testing would not hurt
# changes:
# 15/01/20: larger condition numbers for C realized by using tf_pheno
# of GenoPheno attribute gp.
# 15/01/19: injection method, first implementation, short injections
# and long injections with good fitness need to be addressed yet
# 15/01/xx: prepare_injection_directions to simplify/centralize injected
# solutions from mirroring and TPA
# 14/12/26: bug fix in correlation_matrix computation if np.diag is a view
# 14/12/06: meta_parameters now only as annotations in ## comments
# 14/12/03: unified use of base class constructor call, now always
# super(ThisClass, self).__init__(args_for_base_class_constructor)
# 14/11/29: termination via "stop now" in file cmaes_signals.par
# 14/11/28: bug fix initialization of C took place before setting the
# seed. Now in some dimensions (e.g. 10) results are (still) not
# determistic due to np.linalg.eigh, in some dimensions (<9, 12)
# they seem to be deterministic.
# 14/11/23: bipop option integration, contributed by Petr Baudis
# 14/09/30: initial_elitism option added to fmin
# 14/08/1x: developing fitness wrappers in FFWrappers class
# 14/08/xx: return value of OOOptimizer.optimize changed to self.
# CMAOptions now need to uniquely match an *initial substring*
# only (via method corrected_key).
# Bug fix in CMAEvolutionStrategy.stop: termination conditions
# are now recomputed iff check and self.countiter > 0.
# Doc corrected that self.gp.geno _is_ applied to x0
# Vaste reorganization/modularization/improvements of plotting
# 14/08/01: bug fix to guaranty pos. def. in active CMA
# 14/06/04: gradient of f can now be used with fmin and/or ask
# 14/05/11: global rcParams['font.size'] not permanently changed anymore,
# a little nicer annotations for the plots
# 14/05/07: added method result_pretty to pretty print optimization result
# 14/05/06: associated show() everywhere with ion() which should solve the
# blocked terminal problem
# 14/05/05: all instances of "unicode" removed (was incompatible to 3.x)
# 14/05/05: replaced type(x) == y with isinstance(x, y), reorganized the
# comments before the code starts
# 14/05/xx: change the order of kwargs of OOOptimizer.optimize,
# remove prepare method in AdaptSigma classes, various changes/cleaning
# 14/03/01: bug fix BoundaryHandlerBase.has_bounds didn't check lower bounds correctly
# bug fix in BoundPenalty.repair len(bounds[0]) was used instead of len(bounds[1])
# bug fix in GenoPheno.pheno, where x was not copied when only boundary-repair was applied
# 14/02/27: bug fixed when BoundPenalty was combined with fixed variables.
# 13/xx/xx: step-size adaptation becomes a class derived from CMAAdaptSigmaBase,
# to make testing different adaptation rules (much) easier
# 12/12/14: separated CMAOptions and arguments to fmin
# 12/10/25: removed useless check_points from fmin interface
# 12/10/17: bug fix printing number of infeasible samples, moved not-in-use methods
# timesCroot and divCroot to the right class
# 12/10/16 (0.92.00): various changes commit: bug bound[0] -> bounds[0], more_to_write fixed,
# sigma_vec introduced, restart from elitist, trace normalization, max(mu,popsize/2)
# is used for weight calculation.
# 12/07/23: (bug:) BoundPenalty.update respects now genotype-phenotype transformation
# 12/07/21: convert value True for noisehandling into 1 making the output compatible
# 12/01/30: class Solution and more old stuff removed r3101
# 12/01/29: class Solution is depreciated, GenoPheno and SolutionDict do the job (v0.91.00, r3100)
# 12/01/06: CMA_eigenmethod option now takes a function (integer still works)
# 11/09/30: flat fitness termination checks also history length
# 11/09/30: elitist option (using method clip_or_fit_solutions)
# 11/09/xx: method clip_or_fit_solutions for check_points option for all sorts of
# injected or modified solutions and even reliable adaptive encoding
# 11/08/19: fixed: scaling and typical_x type clashes 1 vs array(1) vs ones(dim) vs dim * [1]
# 11/07/25: fixed: fmin wrote first and last line even with verb_log==0
# fixed: method settableOptionsList, also renamed to versatileOptions
# default seed depends on time now
# 11/07/xx (0.9.92): added: active CMA, selective mirrored sampling, noise/uncertainty handling
# fixed: output argument ordering in fmin, print now only used as function
# removed: parallel option in fmin
# 11/07/01: another try to get rid of the memory leak by replacing self.unrepaired = self[:]
# 11/07/01: major clean-up and reworking of abstract base classes and of the documentation,
# also the return value of fmin changed and attribute stop is now a method.
# 11/04/22: bug-fix: option fixed_variables in combination with scaling
# 11/04/21: stopdict is not a copy anymore
# 11/04/15: option fixed_variables implemented
# 11/03/23: bug-fix boundary update was computed even without boundaries
# 11/03/12: bug-fix of variable annotation in plots
# 11/02/05: work around a memory leak in numpy
# 11/02/05: plotting routines improved
# 10/10/17: cleaning up, now version 0.9.30
# 10/10/17: bug-fix: return values of fmin now use phenotyp (relevant
# if input scaling_of_variables is given)
# 08/10/01: option evalparallel introduced,
# bug-fix for scaling being a vector
# 08/09/26: option CMAseparable becomes CMA_diagonal
# 08/10/18: some names change, test functions go into a class
# 08/10/24: more refactorizing
# 10/03/09: upper bound exp(min(1,...)) for step-size control
from __future__ import division
# future is >= 3.0, this code has mainly been used with 2.6 & 2.7
from __future__ import with_statement
# only necessary for python 2.5 and not in heavy use
from __future__ import print_function
# available from python 2.6, code should also work without
from __future__ import absolute_import
from __future__ import unicode_literals
# from __future__ import collections.MutableMapping
# does not exist in future, otherwise Python 2.5 would work, since 0.91.01
import sys
if not sys.version.startswith('2'): # in python 3
xrange = range
raw_input = input
basestring = str
else:
input = raw_input # in py2, input(x) == eval(raw_input(x))
import time # not really essential
import collections
import numpy as np
# arange, cos, size, eye, inf, dot, floor, outer, zeros, linalg.eigh,
# sort, argsort, random, ones,...
from numpy import inf, array, dot, exp, log, sqrt, sum, isscalar, isfinite
# to access the built-in sum fct: ``__builtins__.sum`` or ``del sum``
# removes the imported sum and recovers the shadowed build-in
try:
from matplotlib import pyplot
savefig = pyplot.savefig # now we can use cma.savefig() etc
closefig = pyplot.close
def show():
# is_interactive = matplotlib.is_interactive()
pyplot.ion()
pyplot.show()
# if we call now matplotlib.interactive(True), the console is
# blocked
pyplot.ion() # prevents that execution stops after plotting
except:
pyplot = None
savefig = None
closefig = None
def show():
print('pyplot.show() is not available')
print('Could not import matplotlib.pyplot, therefore ``cma.plot()``" +'
' etc. is not available')
__author__ = 'Nikolaus Hansen'
__version__ = "1.1.06 $Revision: 4129 $ $Date: 2015-01-23 20:13:51 +0100 (Fri, 23 Jan 2015) $"
# $Source$ # according to PEP 8 style guides, but what is it good for?
# $Id: cma.py 4129 2015-01-23 19:13:51Z hansen $
# bash $: svn propset svn:keywords 'Date Revision Id' cma.py
__docformat__ = "reStructuredText" # this hides some comments entirely?
__all__ = (
'main',
'fmin',
'fcts',
'Fcts',
'felli',
'rotate',
'pprint',
'plot',
'disp',
'show',
'savefig',
'closefig',
'use_archives',
'is_feasible',
'unitdoctest',
'DerivedDictBase',
'SolutionDict',
'CMASolutionDict',
'BestSolution',
# 'BoundaryHandlerBase',
'BoundNone',
'BoundTransform',
'BoundPenalty',
# 'BoxConstraintsTransformationBase',
# 'BoxConstraintsLinQuadTransformation',
'GenoPheno',
'OOOptimizer',
'CMAEvolutionStrategy',
'CMAOptions',
'CMASolutionDict',
'CMAAdaptSigmaBase',
'CMAAdaptSigmaNone',
'CMAAdaptSigmaDistanceProportional',
'CMAAdaptSigmaCSA',
'CMAAdaptSigmaTPA',
'CMAAdaptSigmaMedianImprovement',
'BaseDataLogger',
'CMADataLogger',
'NoiseHandler',
'Sections',
'Misc',
'Mh',
'ElapsedTime',
'Rotation',
'fcts',
'FFWrappers',
)
use_archives = True # on False some unit tests fail
"""speed up for very large population size. `use_archives` prevents the
need for an inverse gp-transformation, relies on collections module,
not sure what happens if set to ``False``. """
class MetaParameters(object):
"""meta parameters are either "modifiable constants" or refer to
options from ``CMAOptions`` or are arguments to ``fmin`` or to the
``NoiseHandler`` class constructor.
Details
-------
This code contains a single class instance `meta_parameters`
Some interfaces rely on parameters being either `int` or
`float` only. More sophisticated choices are implemented via
``choice_value = {1: 'this', 2: 'or that'}[int_param_value]`` here.
CAVEAT
------
``meta_parameters`` should not be used to determine default
arguments, because these are assigned only once and for all during
module import.
"""
def __init__(self):
self.sigma0 = None ## [~0.01, ~10] # no default available
# learning rates and back-ward time horizons
self.CMA_cmean = 1.0 ## [~0.1, ~10] #
self.c1_multiplier = 1.0 ## [~1e-4, ~20] l
self.cmu_multiplier = 2.0 ## [~1e-4, ~30] l # zero means off
self.CMA_active = 1.0 ## [~1e-4, ~10] l # 0 means off, was CMA_activefac
self.cc_multiplier = 1.0 ## [~0.01, ~20] l
self.cs_multiplier = 1.0 ## [~0.01, ~10] l # learning rate for cs
self.CSA_dampfac = 1.0 ## [~0.01, ~10]
self.CMA_dampsvec_fac = None ## [~0.01, ~100] # def=np.Inf or 0.5, not clear whether this is a log parameter
self.CMA_dampsvec_fade = 0.1 ## [0, ~2]
# exponents for learning rates
self.c1_exponent = 2.0 ## [~1.25, 2]
self.cmu_exponent = 2.0 ## [~1.25, 2]
self.cact_exponent = 1.5 ## [~1.25, 2]
self.cc_exponent = 1.0 ## [~0.25, ~1.25]
self.cs_exponent = 1.0 ## [~0.25, ~1.75] # upper bound depends on CSA_clip_length_value
# selection related parameters
self.lambda_exponent = 0.0 ## [0, ~2.5] # usually <= 2, used by adding N**lambda_exponent to popsize-1
self.parent_fraction = 0.5 ## [0, 1] # default is weighted recombination
self.CMA_elitist = 0 ## [0, 2] i # a choice variable
self.CMA_mirrors = 0.0 ## [0, 0.5) # values <0.5 are interpreted as fraction, values >1 as numbers (rounded), otherwise about 0.16 is used',
# sampling strategies
self.CMA_sample_on_sphere_surface = 0 ## [0, 1] i # boolean
self.mean_shift_line_samples = 0 ## [0, 1] i # boolean
self.pc_line_samples = 0 ## [0, 1] i # boolean
# step-size adapation related parameters
self.CSA_damp_mueff_exponent = 0.5 ## [~0.25, ~1.5] # zero would mean no dependency of damping on mueff, useful with CSA_disregard_length option',
self.CSA_disregard_length = 0 ## [0, 1] i
self.CSA_squared = 0 ## [0, 1] i
self.CSA_clip_length_value = None ## [0, ~20] # None reflects inf
# noise handling
self.noise_reeval_multiplier = 1.0 ## [0.2, 4] # usually 2 offspring are reevaluated
self.noise_choose_reeval = 1 ## [1, 3] i # which ones to reevaluate
self.noise_theta = 0.5 ## [~0.05, ~0.9]
self.noise_alphasigma = 2.0 ## [0, 10]
self.noise_alphaevals = 2.0 ## [0, 10]
self.noise_alphaevalsdown_exponent = -0.25 ## [-1.5, 0]
self.noise_aggregate = None ## [1, 2] i # None and 0 == default or user option choice, 1 == median, 2 == mean
# TODO: more noise handling options (maxreevals...)
# restarts
self.restarts = 0 ## [0, ~30] # but depends on popsize inc
self.restart_from_best = 0 ## [0, 1] i # bool
self.incpopsize = 2.0 ## [~1, ~5]
# termination conditions (for restarts)
self.maxiter_multiplier = 1.0 ## [~0.01, ~100] l
self.mindx = 0.0 ## [1e-17, ~1e-3] l #v minimal std in any direction, cave interference with tol*',
self.minstd = 0.0 ## [1e-17, ~1e-3] l #v minimal std in any coordinate direction, cave interference with tol*',
self.maxstd = None ## [~1, ~1e9] l #v maximal std in any coordinate direction, default is inf',
self.tolfacupx = 1e3 ## [~10, ~1e9] l #v termination when step-size increases by tolfacupx (diverges). That is, the initial step-size was chosen far too small and better solutions were found far away from the initial solution x0',
self.tolupsigma = 1e20 ## [~100, ~1e99] l #v sigma/sigma0 > tolupsigma * max(sqrt(eivenvals(C))) indicates "creeping behavior" with usually minor improvements',
self.tolx = 1e-11 ## [1e-17, ~1e-3] l #v termination criterion: tolerance in x-changes',
self.tolfun = 1e-11 ## [1e-17, ~1e-3] l #v termination criterion: tolerance in function value, quite useful',
self.tolfunhist = 1e-12 ## [1e-17, ~1e-3] l #v termination criterion: tolerance in function value history',
self.tolstagnation_multiplier = 1.0 ## [0.01, ~100] # ': 'int(100 + 100 * N**1.5 / popsize) #v termination if no improvement over tolstagnation iterations',
# abandoned:
# self.noise_change_sigma_exponent = 1.0 ## [0, 2]
# self.noise_epsilon = 1e-7 ## [0, ~1e-2] l #
# self.maxfevals = None ## [1, ~1e11] l # is not a performance parameter
# self.cc_mu_multiplier = 1 ## [0, ~10] # AKA alpha_cc
# self.lambda_log_multiplier = 3 ## [0, ~10]
# self.lambda_multiplier = 0 ## (0, ~10]
meta_parameters = MetaParameters()
# emptysets = ('', (), [], {})
# array([]) does not work but np.size(.) == 0
# here is the problem:
# bool(array([0])) is False
# bool(list(array([0]))) is True
# bool(list(array([0, 1]))) is True
# bool(array([0, 1])) raises ValueError
#
# "x in emptysets" cannot be well replaced by "not x"
# which is also True for array([]) and None, but also for 0 and False,
# and False for NaN, and an exception for array([0,1]), see also
# http://google-styleguide.googlecode.com/svn/trunk/pyguide.html#True/False_evaluations
# ____________________________________________________________
# ____________________________________________________________
#
def rglen(ar):
"""shortcut for the iterator ``xrange(len(ar))``"""
return xrange(len(ar))
def is_feasible(x, f):
"""default to check feasibility, see also ``cma_default_options``"""
return f is not None and f is not np.NaN
global_verbosity = 1
def _print_warning(msg, method_name=None, class_name=None, iteration=None,
verbose=None):
if verbose is None:
verbose = global_verbosity
if verbose > 0:
print('WARNING (module=' + __name__ +
(', class=' + str(class_name) if class_name else '') +
(', method=' + str(method_name) if method_name else '') +
(', iteration=' + str(iteration) if iteration else '') +
'): ', msg)
# ____________________________________________________________
# ____________________________________________________________
#
def unitdoctest():
"""is used to describe test cases and might in future become helpful
as an experimental tutorial as well. The main testing feature at the
moment is by doctest with ``cma._test()`` or conveniently by
``python cma.py --test``. With the ``--verbose`` option added, the
results will always slightly differ and many "failed" test cases
might be reported.
A simple first overall test:
>>> import cma
>>> res = cma.fmin(cma.fcts.elli, 3*[1], 1,
... {'CMA_diagonal':2, 'seed':1, 'verb_time':0})
(3_w,7)-CMA-ES (mu_w=2.3,w_1=58%) in dimension 3 (seed=1)
Covariance matrix is diagonal for 2 iterations (1/ccov=7.0)
Iterat #Fevals function value axis ratio sigma minstd maxstd min:sec
1 7 1.453161670768570e+04 1.2e+00 1.08e+00 1e+00 1e+00
2 14 3.281197961927601e+04 1.3e+00 1.22e+00 1e+00 2e+00
3 21 1.082851071704020e+04 1.3e+00 1.24e+00 1e+00 2e+00
100 700 8.544042012075362e+00 1.4e+02 3.18e-01 1e-03 2e-01
200 1400 5.691152415221861e-12 1.0e+03 3.82e-05 1e-09 1e-06
220 1540 3.890107746209078e-15 9.5e+02 4.56e-06 8e-11 7e-08
termination on tolfun : 1e-11
final/bestever f-value = 3.89010774621e-15 2.52273602735e-15
mean solution: [ -4.63614606e-08 -3.42761465e-10 1.59957987e-11]
std deviation: [ 6.96066282e-08 2.28704425e-09 7.63875911e-11]
Test on the Rosenbrock function with 3 restarts. The first trial only
finds the local optimum, which happens in about 20% of the cases.
>>> import cma
>>> res = cma.fmin(cma.fcts.rosen, 4*[-1], 1,
... options={'ftarget':1e-6, 'verb_time':0,
... 'verb_disp':500, 'seed':3},
... restarts=3)
(4_w,8)-CMA-ES (mu_w=2.6,w_1=52%) in dimension 4 (seed=3)
Iterat #Fevals function value axis ratio sigma minstd maxstd min:sec
1 8 4.875315645656848e+01 1.0e+00 8.43e-01 8e-01 8e-01
2 16 1.662319948123120e+02 1.1e+00 7.67e-01 7e-01 8e-01
3 24 6.747063604799602e+01 1.2e+00 7.08e-01 6e-01 7e-01
184 1472 3.701428610430019e+00 4.3e+01 9.41e-07 3e-08 5e-08
termination on tolfun : 1e-11
final/bestever f-value = 3.70142861043 3.70142861043
mean solution: [-0.77565922 0.61309336 0.38206284 0.14597202]
std deviation: [ 2.54211502e-08 3.88803698e-08 4.74481641e-08 3.64398108e-08]
(8_w,16)-CMA-ES (mu_w=4.8,w_1=32%) in dimension 4 (seed=4)
Iterat #Fevals function value axis ratio sigma minstd maxstd min:sec
1 1489 2.011376859371495e+02 1.0e+00 8.90e-01 8e-01 9e-01
2 1505 4.157106647905128e+01 1.1e+00 8.02e-01 7e-01 7e-01
3 1521 3.548184889359060e+01 1.1e+00 1.02e+00 8e-01 1e+00
111 3249 6.831867555502181e-07 5.1e+01 2.62e-02 2e-04 2e-03
termination on ftarget : 1e-06
final/bestever f-value = 6.8318675555e-07 1.18576673231e-07
mean solution: [ 0.99997004 0.99993938 0.99984868 0.99969505]
std deviation: [ 0.00018973 0.00038006 0.00076479 0.00151402]
>>> assert res[1] <= 1e-6
Notice the different termination conditions. Termination on the target
function value ftarget prevents further restarts.
Test of scaling_of_variables option
>>> import cma
>>> opts = cma.CMAOptions()
>>> opts['seed'] = 456
>>> opts['verb_disp'] = 0
>>> opts['CMA_active'] = 1
>>> # rescaling of third variable: for searching in roughly
>>> # x0 plus/minus 1e3*sigma0 (instead of plus/minus sigma0)
>>> opts['scaling_of_variables'] = [1, 1, 1e3, 1]
>>> res = cma.fmin(cma.fcts.rosen, 4 * [0.1], 0.1, opts)
termination on tolfun : 1e-11
final/bestever f-value = 2.68096173031e-14 1.09714829146e-14
mean solution: [ 1.00000001 1.00000002 1.00000004 1.00000007]
std deviation: [ 3.00466854e-08 5.88400826e-08 1.18482371e-07 2.34837383e-07]
The printed std deviations reflect the actual value in the parameters
of the function (not the one in the internal representation which
can be different).
Test of CMA_stds scaling option.
>>> import cma
>>> opts = cma.CMAOptions()
>>> s = 5 * [1]
>>> s[0] = 1e3
>>> opts.set('CMA_stds', s)
>>> opts.set('verb_disp', 0)
>>> res = cma.fmin(cma.fcts.cigar, 5 * [0.1], 0.1, opts)
>>> assert res[1] < 1800
:See: cma.main(), cma._test()
"""
pass
class _BlancClass(object):
"""blanc container class for having a collection of attributes,
that might/should at some point become a more tailored class"""
if use_archives:
class DerivedDictBase(collections.MutableMapping):
"""for conveniently adding "features" to a dictionary. The actual
dictionary is in ``self.data``. Copy-paste
and modify setitem, getitem, and delitem, if necessary.
Details: This is the clean way to subclass build-in dict.
"""
def __init__(self, *args, **kwargs):
# collections.MutableMapping.__init__(self)
super(DerivedDictBase, self).__init__()
# super(SolutionDict, self).__init__() # the same
self.data = dict()
self.data.update(dict(*args, **kwargs))
def __len__(self):
return len(self.data)
def __contains__(self, key):
return key in self.data
def __iter__(self):
return iter(self.data)
def __setitem__(self, key, value):
"""defines self[key] = value"""
self.data[key] = value
def __getitem__(self, key):
"""defines self[key]"""
return self.data[key]
def __delitem__(self, key):
del self.data[key]
class SolutionDict(DerivedDictBase):
"""dictionary with computation of an hash key.
The hash key is generated from the inserted solution and a stack of
previously inserted same solutions is provided. Each entry is meant
to store additional information related to the solution.
>>> import cma, numpy as np
>>> d = cma.SolutionDict()
>>> x = np.array([1,2,4])
>>> d[x] = {'f': sum(x**2), 'iteration': 1}
>>> assert d[x]['iteration'] == 1
>>> assert d.get(x) == (d[x] if d.key(x) in d.keys() else None)
TODO: data_with_same_key behaves like a stack (see setitem and
delitem), but rather should behave like a queue?! A queue is less
consistent with the operation self[key] = ..., if
self.data_with_same_key[key] is not empty.
TODO: iteration key is used to clean up without error management
"""
def __init__(self, *args, **kwargs):
# DerivedDictBase.__init__(self, *args, **kwargs)
super(SolutionDict, self).__init__(*args, **kwargs)
self.data_with_same_key = {}
self.last_iteration = 0
def key(self, x):
try:
return tuple(x)
# using sum(x) is slower, using x[0] is slightly faster
except TypeError:
return x
def __setitem__(self, key, value):
"""defines self[key] = value"""
key = self.key(key)
if key in self.data_with_same_key:
self.data_with_same_key[key] += [self.data[key]]
elif key in self.data:
self.data_with_same_key[key] = [self.data[key]]
self.data[key] = value
def __getitem__(self, key): # 50% of time of
"""defines self[key]"""
return self.data[self.key(key)]
def __delitem__(self, key):
"""remove only most current key-entry"""
key = self.key(key)
if key in self.data_with_same_key:
if len(self.data_with_same_key[key]) == 1:
self.data[key] = self.data_with_same_key.pop(key)[0]
else:
self.data[key] = self.data_with_same_key[key].pop(-1)
else:
del self.data[key]
def truncate(self, max_len, min_iter):
if len(self) > max_len:
for k in list(self.keys()):
if self[k]['iteration'] < min_iter:
del self[k]
# deletes one item with k as key, better delete all?
class CMASolutionDict(SolutionDict):
def __init__(self, *args, **kwargs):
# SolutionDict.__init__(self, *args, **kwargs)
super(CMASolutionDict, self).__init__(*args, **kwargs)
self.last_solution_index = 0
# TODO: insert takes 30% of the overall CPU time, mostly in def key()
# with about 15% of the overall CPU time
def insert(self, key, geno=None, iteration=None, fitness=None, value=None):
"""insert an entry with key ``key`` and value
``value if value is not None else {'geno':key}`` and
``self[key]['kwarg'] = kwarg if kwarg is not None`` for the further kwargs.
"""
# archive returned solutions, first clean up archive
if iteration is not None and iteration > self.last_iteration and (iteration % 10) < 1:
self.truncate(300, iteration - 3)
elif value is not None and value.get('iteration'):
iteration = value['iteration']
if (iteration % 10) < 1:
self.truncate(300, iteration - 3)
self.last_solution_index += 1
if value is not None:
try:
iteration = value['iteration']
except:
pass
if iteration is not None:
if iteration > self.last_iteration:
self.last_solution_index = 0
self.last_iteration = iteration
else:
iteration = self.last_iteration + 0.5 # a hack to get a somewhat reasonable value
if value is not None:
self[key] = value
else:
self[key] = {'pheno': key}
if geno is not None:
self[key]['geno'] = geno
if iteration is not None:
self[key]['iteration'] = iteration
if fitness is not None:
self[key]['fitness'] = fitness
return self[key]
if not use_archives:
class CMASolutionDict(dict):
"""a hack to get most code examples running"""
def insert(self, *args, **kwargs):
pass
def get(self, key):
return None
def __getitem__(self, key):
return None
def __setitem__(self, key, value):
pass
class BestSolution(object):
"""container to keep track of the best solution seen"""
def __init__(self, x=None, f=np.inf, evals=None):
"""initialize the best solution with `x`, `f`, and `evals`.
Better solutions have smaller `f`-values.
"""
self.x = x
self.x_geno = None
self.f = f if f is not None and f is not np.nan else np.inf
self.evals = evals
self.evalsall = evals
self.last = _BlancClass()
self.last.x = x
self.last.f = f
def update(self, arx, xarchive=None, arf=None, evals=None):
"""checks for better solutions in list `arx`.
Based on the smallest corresponding value in `arf`,
alternatively, `update` may be called with a `BestSolution`
instance like ``update(another_best_solution)`` in which case
the better solution becomes the current best.
`xarchive` is used to retrieve the genotype of a solution.
"""
if isinstance(arx, BestSolution):
if self.evalsall is None:
self.evalsall = arx.evalsall
elif arx.evalsall is not None:
self.evalsall = max((self.evalsall, arx.evalsall))
if arx.f is not None and arx.f < np.inf:
self.update([arx.x], xarchive, [arx.f], arx.evals)
return self
assert arf is not None
# find failsave minimum
minidx = np.nanargmin(arf)
if minidx is np.nan:
return
minarf = arf[minidx]
# minarf = reduce(lambda x, y: y if y and y is not np.nan
# and y < x else x, arf, np.inf)
if minarf < np.inf and (minarf < self.f or self.f is None):
self.x, self.f = arx[minidx], arf[minidx]
if xarchive is not None and xarchive.get(self.x) is not None:
self.x_geno = xarchive[self.x].get('geno')
else:
self.x_geno = None
self.evals = None if not evals else evals - len(arf) + minidx + 1
self.evalsall = evals
elif evals:
self.evalsall = evals
self.last.x = arx[minidx]
self.last.f = minarf
def get(self):
"""return ``(x, f, evals)`` """
return self.x, self.f, self.evals # , self.x_geno
# ____________________________________________________________
# ____________________________________________________________
#
class BoundaryHandlerBase(object):
"""hacked base class """
def __init__(self, bounds):
"""bounds are not copied, but possibly modified and
put into a normalized form: ``bounds`` can be ``None``
or ``[lb, ub]`` where ``lb`` and ``ub`` are
either None or a vector (which can have ``None`` entries).
Generally, the last entry is recycled to compute bounds
for any dimension.
"""
if not bounds:
self.bounds = None
else:
l = [None, None] # figure out lenths
for i in [0, 1]:
try:
l[i] = len(bounds[i])
except TypeError:
bounds[i] = [bounds[i]]
l[i] = 1
if all([bounds[i][j] is None or not isfinite(bounds[i][j])
for j in rglen(bounds[i])]):
bounds[i] = None
if bounds[i] is not None and any([bounds[i][j] == (-1)**i * np.inf
for j in rglen(bounds[i])]):
raise ValueError('lower/upper is +inf/-inf and ' +
'therefore no finite feasible solution is available')
self.bounds = bounds
def __call__(self, solutions, *args, **kwargs):
"""return penalty or list of penalties, by default zero(s).
This interface seems too specifically tailored to the derived
BoundPenalty class, it should maybe change.
"""
if isscalar(solutions[0]):
return 0.0
else:
return len(solutions) * [0.0]
def update(self, *args, **kwargs):
return self
def repair(self, x, copy_if_changed=True, copy_always=False):
"""projects infeasible values on the domain bound, might be
overwritten by derived class """
if copy_always:
x = array(x, copy=True)
copy = False
else:
copy = copy_if_changed
if self.bounds is None:
return x
for ib in [0, 1]:
if self.bounds[ib] is None:
continue
for i in rglen(x):
idx = min([i, len(self.bounds[ib]) - 1])
if self.bounds[ib][idx] is not None and \
(-1)**ib * x[i] < (-1)**ib * self.bounds[ib][idx]:
if copy:
x = array(x, copy=True)
copy = False
x[i] = self.bounds[ib][idx]
def inverse(self, y, copy_if_changed=True, copy_always=False):
return y if not copy_always else array(y, copy=True)
def get_bounds(self, which, dimension):
"""``get_bounds('lower', 8)`` returns the lower bounds in 8-D"""
if which == 'lower' or which == 0:
return self._get_bounds(0, dimension)
elif which == 'upper' or which == 1:
return self._get_bounds(1, dimension)
else:
raise ValueError("argument which must be 'lower' or 'upper'")
def _get_bounds(self, ib, dimension):
"""ib == 0/1 means lower/upper bound, return a vector of length
`dimension` """
sign_ = 2 * ib - 1
assert sign_**2 == 1
if self.bounds is None or self.bounds[ib] is None:
return array(dimension * [sign_ * np.Inf])
res = []
for i in xrange(dimension):
res.append(self.bounds[ib][min([i, len(self.bounds[ib]) - 1])])
if res[-1] is None:
res[-1] = sign_ * np.Inf
return array(res)
def has_bounds(self):
"""return True, if any variable is bounded"""
bounds = self.bounds
if bounds in (None, [None, None]):
return False
for ib, bound in enumerate(bounds):
if bound is not None:
sign_ = 2 * ib - 1
for bound_i in bound:
if bound_i is not None and sign_ * bound_i < np.inf:
return True
return False
def is_in_bounds(self, x):
"""not yet tested"""
if self.bounds is None:
return True
for ib in [0, 1]:
if self.bounds[ib] is None:
continue
for i in rglen(x):
idx = min([i, len(self.bounds[ib]) - 1])
if self.bounds[ib][idx] is not None and \
(-1)**ib * x[i] < (-1)**ib * self.bounds[ib][idx]:
return False
return True
def to_dim_times_two(self, bounds):
"""return boundaries in format ``[[lb0, ub0], [lb1, ub1], ...]``,
as used by ``BoxConstraints...`` class.
"""
if not bounds:
b = [[None, None]]
else:
l = [None, None] # figure out lenths
for i in [0, 1]:
try:
l[i] = len(bounds[i])
except TypeError:
bounds[i] = [bounds[i]]
l[i] = 1
b = [] # bounds in different format
try:
for i in xrange(max(l)):
b.append([bounds[0][i] if i < l[0] else None,
bounds[1][i] if i < l[1] else None])