1 /* --------------------------------------------------------- */
2 /* --- File: cmaes.c -------- Author: Nikolaus Hansen --- */
3 /* --------------------------------------------------------- */
4 /*
5 CMA-ES for non-linear function minimization.
6
7 Copyright 1996, 2003, 2007, 2013 Nikolaus Hansen
8 e-mail: hansen .AT. lri.fr
9
10 SOURCE:
11 https://github.com/cma-es/c-cma-es
12 https://github.com/cma-es/c-cma-es/blob/master/src/cmaes.c
13
14 LICENSE: this library is free/open software and may be used
15 either under the
16
17 Apache License 2.0
18
19 or under the
20
21 GNU Lesser General Public License 2.1 or later
22
23 whichever suits best.
24
25 See also the LICENSE file
26 https://github.com/cma-es/c-cma-es/blob/master/LICENSE
27 */
28
29 /* --- Changes : ---
30 03/03/21: argument const double *rgFunVal of
31 cmaes_ReestimateDistribution() was treated incorrectly.
32 03/03/29: restart via cmaes_resume_distribution() implemented.
33 03/03/30: Always max std dev / largest axis is printed first.
34 03/08/30: Damping is adjusted for large mueff.
35 03/10/30: Damping is adjusted for large mueff always.
36 04/04/22: Cumulation time and damping for step size adjusted.
37 No iniphase but conditional update of pc.
38 05/03/15: in ccov-setting mucov replaced by mueff.
39 05/10/05: revise comment on resampling in example.c
40 05/10/13: output of "coorstddev" changed from sigma * C[i][i]
41 to correct sigma * sqrt(C[i][i]).
42 05/11/09: Numerical problems are not anymore handled by increasing
43 sigma, but lead to satisfy a stopping criterion in
44 cmaes_Test().
45 05/11/09: Update of eigensystem and test for numerical problems
46 moved right before sampling.
47 06/02/24: Non-ansi array definitions replaced (thanks to Marc
48 Toussaint).
49 06/02/25: Overflow in time measurement for runs longer than
50 2100 seconds. This could lead to stalling the
51 covariance matrix update for long periods.
52 Time measurement completely rewritten.
53 06/02/26: Included population size lambda as parameter to
54 cmaes_init (thanks to MT).
55 06/02/26: Allow no initial reading/writing of parameters via
56 "non" and "writeonly" keywords for input parameter
57 filename in cmaes_init.
58 06/02/27: Optimized code regarding time spent in updating the
59 covariance matrix in function Adapt_C2().
60 07/08/03: clean up and implementation of an exhaustive test
61 of the eigendecomposition (via #ifdef for now)
62 07/08/04: writing of output improved
63 07/08/xx: termination criteria revised and more added,
64 damp replaced by damps=damp*cs, documentation improved.
65 Interface significantly changed, evaluateSample function
66 and therefore the function pointer argument removed.
67 Renaming of functions in accordance with Java code.
68 Clean up of parameter names, mainly in accordance with
69 Matlab conventions. Most termination criteria can be
70 changed online now. Many more small changes, but not in
71 the core procedure.
72 07/10/29: ReSampleSingle() got a better interface. ReSampleSingle()
73 is now ReSampleSingle_old only for backward
74 compatibility. Also fixed incorrect documentation. The new
75 function SampleSingleInto() has an interface similar to
76 the old ReSampleSingle(), but is not really necessary.
77 07/11/20: bug: stopMaxIter did not translate into the correct default
78 value but into -1 as default. This lead to a too large
79 damps and the termination test became true from the first
80 iteration. (Thanks to Michael Calonder)
81 07/11/20: new default stopTolFunHist = 1e-13; (instead of zero)
82 08/09/26: initial diagonal covariance matrix in code, but not
83 yet in interface
84 08/09/27: diagonalCovarianceMatrix option in initials.par provided
85 08/10/17: uncertainty handling implemented in example3.c.
86 PerturbSolutionInto() provides the optional small
87 perturbations before reevaluation.
88 10/10/16: TestForTermination changed such that diagonalCovarianceMatrix
89 option now yields linear time behavior
90 12/05/28: random seed > 2e9 prohibited to avoid an infinite loop on 32bit systems
91 12/10/21: input parameter file values "no", "none" now work as "non".
92 12/10/xx: tentative implementation of cmaes_Optimize
93 12/10/xx: some small changes with char * mainly to prevent warnings in C++
94 12/10/xx: added some string convenience functions isNoneStr, new_string, assign_string
95 13/01/03: rename files example?, initials.par, signals.par
96 14/04/29: removed bug, au = t->al[...], from the (new) boundary handling
97 code (thanks to Emmanuel Benazera for the hint)
98 14/06/16: test of un-initialized version number removed (thanks to Paul Zimmermann)
99 14/10/18: splitted cmaes_init() into cmaes_init_para() and cmaes_init_final(),
100 such that parameters can be set also comparatively safely within the
101 code, namely after calling cmaes_init_para(). The order of parameters
102 of readpara_init() has changed to be the same as for cmaes_init().
103 14/11/25 fix warnings from Microsoft C compiler (sherm)
104 14/11/26: renamed exported symbols so they begin with a cmaes_prefix.
105
106 Wish List
107 o make signals_filename part of cmaes_t using assign_string()
108
109 o as writing time is measure for all files at once, the display
110 cannot be independently written to a file via signals.par, while
111 this would be desirable.
112
113 o clean up sorting of eigenvalues and vectors which is done repeatedly.
114
115 o either use cmaes_Get() in cmaes_WriteToFilePtr(): revise the
116 cmaes_write that all keywords available with get and getptr are
117 recognized. Also revise the keywords, keeping backward
118 compatibility. (not only) for this it would be useful to find a
119 way how cmaes_Get() signals an unrecognized keyword. For GetPtr
120 it can return NULL.
121
122 o or break cmaes_Get() into single getter functions, being a nicer
123 interface, and compile instead of runtime error, and faster. For
124 file signals.par it does not help.
125
126 o writing data depending on timing in a smarter way, e.g. using 10%
127 of all time. First find out whether clock() is useful for measuring
128 disc writing time and then cmaes_timings_t class can be utilized.
129 For very large dimension the default of 1 seconds waiting might
130 be too small.
131
132 o allow modification of best solution depending on delivered f(xmean)
133
134 o re-write input and output procedures
135 */
136
137 /* Prevent Microsoft compiler from complaining that common library functions
138 like strncpy(), ctime(), sprintf(), fopen(), fscanf(), etc. "may be unsafe".
139 This must come before the first #include.
140 */
141 #ifdef _MSC_VER
142 #define _CRT_SECURE_NO_WARNINGS
143 #endif
144
145 #include <math.h> /* sqrt() */
146 #include <stddef.h> /* size_t */
147 #include <stdlib.h> /* NULL, free */
148 #include <string.h> /* strlen() */
149 #include <stdio.h> /* sprintf(), NULL? */
150 #include "cmaes_interface.h" /* <time.h> via cmaes.h */
151
152 /* --------------------------------------------------------- */
153 /* ------------------- Declarations ------------------------ */
154 /* --------------------------------------------------------- */
155
156 /* ------------------- External Visibly -------------------- */
157
158 /* see cmaes_interface.h for those, not listed here */
159
160 long cmaes_random_init(cmaes_random_t *, long unsigned seed /* 0==clock */);
161 void cmaes_random_exit(cmaes_random_t *);
162 double cmaes_random_Gauss(cmaes_random_t *); /* (0,1)-normally distributed */
163 double cmaes_random_Uniform(cmaes_random_t *);
164 long cmaes_random_Start(cmaes_random_t *, long unsigned seed /* 0==1 */);
165
166 void cmaes_timings_init(cmaes_timings_t *timing);
167 void cmaes_timings_start(cmaes_timings_t *timing); /* fields totaltime and tictoctime */
168 double cmaes_timings_update(cmaes_timings_t *timing);
169 void cmaes_timings_tic(cmaes_timings_t *timing);
170 double cmaes_timings_toc(cmaes_timings_t *timing);
171
172 void cmaes_readpara_init (cmaes_readpara_t *, int dim, const double * xstart,
173 const double * sigma, int seed, int lambda,
174 const char * filename);
175 void cmaes_readpara_exit(cmaes_readpara_t *);
176 void cmaes_readpara_ReadFromFile(cmaes_readpara_t *, const char *szFileName);
177 void cmaes_readpara_SupplementDefaults(cmaes_readpara_t *);
178 void cmaes_readpara_SetWeights(cmaes_readpara_t *, const char * mode);
179 void cmaes_readpara_WriteToFile(cmaes_readpara_t *, const char *filenamedest);
180
181 const double * cmaes_Optimize( cmaes_t *, double(*pFun)(double const *, int dim),
182 long iterations);
183 double const * cmaes_SetMean(cmaes_t *, const double *xmean);
184 double * cmaes_PerturbSolutionInto(cmaes_t *t, double *xout,
185 double const *xin, double eps);
186 void cmaes_WriteToFile(cmaes_t *, const char *key, const char *name);
187 void cmaes_WriteToFileAW(cmaes_t *t, const char *key, const char *name,
188 const char * append);
189 void cmaes_WriteToFilePtr(cmaes_t *, const char *key, FILE *fp);
190 void cmaes_ReadFromFilePtr(cmaes_t *, FILE *fp);
191 void cmaes_FATAL(char const *s1, char const *s2,
192 char const *s3, char const *s4);
193
194
195 /* ------------------- Locally visibly ----------------------- */
196
197 static char * getTimeStr(void);
198 static void TestMinStdDevs( cmaes_t *);
199 /* static void WriteMaxErrorInfo( cmaes_t *); */
200
201 static void Eigen( int N, double **C, double *diag, double **Q,
202 double *rgtmp);
203 static int Check_Eigen( int N, double **C, double *diag, double **Q);
204 static void QLalgo2 (int n, double *d, double *e, double **V);
205 static void Householder2(int n, double **V, double *d, double *e);
206 static void Adapt_C2(cmaes_t *t, int hsig);
207
208 static void FATAL(char const *sz1, char const *s2,
209 char const *s3, char const *s4);
210 static void ERRORMESSAGE(char const *sz1, char const *s2,
211 char const *s3, char const *s4);
212 static int isNoneStr(const char * filename);
213 static void Sorted_index( const double *rgFunVal, int *index, int n);
214 static int SignOfDiff( const void *d1, const void * d2);
215 static double douSquare(double);
216 static double rgdouMax( const double *rgd, int len);
217 static double rgdouMin( const double *rgd, int len);
218 static double douMax( double d1, double d2);
219 static double douMin( double d1, double d2);
220 static int intMin( int i, int j);
221 static int MaxIdx( const double *rgd, int len);
222 static int MinIdx( const double *rgd, int len);
223 static double myhypot(double a, double b);
224 static double * new_double( int n);
225 static void * new_void( int n, size_t size);
226 static char * new_string( const char *);
227 static void assign_string( char **, const char*);
228
229 static const char * c_cmaes_version = "3.20.00.beta";
230
231 /* --------------------------------------------------------- */
232 /* ---------------- Functions: cmaes_t --------------------- */
233 /* --------------------------------------------------------- */
234
235 static char *
getTimeStr(void)236 getTimeStr(void) {
237 time_t tm = time(NULL);
238 static char s[33];
239
240 /* get time */
241 strncpy(s, ctime(&tm), 24); /* TODO: hopefully we read something useful */
242 s[24] = '\0'; /* cut the \n */
243 return s;
244 }
245
246 char *
cmaes_SayHello(cmaes_t * t)247 cmaes_SayHello(cmaes_t *t)
248 {
249 /* write initial message */
250 sprintf(t->sOutString,
251 "(%d,%d)-CMA-ES(mu_eff=%.1f), Ver=\"%s\", dimension=%d, diagonalIterations=%ld, randomSeed=%d (%s)",
252 t->sp.mu, t->sp.lambda, t->sp.mueff, t->version, t->sp.N, (long)t->sp.diagonalCov,
253 t->sp.seed, getTimeStr());
254
255 return t->sOutString;
256 }
257
258 /* --------------------------------------------------------- */
259 /* --------------------------------------------------------- */
260 void
cmaes_init_para(cmaes_t * t,int dimension,double * inxstart,double * inrgstddev,long int inseed,int lambda,const char * input_parameter_filename)261 cmaes_init_para(cmaes_t *t, /* "this" */
262 int dimension,
263 double *inxstart,
264 double *inrgstddev, /* initial stds */
265 long int inseed,
266 int lambda,
267 const char *input_parameter_filename)
268 {
269 t->version = c_cmaes_version;
270 cmaes_readpara_init(&t->sp, dimension, inxstart, inrgstddev, inseed,
271 lambda, input_parameter_filename);
272 }
273
274 double *
cmaes_init_final(cmaes_t * t)275 cmaes_init_final(cmaes_t *t /* "this" */)
276 /*
277 * */
278 {
279 int i, j, N;
280 double dtest, trace;
281
282 if (t->version == NULL) {
283 ERRORMESSAGE("cmaes_init_final called (probably) without calling cmaes_init_para first",
284 ", which will likely lead to unexpected results",0,0);
285 printf("Warning: cmaes_init_final called (probably) without calling cmaes_init_para first\n");
286 }
287 if (strcmp(c_cmaes_version, t->version) != 0) {
288 ERRORMESSAGE("cmaes_init_final called twice, which will lead to a memory leak",
289 "; use cmaes_exit() first",0,0);
290 printf("Warning: cmaes_init_final called twice, which will lead to a memory leak; use cmaes_exit first\n");
291 }
292 /* assign_string(&t->signalsFilename, "cmaes_signals.par"); */
293
294 if (!t->sp.flgsupplemented) {
295 cmaes_readpara_SupplementDefaults(&t->sp);
296 if (!isNoneStr(t->sp.filename))
297 cmaes_readpara_WriteToFile(&t->sp, "actparcmaes.par");
298 }
299
300 t->sp.seed = cmaes_random_init( &t->rand, (long unsigned int) t->sp.seed);
301
302 N = t->sp.N; /* for convenience */
303
304 /* initialization */
305 for (i = 0, trace = 0.; i < N; ++i)
306 trace += t->sp.rgInitialStds[i]*t->sp.rgInitialStds[i];
307 t->sigma = sqrt(trace/N); /* t->sp.mueff/(0.2*t->sp.mueff+sqrt(N)) * sqrt(trace/N); */
308
309 t->chiN = sqrt((double) N) * (1. - 1./(4.*N) + 1./(21.*N*N));
310 t->flgEigensysIsUptodate = 1;
311 t->flgCheckEigen = 0;
312 t->genOfEigensysUpdate = 0;
313 cmaes_timings_init(&t->eigenTimings);
314 t->flgIniphase = 0; /* do not use iniphase, hsig does the job now */
315 t->flgresumedone = 0;
316 t->flgStop = 0;
317
318 for (dtest = 1.; dtest && dtest < 1.1 * dtest; dtest *= 2.)
319 if (dtest == dtest + 1.)
320 break;
321 t->dMaxSignifKond = dtest / 1000.; /* not sure whether this is really save, 100 does not work well enough */
322
323 t->gen = 0;
324 t->countevals = 0;
325 t->state = 0;
326 t->dLastMinEWgroesserNull = 1.0;
327 t->printtime = t->writetime = t->firstwritetime = t->firstprinttime = 0;
328
329 t->rgpc = new_double(N);
330 t->rgps = new_double(N);
331 t->rgdTmp = new_double(N+1);
332 t->rgBDz = new_double(N);
333 t->rgxmean = new_double(N+2); t->rgxmean[0] = N; ++t->rgxmean;
334 t->rgxold = new_double(N+2); t->rgxold[0] = N; ++t->rgxold;
335 t->rgxbestever = new_double(N+3); t->rgxbestever[0] = N; ++t->rgxbestever;
336 t->rgout = new_double(N+2); t->rgout[0] = N; ++t->rgout;
337 t->rgD = new_double(N);
338 t->C = (double**)new_void(N, sizeof(double*));
339 t->B = (double**)new_void(N, sizeof(double*));
340 t->publicFitness = new_double(t->sp.lambda);
341 t->rgFuncValue = new_double(t->sp.lambda+1);
342 t->rgFuncValue[0]=t->sp.lambda; ++t->rgFuncValue;
343 t->arFuncValueHist = new_double(10+(int)ceil(3.*10.*N/t->sp.lambda)+1);
344 t->arFuncValueHist[0] = (double)(10+(int)ceil(3.*10.*N/t->sp.lambda));
345 t->arFuncValueHist++;
346
347 for (i = 0; i < N; ++i) {
348 t->C[i] = new_double(i+1);
349 t->B[i] = new_double(N);
350 }
351 t->index = (int *) new_void(t->sp.lambda, sizeof(int));
352 for (i = 0; i < t->sp.lambda; ++i)
353 t->index[i] = i; /* should not be necessary */
354 t->rgrgx = (double **)new_void(t->sp.lambda, sizeof(double*));
355 for (i = 0; i < t->sp.lambda; ++i) {
356 t->rgrgx[i] = new_double(N+2);
357 t->rgrgx[i][0] = N;
358 t->rgrgx[i]++;
359 }
360
361 /* Initialize newed space */
362
363 for (i = 0; i < N; ++i)
364 for (j = 0; j < i; ++j)
365 t->C[i][j] = t->B[i][j] = t->B[j][i] = 0.;
366
367 for (i = 0; i < N; ++i)
368 {
369 t->B[i][i] = 1.;
370 t->C[i][i] = t->rgD[i] = t->sp.rgInitialStds[i] * sqrt(N / trace);
371 t->C[i][i] *= t->C[i][i];
372 t->rgpc[i] = t->rgps[i] = 0.;
373 }
374
375 t->minEW = rgdouMin(t->rgD, N); t->minEW = t->minEW * t->minEW;
376 t->maxEW = rgdouMax(t->rgD, N); t->maxEW = t->maxEW * t->maxEW;
377
378 t->maxdiagC=t->C[0][0]; for(i=1;i<N;++i) if(t->maxdiagC<t->C[i][i]) t->maxdiagC=t->C[i][i];
379 t->mindiagC=t->C[0][0]; for(i=1;i<N;++i) if(t->mindiagC>t->C[i][i]) t->mindiagC=t->C[i][i];
380
381 /* set xmean */
382 for (i = 0; i < N; ++i)
383 t->rgxmean[i] = t->rgxold[i] = t->sp.xstart[i];
384 /* use in case xstart as typicalX */
385 if (t->sp.typicalXcase)
386 for (i = 0; i < N; ++i)
387 t->rgxmean[i] += t->sigma * t->rgD[i] * cmaes_random_Gauss(&t->rand);
388
389 if (strcmp(t->sp.resumefile, "_no_") != 0)
390 cmaes_resume_distribution(t, t->sp.resumefile);
391
392 return (t->publicFitness);
393
394 } /* cmaes_init_final() */
395
396
397 /* --------------------------------------------------------- */
398 /* --------------------------------------------------------- */
399 double *
cmaes_init(cmaes_t * t,int dimension,double * inxstart,double * inrgstddev,long int inseed,int lambda,const char * input_parameter_filename)400 cmaes_init(cmaes_t *t, /* "this" */
401 int dimension,
402 double *inxstart,
403 double *inrgstddev, /* initial stds */
404 long int inseed,
405 int lambda,
406 const char *input_parameter_filename)
407 {
408 cmaes_init_para(t, dimension, inxstart, inrgstddev, inseed,
409 lambda, input_parameter_filename);
410 return cmaes_init_final(t);
411 }
412
413 /* --------------------------------------------------------- */
414 /* --------------------------------------------------------- */
415
416 #ifdef __GNUC__
417 // These macros generate warnings in Visual Studio.
418 #pragma GCC diagnostic push
419 #pragma GCC diagnostic ignored "-Wunused-result"
420 #endif
421
422 void
cmaes_resume_distribution(cmaes_t * t,char * filename)423 cmaes_resume_distribution(cmaes_t *t, char *filename)
424 {
425 int i, j, res, n;
426 double d;
427 FILE *fp = fopen( filename, "r");
428 if(fp == NULL) {
429 ERRORMESSAGE("cmaes_resume_distribution(): could not open '",
430 filename, "'",0);
431 return;
432 }
433 /* count number of "resume" entries */
434 i = 0; res = 0;
435 while (1) {
436 if ((res = fscanf(fp, " resume %lg", &d)) == EOF)
437 break;
438 else if (res==0)
439 fscanf(fp, " %*s");
440 else if(res > 0)
441 i += 1;
442 }
443
444 /* go to last "resume" entry */
445 n = i; i = 0; res = 0; rewind(fp);
446 while (i<n) {
447 if ((res = fscanf(fp, " resume %lg", &d)) == EOF)
448 FATAL("cmaes_resume_distribution(): Unexpected error, bug",0,0,0);
449 else if (res==0)
450 fscanf(fp, " %*s");
451 else if(res > 0)
452 ++i;
453 }
454 if (d != t->sp.N)
455 FATAL("cmaes_resume_distribution(): Dimension numbers do not match",0,0,0);
456
457 /* find next "xmean" entry */
458 while (1) {
459 if ((res = fscanf(fp, " xmean %lg", &d)) == EOF)
460 FATAL("cmaes_resume_distribution(): 'xmean' not found",0,0,0);
461 else if (res==0)
462 fscanf(fp, " %*s");
463 else if(res > 0)
464 break;
465 }
466
467 /* read xmean */
468 t->rgxmean[0] = d; res = 1;
469 for(i = 1; i < t->sp.N; ++i)
470 res += fscanf(fp, " %lg", &t->rgxmean[i]);
471 if (res != t->sp.N)
472 FATAL("cmaes_resume_distribution(): xmean: dimensions differ",0,0,0);
473
474 /* find next "path for sigma" entry */
475 while (1) {
476 if ((res = fscanf(fp, " path for sigma %lg", &d)) == EOF)
477 FATAL("cmaes_resume_distribution(): 'path for sigma' not found",0,0,0);
478 else if (res==0)
479 fscanf(fp, " %*s");
480 else if(res > 0)
481 break;
482 }
483
484 /* read ps */
485 t->rgps[0] = d; res = 1;
486 for(i = 1; i < t->sp.N; ++i)
487 res += fscanf(fp, " %lg", &t->rgps[i]);
488 if (res != t->sp.N)
489 FATAL("cmaes_resume_distribution(): ps: dimensions differ",0,0,0);
490
491 /* find next "path for C" entry */
492 while (1) {
493 if ((res = fscanf(fp, " path for C %lg", &d)) == EOF)
494 FATAL("cmaes_resume_distribution(): 'path for C' not found",0,0,0);
495 else if (res==0)
496 fscanf(fp, " %*s");
497 else if(res > 0)
498 break;
499 }
500 /* read pc */
501 t->rgpc[0] = d; res = 1;
502 for(i = 1; i < t->sp.N; ++i)
503 res += fscanf(fp, " %lg", &t->rgpc[i]);
504 if (res != t->sp.N)
505 FATAL("cmaes_resume_distribution(): pc: dimensions differ",0,0,0);
506
507 /* find next "sigma" entry */
508 while (1) {
509 if ((res = fscanf(fp, " sigma %lg", &d)) == EOF)
510 FATAL("cmaes_resume_distribution(): 'sigma' not found",0,0,0);
511 else if (res==0)
512 fscanf(fp, " %*s");
513 else if(res > 0)
514 break;
515 }
516 t->sigma = d;
517
518 /* find next entry "covariance matrix" */
519 while (1) {
520 if ((res = fscanf(fp, " covariance matrix %lg", &d)) == EOF)
521 FATAL("cmaes_resume_distribution(): 'covariance matrix' not found",0,0,0);
522 else if (res==0)
523 fscanf(fp, " %*s");
524 else if(res > 0)
525 break;
526 }
527 /* read C */
528 t->C[0][0] = d; res = 1;
529 for (i = 1; i < t->sp.N; ++i)
530 for (j = 0; j <= i; ++j)
531 res += fscanf(fp, " %lg", &t->C[i][j]);
532 if (res != (t->sp.N*t->sp.N+t->sp.N)/2)
533 FATAL("cmaes_resume_distribution(): C: dimensions differ",0,0,0);
534
535 t->flgIniphase = 0;
536 t->flgEigensysIsUptodate = 0;
537 t->flgresumedone = 1;
538 cmaes_UpdateEigensystem(t, 1);
539
540 } /* cmaes_resume_distribution() */
541 #ifdef __GNUC__
542 #pragma GCC diagnostic pop
543 #endif
544 /* --------------------------------------------------------- */
545 /* --------------------------------------------------------- */
546
547 void
cmaes_exit(cmaes_t * t)548 cmaes_exit(cmaes_t *t)
549 {
550 int i, N = t->sp.N;
551 t->version = NULL;
552 /* free(t->signals_filename) */
553 t->state = -1; /* not really useful at the moment */
554 free( t->rgpc);
555 free( t->rgps);
556 free( t->rgdTmp);
557 free( t->rgBDz);
558 free( --t->rgxmean);
559 free( --t->rgxold);
560 free( --t->rgxbestever);
561 free( --t->rgout);
562 free( t->rgD);
563 for (i = 0; i < N; ++i) {
564 free( t->C[i]);
565 free( t->B[i]);
566 }
567 for (i = 0; i < t->sp.lambda; ++i)
568 free( --t->rgrgx[i]);
569 free( t->rgrgx);
570 free( t->C);
571 free( t->B);
572 free( t->index);
573 free( t->publicFitness);
574 free( --t->rgFuncValue);
575 free( --t->arFuncValueHist);
576 cmaes_random_exit (&t->rand);
577 cmaes_readpara_exit (&t->sp);
578 } /* cmaes_exit() */
579
580
581 /* --------------------------------------------------------- */
582 /* --------------------------------------------------------- */
583 double const *
cmaes_SetMean(cmaes_t * t,const double * xmean)584 cmaes_SetMean(cmaes_t *t, const double *xmean)
585 /*
586 * Distribution mean could be changed before SamplePopulation().
587 * This might lead to unexpected behaviour if done repeatedly.
588 */
589 {
590 int i, N=t->sp.N;
591
592 if (t->state >= 1 && t->state < 3)
593 FATAL("cmaes_SetMean: mean cannot be set between the calls of ",
594 "SamplePopulation and UpdateDistribution",0,0);
595
596 if (xmean != NULL && xmean != t->rgxmean)
597 for(i = 0; i < N; ++i)
598 t->rgxmean[i] = xmean[i];
599 else
600 xmean = t->rgxmean;
601
602 return xmean;
603 }
604
605 /* --------------------------------------------------------- */
606 /* --------------------------------------------------------- */
607 double * const *
cmaes_SamplePopulation(cmaes_t * t)608 cmaes_SamplePopulation(cmaes_t *t)
609 {
610 int iNk, i, j, N=t->sp.N;
611 int flgdiag = ((t->sp.diagonalCov == 1) || (t->sp.diagonalCov >= t->gen));
612 double sum;
613 double const *xmean = t->rgxmean;
614
615 /* cmaes_SetMean(t, xmean); * xmean could be changed at this point */
616
617 /* calculate eigensystem */
618 if (!t->flgEigensysIsUptodate) {
619 if (!flgdiag)
620 cmaes_UpdateEigensystem(t, 0);
621 else {
622 for (i = 0; i < N; ++i)
623 t->rgD[i] = sqrt(t->C[i][i]);
624 t->minEW = douSquare(rgdouMin(t->rgD, N));
625 t->maxEW = douSquare(rgdouMax(t->rgD, N));
626 t->flgEigensysIsUptodate = 1;
627 cmaes_timings_start(&t->eigenTimings);
628 }
629 }
630
631 /* treat minimal standard deviations and numeric problems */
632 TestMinStdDevs(t);
633
634 for (iNk = 0; iNk < t->sp.lambda; ++iNk)
635 { /* generate scaled cmaes_random vector (D * z) */
636 for (i = 0; i < N; ++i)
637 if (flgdiag)
638 t->rgrgx[iNk][i] = xmean[i] + t->sigma * t->rgD[i] * cmaes_random_Gauss(&t->rand);
639 else
640 t->rgdTmp[i] = t->rgD[i] * cmaes_random_Gauss(&t->rand);
641 if (!flgdiag)
642 /* add mutation (sigma * B * (D*z)) */
643 for (i = 0; i < N; ++i) {
644 for (j = 0, sum = 0.; j < N; ++j)
645 sum += t->B[i][j] * t->rgdTmp[j];
646 t->rgrgx[iNk][i] = xmean[i] + t->sigma * sum;
647 }
648 }
649 if(t->state == 3 || t->gen == 0)
650 ++t->gen;
651 t->state = 1;
652
653 return(t->rgrgx);
654 } /* SamplePopulation() */
655
656 /* --------------------------------------------------------- */
657 /* --------------------------------------------------------- */
658 double const *
cmaes_ReSampleSingle_old(cmaes_t * t,double * rgx)659 cmaes_ReSampleSingle_old( cmaes_t *t, double *rgx)
660 {
661 int i, j, N=t->sp.N;
662 double sum;
663
664 if (rgx == NULL)
665 FATAL("cmaes_ReSampleSingle(): Missing input double *x",0,0,0);
666
667 for (i = 0; i < N; ++i)
668 t->rgdTmp[i] = t->rgD[i] * cmaes_random_Gauss(&t->rand);
669 /* add mutation (sigma * B * (D*z)) */
670 for (i = 0; i < N; ++i) {
671 for (j = 0, sum = 0.; j < N; ++j)
672 sum += t->B[i][j] * t->rgdTmp[j];
673 rgx[i] = t->rgxmean[i] + t->sigma * sum;
674 }
675 return rgx;
676 }
677
678 /* --------------------------------------------------------- */
679 /* --------------------------------------------------------- */
680 double * const *
cmaes_ReSampleSingle(cmaes_t * t,int iindex)681 cmaes_ReSampleSingle( cmaes_t *t, int iindex)
682 {
683 int i, j, N=t->sp.N;
684 double *rgx;
685 double sum;
686 static char s[99];
687
688 if (iindex < 0 || iindex >= t->sp.lambda) {
689 sprintf(s, "index==%d must be between 0 and %d", iindex, t->sp.lambda);
690 FATAL("cmaes_ReSampleSingle(): Population member ",s,0,0);
691 }
692 rgx = t->rgrgx[iindex];
693
694 for (i = 0; i < N; ++i)
695 t->rgdTmp[i] = t->rgD[i] * cmaes_random_Gauss(&t->rand);
696 /* add mutation (sigma * B * (D*z)) */
697 for (i = 0; i < N; ++i) {
698 for (j = 0, sum = 0.; j < N; ++j)
699 sum += t->B[i][j] * t->rgdTmp[j];
700 rgx[i] = t->rgxmean[i] + t->sigma * sum;
701 }
702 return(t->rgrgx);
703 }
704
705 /* --------------------------------------------------------- */
706 /* --------------------------------------------------------- */
707 double *
cmaes_SampleSingleInto(cmaes_t * t,double * rgx)708 cmaes_SampleSingleInto( cmaes_t *t, double *rgx)
709 {
710 int i, j, N=t->sp.N;
711 double sum;
712
713 if (rgx == NULL)
714 rgx = new_double(N);
715
716 for (i = 0; i < N; ++i)
717 t->rgdTmp[i] = t->rgD[i] * cmaes_random_Gauss(&t->rand);
718 /* add mutation (sigma * B * (D*z)) */
719 for (i = 0; i < N; ++i) {
720 for (j = 0, sum = 0.; j < N; ++j)
721 sum += t->B[i][j] * t->rgdTmp[j];
722 rgx[i] = t->rgxmean[i] + t->sigma * sum;
723 }
724 return rgx;
725 }
726
727 /* --------------------------------------------------------- */
728 /* --------------------------------------------------------- */
729 double *
cmaes_PerturbSolutionInto(cmaes_t * t,double * rgx,double const * xmean,double eps)730 cmaes_PerturbSolutionInto( cmaes_t *t, double *rgx, double const *xmean, double eps)
731 {
732 int i, j, N=t->sp.N;
733 double sum;
734
735 if (rgx == NULL)
736 rgx = new_double(N);
737 if (xmean == NULL)
738 FATAL("cmaes_PerturbSolutionInto(): xmean was not given",0,0,0);
739
740 for (i = 0; i < N; ++i)
741 t->rgdTmp[i] = t->rgD[i] * cmaes_random_Gauss(&t->rand);
742 /* add mutation (sigma * B * (D*z)) */
743 for (i = 0; i < N; ++i) {
744 for (j = 0, sum = 0.; j < N; ++j)
745 sum += t->B[i][j] * t->rgdTmp[j];
746 rgx[i] = xmean[i] + eps * t->sigma * sum;
747 }
748 return rgx;
749 }
750
751 /* --------------------------------------------------------- */
752 /* --------------------------------------------------------- */
753 const double *
cmaes_Optimize(cmaes_t * evo,double (* pFun)(double const *,int dim),long iterations)754 cmaes_Optimize( cmaes_t *evo, double(*pFun)(double const *, int dim), long iterations)
755 /* TODO: make signals.par another argument or, even better, part of cmaes_t */
756 {
757 const char * signalsFilename = "cmaes_signals.par";
758 double *const*pop; /* sampled population */
759 const char *stop;
760 int i;
761 long startiter = (long)evo->gen;
762
763 while(!(stop=cmaes_TestForTermination(evo)) &&
764 ((long)evo->gen < startiter + iterations || !iterations))
765 {
766 /* Generate population of new candidate solutions */
767 pop = cmaes_SamplePopulation(evo); /* do not change content of pop */
768
769 /* Compute fitness value for each candidate solution */
770 for (i = 0; i < cmaes_Get(evo, "popsize"); ++i) {
771 evo->publicFitness[i] = (*pFun)(pop[i], evo->sp.N);
772 }
773
774 /* update search distribution */
775 cmaes_UpdateDistribution(evo, evo->publicFitness);
776
777 /* read control signals for output and termination */
778 if (signalsFilename)
779 cmaes_ReadSignals(evo, signalsFilename);
780 fflush(stdout);
781 } /* while !cmaes_TestForTermination(evo) */
782
783 /* write some data */
784 cmaes_WriteToFile(evo, "all", "allcmaes.dat");
785
786 return cmaes_GetPtr(evo, "xbestever");
787 }
788
789
790 /* --------------------------------------------------------- */
791 /* --------------------------------------------------------- */
792 double *
cmaes_UpdateDistribution(cmaes_t * t,const double * rgFunVal)793 cmaes_UpdateDistribution( cmaes_t *t, const double *rgFunVal)
794 {
795 int i, j, iNk, hsig, N=t->sp.N;
796 int flgdiag = ((t->sp.diagonalCov == 1) || (t->sp.diagonalCov >= t->gen));
797 double sum;
798 double psxps;
799
800 if(t->state == 3)
801 FATAL("cmaes_UpdateDistribution(): You need to call \n",
802 "SamplePopulation() before update can take place.",0,0);
803 if(rgFunVal == NULL)
804 FATAL("cmaes_UpdateDistribution(): ",
805 "Fitness function value array input is missing.",0,0);
806
807 if(t->state == 1) /* function values are delivered here */
808 t->countevals += t->sp.lambda;
809 else
810 ERRORMESSAGE("cmaes_UpdateDistribution(): unexpected state",0,0,0);
811
812 /* assign function values */
813 for (i=0; i < t->sp.lambda; ++i)
814 t->rgrgx[i][N] = t->rgFuncValue[i] = rgFunVal[i];
815
816
817 /* Generate index */
818 Sorted_index(rgFunVal, t->index, t->sp.lambda);
819
820 /* Test if function values are identical, escape flat fitness */
821 if (t->rgFuncValue[t->index[0]] ==
822 t->rgFuncValue[t->index[(int)t->sp.lambda/2]]) {
823 t->sigma *= exp(0.2+t->sp.cs/t->sp.damps);
824 ERRORMESSAGE("Warning: sigma increased due to equal function values\n",
825 " Reconsider the formulation of the objective function",0,0);
826 }
827
828 /* update function value history */
829 for(i = (int)*(t->arFuncValueHist-1)-1; i > 0; --i) /* for(i = t->arFuncValueHist[-1]-1; i > 0; --i) */
830 t->arFuncValueHist[i] = t->arFuncValueHist[i-1];
831 t->arFuncValueHist[0] = rgFunVal[t->index[0]];
832
833 /* update xbestever */
834 if (t->rgxbestever[N] > t->rgrgx[t->index[0]][N] || t->gen == 1)
835 for (i = 0; i <= N; ++i) {
836 t->rgxbestever[i] = t->rgrgx[t->index[0]][i];
837 t->rgxbestever[N+1] = t->countevals;
838 }
839
840 /* calculate xmean and rgBDz~N(0,C) */
841 for (i = 0; i < N; ++i) {
842 t->rgxold[i] = t->rgxmean[i];
843 t->rgxmean[i] = 0.;
844 for (iNk = 0; iNk < t->sp.mu; ++iNk)
845 t->rgxmean[i] += t->sp.weights[iNk] * t->rgrgx[t->index[iNk]][i];
846 t->rgBDz[i] = sqrt(t->sp.mueff)*(t->rgxmean[i] - t->rgxold[i])/t->sigma;
847 }
848
849 /* calculate z := D^(-1) * B^(-1) * rgBDz into rgdTmp */
850 for (i = 0; i < N; ++i) {
851 if (!flgdiag)
852 for (j = 0, sum = 0.; j < N; ++j)
853 sum += t->B[j][i] * t->rgBDz[j];
854 else
855 sum = t->rgBDz[i];
856 t->rgdTmp[i] = sum / t->rgD[i];
857 }
858
859 /* TODO?: check length of t->rgdTmp and set an upper limit, e.g. 6 stds */
860 /* in case of manipulation of arx,
861 this can prevent an increase of sigma by several orders of magnitude
862 within one step; a five-fold increase in one step can still happen.
863 */
864 /*
865 for (j = 0, sum = 0.; j < N; ++j)
866 sum += t->rgdTmp[j] * t->rgdTmp[j];
867 if (sqrt(sum) > chiN + 6. * sqrt(0.5)) {
868 rgdTmp length should be set to upper bound and hsig should become zero
869 }
870 */
871
872 /* cumulation for sigma (ps) using B*z */
873 for (i = 0; i < N; ++i) {
874 if (!flgdiag)
875 for (j = 0, sum = 0.; j < N; ++j)
876 sum += t->B[i][j] * t->rgdTmp[j];
877 else
878 sum = t->rgdTmp[i];
879 t->rgps[i] = (1. - t->sp.cs) * t->rgps[i] +
880 sqrt(t->sp.cs * (2. - t->sp.cs)) * sum;
881 }
882
883 /* calculate norm(ps)^2 */
884 for (i = 0, psxps = 0.; i < N; ++i)
885 psxps += t->rgps[i] * t->rgps[i];
886
887 /* cumulation for covariance matrix (pc) using B*D*z~N(0,C) */
888 hsig = sqrt(psxps) / sqrt(1. - pow(1.-t->sp.cs, 2*t->gen)) / t->chiN
889 < 1.4 + 2./(N+1);
890 for (i = 0; i < N; ++i) {
891 t->rgpc[i] = (1. - t->sp.ccumcov) * t->rgpc[i] +
892 hsig * sqrt(t->sp.ccumcov * (2. - t->sp.ccumcov)) * t->rgBDz[i];
893 }
894
895 /* stop initial phase */
896 if (t->flgIniphase &&
897 t->gen > douMin(1/t->sp.cs, 1+N/t->sp.mucov))
898 {
899 if (psxps / t->sp.damps / (1.-pow((1. - t->sp.cs), t->gen))
900 < N * 1.05)
901 t->flgIniphase = 0;
902 }
903
904 #if 0
905 /* remove momentum in ps, if ps is large and fitness is getting worse */
906 /* This is obsolete due to hsig and harmful in a dynamic environment */
907 if(psxps/N > 1.5 + 10.*sqrt(2./N)
908 && t->arFuncValueHist[0] > t->arFuncValueHist[1]
909 && t->arFuncValueHist[0] > t->arFuncValueHist[2]) {
910 double tfac = sqrt((1 + douMax(0, log(psxps/N))) * N / psxps);
911 for (i=0; i<N; ++i)
912 t->rgps[i] *= tfac;
913 psxps *= tfac*tfac;
914 }
915 #endif
916
917 /* update of C */
918
919 Adapt_C2(t, hsig);
920
921 /* Adapt_C(t); not used anymore */
922
923 #if 0
924 if (t->sp.ccov != 0. && t->flgIniphase == 0) {
925 int k;
926
927 t->flgEigensysIsUptodate = 0;
928
929 /* update covariance matrix */
930 for (i = 0; i < N; ++i)
931 for (j = 0; j <=i; ++j) {
932 t->C[i][j] = (1 - t->sp.ccov) * t->C[i][j]
933 + t->sp.ccov * (1./t->sp.mucov)
934 * (t->rgpc[i] * t->rgpc[j]
935 + (1-hsig)*t->sp.ccumcov*(2.-t->sp.ccumcov) * t->C[i][j]);
936 for (k = 0; k < t->sp.mu; ++k) /* additional rank mu update */
937 t->C[i][j] += t->sp.ccov * (1-1./t->sp.mucov) * t->sp.weights[k]
938 * (t->rgrgx[t->index[k]][i] - t->rgxold[i])
939 * (t->rgrgx[t->index[k]][j] - t->rgxold[j])
940 / t->sigma / t->sigma;
941 }
942 }
943 #endif
944
945
946 /* update of sigma */
947 t->sigma *= exp(((sqrt(psxps)/t->chiN)-1.)*t->sp.cs/t->sp.damps);
948
949 t->state = 3;
950
951 return (t->rgxmean);
952
953 } /* cmaes_UpdateDistribution() */
954
955
956 /* --------------------------------------------------------- */
957 /* --------------------------------------------------------- */
958 static void
Adapt_C2(cmaes_t * t,int hsig)959 Adapt_C2(cmaes_t *t, int hsig)
960 {
961 int i, j, k, N=t->sp.N;
962 int flgdiag = ((t->sp.diagonalCov == 1) || (t->sp.diagonalCov >= t->gen));
963
964 if (t->sp.ccov != 0. && t->flgIniphase == 0) {
965
966 /* definitions for speeding up inner-most loop */
967 double ccov1 = douMin(t->sp.ccov * (1./t->sp.mucov) * (flgdiag ? (N+1.5) / 3. : 1.), 1.);
968 double ccovmu = douMin(t->sp.ccov * (1-1./t->sp.mucov)* (flgdiag ? (N+1.5) / 3. : 1.), 1.-ccov1);
969 double sigmasquare = t->sigma * t->sigma;
970
971 t->flgEigensysIsUptodate = 0;
972
973 /* update covariance matrix */
974 for (i = 0; i < N; ++i)
975 for (j = flgdiag ? i : 0; j <= i; ++j) {
976 t->C[i][j] = (1 - ccov1 - ccovmu) * t->C[i][j]
977 + ccov1
978 * (t->rgpc[i] * t->rgpc[j]
979 + (1-hsig)*t->sp.ccumcov*(2.-t->sp.ccumcov) * t->C[i][j]);
980 for (k = 0; k < t->sp.mu; ++k) { /* additional rank mu update */
981 t->C[i][j] += ccovmu * t->sp.weights[k]
982 * (t->rgrgx[t->index[k]][i] - t->rgxold[i])
983 * (t->rgrgx[t->index[k]][j] - t->rgxold[j])
984 / sigmasquare;
985 }
986 }
987 /* update maximal and minimal diagonal value */
988 t->maxdiagC = t->mindiagC = t->C[0][0];
989 for (i = 1; i < N; ++i) {
990 if (t->maxdiagC < t->C[i][i])
991 t->maxdiagC = t->C[i][i];
992 else if (t->mindiagC > t->C[i][i])
993 t->mindiagC = t->C[i][i];
994 }
995 } /* if ccov... */
996 }
997
998
999 /* --------------------------------------------------------- */
1000 /* --------------------------------------------------------- */
1001 static void
TestMinStdDevs(cmaes_t * t)1002 TestMinStdDevs(cmaes_t *t)
1003 /* increases sigma */
1004 {
1005 int i, N = t->sp.N;
1006 if (t->sp.rgDiffMinChange == NULL)
1007 return;
1008
1009 for (i = 0; i < N; ++i)
1010 while (t->sigma * sqrt(t->C[i][i]) < t->sp.rgDiffMinChange[i])
1011 t->sigma *= exp(0.05+t->sp.cs/t->sp.damps);
1012
1013 } /* cmaes_TestMinStdDevs() */
1014
1015
1016 /* --------------------------------------------------------- */
1017 /* --------------------------------------------------------- */
cmaes_WriteToFile(cmaes_t * t,const char * key,const char * name)1018 void cmaes_WriteToFile(cmaes_t *t, const char *key, const char *name)
1019 {
1020 cmaes_WriteToFileAW(t, key, name, "a"); /* default is append */
1021 }
1022
1023 /* --------------------------------------------------------- */
1024 /* --------------------------------------------------------- */
cmaes_WriteToFileAW(cmaes_t * t,const char * key,const char * name,const char * appendwrite)1025 void cmaes_WriteToFileAW(cmaes_t *t, const char *key, const char *name,
1026 const char *appendwrite)
1027 {
1028 const char *s = "tmpcmaes.dat";
1029 FILE *fp;
1030
1031 if (name == NULL)
1032 name = s;
1033
1034 fp = fopen( name, appendwrite);
1035
1036 if(fp == NULL) {
1037 ERRORMESSAGE("cmaes_WriteToFile(): could not open '", name,
1038 "' with flag ", appendwrite);
1039 return;
1040 }
1041
1042 if (appendwrite[0] == 'w') {
1043 /* write a header line, very rudimentary */
1044 fprintf(fp, "%% # %s (randomSeed=%d, %s)\n", key, t->sp.seed, getTimeStr());
1045 } else
1046 if (t->gen > 0 || strncmp(name, "outcmaesfit", 11) != 0)
1047 cmaes_WriteToFilePtr(t, key, fp); /* do not write fitness for gen==0 */
1048
1049 fclose(fp);
1050
1051 } /* WriteToFile */
1052
1053 /* --------------------------------------------------------- */
cmaes_WriteToFilePtr(cmaes_t * t,const char * key,FILE * fp)1054 void cmaes_WriteToFilePtr(cmaes_t *t, const char *key, FILE *fp)
1055
1056 /* this hack reads key words from input key for data to be written to
1057 * a file, see file signals.par as input file. The length of the keys
1058 * is mostly fixed, see key += number in the code! If the key phrase
1059 * does not match the expectation the output might be strange. for
1060 * cmaes_t *t == NULL it solely prints key as a header line. Input key
1061 * must be zero terminated.
1062 */
1063 {
1064 int i, k, N=(t ? t->sp.N : 0);
1065 char const *keyend; /* *keystart; */
1066 const char *s = "few";
1067 if (key == NULL)
1068 key = s;
1069 /* keystart = key; for debugging purpose */
1070 keyend = key + strlen(key);
1071
1072 while (key < keyend)
1073 {
1074 if (strncmp(key, "axisratio", 9) == 0)
1075 {
1076 fprintf(fp, "%.2e", sqrt(t->maxEW/t->minEW));
1077 while (*key != '+' && *key != '\0' && key < keyend)
1078 ++key;
1079 fprintf(fp, "%c", (*key=='+') ? '\t':'\n');
1080 }
1081 if (strncmp(key, "idxminSD", 8) == 0)
1082 {
1083 int mini=0; for(i=N-1;i>0;--i) if(t->mindiagC==t->C[i][i]) mini=i;
1084 fprintf(fp, "%d", mini+1);
1085 while (*key != '+' && *key != '\0' && key < keyend)
1086 ++key;
1087 fprintf(fp, "%c", (*key=='+') ? '\t':'\n');
1088 }
1089 if (strncmp(key, "idxmaxSD", 8) == 0)
1090 {
1091 int maxi=0; for(i=N-1;i>0;--i) if(t->maxdiagC==t->C[i][i]) maxi=i;
1092 fprintf(fp, "%d", maxi+1);
1093 while (*key != '+' && *key != '\0' && key < keyend)
1094 ++key;
1095 fprintf(fp, "%c", (*key=='+') ? '\t':'\n');
1096 }
1097 /* new coordinate system == all eigenvectors */
1098 if (strncmp(key, "B", 1) == 0)
1099 {
1100 /* int j, index[N]; */
1101 int j, *iindex=(int*)(new_void(N,sizeof(int))); /* MT */
1102 Sorted_index(t->rgD, iindex, N); /* should not be necessary, see end of QLalgo2 */
1103 /* One eigenvector per row, sorted: largest eigenvalue first */
1104 for (i = 0; i < N; ++i)
1105 for (j = 0; j < N; ++j)
1106 fprintf(fp, "%g%c", t->B[j][iindex[N-1-i]], (j==N-1)?'\n':'\t');
1107 ++key;
1108 free(iindex); /* MT */
1109 }
1110 /* covariance matrix */
1111 if (strncmp(key, "C", 1) == 0)
1112 {
1113 int j;
1114 for (i = 0; i < N; ++i)
1115 for (j = 0; j <= i; ++j)
1116 fprintf(fp, "%g%c", t->C[i][j], (j==i)?'\n':'\t');
1117 ++key;
1118 }
1119 /* (processor) time (used) since begin of execution */
1120 if (strncmp(key, "clock", 4) == 0)
1121 {
1122 cmaes_timings_update(&t->eigenTimings);
1123 fprintf(fp, "%.1f %.1f", t->eigenTimings.totaltotaltime,
1124 t->eigenTimings.tictoctime);
1125 while (*key != '+' && *key != '\0' && key < keyend)
1126 ++key;
1127 fprintf(fp, "%c", (*key=='+') ? '\t':'\n');
1128 }
1129 /* ratio between largest and smallest standard deviation */
1130 if (strncmp(key, "stddevratio", 11) == 0) /* std dev in coordinate axes */
1131 {
1132 fprintf(fp, "%g", sqrt(t->maxdiagC/t->mindiagC));
1133 while (*key != '+' && *key != '\0' && key < keyend)
1134 ++key;
1135 fprintf(fp, "%c", (*key=='+') ? '\t':'\n');
1136 }
1137 /* standard deviations in coordinate directions (sigma*sqrt(C[i,i])) */
1138 if (strncmp(key, "coorstddev", 10) == 0
1139 || strncmp(key, "stddev", 6) == 0) /* std dev in coordinate axes */
1140 {
1141 for (i = 0; i < N; ++i)
1142 fprintf(fp, "%s%g", (i==0) ? "":"\t", t->sigma*sqrt(t->C[i][i]));
1143 while (*key != '+' && *key != '\0' && key < keyend)
1144 ++key;
1145 fprintf(fp, "%c", (*key=='+') ? '\t':'\n');
1146 }
1147 /* diagonal of D == roots of eigenvalues, sorted */
1148 if (strncmp(key, "diag(D)", 7) == 0)
1149 {
1150 for (i = 0; i < N; ++i)
1151 t->rgdTmp[i] = t->rgD[i];
1152 qsort(t->rgdTmp, (unsigned) N, sizeof(double), &SignOfDiff); /* superfluous */
1153 for (i = 0; i < N; ++i)
1154 fprintf(fp, "%s%g", (i==0) ? "":"\t", t->rgdTmp[i]);
1155 while (*key != '+' && *key != '\0' && key < keyend)
1156 ++key;
1157 fprintf(fp, "%c", (*key=='+') ? '\t':'\n');
1158 }
1159 if (strncmp(key, "dim", 3) == 0)
1160 {
1161 fprintf(fp, "%d", N);
1162 while (*key != '+' && *key != '\0' && key < keyend)
1163 ++key;
1164 fprintf(fp, "%c", (*key=='+') ? '\t':'\n');
1165 }
1166 if (strncmp(key, "eval", 4) == 0)
1167 {
1168 fprintf(fp, "%.0f", t->countevals);
1169 while (*key != '+' && *key != '\0' && key < keyend)
1170 ++key;
1171 fprintf(fp, "%c", (*key=='+') ? '\t':'\n');
1172 }
1173 if (strncmp(key, "few(diag(D))", 12) == 0)/* between four and six axes */
1174 {
1175 int add = (int)(0.5 + (N + 1.) / 5.);
1176 for (i = 0; i < N; ++i)
1177 t->rgdTmp[i] = t->rgD[i];
1178 qsort(t->rgdTmp, (unsigned) N, sizeof(double), &SignOfDiff);
1179 for (i = 0; i < N-1; i+=add) /* print always largest */
1180 fprintf(fp, "%s%g", (i==0) ? "":"\t", t->rgdTmp[N-1-i]);
1181 fprintf(fp, "\t%g\n", t->rgdTmp[0]); /* and smallest */
1182 break; /* number of printed values is not determined */
1183 }
1184 if (strncmp(key, "fewinfo", 7) == 0) {
1185 fprintf(fp," Iter Fevals Function Value Sigma ");
1186 fprintf(fp, "MaxCoorDev MinCoorDev AxisRatio MinDii Time in eig\n");
1187 while (*key != '+' && *key != '\0' && key < keyend)
1188 ++key;
1189 }
1190 if (strncmp(key, "few", 3) == 0) {
1191 fprintf(fp, " %4.0f ", t->gen);
1192 fprintf(fp, " %5.0f ", t->countevals);
1193 fprintf(fp, "%.15e", t->rgFuncValue[t->index[0]]);
1194 fprintf(fp, " %.2e %.2e %.2e", t->sigma, t->sigma*sqrt(t->maxdiagC),
1195 t->sigma*sqrt(t->mindiagC));
1196 fprintf(fp, " %.2e %.2e", sqrt(t->maxEW/t->minEW), sqrt(t->minEW));
1197 while (*key != '+' && *key != '\0' && key < keyend)
1198 ++key;
1199 fprintf(fp, "%c", (*key=='+') ? '\t':'\n');
1200 }
1201 if (strncmp(key, "funval", 6) == 0 || strncmp(key, "fitness", 6) == 0)
1202 {
1203 fprintf(fp, "%.15e", t->rgFuncValue[t->index[0]]);
1204 while (*key != '+' && *key != '\0' && key < keyend)
1205 ++key;
1206 fprintf(fp, "%c", (*key=='+') ? '\t':'\n');
1207 }
1208 if (strncmp(key, "fbestever", 9) == 0)
1209 {
1210 fprintf(fp, "%.15e", t->rgxbestever[N]); /* f-value */
1211 while (*key != '+' && *key != '\0' && key < keyend)
1212 ++key;
1213 fprintf(fp, "%c", (*key=='+') ? '\t':'\n');
1214 }
1215 if (strncmp(key, "fmedian", 7) == 0)
1216 {
1217 fprintf(fp, "%.15e", t->rgFuncValue[t->index[(int)(t->sp.lambda/2)]]);
1218 while (*key != '+' && *key != '\0' && key < keyend)
1219 ++key;
1220 fprintf(fp, "%c", (*key=='+') ? '\t':'\n');
1221 }
1222 if (strncmp(key, "fworst", 6) == 0)
1223 {
1224 fprintf(fp, "%.15e", t->rgFuncValue[t->index[t->sp.lambda-1]]);
1225 while (*key != '+' && *key != '\0' && key < keyend)
1226 ++key;
1227 fprintf(fp, "%c", (*key=='+') ? '\t':'\n');
1228 }
1229 if (strncmp(key, "arfunval", 8) == 0 || strncmp(key, "arfitness", 8) == 0)
1230 {
1231 for (i = 0; i < N; ++i)
1232 fprintf(fp, "%s%.10e", (i==0) ? "" : "\t",
1233 t->rgFuncValue[t->index[i]]);
1234 while (*key != '+' && *key != '\0' && key < keyend)
1235 ++key;
1236 fprintf(fp, "%c", (*key=='+') ? '\t':'\n');
1237 }
1238 if (strncmp(key, "gen", 3) == 0)
1239 {
1240 fprintf(fp, "%.0f", t->gen);
1241 while (*key != '+' && *key != '\0' && key < keyend)
1242 ++key;
1243 fprintf(fp, "%c", (*key=='+') ? '\t':'\n');
1244 }
1245 if (strncmp(key, "iter", 4) == 0)
1246 {
1247 fprintf(fp, "%.0f", t->gen);
1248 while (*key != '+' && *key != '\0' && key < keyend)
1249 ++key;
1250 fprintf(fp, "%c", (*key=='+') ? '\t':'\n');
1251 }
1252 if (strncmp(key, "sigma", 5) == 0)
1253 {
1254 fprintf(fp, "%.4e", t->sigma);
1255 while (*key != '+' && *key != '\0' && key < keyend)
1256 ++key;
1257 fprintf(fp, "%c", (*key=='+') ? '\t':'\n');
1258 }
1259 if (strncmp(key, "minSD", 5) == 0) /* minimal standard deviation */
1260 {
1261 fprintf(fp, "%.4e", sqrt(t->mindiagC));
1262 while (*key != '+' && *key != '\0' && key < keyend)
1263 ++key;
1264 fprintf(fp, "%c", (*key=='+') ? '\t':'\n');
1265 }
1266 if (strncmp(key, "maxSD", 5) == 0)
1267 {
1268 fprintf(fp, "%.4e", sqrt(t->maxdiagC));
1269 while (*key != '+' && *key != '\0' && key < keyend)
1270 ++key;
1271 fprintf(fp, "%c", (*key=='+') ? '\t':'\n');
1272 }
1273 if (strncmp(key, "mindii", 6) == 0)
1274 {
1275 fprintf(fp, "%.4e", sqrt(t->minEW));
1276 while (*key != '+' && *key != '\0' && key < keyend)
1277 ++key;
1278 fprintf(fp, "%c", (*key=='+') ? '\t':'\n');
1279 }
1280 if (strncmp(key, "0", 1) == 0)
1281 {
1282 fprintf(fp, "0");
1283 ++key;
1284 fprintf(fp, "%c", (*key=='+') ? '\t':'\n');
1285 }
1286 if (strncmp(key, "lambda", 6) == 0 || strncmp(key, "popsi", 5) == 0 || strncmp(key, "populationsi", 12) == 0)
1287 {
1288 fprintf(fp, "%d", t->sp.lambda);
1289 while (*key != '+' && *key != '\0' && key < keyend)
1290 ++key;
1291 fprintf(fp, "%c", (*key=='+') ? '\t':'\n');
1292 }
1293 if (strncmp(key, "N", 1) == 0)
1294 {
1295 fprintf(fp, "%d", N);
1296 ++key;
1297 fprintf(fp, "%c", (*key=='+') ? '\t':'\n');
1298 }
1299 if (strncmp(key, "resume", 6) == 0)
1300 {
1301 fprintf(fp, "\n# resume %d\n", N);
1302 fprintf(fp, "xmean\n");
1303 cmaes_WriteToFilePtr(t, "xmean", fp);
1304 fprintf(fp, "path for sigma\n");
1305 for(i=0; i<N; ++i)
1306 fprintf(fp, "%g%s", t->rgps[i], (i==N-1) ? "\n":"\t");
1307 fprintf(fp, "path for C\n");
1308 for(i=0; i<N; ++i)
1309 fprintf(fp, "%g%s", t->rgpc[i], (i==N-1) ? "\n":"\t");
1310 fprintf(fp, "sigma %g\n", t->sigma);
1311 /* note than B and D might not be up-to-date */
1312 fprintf(fp, "covariance matrix\n");
1313 cmaes_WriteToFilePtr(t, "C", fp);
1314 while (*key != '+' && *key != '\0' && key < keyend)
1315 ++key;
1316 }
1317 if (strncmp(key, "xbest", 5) == 0) { /* best x in recent generation */
1318 for(i=0; i<N; ++i)
1319 fprintf(fp, "%s%g", (i==0) ? "":"\t", t->rgrgx[t->index[0]][i]);
1320 while (*key != '+' && *key != '\0' && key < keyend)
1321 ++key;
1322 fprintf(fp, "%c", (*key=='+') ? '\t':'\n');
1323 }
1324 if (strncmp(key, "xmean", 5) == 0) {
1325 for(i=0; i<N; ++i)
1326 fprintf(fp, "%s%g", (i==0) ? "":"\t", t->rgxmean[i]);
1327 while (*key != '+' && *key != '\0' && key < keyend)
1328 ++key;
1329 fprintf(fp, "%c", (*key=='+') ? '\t':'\n');
1330 }
1331 if (strncmp(key, "all", 3) == 0)
1332 {
1333 time_t ti = time(NULL);
1334 fprintf(fp, "\n# --------- %s\n", asctime(localtime(&ti)));
1335 fprintf(fp, " N %d\n", N);
1336 fprintf(fp, " seed %d\n", t->sp.seed);
1337 fprintf(fp, "function evaluations %.0f\n", t->countevals);
1338 fprintf(fp, "elapsed (CPU) time [s] %.2f\n", t->eigenTimings.totaltotaltime);
1339 fprintf(fp, "function value f(x)=%g\n", t->rgrgx[t->index[0]][N]);
1340 fprintf(fp, "maximal standard deviation %g\n", t->sigma*sqrt(t->maxdiagC));
1341 fprintf(fp, "minimal standard deviation %g\n", t->sigma*sqrt(t->mindiagC));
1342 fprintf(fp, "sigma %g\n", t->sigma);
1343 fprintf(fp, "axisratio %g\n", rgdouMax(t->rgD, N)/rgdouMin(t->rgD, N));
1344 fprintf(fp, "xbestever found after %.0f evaluations, function value %g\n",
1345 t->rgxbestever[N+1], t->rgxbestever[N]);
1346 for(i=0; i<N; ++i)
1347 fprintf(fp, " %12g%c", t->rgxbestever[i],
1348 (i%5==4||i==N-1)?'\n':' ');
1349 fprintf(fp, "xbest (of last generation, function value %g)\n",
1350 t->rgrgx[t->index[0]][N]);
1351 for(i=0; i<N; ++i)
1352 fprintf(fp, " %12g%c", t->rgrgx[t->index[0]][i],
1353 (i%5==4||i==N-1)?'\n':' ');
1354 fprintf(fp, "xmean \n");
1355 for(i=0; i<N; ++i)
1356 fprintf(fp, " %12g%c", t->rgxmean[i],
1357 (i%5==4||i==N-1)?'\n':' ');
1358 fprintf(fp, "Standard deviation of coordinate axes (sigma*sqrt(diag(C)))\n");
1359 for(i=0; i<N; ++i)
1360 fprintf(fp, " %12g%c", t->sigma*sqrt(t->C[i][i]),
1361 (i%5==4||i==N-1)?'\n':' ');
1362 fprintf(fp, "Main axis lengths of mutation ellipsoid (sigma*diag(D))\n");
1363 for (i = 0; i < N; ++i)
1364 t->rgdTmp[i] = t->rgD[i];
1365 qsort(t->rgdTmp, (unsigned) N, sizeof(double), &SignOfDiff);
1366 for(i=0; i<N; ++i)
1367 fprintf(fp, " %12g%c", t->sigma*t->rgdTmp[N-1-i],
1368 (i%5==4||i==N-1)?'\n':' ');
1369 fprintf(fp, "Longest axis (b_i where d_ii=max(diag(D))\n");
1370 k = MaxIdx(t->rgD, N);
1371 for(i=0; i<N; ++i)
1372 fprintf(fp, " %12g%c", t->B[i][k], (i%5==4||i==N-1)?'\n':' ');
1373 fprintf(fp, "Shortest axis (b_i where d_ii=max(diag(D))\n");
1374 k = MinIdx(t->rgD, N);
1375 for(i=0; i<N; ++i)
1376 fprintf(fp, " %12g%c", t->B[i][k], (i%5==4||i==N-1)?'\n':' ');
1377 while (*key != '+' && *key != '\0' && key < keyend)
1378 ++key;
1379 } /* "all" */
1380
1381 #if 0 /* could become generic part */
1382 s0 = key;
1383 d = cmaes_Get(t, key); /* TODO find way to detect whether key was found */
1384 if (key == s0) /* this does not work, is always true */
1385 {
1386 /* write out stuff, problem: only generic format is available */
1387 /* move in key until "+" or end */
1388 }
1389 #endif
1390
1391 if (*key == '\0')
1392 break;
1393 else if (*key != '+') { /* last key was not recognized */
1394 ERRORMESSAGE("cmaes_t:WriteToFilePtr(): unrecognized key '", key, "'", 0);
1395 while (*key != '+' && *key != '\0' && key < keyend)
1396 ++key;
1397 }
1398 while (*key == '+')
1399 ++key;
1400 } /* while key < keyend */
1401
1402 if (key > keyend)
1403 FATAL("cmaes_t:WriteToFilePtr(): BUG regarding key sequence",0,0,0);
1404
1405 } /* WriteToFilePtr */
1406
1407 /* --------------------------------------------------------- */
1408 double
cmaes_Get(cmaes_t * t,char const * s)1409 cmaes_Get( cmaes_t *t, char const *s)
1410 {
1411 int N=t->sp.N;
1412
1413 if (strncmp(s, "axisratio", 5) == 0) { /* between lengths of longest and shortest principal axis of the distribution ellipsoid */
1414 return (rgdouMax(t->rgD, N)/rgdouMin(t->rgD, N));
1415 }
1416 else if (strncmp(s, "eval", 4) == 0) { /* number of function evaluations */
1417 return (t->countevals);
1418 }
1419 else if (strncmp(s, "fctvalue", 6) == 0
1420 || strncmp(s, "funcvalue", 6) == 0
1421 || strncmp(s, "funvalue", 6) == 0
1422 || strncmp(s, "fitness", 3) == 0) { /* recent best function value */
1423 return(t->rgFuncValue[t->index[0]]);
1424 }
1425 else if (strncmp(s, "fbestever", 7) == 0) { /* ever best function value */
1426 return(t->rgxbestever[N]);
1427 }
1428 else if (strncmp(s, "generation", 3) == 0
1429 || strncmp(s, "iteration", 4) == 0) {
1430 return(t->gen);
1431 }
1432 else if (strncmp(s, "maxeval", 4) == 0
1433 || strncmp(s, "MaxFunEvals", 8) == 0
1434 || strncmp(s, "stopMaxFunEvals", 12) == 0) { /* maximal number of function evaluations */
1435 return(t->sp.stopMaxFunEvals);
1436 }
1437 else if (strncmp(s, "maxgen", 4) == 0
1438 || strncmp(s, "MaxIter", 7) == 0
1439 || strncmp(s, "stopMaxIter", 11) == 0) { /* maximal number of generations */
1440 return(ceil(t->sp.stopMaxIter));
1441 }
1442 else if (strncmp(s, "maxaxislength", 5) == 0) { /* sigma * max(diag(D)) */
1443 return(t->sigma * sqrt(t->maxEW));
1444 }
1445 else if (strncmp(s, "minaxislength", 5) == 0) { /* sigma * min(diag(D)) */
1446 return(t->sigma * sqrt(t->minEW));
1447 }
1448 else if (strncmp(s, "maxstddev", 4) == 0) { /* sigma * sqrt(max(diag(C))) */
1449 return(t->sigma * sqrt(t->maxdiagC));
1450 }
1451 else if (strncmp(s, "minstddev", 4) == 0) { /* sigma * sqrt(min(diag(C))) */
1452 return(t->sigma * sqrt(t->mindiagC));
1453 }
1454 else if (strncmp(s, "N", 1) == 0 || strcmp(s, "n") == 0 ||
1455 strncmp(s, "dimension", 3) == 0) {
1456 return (N);
1457 }
1458 else if (strncmp(s, "lambda", 3) == 0
1459 || strncmp(s, "samplesize", 8) == 0
1460 || strncmp(s, "popsize", 7) == 0) { /* sample size, offspring population size */
1461 return(t->sp.lambda);
1462 }
1463 else if (strncmp(s, "sigma", 3) == 0) {
1464 return(t->sigma);
1465 }
1466 FATAL( "cmaes_Get(cmaes_t, char const * s): No match found for s='", s, "'",0);
1467 return(0);
1468 } /* cmaes_Get() */
1469
1470 /* --------------------------------------------------------- */
1471 double *
cmaes_GetInto(cmaes_t * t,char const * s,double * res)1472 cmaes_GetInto( cmaes_t *t, char const *s, double *res)
1473 {
1474 int i, N = t->sp.N;
1475 double const * res0 = cmaes_GetPtr(t, s);
1476 if (res == NULL)
1477 res = new_double(N);
1478 for (i = 0; i < N; ++i)
1479 res[i] = res0[i];
1480 return res;
1481 }
1482
1483 /* --------------------------------------------------------- */
1484 double *
cmaes_GetNew(cmaes_t * t,char const * s)1485 cmaes_GetNew( cmaes_t *t, char const *s)
1486 {
1487 return (cmaes_GetInto(t, s, NULL));
1488 }
1489
1490 /* --------------------------------------------------------- */
1491 const double *
cmaes_GetPtr(cmaes_t * t,char const * s)1492 cmaes_GetPtr( cmaes_t *t, char const *s)
1493 {
1494 int i, N=t->sp.N;
1495
1496 /* diagonal of covariance matrix */
1497 if (strncmp(s, "diag(C)", 7) == 0) {
1498 for (i = 0; i < N; ++i)
1499 t->rgout[i] = t->C[i][i];
1500 return(t->rgout);
1501 }
1502 /* diagonal of axis lengths matrix */
1503 else if (strncmp(s, "diag(D)", 7) == 0) {
1504 return(t->rgD);
1505 }
1506 /* vector of standard deviations sigma*sqrt(diag(C)) */
1507 else if (strncmp(s, "stddev", 3) == 0) {
1508 for (i = 0; i < N; ++i)
1509 t->rgout[i] = t->sigma * sqrt(t->C[i][i]);
1510 return(t->rgout);
1511 }
1512 /* bestever solution seen so far */
1513 else if (strncmp(s, "xbestever", 7) == 0)
1514 return(t->rgxbestever);
1515 /* recent best solution of the recent population */
1516 else if (strncmp(s, "xbest", 5) == 0)
1517 return(t->rgrgx[t->index[0]]);
1518 /* mean of the recent distribution */
1519 else if (strncmp(s, "xmean", 1) == 0)
1520 return(t->rgxmean);
1521
1522 return(NULL);
1523 }
1524
1525 /* --------------------------------------------------------- */
1526 /* tests stopping criteria
1527 * returns a string of satisfied stopping criterion for each line
1528 * otherwise NULL
1529 */
1530 const char *
cmaes_TestForTermination(cmaes_t * t)1531 cmaes_TestForTermination( cmaes_t *t)
1532 {
1533 double range, fac;
1534 int iAchse, iKoo;
1535 int flgdiag = ((t->sp.diagonalCov == 1) || (t->sp.diagonalCov >= t->gen));
1536 static char sTestOutString[3024];
1537 char * cp = sTestOutString;
1538 int i, cTemp, N=t->sp.N;
1539 cp[0] = '\0';
1540
1541 /* function value reached */
1542 if ((t->gen > 1 || t->state > 1) && t->sp.stStopFitness.flg &&
1543 t->rgFuncValue[t->index[0]] <= t->sp.stStopFitness.val)
1544 cp += sprintf(cp, "Fitness: function value %7.2e <= stopFitness (%7.2e)\n",
1545 t->rgFuncValue[t->index[0]], t->sp.stStopFitness.val);
1546
1547 /* TolFun */
1548 range = douMax(rgdouMax(t->arFuncValueHist, (int)douMin(t->gen,*(t->arFuncValueHist-1))),
1549 rgdouMax(t->rgFuncValue, t->sp.lambda)) -
1550 douMin(rgdouMin(t->arFuncValueHist, (int)douMin(t->gen, *(t->arFuncValueHist-1))),
1551 rgdouMin(t->rgFuncValue, t->sp.lambda));
1552
1553 if (t->gen > 0 && range <= t->sp.stopTolFun) {
1554 cp += sprintf(cp,
1555 "TolFun: function value differences %7.2e < stopTolFun=%7.2e\n",
1556 range, t->sp.stopTolFun);
1557 }
1558
1559 /* TolFunHist */
1560 if (t->gen > *(t->arFuncValueHist-1)) {
1561 range = rgdouMax(t->arFuncValueHist, (int)*(t->arFuncValueHist-1))
1562 - rgdouMin(t->arFuncValueHist, (int)*(t->arFuncValueHist-1));
1563 if (range <= t->sp.stopTolFunHist)
1564 cp += sprintf(cp,
1565 "TolFunHist: history of function value changes %7.2e stopTolFunHist=%7.2e",
1566 range, t->sp.stopTolFunHist);
1567 }
1568
1569 /* TolX */
1570 for(i=0, cTemp=0; i<N; ++i) {
1571 cTemp += (t->sigma * sqrt(t->C[i][i]) < t->sp.stopTolX) ? 1 : 0;
1572 cTemp += (t->sigma * t->rgpc[i] < t->sp.stopTolX) ? 1 : 0;
1573 }
1574 if (cTemp == 2*N) {
1575 cp += sprintf(cp,
1576 "TolX: object variable changes below %7.2e \n",
1577 t->sp.stopTolX);
1578 }
1579
1580 /* TolUpX */
1581 for(i=0; i<N; ++i) {
1582 if (t->sigma * sqrt(t->C[i][i]) > t->sp.stopTolUpXFactor * t->sp.rgInitialStds[i])
1583 break;
1584 }
1585 if (i < N) {
1586 cp += sprintf(cp,
1587 "TolUpX: standard deviation increased by more than %7.2e, larger initial standard deviation recommended \n",
1588 t->sp.stopTolUpXFactor);
1589 }
1590
1591 /* Condition of C greater than dMaxSignifKond */
1592 if (t->maxEW >= t->minEW * t->dMaxSignifKond) {
1593 cp += sprintf(cp,
1594 "ConditionNumber: maximal condition number %7.2e reached. maxEW=%7.2e,minEW=%7.2e,maxdiagC=%7.2e,mindiagC=%7.2e\n",
1595 t->dMaxSignifKond, t->maxEW, t->minEW, t->maxdiagC, t->mindiagC);
1596 } /* if */
1597
1598 /* Principal axis i has no effect on xmean, ie.
1599 x == x + 0.1 * sigma * rgD[i] * B[i] */
1600 if (!flgdiag) {
1601 for (iAchse = 0; iAchse < N; ++iAchse)
1602 {
1603 fac = 0.1 * t->sigma * t->rgD[iAchse];
1604 for (iKoo = 0; iKoo < N; ++iKoo){
1605 if (t->rgxmean[iKoo] != t->rgxmean[iKoo] + fac * t->B[iKoo][iAchse])
1606 break;
1607 }
1608 if (iKoo == N)
1609 {
1610 /* t->sigma *= exp(0.2+t->sp.cs/t->sp.damps); */
1611 cp += sprintf(cp,
1612 "NoEffectAxis: standard deviation 0.1*%7.2e in principal axis %d without effect\n",
1613 fac/0.1, iAchse);
1614 break;
1615 } /* if (iKoo == N) */
1616 } /* for iAchse */
1617 } /* if flgdiag */
1618 /* Component of xmean is not changed anymore */
1619 for (iKoo = 0; iKoo < N; ++iKoo)
1620 {
1621 if (t->rgxmean[iKoo] == t->rgxmean[iKoo] +
1622 0.2*t->sigma*sqrt(t->C[iKoo][iKoo]))
1623 {
1624 /* t->C[iKoo][iKoo] *= (1 + t->sp.ccov); */
1625 /* flg = 1; */
1626 cp += sprintf(cp,
1627 "NoEffectCoordinate: standard deviation 0.2*%7.2e in coordinate %d without effect\n",
1628 t->sigma*sqrt(t->C[iKoo][iKoo]), iKoo);
1629 break;
1630 }
1631
1632 } /* for iKoo */
1633 /* if (flg) t->sigma *= exp(0.05+t->sp.cs/t->sp.damps); */
1634
1635 if(t->countevals >= t->sp.stopMaxFunEvals)
1636 cp += sprintf(cp, "MaxFunEvals: conducted function evaluations %.0f >= %g\n",
1637 t->countevals, t->sp.stopMaxFunEvals);
1638 if(t->gen >= t->sp.stopMaxIter)
1639 cp += sprintf(cp, "MaxIter: number of iterations %.0f >= %g\n",
1640 t->gen, t->sp.stopMaxIter);
1641 if(t->flgStop)
1642 cp += sprintf(cp, "Manual: stop signal read\n");
1643
1644 #if 0
1645 else if (0) {
1646 for(i=0, cTemp=0; i<N; ++i) {
1647 cTemp += (sigma * sqrt(C[i][i]) < stopdx) ? 1 : 0;
1648 cTemp += (sigma * rgpc[i] < stopdx) ? 1 : 0;
1649 }
1650 if (cTemp == 2*N)
1651 flgStop = 1;
1652 }
1653 #endif
1654
1655 if (cp - sTestOutString>320)
1656 ERRORMESSAGE("Bug in cmaes_t:Test(): sTestOutString too short",0,0,0);
1657
1658 if (cp != sTestOutString) {
1659 return sTestOutString;
1660 }
1661
1662 return(NULL);
1663
1664 } /* cmaes_Test() */
1665
1666 /* --------------------------------------------------------- */
cmaes_ReadSignals(cmaes_t * t,char const * filename)1667 void cmaes_ReadSignals(cmaes_t *t, char const *filename)
1668 {
1669 const char *s = "cmaes_signals.par";
1670 FILE *fp;
1671 if (filename == NULL)
1672 filename = s;
1673 /* if (filename) assign_string(&(t->signalsFilename), filename)*/
1674 fp = fopen( filename, "r");
1675 if(fp == NULL) {
1676 return;
1677 }
1678 cmaes_ReadFromFilePtr( t, fp);
1679 fclose(fp);
1680 }
1681 /* --------------------------------------------------------- */
cmaes_ReadFromFilePtr(cmaes_t * t,FILE * fp)1682 void cmaes_ReadFromFilePtr( cmaes_t *t, FILE *fp)
1683 /* reading commands e.g. from signals.par file
1684 */
1685 {
1686 const char *keys[15]; /* key strings for scanf */
1687 char s[199], sin1[99], sin2[129], sin3[99], sin4[99];
1688 int ikey, ckeys, nb;
1689 double d;
1690 static int flglockprint = 0;
1691 static int flglockwrite = 0;
1692 static long countiterlastwritten;
1693 static long maxdiffitertowrite; /* to prevent long gaps at the beginning */
1694 int flgprinted = 0;
1695 int flgwritten = 0;
1696 double deltaprinttime = (double)(time(NULL)-t->printtime); /* using clock instead might not be a good */
1697 double deltawritetime = (double)(time(NULL)-t->writetime); /* idea as disc time is not CPU time? */
1698 double deltaprinttimefirst = (double)(t->firstprinttime ? time(NULL)-t->firstprinttime : 0); /* time is in seconds!? */
1699 double deltawritetimefirst = (double)(t->firstwritetime ? time(NULL)-t->firstwritetime : 0);
1700 if (countiterlastwritten > t->gen) { /* probably restarted */
1701 maxdiffitertowrite = 0;
1702 countiterlastwritten = 0;
1703 }
1704
1705 keys[0] = " stop%98s %98s"; /* s=="now" or eg "MaxIter+" %lg"-number */
1706 /* works with and without space */
1707 keys[1] = " print %98s %98s"; /* s==keyword for WriteFile */
1708 keys[2] = " write %98s %128s %98s"; /* s1==keyword, s2==filename */
1709 keys[3] = " check%98s %98s";
1710 keys[4] = " maxTimeFractionForEigendecompostion %98s";
1711 ckeys = 5;
1712 strcpy(sin2, "tmpcmaes.dat");
1713
1714 if (cmaes_TestForTermination(t))
1715 {
1716 deltaprinttime = (double)time(NULL); /* forces printing */
1717 deltawritetime = (double)time(NULL);
1718 }
1719 while(fgets(s, sizeof(s), fp) != NULL)
1720 {
1721 if (s[0] == '#' || s[0] == '%') /* skip comments */
1722 continue;
1723 sin1[0] = sin2[0] = sin3[0] = sin4[0] = '\0';
1724 for (ikey=0; ikey < ckeys; ++ikey)
1725 {
1726 if((nb=sscanf(s, keys[ikey], sin1, sin2, sin3, sin4)) >= 1)
1727 {
1728 switch(ikey) {
1729 case 0 : /* "stop", reads "stop now" or eg. stopMaxIter */
1730 if (strncmp(sin1, "now", 3) == 0)
1731 t->flgStop = 1;
1732 else if (strncmp(sin1, "MaxFunEvals", 11) == 0) {
1733 if (sscanf(sin2, " %lg", &d) == 1)
1734 t->sp.stopMaxFunEvals = d;
1735 }
1736 else if (strncmp(sin1, "MaxIter", 4) == 0) {
1737 if (sscanf(sin2, " %lg", &d) == 1)
1738 t->sp.stopMaxIter = d;
1739 }
1740 else if (strncmp(sin1, "Fitness", 7) == 0) {
1741 if (sscanf(sin2, " %lg", &d) == 1)
1742 {
1743 t->sp.stStopFitness.flg = 1;
1744 t->sp.stStopFitness.val = d;
1745 }
1746 }
1747 else if (strncmp(sin1, "TolFunHist", 10) == 0) {
1748 if (sscanf(sin2, " %lg", &d) == 1)
1749 t->sp.stopTolFunHist = d;
1750 }
1751 else if (strncmp(sin1, "TolFun", 6) == 0) {
1752 if (sscanf(sin2, " %lg", &d) == 1)
1753 t->sp.stopTolFun = d;
1754 }
1755 else if (strncmp(sin1, "TolX", 4) == 0) {
1756 if (sscanf(sin2, " %lg", &d) == 1)
1757 t->sp.stopTolX = d;
1758 }
1759 else if (strncmp(sin1, "TolUpXFactor", 4) == 0) {
1760 if (sscanf(sin2, " %lg", &d) == 1)
1761 t->sp.stopTolUpXFactor = d;
1762 }
1763 break;
1764 case 1 : /* "print" */
1765 d = 1; /* default */
1766 if (sscanf(sin2, "%lg", &d) < 1 && deltaprinttimefirst < 1)
1767 d = 0; /* default at first time */
1768 if (deltaprinttime >= d && !flglockprint) {
1769 cmaes_WriteToFilePtr(t, sin1, stdout);
1770 flgprinted = 1;
1771 }
1772 if(d < 0)
1773 flglockprint += 2;
1774 break;
1775 case 2 : /* "write" */
1776 /* write header, before first generation */
1777 if (t->countevals < t->sp.lambda && t->flgresumedone == 0)
1778 cmaes_WriteToFileAW(t, sin1, sin2, "w"); /* overwrite */
1779 d = 0.9; /* default is one with smooth increment of gaps */
1780 if (sscanf(sin3, "%lg", &d) < 1 && deltawritetimefirst < 2)
1781 d = 0; /* default is zero for the first second */
1782 if(d < 0)
1783 flglockwrite += 2;
1784 if (!flglockwrite) {
1785 if (deltawritetime >= d) {
1786 cmaes_WriteToFile(t, sin1, sin2);
1787 flgwritten = 1;
1788 } else if (d < 1
1789 && t->gen-countiterlastwritten > maxdiffitertowrite) {
1790 cmaes_WriteToFile(t, sin1, sin2);
1791 flgwritten = 1;
1792 }
1793 }
1794 break;
1795 case 3 : /* check, checkeigen 1 or check eigen 1 */
1796 if (strncmp(sin1, "eigen", 5) == 0) {
1797 if (sscanf(sin2, " %lg", &d) == 1) {
1798 if (d > 0)
1799 t->flgCheckEigen = 1;
1800 else
1801 t->flgCheckEigen = 0;
1802 }
1803 else
1804 t->flgCheckEigen = 0;
1805 }
1806 break;
1807 case 4 : /* maxTimeFractionForEigendecompostion */
1808 if (sscanf(sin1, " %lg", &d) == 1)
1809 t->sp.updateCmode.maxtime = d;
1810 break;
1811 default :
1812 break;
1813 }
1814 break; /* for ikey */
1815 } /* if line contains keyword */
1816 } /* for each keyword */
1817 } /* while not EOF of signals.par */
1818 if (t->writetime == 0)
1819 t->firstwritetime = time(NULL);
1820 if (t->printtime == 0)
1821 t->firstprinttime = time(NULL);
1822
1823 if (flgprinted)
1824 t->printtime = time(NULL);
1825 if (flgwritten) {
1826 t->writetime = time(NULL);
1827 if (t->gen-countiterlastwritten > maxdiffitertowrite)
1828 ++maxdiffitertowrite; /* smooth prolongation of writing gaps/intervals */
1829 countiterlastwritten = (long int) t->gen;
1830 }
1831 --flglockprint;
1832 --flglockwrite;
1833 flglockprint = (flglockprint > 0) ? 1 : 0;
1834 flglockwrite = (flglockwrite > 0) ? 1 : 0;
1835 } /* cmaes_ReadFromFilePtr */
1836
1837 /* ========================================================= */
1838 static int
Check_Eigen(int N,double ** C,double * diag,double ** Q)1839 Check_Eigen( int N, double **C, double *diag, double **Q)
1840 /*
1841 exhaustive test of the output of the eigendecomposition
1842 needs O(n^3) operations
1843
1844 writes to error file
1845 returns number of detected inaccuracies
1846 */
1847 {
1848 /* compute Q diag Q^T and Q Q^T to check */
1849 int i, j, k, res = 0;
1850 double cc, dd;
1851 static char s[324];
1852
1853 for (i=0; i < N; ++i)
1854 for (j=0; j < N; ++j) {
1855 for (cc=0.,dd=0., k=0; k < N; ++k) {
1856 cc += diag[k] * Q[i][k] * Q[j][k];
1857 dd += Q[i][k] * Q[j][k];
1858 }
1859 /* check here, is the normalization the right one? */
1860 if (fabs(cc - C[i>j?i:j][i>j?j:i])/sqrt(C[i][i]*C[j][j]) > 1e-10
1861 && fabs(cc - C[i>j?i:j][i>j?j:i]) > 3e-14) {
1862 sprintf(s, "%d %d: %.17e %.17e, %e",
1863 i, j, cc, C[i>j?i:j][i>j?j:i], cc-C[i>j?i:j][i>j?j:i]);
1864 ERRORMESSAGE("cmaes_t:Eigen(): imprecise result detected ",
1865 s, 0, 0);
1866 ++res;
1867 }
1868 if (fabs(dd - (i==j)) > 1e-10) {
1869 sprintf(s, "%d %d %.17e ", i, j, dd);
1870 ERRORMESSAGE("cmaes_t:Eigen(): imprecise result detected (Q not orthog.)",
1871 s, 0, 0);
1872 ++res;
1873 }
1874 }
1875 return res;
1876 }
1877
1878 /* --------------------------------------------------------- */
1879 /* --------------------------------------------------------- */
1880 void
cmaes_UpdateEigensystem(cmaes_t * t,int flgforce)1881 cmaes_UpdateEigensystem(cmaes_t *t, int flgforce)
1882 {
1883 int i, N = t->sp.N;
1884
1885 cmaes_timings_update(&t->eigenTimings);
1886
1887 if(flgforce == 0) {
1888 if (t->flgEigensysIsUptodate == 1)
1889 return;
1890
1891 /* return on modulo generation number */
1892 if (t->sp.updateCmode.flgalways == 0 /* not implemented, always ==0 */
1893 && t->gen < t->genOfEigensysUpdate + t->sp.updateCmode.modulo
1894 )
1895 return;
1896
1897 /* return on time percentage */
1898 if (t->sp.updateCmode.maxtime < 1.00
1899 && t->eigenTimings.tictoctime > t->sp.updateCmode.maxtime * t->eigenTimings.totaltime
1900 && t->eigenTimings.tictoctime > 0.0002)
1901 return;
1902 }
1903 cmaes_timings_tic(&t->eigenTimings);
1904
1905 Eigen( N, t->C, t->rgD, t->B, t->rgdTmp);
1906
1907 cmaes_timings_toc(&t->eigenTimings);
1908
1909 /* find largest and smallest eigenvalue, they are supposed to be sorted anyway */
1910 t->minEW = rgdouMin(t->rgD, N);
1911 t->maxEW = rgdouMax(t->rgD, N);
1912
1913 if (t->flgCheckEigen)
1914 /* needs O(n^3)! writes, in case, error message in error file */
1915 i = Check_Eigen( N, t->C, t->rgD, t->B);
1916
1917 #if 0
1918 /* Limit Condition of C to dMaxSignifKond+1 */
1919 if (t->maxEW > t->minEW * t->dMaxSignifKond) {
1920 ERRORMESSAGE("Warning: Condition number of covariance matrix at upper limit.",
1921 " Consider a rescaling or redesign of the objective function. " ,"","");
1922 printf("\nWarning: Condition number of covariance matrix at upper limit\n");
1923 tmp = t->maxEW/t->dMaxSignifKond - t->minEW;
1924 tmp = t->maxEW/t->dMaxSignifKond;
1925 t->minEW += tmp;
1926 for (i=0;i<N;++i) {
1927 t->C[i][i] += tmp;
1928 t->rgD[i] += tmp;
1929 }
1930 } /* if */
1931 t->dLastMinEWgroesserNull = minEW;
1932 #endif
1933
1934 for (i = 0; i < N; ++i)
1935 t->rgD[i] = sqrt(t->rgD[i]);
1936
1937 t->flgEigensysIsUptodate = 1;
1938 t->genOfEigensysUpdate = t->gen;
1939
1940 return;
1941
1942 } /* cmaes_UpdateEigensystem() */
1943
1944
1945 /* ========================================================= */
1946 static void
Eigen(int N,double ** C,double * diag,double ** Q,double * rgtmp)1947 Eigen( int N, double **C, double *diag, double **Q, double *rgtmp)
1948 /*
1949 Calculating eigenvalues and vectors.
1950 Input:
1951 N: dimension.
1952 C: symmetric (1:N)xN-matrix, solely used to copy data to Q
1953 niter: number of maximal iterations for QL-Algorithm.
1954 rgtmp: N+1-dimensional vector for temporal use.
1955 Output:
1956 diag: N eigenvalues.
1957 Q: Columns are normalized eigenvectors.
1958 */
1959 {
1960 int i, j;
1961
1962 if (rgtmp == NULL) /* was OK in former versions */
1963 FATAL("cmaes_t:Eigen(): input parameter double *rgtmp must be non-NULL", 0,0,0);
1964
1965 /* copy C to Q */
1966 if (C != Q) {
1967 for (i=0; i < N; ++i)
1968 for (j = 0; j <= i; ++j)
1969 Q[i][j] = Q[j][i] = C[i][j];
1970 }
1971
1972 #if 0
1973 Householder( N, Q, diag, rgtmp);
1974 QLalgo( N, diag, Q, 30*N, rgtmp+1);
1975 #else
1976 Householder2( N, Q, diag, rgtmp);
1977 QLalgo2( N, diag, rgtmp, Q);
1978 #endif
1979
1980 }
1981
1982
1983 /* ========================================================= */
1984 static void
QLalgo2(int n,double * d,double * e,double ** V)1985 QLalgo2 (int n, double *d, double *e, double **V) {
1986 /*
1987 -> n : Dimension.
1988 -> d : Diagonale of tridiagonal matrix.
1989 -> e[1..n-1] : off-diagonal, output from Householder
1990 -> V : matrix output von Householder
1991 <- d : eigenvalues
1992 <- e : garbage?
1993 <- V : basis of eigenvectors, according to d
1994
1995 Symmetric tridiagonal QL algorithm, iterative
1996 Computes the eigensystem from a tridiagonal matrix in roughtly 3N^3 operations
1997
1998 code adapted from Java JAMA package, function tql2.
1999 */
2000
2001 int i, k, l, m;
2002 double f = 0.0;
2003 double tst1 = 0.0;
2004 double eps = 2.22e-16; /* Math.pow(2.0,-52.0); == 2.22e-16 */
2005
2006 /* shift input e */
2007 for (i = 1; i < n; i++) {
2008 e[i-1] = e[i];
2009 }
2010 e[n-1] = 0.0; /* never changed again */
2011
2012 for (l = 0; l < n; l++) {
2013
2014 /* Find small subdiagonal element */
2015
2016 if (tst1 < fabs(d[l]) + fabs(e[l]))
2017 tst1 = fabs(d[l]) + fabs(e[l]);
2018 m = l;
2019 while (m < n) {
2020 if (fabs(e[m]) <= eps*tst1) {
2021 /* if (fabs(e[m]) + fabs(d[m]+d[m+1]) == fabs(d[m]+d[m+1])) { */
2022 break;
2023 }
2024 m++;
2025 }
2026
2027 /* If m == l, d[l] is an eigenvalue, */
2028 /* otherwise, iterate. */
2029
2030 if (m > l) { /* TODO: check the case m == n, should be rejected here!? */
2031 int iter = 0;
2032 do { /* while (fabs(e[l]) > eps*tst1); */
2033 double dl1, h;
2034 double g = d[l];
2035 double p = (d[l+1] - g) / (2.0 * e[l]);
2036 double r = myhypot(p, 1.);
2037
2038 iter = iter + 1; /* Could check iteration count here */
2039
2040 /* Compute implicit shift */
2041
2042 if (p < 0) {
2043 r = -r;
2044 }
2045 d[l] = e[l] / (p + r);
2046 d[l+1] = e[l] * (p + r);
2047 dl1 = d[l+1];
2048 h = g - d[l];
2049 for (i = l+2; i < n; i++) {
2050 d[i] -= h;
2051 }
2052 f = f + h;
2053
2054 /* Implicit QL transformation. */
2055
2056 p = d[m];
2057 {
2058 double c = 1.0;
2059 double c2 = c;
2060 double c3 = c;
2061 double el1 = e[l+1];
2062 double s = 0.0;
2063 double s2 = 0.0;
2064 for (i = m-1; i >= l; i--) {
2065 c3 = c2;
2066 c2 = c;
2067 s2 = s;
2068 g = c * e[i];
2069 h = c * p;
2070 r = myhypot(p, e[i]);
2071 e[i+1] = s * r;
2072 s = e[i] / r;
2073 c = p / r;
2074 p = c * d[i] - s * g;
2075 d[i+1] = h + s * (c * g + s * d[i]);
2076
2077 /* Accumulate transformation. */
2078
2079 for (k = 0; k < n; k++) {
2080 h = V[k][i+1];
2081 V[k][i+1] = s * V[k][i] + c * h;
2082 V[k][i] = c * V[k][i] - s * h;
2083 }
2084 }
2085 p = -s * s2 * c3 * el1 * e[l] / dl1;
2086 e[l] = s * p;
2087 d[l] = c * p;
2088 }
2089
2090 /* Check for convergence. */
2091
2092 } while (fabs(e[l]) > eps*tst1);
2093 }
2094 d[l] = d[l] + f;
2095 e[l] = 0.0;
2096 }
2097
2098 /* Sort eigenvalues and corresponding vectors. */
2099 #if 1
2100 /* TODO: really needed here? So far not, but practical and only O(n^2) */
2101 {
2102 int j;
2103 double p;
2104 for (i = 0; i < n-1; i++) {
2105 k = i;
2106 p = d[i];
2107 for (j = i+1; j < n; j++) {
2108 if (d[j] < p) {
2109 k = j;
2110 p = d[j];
2111 }
2112 }
2113 if (k != i) {
2114 d[k] = d[i];
2115 d[i] = p;
2116 for (j = 0; j < n; j++) {
2117 p = V[j][i];
2118 V[j][i] = V[j][k];
2119 V[j][k] = p;
2120 }
2121 }
2122 }
2123 }
2124 #endif
2125 } /* QLalgo2 */
2126
2127
2128 /* ========================================================= */
2129 static void
Householder2(int n,double ** V,double * d,double * e)2130 Householder2(int n, double **V, double *d, double *e) {
2131 /*
2132 Householder transformation of a symmetric matrix V into tridiagonal form.
2133 -> n : dimension
2134 -> V : symmetric nxn-matrix
2135 <- V : orthogonal transformation matrix:
2136 tridiag matrix == V * V_in * V^t
2137 <- d : diagonal
2138 <- e[0..n-1] : off diagonal (elements 1..n-1)
2139
2140 code slightly adapted from the Java JAMA package, function private tred2()
2141
2142 */
2143
2144 int i,j,k;
2145
2146 for (j = 0; j < n; j++) {
2147 d[j] = V[n-1][j];
2148 }
2149
2150 /* Householder reduction to tridiagonal form */
2151
2152 for (i = n-1; i > 0; i--) {
2153
2154 /* Scale to avoid under/overflow */
2155
2156 double scale = 0.0;
2157 double h = 0.0;
2158 for (k = 0; k < i; k++) {
2159 scale = scale + fabs(d[k]);
2160 }
2161 if (scale == 0.0) {
2162 e[i] = d[i-1];
2163 for (j = 0; j < i; j++) {
2164 d[j] = V[i-1][j];
2165 V[i][j] = 0.0;
2166 V[j][i] = 0.0;
2167 }
2168 } else {
2169
2170 /* Generate Householder vector */
2171
2172 double f, g, hh;
2173
2174 for (k = 0; k < i; k++) {
2175 d[k] /= scale;
2176 h += d[k] * d[k];
2177 }
2178 f = d[i-1];
2179 g = sqrt(h);
2180 if (f > 0) {
2181 g = -g;
2182 }
2183 e[i] = scale * g;
2184 h = h - f * g;
2185 d[i-1] = f - g;
2186 for (j = 0; j < i; j++) {
2187 e[j] = 0.0;
2188 }
2189
2190 /* Apply similarity transformation to remaining columns */
2191
2192 for (j = 0; j < i; j++) {
2193 f = d[j];
2194 V[j][i] = f;
2195 g = e[j] + V[j][j] * f;
2196 for (k = j+1; k <= i-1; k++) {
2197 g += V[k][j] * d[k];
2198 e[k] += V[k][j] * f;
2199 }
2200 e[j] = g;
2201 }
2202 f = 0.0;
2203 for (j = 0; j < i; j++) {
2204 e[j] /= h;
2205 f += e[j] * d[j];
2206 }
2207 hh = f / (h + h);
2208 for (j = 0; j < i; j++) {
2209 e[j] -= hh * d[j];
2210 }
2211 for (j = 0; j < i; j++) {
2212 f = d[j];
2213 g = e[j];
2214 for (k = j; k <= i-1; k++) {
2215 V[k][j] -= (f * e[k] + g * d[k]);
2216 }
2217 d[j] = V[i-1][j];
2218 V[i][j] = 0.0;
2219 }
2220 }
2221 d[i] = h;
2222 }
2223
2224 /* Accumulate transformations */
2225
2226 for (i = 0; i < n-1; i++) {
2227 double h;
2228 V[n-1][i] = V[i][i];
2229 V[i][i] = 1.0;
2230 h = d[i+1];
2231 if (h != 0.0) {
2232 for (k = 0; k <= i; k++) {
2233 d[k] = V[k][i+1] / h;
2234 }
2235 for (j = 0; j <= i; j++) {
2236 double g = 0.0;
2237 for (k = 0; k <= i; k++) {
2238 g += V[k][i+1] * V[k][j];
2239 }
2240 for (k = 0; k <= i; k++) {
2241 V[k][j] -= g * d[k];
2242 }
2243 }
2244 }
2245 for (k = 0; k <= i; k++) {
2246 V[k][i+1] = 0.0;
2247 }
2248 }
2249 for (j = 0; j < n; j++) {
2250 d[j] = V[n-1][j];
2251 V[n-1][j] = 0.0;
2252 }
2253 V[n-1][n-1] = 1.0;
2254 e[0] = 0.0;
2255
2256 } /* Housholder() */
2257
2258
2259 #if 0
2260 /* ========================================================= */
2261 static void
2262 WriteMaxErrorInfo(cmaes_t *t)
2263 {
2264 int i,j, N=t->sp.N;
2265 char *s = (char *)new_void(200+30*(N+2), sizeof(char)); s[0] = '\0';
2266
2267 sprintf( s+strlen(s),"\nComplete Info\n");
2268 sprintf( s+strlen(s)," Gen %20.12g\n", t->gen);
2269 sprintf( s+strlen(s)," Dimension %d\n", N);
2270 sprintf( s+strlen(s)," sigma %e\n", t->sigma);
2271 sprintf( s+strlen(s)," lastminEW %e\n",
2272 t->dLastMinEWgroesserNull);
2273 sprintf( s+strlen(s)," maxKond %e\n\n", t->dMaxSignifKond);
2274 sprintf( s+strlen(s)," x-vector rgD Basis...\n");
2275 ERRORMESSAGE( s,0,0,0);
2276 s[0] = '\0';
2277 for (i = 0; i < N; ++i)
2278 {
2279 sprintf( s+strlen(s), " %20.12e", t->rgxmean[i]);
2280 sprintf( s+strlen(s), " %10.4e", t->rgD[i]);
2281 for (j = 0; j < N; ++j)
2282 sprintf( s+strlen(s), " %10.2e", t->B[i][j]);
2283 ERRORMESSAGE( s,0,0,0);
2284 s[0] = '\0';
2285 }
2286 ERRORMESSAGE( "\n",0,0,0);
2287 free( s);
2288 } /* WriteMaxErrorInfo() */
2289 #endif
2290
2291 /* --------------------------------------------------------- */
2292 /* --------------- Functions: cmaes_timings_t -------------- */
2293 /* --------------------------------------------------------- */
2294 /* cmaes_timings_t measures overall time and times between calls
2295 * of tic and toc. For small time spans (up to 1000 seconds)
2296 * CPU time via clock() is used. For large time spans the
2297 * fall-back to elapsed time from time() is used.
2298 * cmaes_timings_update() must be called often enough to prevent
2299 * the fallback. */
2300 /* --------------------------------------------------------- */
2301 void
cmaes_timings_init(cmaes_timings_t * t)2302 cmaes_timings_init(cmaes_timings_t *t) {
2303 t->totaltotaltime = 0;
2304 cmaes_timings_start(t);
2305 }
2306 void
cmaes_timings_start(cmaes_timings_t * t)2307 cmaes_timings_start(cmaes_timings_t *t) {
2308 t->totaltime = 0;
2309 t->tictoctime = 0;
2310 t->lasttictoctime = 0;
2311 t->istic = 0;
2312 t->lastclock = clock();
2313 t->lasttime = time(NULL);
2314 t->lastdiff = 0;
2315 t->tictoczwischensumme = 0;
2316 t->isstarted = 1;
2317 }
2318
2319 double
cmaes_timings_update(cmaes_timings_t * t)2320 cmaes_timings_update(cmaes_timings_t *t) {
2321 /* returns time between last call of cmaes_timings_*() and now,
2322 * should better return totaltime or tictoctime?
2323 */
2324 double diffc, difft;
2325 clock_t lc = t->lastclock; /* measure CPU in 1e-6s */
2326 time_t lt = t->lasttime; /* measure time in s */
2327
2328 if (t->isstarted != 1)
2329 FATAL("cmaes_timings_started() must be called before using timings... functions",0,0,0);
2330
2331 t->lastclock = clock(); /* measures at most 2147 seconds, where 1s = 1e6 CLOCKS_PER_SEC */
2332 t->lasttime = time(NULL);
2333
2334 diffc = (double)(t->lastclock - lc) / CLOCKS_PER_SEC; /* is presumably in [-21??, 21??] */
2335 difft = difftime(t->lasttime, lt); /* is presumably an integer */
2336
2337 t->lastdiff = difft; /* on the "save" side */
2338
2339 /* use diffc clock measurement if appropriate */
2340 if (diffc > 0 && difft < 1000)
2341 t->lastdiff = diffc;
2342
2343 if (t->lastdiff < 0)
2344 FATAL("BUG in time measurement", 0, 0, 0);
2345
2346 t->totaltime += t->lastdiff;
2347 t->totaltotaltime += t->lastdiff;
2348 if (t->istic) {
2349 t->tictoczwischensumme += t->lastdiff;
2350 t->tictoctime += t->lastdiff;
2351 }
2352
2353 return t->lastdiff;
2354 }
2355
2356 void
cmaes_timings_tic(cmaes_timings_t * t)2357 cmaes_timings_tic(cmaes_timings_t *t) {
2358 if (t->istic) { /* message not necessary ? */
2359 ERRORMESSAGE("Warning: cmaes_timings_tic called twice without toc",0,0,0);
2360 return;
2361 }
2362 cmaes_timings_update(t);
2363 t->istic = 1;
2364 }
2365
2366 double
cmaes_timings_toc(cmaes_timings_t * t)2367 cmaes_timings_toc(cmaes_timings_t *t) {
2368 if (!t->istic) {
2369 ERRORMESSAGE("Warning: cmaes_timings_toc called without tic",0,0,0);
2370 return -1;
2371 }
2372 cmaes_timings_update(t);
2373 t->lasttictoctime = t->tictoczwischensumme;
2374 t->tictoczwischensumme = 0;
2375 t->istic = 0;
2376 return t->lasttictoctime;
2377 }
2378
2379 /* --------------------------------------------------------- */
2380 /* ---------------- Functions: cmaes_random_t -------------- */
2381 /* --------------------------------------------------------- */
2382 /* --------------------------------------------------------- */
2383 /* X_1 exakt : 0.79788456) */
2384 /* chi_eins simuliert : 0.798xx (seed -3) */
2385 /* +-0.001 */
2386 /* --------------------------------------------------------- */
2387 /*
2388 Gauss() liefert normalverteilte Zufallszahlen
2389 bei vorgegebenem seed.
2390 */
2391 /* --------------------------------------------------------- */
2392 /* --------------------------------------------------------- */
2393
2394 long
cmaes_random_init(cmaes_random_t * t,long unsigned inseed)2395 cmaes_random_init( cmaes_random_t *t, long unsigned inseed)
2396 {
2397 clock_t cloc = clock();
2398
2399 t->flgstored = 0;
2400 t->rgrand = (long *) new_void(32, sizeof(long));
2401 if (inseed < 1) {
2402 while ((long) (cloc - clock()) == 0)
2403 ; /* TODO: remove this for time critical applications? */
2404 inseed = (long unsigned)abs((long)(100*time(NULL)+clock()));
2405 }
2406 return cmaes_random_Start(t, inseed);
2407 }
2408
2409 void
cmaes_random_exit(cmaes_random_t * t)2410 cmaes_random_exit(cmaes_random_t *t)
2411 {
2412 free( t->rgrand);
2413 }
2414
2415 /* --------------------------------------------------------- */
cmaes_random_Start(cmaes_random_t * t,long unsigned inseed)2416 long cmaes_random_Start( cmaes_random_t *t, long unsigned inseed)
2417 {
2418 long tmp;
2419 int i;
2420
2421 t->flgstored = 0;
2422 t->startseed = inseed; /* purely for bookkeeping */
2423 while (inseed > 2e9)
2424 inseed /= 2; /* prevent infinite loop on 32 bit system */
2425 if (inseed < 1)
2426 inseed = 1;
2427 t->aktseed = inseed;
2428 for (i = 39; i >= 0; --i)
2429 {
2430 tmp = t->aktseed/127773;
2431 t->aktseed = 16807 * (t->aktseed - tmp * 127773)
2432 - 2836 * tmp;
2433 if (t->aktseed < 0) t->aktseed += 2147483647;
2434 if (i < 32)
2435 t->rgrand[i] = t->aktseed;
2436 }
2437 t->aktrand = t->rgrand[0];
2438 return inseed;
2439 }
2440
2441 /* --------------------------------------------------------- */
cmaes_random_Gauss(cmaes_random_t * t)2442 double cmaes_random_Gauss(cmaes_random_t *t)
2443 {
2444 double x1, x2, rquad, fac;
2445
2446 if (t->flgstored)
2447 {
2448 t->flgstored = 0;
2449 return t->hold;
2450 }
2451 do
2452 {
2453 x1 = 2.0 * cmaes_random_Uniform(t) - 1.0;
2454 x2 = 2.0 * cmaes_random_Uniform(t) - 1.0;
2455 rquad = x1*x1 + x2*x2;
2456 } while(rquad >= 1 || rquad <= 0);
2457 fac = sqrt(-2.0*log(rquad)/rquad);
2458 t->flgstored = 1;
2459 t->hold = fac * x1;
2460 return fac * x2;
2461 }
2462
2463 /* --------------------------------------------------------- */
cmaes_random_Uniform(cmaes_random_t * t)2464 double cmaes_random_Uniform( cmaes_random_t *t)
2465 {
2466 long tmp;
2467
2468 tmp = t->aktseed/127773;
2469 t->aktseed = 16807 * (t->aktseed - tmp * 127773)
2470 - 2836 * tmp;
2471 if (t->aktseed < 0)
2472 t->aktseed += 2147483647;
2473 tmp = t->aktrand / 67108865;
2474 t->aktrand = t->rgrand[tmp];
2475 t->rgrand[tmp] = t->aktseed;
2476 return (double)(t->aktrand)/(2.147483647e9);
2477 }
2478
2479 static char *
2480 szCat(const char *sz1, const char*sz2,
2481 const char *sz3, const char *sz4);
2482
2483 /* --------------------------------------------------------- */
2484 /* -------------- Functions: cmaes_readpara_t -------------- */
2485 /* --------------------------------------------------------- */
2486 void
cmaes_readpara_init(cmaes_readpara_t * t,int dim,const double * inxstart,const double * inrgsigma,int inseed,int lambda,const char * filename)2487 cmaes_readpara_init (cmaes_readpara_t *t,
2488 int dim,
2489 const double * inxstart,
2490 const double * inrgsigma,
2491 int inseed,
2492 int lambda,
2493 const char * filename)
2494 {
2495 int i, N;
2496 /* TODO: make sure cmaes_readpara_init has not been called already */
2497 t->filename = NULL; /* set after successful Read */
2498 t->rgsformat = (const char **) new_void(55, sizeof(char *));
2499 t->rgpadr = (void **) new_void(55, sizeof(void *));
2500 t->rgskeyar = (const char **) new_void(11, sizeof(char *));
2501 t->rgp2adr = (double ***) new_void(11, sizeof(double **));
2502 t->weigkey = (char *)new_void(7, sizeof(char));
2503
2504 /* All scalars: */
2505 i = 0;
2506 t->rgsformat[i] = " N %d"; t->rgpadr[i++] = (void *) &t->N;
2507 t->rgsformat[i] = " seed %d"; t->rgpadr[i++] = (void *) &t->seed;
2508 t->rgsformat[i] = " stopMaxFunEvals %lg"; t->rgpadr[i++] = (void *) &t->stopMaxFunEvals;
2509 t->rgsformat[i] = " stopMaxIter %lg"; t->rgpadr[i++] = (void *) &t->stopMaxIter;
2510 t->rgsformat[i] = " stopFitness %lg"; t->rgpadr[i++]=(void *) &t->stStopFitness.val;
2511 t->rgsformat[i] = " stopTolFun %lg"; t->rgpadr[i++]=(void *) &t->stopTolFun;
2512 t->rgsformat[i] = " stopTolFunHist %lg"; t->rgpadr[i++]=(void *) &t->stopTolFunHist;
2513 t->rgsformat[i] = " stopTolX %lg"; t->rgpadr[i++]=(void *) &t->stopTolX;
2514 t->rgsformat[i] = " stopTolUpXFactor %lg"; t->rgpadr[i++]=(void *) &t->stopTolUpXFactor;
2515 t->rgsformat[i] = " lambda %d"; t->rgpadr[i++] = (void *) &t->lambda;
2516 t->rgsformat[i] = " mu %d"; t->rgpadr[i++] = (void *) &t->mu;
2517 t->rgsformat[i] = " weights %5s"; t->rgpadr[i++] = (void *) t->weigkey;
2518 t->rgsformat[i] = " fac*cs %lg";t->rgpadr[i++] = (void *) &t->cs;
2519 t->rgsformat[i] = " fac*damps %lg"; t->rgpadr[i++] = (void *) &t->damps;
2520 t->rgsformat[i] = " ccumcov %lg"; t->rgpadr[i++] = (void *) &t->ccumcov;
2521 t->rgsformat[i] = " mucov %lg"; t->rgpadr[i++] = (void *) &t->mucov;
2522 t->rgsformat[i] = " fac*ccov %lg"; t->rgpadr[i++]=(void *) &t->ccov;
2523 t->rgsformat[i] = " diagonalCovarianceMatrix %lg"; t->rgpadr[i++]=(void *) &t->diagonalCov;
2524 t->rgsformat[i] = " updatecov %lg"; t->rgpadr[i++]=(void *) &t->updateCmode.modulo;
2525 t->rgsformat[i] = " maxTimeFractionForEigendecompostion %lg"; t->rgpadr[i++]=(void *) &t->updateCmode.maxtime;
2526 t->rgsformat[i] = " resume %59s"; t->rgpadr[i++] = (void *) t->resumefile;
2527 t->rgsformat[i] = " fac*maxFunEvals %lg"; t->rgpadr[i++] = (void *) &t->facmaxeval;
2528 t->rgsformat[i] = " fac*updatecov %lg"; t->rgpadr[i++]=(void *) &t->facupdateCmode;
2529 t->n1para = i;
2530 t->n1outpara = i-2; /* disregard last parameters in WriteToFile() */
2531
2532 /* arrays */
2533 i = 0;
2534 t->rgskeyar[i] = " typicalX %d"; t->rgp2adr[i++] = &t->typicalX;
2535 t->rgskeyar[i] = " initialX %d"; t->rgp2adr[i++] = &t->xstart;
2536 t->rgskeyar[i] = " initialStandardDeviations %d"; t->rgp2adr[i++] = &t->rgInitialStds;
2537 t->rgskeyar[i] = " diffMinChange %d"; t->rgp2adr[i++] = &t->rgDiffMinChange;
2538 t->n2para = i;
2539
2540 t->N = dim;
2541 t->seed = (unsigned) inseed;
2542 t->xstart = NULL;
2543 t->typicalX = NULL;
2544 t->typicalXcase = 0;
2545 t->rgInitialStds = NULL;
2546 t->rgDiffMinChange = NULL;
2547 t->stopMaxFunEvals = -1;
2548 t->stopMaxIter = -1;
2549 t->facmaxeval = 1;
2550 t->stStopFitness.flg = -1;
2551 t->stopTolFun = 1e-12;
2552 t->stopTolFunHist = 1e-13;
2553 t->stopTolX = 0; /* 1e-11*insigma would also be reasonable */
2554 t->stopTolUpXFactor = 1e3;
2555
2556 t->lambda = lambda;
2557 t->mu = -1;
2558 t->mucov = -1;
2559 t->weights = NULL;
2560 strcpy(t->weigkey, "log");
2561
2562 t->cs = -1;
2563 t->ccumcov = -1;
2564 t->damps = -1;
2565 t->ccov = -1;
2566
2567 t->diagonalCov = 0; /* default is 0, but this might change in future, see below */
2568
2569 t->updateCmode.modulo = -1;
2570 t->updateCmode.maxtime = -1;
2571 t->updateCmode.flgalways = 0;
2572 t->facupdateCmode = 1;
2573 strcpy(t->resumefile, "_no_");
2574
2575 /* filename == NULL invokes default in cmaes_readpara_Read... */
2576 if (!isNoneStr(filename) && (!filename || strcmp(filename, "writeonly") != 0))
2577 cmaes_readpara_ReadFromFile(t, filename);
2578
2579 if (t->N <= 0)
2580 t->N = dim;
2581
2582 N = t->N;
2583 if (N == 0)
2584 FATAL("cmaes_readpara_cmaes_readpara_t(): problem dimension N undefined.\n",
2585 " (no default value available).",0,0);
2586 if (t->xstart == NULL && inxstart == NULL && t->typicalX == NULL) {
2587 ERRORMESSAGE("Warning: initialX undefined. typicalX = 0.5...0.5 used.","","","");
2588 printf("\nWarning: initialX undefined. typicalX = 0.5...0.5 used.\n");
2589 }
2590 if (t->rgInitialStds == NULL && inrgsigma == NULL) {
2591 /* FATAL("initialStandardDeviations undefined","","",""); */
2592 ERRORMESSAGE("Warning: initialStandardDeviations undefined. 0.3...0.3 used.","","","");
2593 printf("\nWarning: initialStandardDeviations. 0.3...0.3 used.\n");
2594 }
2595
2596 if (t->xstart == NULL) {
2597 t->xstart = new_double(N);
2598
2599 /* put inxstart into xstart */
2600 if (inxstart != NULL) {
2601 for (i=0; i<N; ++i)
2602 t->xstart[i] = inxstart[i];
2603 }
2604 /* otherwise use typicalX or default */
2605 else {
2606 t->typicalXcase = 1;
2607 for (i=0; i<N; ++i)
2608 t->xstart[i] = (t->typicalX == NULL) ? 0.5 : t->typicalX[i];
2609 }
2610 } /* xstart == NULL */
2611
2612 if (t->rgInitialStds == NULL) {
2613 t->rgInitialStds = new_double(N);
2614 for (i=0; i<N; ++i)
2615 t->rgInitialStds[i] = (inrgsigma == NULL) ? 0.3 : inrgsigma[i];
2616 }
2617
2618 t->flgsupplemented = 0;
2619
2620 } /* cmaes_readpara_init */
2621
2622 /* --------------------------------------------------------- */
2623 /* --------------------------------------------------------- */
cmaes_readpara_exit(cmaes_readpara_t * t)2624 void cmaes_readpara_exit(cmaes_readpara_t *t)
2625 {
2626 if (t->filename != NULL)
2627 free( t->filename);
2628 if (t->xstart != NULL) /* not really necessary */
2629 free( t->xstart);
2630 if (t->typicalX != NULL)
2631 free( t->typicalX);
2632 if (t->rgInitialStds != NULL)
2633 free( t->rgInitialStds);
2634 if (t->rgDiffMinChange != NULL)
2635 free( t->rgDiffMinChange);
2636 if (t->weights != NULL)
2637 free( t->weights);
2638
2639 free((void*)t->rgsformat);
2640 free(t->rgpadr);
2641 free((void*)t->rgskeyar);
2642 free(t->rgp2adr);
2643 free(t->weigkey);
2644 }
2645
2646 /* --------------------------------------------------------- */
2647 /* --------------------------------------------------------- */
2648 void
cmaes_readpara_ReadFromFile(cmaes_readpara_t * t,const char * filename)2649 cmaes_readpara_ReadFromFile(cmaes_readpara_t *t, const char * filename)
2650 {
2651 char s[1000];
2652 const char *ss = "cmaes_initials.par";
2653 int ipara, i;
2654 int size;
2655 FILE *fp;
2656 if (filename == NULL) {
2657 filename = ss;
2658 }
2659 t->filename = NULL; /* nothing read so far */
2660 fp = fopen( filename, "r");
2661 if (fp == NULL) {
2662 ERRORMESSAGE("cmaes_ReadFromFile(): could not open '", filename, "'",0);
2663 return;
2664 }
2665 for (ipara=0; ipara < t->n1para; ++ipara)
2666 {
2667 rewind(fp);
2668 while(fgets(s, sizeof(s), fp) != NULL)
2669 { /* skip comments */
2670 if (s[0] == '#' || s[0] == '%')
2671 continue;
2672 if(sscanf(s, t->rgsformat[ipara], t->rgpadr[ipara]) == 1) {
2673 if (strncmp(t->rgsformat[ipara], " stopFitness ", 13) == 0)
2674 t->stStopFitness.flg = 1;
2675 break;
2676 }
2677 }
2678 } /* for */
2679 if (t->N <= 0)
2680 FATAL("cmaes_readpara_ReadFromFile(): No valid dimension N",0,0,0);
2681 for (ipara=0; ipara < t->n2para; ++ipara)
2682 {
2683 rewind(fp);
2684 while(fgets(s, sizeof(s), fp) != NULL) /* read one line */
2685 { /* skip comments */
2686 if (s[0] == '#' || s[0] == '%')
2687 continue;
2688 if(sscanf(s, t->rgskeyar[ipara], &size) == 1) { /* size==number of values to be read */
2689 if (size > 0) {
2690 *t->rgp2adr[ipara] = new_double(t->N);
2691 for (i=0;i<size&&i<t->N;++i) /* start reading next line */
2692 if (fscanf(fp, " %lf", &(*t->rgp2adr[ipara])[i]) != 1)
2693 break;
2694 if (i<size && i < t->N) {
2695 ERRORMESSAGE("cmaes_readpara_ReadFromFile ", filename, ": ",0);
2696 FATAL( "'", t->rgskeyar[ipara],
2697 "' not enough values found.\n",
2698 " Remove all comments between numbers.");
2699 }
2700 for (; i < t->N; ++i) /* recycle */
2701 (*t->rgp2adr[ipara])[i] = (*t->rgp2adr[ipara])[i%size];
2702 }
2703 }
2704 }
2705 } /* for */
2706 fclose(fp);
2707 assign_string(&(t->filename), filename); /* t->filename must be freed */
2708 return;
2709 } /* cmaes_readpara_ReadFromFile() */
2710
2711 /* --------------------------------------------------------- */
2712 /* --------------------------------------------------------- */
2713 void
cmaes_readpara_WriteToFile(cmaes_readpara_t * t,const char * filenamedest)2714 cmaes_readpara_WriteToFile(cmaes_readpara_t *t, const char *filenamedest)
2715 {
2716 int ipara, i;
2717 size_t len;
2718 time_t ti = time(NULL);
2719 FILE *fp = fopen( filenamedest, "a");
2720 if(fp == NULL) {
2721 ERRORMESSAGE("cmaes_WriteToFile(): could not open '",
2722 filenamedest, "'",0);
2723 return;
2724 }
2725 fprintf(fp, "\n# Read from %s at %s\n", t->filename ? t->filename : "",
2726 asctime(localtime(&ti))); /* == ctime() */
2727 for (ipara=0; ipara < 1; ++ipara) {
2728 fprintf(fp, t->rgsformat[ipara], *(int *)t->rgpadr[ipara]);
2729 fprintf(fp, "\n");
2730 }
2731 for (ipara=0; ipara < t->n2para; ++ipara) {
2732 if(*t->rgp2adr[ipara] == NULL)
2733 continue;
2734 fprintf(fp, t->rgskeyar[ipara], t->N);
2735 fprintf(fp, "\n");
2736 for (i=0; i<t->N; ++i)
2737 fprintf(fp, "%7.3g%c", (*t->rgp2adr[ipara])[i], (i%5==4)?'\n':' ');
2738 fprintf(fp, "\n");
2739 }
2740 for (ipara=1; ipara < t->n1outpara; ++ipara) {
2741 if (strncmp(t->rgsformat[ipara], " stopFitness ", 13) == 0)
2742 if(t->stStopFitness.flg == 0) {
2743 fprintf(fp, " stopFitness\n");
2744 continue;
2745 }
2746 len = strlen(t->rgsformat[ipara]);
2747 if (t->rgsformat[ipara][len-1] == 'd') /* read integer */
2748 fprintf(fp, t->rgsformat[ipara], *(int *)t->rgpadr[ipara]);
2749 else if (t->rgsformat[ipara][len-1] == 's') /* read string */
2750 fprintf(fp, t->rgsformat[ipara], (char *)t->rgpadr[ipara]);
2751 else {
2752 if (strncmp(" fac*", t->rgsformat[ipara], 5) == 0) {
2753 fprintf(fp, " ");
2754 fprintf(fp, t->rgsformat[ipara]+5, *(double *)t->rgpadr[ipara]);
2755 } else
2756 fprintf(fp, t->rgsformat[ipara], *(double *)t->rgpadr[ipara]);
2757 }
2758 fprintf(fp, "\n");
2759 } /* for */
2760 fprintf(fp, "\n");
2761 fclose(fp);
2762 } /* cmaes_readpara_WriteToFile() */
2763
2764 /* --------------------------------------------------------- */
2765 /* --------------------------------------------------------- */
2766 void
cmaes_readpara_SupplementDefaults(cmaes_readpara_t * t)2767 cmaes_readpara_SupplementDefaults(cmaes_readpara_t *t)
2768 /* Called (only) once to finally set parameters. The settings
2769 * typically depend on the current parameter values itself,
2770 * where 0 or -1 may indicate to set them to a certain default
2771 * value. For this reason calling `SupplementDefaults` twice
2772 * might lead to unexpected results.
2773 */
2774 {
2775 double t1, t2;
2776 int N = t->N;
2777 clock_t cloc = clock();
2778
2779 if (t->flgsupplemented)
2780 FATAL("cmaes_readpara_SupplementDefaults() cannot be called twice.",0,0,0);
2781 if (t->seed < 1) {
2782 while ((int) (cloc - clock()) == 0)
2783 ; /* TODO: remove this for time critical applications!? */
2784 t->seed = (unsigned int)abs((long)(100*time(NULL)+clock()));
2785 }
2786
2787 if (t->stStopFitness.flg == -1)
2788 t->stStopFitness.flg = 0;
2789
2790 if (t->lambda < 2)
2791 t->lambda = 4+(int)(3*log((double)N));
2792 if (t->mu == -1) {
2793 t->mu = t->lambda/2;
2794 cmaes_readpara_SetWeights(t, t->weigkey);
2795 }
2796 if (t->weights == NULL)
2797 cmaes_readpara_SetWeights(t, t->weigkey);
2798
2799 if (t->cs > 0) /* factor was read */
2800 t->cs *= (t->mueff + 2.) / (N + t->mueff + 3.);
2801 if (t->cs <= 0 || t->cs >= 1)
2802 t->cs = (t->mueff + 2.) / (N + t->mueff + 3.);
2803
2804 if (t->ccumcov <= 0 || t->ccumcov > 1)
2805 t->ccumcov = 4. / (N + 4);
2806
2807 if (t->mucov < 1) {
2808 t->mucov = t->mueff;
2809 }
2810 t1 = 2. / ((N+1.4142)*(N+1.4142));
2811 t2 = (2.*t->mueff-1.) / ((N+2.)*(N+2.)+t->mueff);
2812 t2 = (t2 > 1) ? 1 : t2;
2813 t2 = (1./t->mucov) * t1 + (1.-1./t->mucov) * t2;
2814 if (t->ccov >= 0) /* ccov holds the read factor */
2815 t->ccov *= t2;
2816 if (t->ccov < 0 || t->ccov > 1) /* set default in case */
2817 t->ccov = t2;
2818
2819 if (t->diagonalCov == -1)
2820 t->diagonalCov = 2 + 100. * N / sqrt((double)t->lambda);
2821
2822 if (t->stopMaxFunEvals == -1) /* may depend on ccov in near future */
2823 t->stopMaxFunEvals = t->facmaxeval*900*(N+3)*(N+3);
2824 else
2825 t->stopMaxFunEvals *= t->facmaxeval;
2826
2827 if (t->stopMaxIter == -1)
2828 t->stopMaxIter = ceil((double)(t->stopMaxFunEvals / t->lambda));
2829
2830 if (t->damps < 0)
2831 t->damps = 1; /* otherwise a factor was read */
2832 t->damps = t->damps
2833 * (1 + 2*douMax(0., sqrt((t->mueff-1.)/(N+1.)) - 1)) /* basic factor */
2834 * douMax(0.3, 1. - /* modify for short runs */
2835 (double)N / (1e-6+douMin(t->stopMaxIter, t->stopMaxFunEvals/t->lambda)))
2836 + t->cs; /* minor increment */
2837
2838 if (t->updateCmode.modulo < 0)
2839 t->updateCmode.modulo = 1./t->ccov/(double)(N)/10.;
2840 t->updateCmode.modulo *= t->facupdateCmode;
2841 if (t->updateCmode.maxtime < 0)
2842 t->updateCmode.maxtime = 0.20; /* maximal 20% of CPU-time */
2843
2844 t->flgsupplemented = 1;
2845
2846 } /* cmaes_readpara_SupplementDefaults() */
2847
2848
2849 /* --------------------------------------------------------- */
2850 /* --------------------------------------------------------- */
2851 void
cmaes_readpara_SetWeights(cmaes_readpara_t * t,const char * mode)2852 cmaes_readpara_SetWeights(cmaes_readpara_t *t, const char * mode)
2853 {
2854 double s1, s2;
2855 int i;
2856
2857 if(t->weights != NULL)
2858 free( t->weights);
2859 t->weights = new_double(t->mu);
2860 if (strcmp(mode, "lin") == 0)
2861 for (i=0; i<t->mu; ++i)
2862 t->weights[i] = t->mu - i;
2863 else if (strncmp(mode, "equal", 3) == 0)
2864 for (i=0; i<t->mu; ++i)
2865 t->weights[i] = 1;
2866 else if (strcmp(mode, "log") == 0)
2867 for (i=0; i<t->mu; ++i)
2868 t->weights[i] = log(t->mu+1.)-log(i+1.);
2869 else
2870 for (i=0; i<t->mu; ++i)
2871 t->weights[i] = log(t->mu+1.)-log(i+1.);
2872
2873 /* normalize weights vector and set mueff */
2874 for (i=0, s1=0, s2=0; i<t->mu; ++i) {
2875 s1 += t->weights[i];
2876 s2 += t->weights[i]*t->weights[i];
2877 }
2878 t->mueff = s1*s1/s2;
2879 for (i=0; i<t->mu; ++i)
2880 t->weights[i] /= s1;
2881
2882 if(t->mu < 1 || t->mu > t->lambda ||
2883 (t->mu==t->lambda && t->weights[0]==t->weights[t->mu-1]))
2884 FATAL("cmaes_readpara_SetWeights(): invalid setting of mu or lambda",0,0,0);
2885
2886 } /* cmaes_readpara_SetWeights() */
2887
2888 /* --------------------------------------------------------- */
2889 /* --------------------------------------------------------- */
2890 static int
isNoneStr(const char * filename)2891 isNoneStr(const char * filename)
2892 {
2893 if (filename && (strcmp(filename, "no") == 0
2894 || strcmp(filename, "non") == 0
2895 || strcmp(filename, "none") == 0))
2896 return 1;
2897
2898 return 0;
2899 }
2900
2901 /* --------------------------------------------------------- */
2902 /* --------------------------------------------------------- */
2903 static double
douSquare(double d)2904 douSquare(double d)
2905 {
2906 return d*d;
2907 }
2908 static int
intMin(int i,int j)2909 intMin( int i, int j)
2910 {
2911 return i < j ? i : j;
2912 }
2913 static double
douMax(double i,double j)2914 douMax( double i, double j)
2915 {
2916 return i > j ? i : j;
2917 }
2918 static double
douMin(double i,double j)2919 douMin( double i, double j)
2920 {
2921 return i < j ? i : j;
2922 }
2923 static double
rgdouMax(const double * rgd,int len)2924 rgdouMax( const double *rgd, int len)
2925 {
2926 int i;
2927 double max = rgd[0];
2928 for (i = 1; i < len; ++i)
2929 max = (max < rgd[i]) ? rgd[i] : max;
2930 return max;
2931 }
2932
2933 static double
rgdouMin(const double * rgd,int len)2934 rgdouMin( const double *rgd, int len)
2935 {
2936 int i;
2937 double min = rgd[0];
2938 for (i = 1; i < len; ++i)
2939 min = (min > rgd[i]) ? rgd[i] : min;
2940 return min;
2941 }
2942
2943 static int
MaxIdx(const double * rgd,int len)2944 MaxIdx( const double *rgd, int len)
2945 {
2946 int i, res;
2947 for(i=1, res=0; i<len; ++i)
2948 if(rgd[i] > rgd[res])
2949 res = i;
2950 return res;
2951 }
2952 static int
MinIdx(const double * rgd,int len)2953 MinIdx( const double *rgd, int len)
2954 {
2955 int i, res;
2956 for(i=1, res=0; i<len; ++i)
2957 if(rgd[i] < rgd[res])
2958 res = i;
2959 return res;
2960 }
2961
2962 static double
myhypot(double a,double b)2963 myhypot(double a, double b)
2964 /* sqrt(a^2 + b^2) numerically stable. */
2965 {
2966 double r = 0;
2967 if (fabs(a) > fabs(b)) {
2968 r = b/a;
2969 r = fabs(a)*sqrt(1+r*r);
2970 } else if (b != 0) {
2971 r = a/b;
2972 r = fabs(b)*sqrt(1+r*r);
2973 }
2974 return r;
2975 }
2976
SignOfDiff(const void * d1,const void * d2)2977 static int SignOfDiff(const void *d1, const void * d2)
2978 {
2979 return *((double *) d1) > *((double *) d2) ? 1 : -1;
2980 }
2981
2982 #if 1
2983 /* dirty index sort */
Sorted_index(const double * rgFunVal,int * iindex,int n)2984 static void Sorted_index(const double *rgFunVal, int *iindex, int n)
2985 {
2986 int i, j;
2987 for (i=1, iindex[0]=0; i<n; ++i) {
2988 for (j=i; j>0; --j) {
2989 if (rgFunVal[iindex[j-1]] < rgFunVal[i])
2990 break;
2991 iindex[j] = iindex[j-1]; /* shift up */
2992 }
2993 iindex[j] = i; /* insert i */
2994 }
2995 }
2996 #endif
2997
new_void(int n,size_t size)2998 static void * new_void(int n, size_t size)
2999 {
3000 static char s[70];
3001 void *p = calloc((unsigned) n, size);
3002 if (p == NULL) {
3003 sprintf(s, "new_void(): calloc(%ld,%ld) failed",(long)n,(long)size);
3004 FATAL(s,0,0,0);
3005 }
3006 return p;
3007 }
3008
3009 double *
cmaes_NewDouble(int n)3010 cmaes_NewDouble(int n)
3011 {
3012 return new_double(n);
3013 }
3014
new_double(int n)3015 static double * new_double(int n)
3016 {
3017 static char s[170];
3018 double *p = (double *) calloc((unsigned) n, sizeof(double));
3019 if (p == NULL) {
3020 sprintf(s, "new_double(): calloc(%ld,%ld) failed",
3021 (long)n,(long)sizeof(double));
3022 FATAL(s,0,0,0);
3023 }
3024 return p;
3025 }
3026
new_string(const char * ins)3027 static char * new_string(const char *ins)
3028 {
3029 static char s[170];
3030 unsigned i;
3031 char *p;
3032 unsigned len = (unsigned) ((ins != NULL) ? strlen(ins) : 0);
3033
3034 if (len > 1000) {
3035 FATAL("new_string(): input string length was larger then 1000 ",
3036 "(possibly due to uninitialized char *filename)",0,0);
3037 }
3038
3039 p = (char *) calloc( len + 1, sizeof(char));
3040 if (p == NULL) {
3041 sprintf(s, "new_string(): calloc(%ld,%ld) failed",
3042 (long)len,(long)sizeof(char));
3043 FATAL(s,0,0,0);
3044 }
3045 for (i = 0; i < len; ++i)
3046 p[i] = ins[i];
3047 return p;
3048 }
assign_string(char ** pdests,const char * ins)3049 static void assign_string(char ** pdests, const char *ins)
3050 {
3051 if (*pdests)
3052 free(*pdests);
3053 if (ins == NULL)
3054 *pdests = NULL;
3055 else
3056 *pdests = new_string(ins);
3057 }
3058
3059 /* --------------------------------------------------------- */
3060 /* --------------------------------------------------------- */
3061
3062 /* ========================================================= */
3063 void
cmaes_FATAL(char const * s1,char const * s2,char const * s3,char const * s4)3064 cmaes_FATAL(char const *s1, char const *s2, char const *s3,
3065 char const *s4)
3066 {
3067 time_t t = time(NULL);
3068 ERRORMESSAGE( s1, s2, s3, s4);
3069 ERRORMESSAGE("*** Exiting cmaes_t ***",0,0,0);
3070 printf("\n -- %s %s\n", asctime(localtime(&t)),
3071 s2 ? szCat(s1, s2, s3, s4) : s1);
3072 printf(" *** CMA-ES ABORTED, see errcmaes.err *** \n");
3073 fflush(stdout);
3074 exit(1);
3075 }
3076
3077 /* ========================================================= */
3078 static void
FATAL(char const * s1,char const * s2,char const * s3,char const * s4)3079 FATAL(char const *s1, char const *s2, char const *s3,
3080 char const *s4)
3081 {
3082 cmaes_FATAL(s1, s2, s3, s4);
3083 }
3084
3085 /* ========================================================= */
ERRORMESSAGE(char const * s1,char const * s2,char const * s3,char const * s4)3086 static void ERRORMESSAGE( char const *s1, char const *s2,
3087 char const *s3, char const *s4)
3088 {
3089 #if 1
3090 /* static char szBuf[700]; desirable but needs additional input argument
3091 sprintf(szBuf, "%f:%f", gen, gen*lambda);
3092 */
3093 time_t t = time(NULL);
3094 FILE *fp = fopen( "errcmaes.err", "a");
3095 if (!fp)
3096 {
3097 printf("\nFATAL ERROR: %s\n", s2 ? szCat(s1, s2, s3, s4) : s1);
3098 printf("cmaes_t could not open file 'errcmaes.err'.");
3099 printf("\n *** CMA-ES ABORTED *** ");
3100 fflush(stdout);
3101 exit(1);
3102 }
3103 fprintf( fp, "\n -- %s %s\n", asctime(localtime(&t)),
3104 s2 ? szCat(s1, s2, s3, s4) : s1);
3105 fclose (fp);
3106 #endif
3107 }
3108
3109 /* ========================================================= */
szCat(const char * sz1,const char * sz2,const char * sz3,const char * sz4)3110 static char *szCat(const char *sz1, const char*sz2,
3111 const char *sz3, const char *sz4)
3112 {
3113 static char szBuf[700];
3114
3115 if (!sz1)
3116 FATAL("szCat() : Invalid Arguments",0,0,0);
3117
3118 strncpy ((char *)szBuf, sz1, (unsigned)intMin( (int)strlen(sz1), 698));
3119 szBuf[intMin( (int)strlen(sz1), 698)] = '\0';
3120 if (sz2)
3121 strncat ((char *)szBuf, sz2,
3122 (unsigned)intMin((int)strlen(sz2)+1, 698 - (int)strlen((char const *)szBuf)));
3123 if (sz3)
3124 strncat((char *)szBuf, sz3,
3125 (unsigned)intMin((int)strlen(sz3)+1, 698 - (int)strlen((char const *)szBuf)));
3126 if (sz4)
3127 strncat((char *)szBuf, sz4,
3128 (unsigned)intMin((int)strlen(sz4)+1, 698 - (int)strlen((char const *)szBuf)));
3129 return (char *) szBuf;
3130 }
3131
3132
3133