A New Challenge: Saving Mark Whitney

In the last blog entry Adding Crossover to CMA-ES we provided further details to the new optimimization algorithm GCMA-ES designed to partly replace search by optimization for space mission design, but also can be applied to hard optimization problems in other areas. As test method we used ESAs GTOP messenger full problem . We observed that ESAs current implementation is flawed, but can easily be fixed by updating the Lambert solver implementation. Even the updated version has a problem: It is quite "easy" to solve for new algorithms. On a powerful single processor machine like the TR2990WX the same optimum is found every few hours. We cannot be sure it is a global optimum, but would prefer a problem where better solutions as the ones currently found are expected, enabling us to measure further improvements of real parameter optimization algorithms. If you know of such a problem, specially if it is not related to space mission planning, please comment.

Extending ESAs' GTOP Messenger Full Benchmark

Until then, the easiest way to design such a problem is to extend messenger full. Extending the start time window increases the search space, as does the inclusion of further planets to visit. In the movie "The Martian" a multi GA mission is planned to save Mark Whitney who stranded on Mars (see Science behind saving Matt Damon). Our idea is to prepend messenger full with such a multi GA trip to Mars. We change the messenger planet sequence from EVVmmmm to EVVEEMEVVmmmm (M = Mars, m = Mercury). Transfer time limits are as for Messenger, only for the trip to and from Mars we double the maximum transfer time to 1000 days. We doubled the number of transfers from six to twelve and increased the number of variables to optimize from 26 to 50. Based on ESAs GTOP code the new problem is easy to implement. As before we analyze two versions, one using the original Lambert solver based on ESA's AstroToolbox ESA's AstroToolbox and one using ESAs new Lambert solver . Only the latter one should be considered as "real life problem" since using the original Lambert solver artificially makes the same problem more difficult to solve.
"Since CEC 2005 competition on real-parameter optimisation, Soft Computing (2017)" criticizes scientific publications in the area of real parameter optimization avoiding the comparison to the winner of the 2005 CEC competition: CMA_ES. As Midaco Messenger we only briefly mentioned the comparison to a plain CMA-ES retry mechanism, but didn't apply a comparable amount of function evaluations, something we want to catch up on now. What happens if we apply a serious number of function evaluations to retry CMA-ES using random seeds and <= 200.000 evaluations per run?

Problem Description

Adapt the function “double messengerfull(const std::vector & x)” provided in GTOPtoolbox for the planet sequence EVVEEMEVVmmmm (M = Mars, m = Mercury). Replace the Lambert solver used by ESAs new Lambert solver. 3 revolutions maximum is sufficient for this problem. Always use the locally best Lambert solution, if there are more than one. Note that we choose a different approach for GTOC1 (How to solve GTOC1 today) to find the globally best Lambert solution.

The box bounds on each of the decision vector variable are given below.

No other constraints are considered for this problem. The objective function is considered to the precision of meters per second.

Results applying GCMA-ES

Lets first have a look using the original Lambert solver used in the original Messenger Full problem. The two diagrams below show the best value we find in 16 runs. As ususal we perform 8 runs in parallel on our TR2990WX, each utilizing 8 threads. The diagram above shows the number of function evaluations used in each run, the one below shows the used time in hours. The best value around 4.28 was found in less than one hour.

Using the original Lambert solver

Using the new Lambert solver

The following two diagrams show the same information using the new PyKep Lambert solver. Convergence to better function values is much faster and we reach a better optimum of value = 1.565189 after about 80 minutes. GCMA-ES meta parameters used are exactly as in the previous experiment using the old Lambert solver.





Using the original Lambert solver makes the problem artificially harder, but we don't know if much better solutions exist yet.

The Final One Percent

In most cases there is no real life relevance for the final one percent, since we usually optimize using a model with limited accuracy and apply the optimization result in the context of a more detailed model of reality. For example in Around the World in Eighty Days and GTOC1 today  we switched from a coast arc / impulse engine model to a continuous thrust model. For low DV trajectories both models converge, which is the reason the approximation is valid, but it would not be worth optimizing the final one percent using the approximating model. On the other hand: To be listed in the GTOP rankings like in Messenger Full, you have to be first. In a research context, the final optimization can matter, therefore we will present our related results in this section.   

The martian mission differs from the original messenger full benchmark regarding the final one percent: For messenger full GCMA-ES was sufficient to compute nearly optimal solutions, for the extended martian mission we observed that the best results can further be optimized using plain CMA-ES retries using the best GCMA-ES result so far as initial guess. But what about applying crossover also in this phase? It turned out that this a good idea despite the fact that the advantage applying crossover is much smaller here.  

GCMA-ES configuration for the final one percent:

• We increase the initial maximum number of function evaluations by factor 5.  
• As before we do the same number of crossover and random runs.
• We leave crossover unchanged.
• The random guess used for the random runs no longer uses the whole range of the box constraints but are randomly generated close to the currently best solution.
• The diversity check now uses a much smaller euclidian distance threshold, otherwise all results would be rejected. 

The following diagram illustrates the value reached using the original Lambert solver after applying a certain number of function evaluations. We use the best result from above as starting point. The best value slightly improved what we got by applying plain CMA-ES retry.

The next diagram shows the value reached using the new Lambert solver. Here we found no improvement compared to applying plain CMA-ES retry. 

Best solution found

The best solution found using the new Lambert solver is illustrated in the following video Video of Mars Messenger Solution . Its has a value = 1.5210857, its variable setting is:

x = [13747.236838938545, 3.874880896418853, 0.4929691144987783, 0.6113203046898301, 434.211099257681, 449.3874222083036, 332.47800534636474, 365.24249274841833, 534.8698410700804, 724.6816204306799, 281.9328315134608, 224.69521265170417, 456.21617796897004, 175.8990441527276, 175.9216746526764, 352.1890545928036, 0.4892431890863098, 0.37096016691573686, 0.35369844104793374, 0.17144699436647176, 0.01, 0.48137678376816395, 0.45290123911179114, 0.47194697225900706, 0.7010630034685941, 0.17328931983955312, 0.10330357342126073, 0.6898573163634435, 1.3666784609970954, 5.198256024010363, 5.769877105405506, 2.1474165526863978, 2.102184447702171, 1.470269058873265, 1.6897189760008684, 1.333251204297449, 1.05, 5.114380104220375, 4.556145873011766, -2.0983274400647525, 0.27086820779592335, 0.7546925752106558, -1.6242722440571364, 1.6864948177154657, 1.826806878183786, 1.6972139097839374, 1.929747123795278, -1.5674555677925717, -0.6839039487169672, -0.8122800548618387]

Note that using the original Lambert solver we get a much worse value = 94.43299, may be it is worth investigating what is the reason.

Using the original Lambert solver the best solution has the value = 4.1515781 with variable setting:

x = [13747.236838938545, 3.874880896418853, 0.4929691144987783, 0.6113203046898301, 434.211099257681, 449.3874222083036, 332.47800534636474, 365.24249274841833, 534.8698410700804, 724.6816204306799, 281.9328315134608, 224.69521265170417, 456.21617796897004, 175.8990441527276, 175.9216746526764, 352.1890545928036, 0.4892431890863098, 0.37096016691573686, 0.35369844104793374, 0.17144699436647176, 0.01, 0.48137678376816395, 0.45290123911179114, 0.47194697225900706, 0.7010630034685941, 0.17328931983955312, 0.10330357342126073, 0.6898573163634435, 1.3666784609970954, 5.198256024010363, 5.769877105405506, 2.1474165526863978, 2.102184447702171, 1.470269058873265, 1.6897189760008684, 1.333251204297449, 1.05, 5.114380104220375, 4.556145873011766, -2.0983274400647525, 0.27086820779592335, 0.7546925752106558, -1.6242722440571364, 1.6864948177154657, 1.826806878183786, 1.6972139097839374, 1.929747123795278, -1.5674555677925717, -0.6839039487169672, -0.8122800548618387]

Applying the new Lambert solver to this solution we obtain a similar value = 4.1515437. 

Beside the plain CMA-ES retry results below unfortunately no comparison values for other algorithms are available yet. Modifying the problem changing only the planet sequence should be easy, please comment if you can provide results for other algorithms. Or if you need help in adapting to the new Lambert algorithm.

Plain CMA-ES Retry

Next we want to compare our GCMA-ES results with plain CMA-ES retry. For Messenger Full this was done already in Midaco Messenger resulting in a best solution valued about 6.0, but this time we use a much higher amount of retries. We apply a similar amount of overall function evaluations than in our GCMA-ES experiments. 

This way we can see how much the addition of crossover to CMA-ES helps for very hard optimization problems.

Using the original Lambert solver

The following diagram shows the result value distribution of plain CMA-ES retry applied to the extended messenger mission problem using the original Lambert solver, 37264 retries, lambda = 31, maximum number of function evaluations = 200000:



Two of the 37264 retries achieved a value around 6.0, GCMA-ES achieved a best value = 4.25, a difference of 1.75.

Next lets have a look at the original Messenger Full problem, this time using 94878 retries.



The result (a best value around 2.6) shows that even plain CMA-ES can reach a quite impressive value using a huge amount of retries. GCMA-ES achieved a best value = 1.958, see Adding Crossover to CMA-ES .

Using the new Lambert solver

The following diagram shows the result value distribution of plain CMA-ES retry, applied to the extended messenger misssion problem using the new Lambert solver, 40347 retries, lambda = 31, maximum number of function evaluations = 200000:



The best value around 4.7 is much worse to the best GCMA-ES value = 1.565, so the addition of crossover to CMA-ES seems really useful here.

Now lets have a look at the original Messenger Full problem using the new Lambert solver, using 128029 retries, lambda = 31, maximum number of function evaluations = 200000:



The best value around 2.3 is not far away from the best value found using GCMA-ES of 1.925, see Adding Crossover to CMA-ES . It seems the advantage of using crossover increases with the number of variables to optimize.

Conclusion

Finally we have to admit that the Mark Whitney mission failed to reach our goal. A near perfect solution after 1.5 hours on a single CPU is not exactly what we had planned. The search for a real new optimization challenge has to be continued.