Solving the GTOPX Benchmark Problems using PYGMO2/PAGMO2
fcmaes performs very well on the hard GTOPX benchmarks, as shown in Performance. This tutorial looks at why. We want to separate two effects: the implementation of the base algorithms (DE → CMA) and the coordinated retry / boundary management meta algorithm.
To do that, we replace the fcmaes versions of DE and CMA with the ones from
pygmo2 / pagmo2.
The results are very similar, which suggests that the meta algorithm is doing most of the work.
For this comparison we use the sequence pg.de1220 followed by pg.cma, called de_cma_pyg
in benchmark_gtop_pygmo.py.
Performance of the PYGMO2/PAGMO2 optimization algorithms
Install pygmo (pip install pygmo) and fcmaes (pip install fcmaes), then run
benchmark_gtop_pygmo.py
to reproduce the results. The same optimization algorithm was used for all problems.
The same parameters were used both for the optimizer and for coordinated retry.
The solution times in the tables below were measured on Linux with an AMD 5950x CPU.
| problem | runs | absolute best | stopVal | success rate | mean time | sdev time |
|---|---|---|---|---|---|---|
Cassini1 |
100 |
4.9307 |
4.95535 |
100% |
3.29s |
3.29s |
Cassini2 |
100 |
8.383 |
8.42491 |
100% |
42.29s |
20.26s |
Gtoc1 |
100 |
-1581950 |
-1574079.60199 |
100% |
23.97s |
16.56s |
Messengerr |
100 |
8.6299 |
8.67305 |
100% |
27.12s |
14.02s |
Rosetta |
100 |
1.3433 |
1.35002 |
100% |
49.78s |
15.92s |
Tandem |
100 |
-1500.46 |
-1492.99502 |
56% |
903.67s |
886.37s |
Sagas |
100 |
18.188 |
18.27894 |
100% |
5.18s |
6.07s |
Messenger Full |
10 |
1.9579 |
2.0 |
60% |
2524.69s |
1539.72s |
Messenger Full |
10 |
1.9579 |
1.96769 |
20% |
8664.12s |
1114.35s |
stopVal is the threshold that defines success, and mean time includes failed runs.
The Messenger Full results are still preliminary. They will be replaced by more accurate numbers.
These results show that pygmo2 provides optimization algorithms that are good enough to solve the GTOPX benchmarks.
Here is a visualization of the coordinated retry runs for Tandem EVEES Constrained, which was not solved until 2013:
The next figure shows the 10 coordinated retry runs for Messenger Full:
PAGMO generates solutions below 2.0 km/s at a rate of more than one per hour on a single 4.0 GHZ CPU. That is higher than what was reported in the MXHCP paper, which used 1000 cores of the Hokudai Supercomputer with Intel Xeon Gold 6148 CPUs at 2.7 GHz. It still cannot compete with the Java variant of fcmaes, but that is not a fair comparison. The coordinated retry meta algorithm has much lower overhead in Java than in Python. It could be even lower in C++. Maybe the PAGMO team sees this as a chance to grab the record?
Challenge
Can you reproduce these results without using fcmaes, relying on the pygmo2 parallelization mechanisms?
Further Improvement
The combined result of the two PAGMO algorithms was better than expected.
But perhaps only one of them, pg.de1220 or pg.cmaes, was responsible.
To test that, we combined PAGMO algorithms with the ones from fcmaes.
The best sequence turned out to be pg.de1220 → fcmaes.cmaescpp.
In benchmark_gtop_pygmo.py
this sequence is called de_pyg_cma.
| problem | runs | absolute best | stopVal | success rate | mean time | sdev time |
|---|---|---|---|---|---|---|
Cassini1 |
100 |
4.9307 |
4.95535 |
100% |
1.39s |
1.08s |
Cassini2 |
100 |
8.383 |
8.42491 |
99% |
62.6s |
44.27s |
Gtoc1 |
100 |
-1581950 |
-1574079.60199 |
100% |
22.61s |
16.81s |
Messenger Reduced |
100 |
8.6299 |
8.67305 |
100% |
16.32s |
9.92s |
Rosetta |
100 |
1.3433 |
1.35002 |
100% |
24.4s |
9.85s |
Tandem EVEES Constrained |
100 |
-1500.46 |
-1492.99502 |
95% |
236.3s |
188.28s |
Sagas |
100 |
18.188 |
18.27894 |
97% |
10.49s |
9.03s |
Messenger full |
46 |
1.9579 |
2.0 |
43% |
3003.63s |
2132.3s |
These tests were executed on a single AMD 5950x CPU. The Tandem EVEES Constrained result is especially impressive:
This suggests that the adaptive de1220 differential evolution variant is worth its own fcmaes implementation.
Messenger Full is also solved quite well:
