fcmaes gives you a clear advantage at an optimization competition like ESAs GECCO 2022 competition if you exploit its parallelization capabilities.
-
Mine the Belt (1 objective, 30000 dimensions). fcmaes is currently ranked 1st. fcmaes was used for the final optimization of the trajectories generated by beam search. We used the C++ version of the CMA-ES algorithm with parallel fitness evaluation.
-
Trappist Tour (2 objectives, 34 dimensions). fcmaes is currently ranked 2nd. Mainly the BiteOpt algorithm was used with parallel retry.
-
Delivery Scheduling (1 objective, 1044 dimensions). fcmaes is currently ranked 1st. We used differential evolution (C++-Version) using the ask/tell interface for parallel fitness evaluation. The fitness function involved SCIP wrapped by Googles or-tools, see pywraplp. A 95% solution can trivially be achieved by applying BiteOpt parallel retry, see trappist_delivery.py. This result is hard to replicate using other algorithms/libraries.
All competition code was written in Python - although fcmaes and or-tools wrap C++ code to improve performance.
In this domain we often have multiple competing objectives and a lot of constraints. We present results for the Mazda real-world car structure design benchmark, the simultaneous optimization of three car models minimizing their weight, increasing the number of shared thicknesses of structural parts thereby fulfilling 54 constraints. 2017 there was a competition related to this problem Report of Evolutionary Computation Competition 2017, but until now not many of the ideas produced there have found their way into open source optimization libraries.
We applied modecpp.py for about 1 hour runtime using one AMD 5950x CPU on Linux, de/rand/1 strategy (nsga_update=False, pareto_update=False, ints=[True]*dim), population size = 256. We choose the best run out of two executed in parallel, each utilizing 16 threads (workers=16). This way about 8200 function evaluations are performed per second for both runs combined.
The resulting pareto front with hypervolume 0.4074 is:
The "reference" NSGA-II solution given as part of the benchmark has hypervolume 0.1456:
Note, that the reference solution was computed using a limited budget. But NSGA-II scales much worse than fcmaes-MoDe using enhanced multiple constraint ranking.
fcmaes provides fast parallel example solvers for the real world space flight design problems GTOP and for the F-8_aircraft problem based on differential equations. On GTOPX you can find implementations of the corresponding objective functions using different programming languages. The solution times given in the tables below are for Linux / AMD 5950x CPU.
| problem | runs | absolute best | stopVal | success rate | mean time | sdev time |
|---|---|---|---|---|---|---|
Cassini1 |
100 |
4.9307 |
4.95535 |
98% |
7.43s |
10.7s |
Cassini2 |
100 |
8.383 |
8.42491 |
97% |
55.18s |
39.79s |
Gtoc1 |
100 |
-1581950 |
-1574080 |
100% |
25.88s |
22.15s |
Messenger |
100 |
8.6299 |
8.67305 |
100% |
18.12s |
15.48s |
Rosetta |
100 |
1.3433 |
1.35002 |
100% |
25.05s |
10.5s |
Tandem EVEES Constrained |
100 |
-1500.46 |
-1493 |
68% |
519.21s |
479.46s |
Sagas |
100 |
18.188 |
18.279 |
99% |
7.59s |
6.91s |
Messenger Full |
100 |
1.9579 |
1.96769 |
41% |
3497.25s |
2508.88s |
Messenger Full |
100 |
1.9579 |
2.0 |
59% |
1960.68s |
2024.24s |
Note that 'stopVal' is the threshold value determining success and 'mean time' includes the time for failed runs. Execute benchmark_gtop.py to reproduce these results. The same optimization algorithm was applied for all problems, using the same parameters both for the optimization algorithm and the coordinated retry / boundary management.
| problem | runs | absolute best | stopVal | success rate | mean time | sdev time |
|---|---|---|---|---|---|---|
Cassini1 |
100 |
4.9307 |
4.93075 |
98% |
8.73s |
10.85s |
Cassini2 |
100 |
8.383 |
8.38305 |
44% |
310.18s |
283.52s |
Gtoc1 |
100 |
-1581950 |
-1581949 |
100% |
46.41s |
35.57s |
Messenger |
100 |
8.6299 |
8.62995 |
98% |
57.91s |
39.97s |
Rosetta |
100 |
1.3433 |
1.34335 |
27% |
268.18s |
207.59s |
Tandem |
100 |
-1500.46 |
-1500 |
65% |
564.26s |
517.94s |
Sagas |
100 |
18.188 |
18.189 |
99% |
8.76s |
7.01s |
Because of its famous complexity ESAs 26-dimensional Messenger full problem is often referenced in the literature, see for instance MXHCP paper.
fcmaes is the only library capable of solving it using a single CPU: In about 1950 seconds on average using an AMD 5950x (1250 seconds for the java variant) .
The Problem models a multi-gravity assist interplanetary space mission from Earth to Mercury. In 2009 the first good solution (6.9 km/s) was submitted. It took more than five years to reach 1.959 km/s and three more years until 2017 to find the optimum 1.958 km/s. The picture below shows the progress of the whole science community since 2009:
The following picture shows 101 coordinated retry runs:
60 out of these 101 runs produced a result better than 2 km/s:
About 1.2*10^6 function evaluations per second were performed which shows excellent scaling of the algorithm utilizing all 16 cores / 32 threads. https://github.com/dietmarwo/fcmaes-java/blob/master/README.adoc shows that the fcmaes java implementation sharing the same C++ code is significantly faster. fcmaesray shows how a 5 node cluster using 96 CPU-cores executing fcmaes coordinated retry performs in comparison.