**DietmarW**

GTOCX is the first GTOC competition were submitted solutions were published.

I opened this thread to discuss how these solutions can be utilized. May be others

can add their ideas, we definitely can achieve better results by joining forces.

Published solutions may be used to:

a) Achieve speedups by implementing a fast approximation for star to star transfers:

Fast approximation of valid star to star transfers speed up your algorithm. You may use

elliptical approximations of your transfers using the Lambert algorithm based on the

assumption that there is a central body as source of gravitation. For a galaxy this

is not the case, but for short transfer times (< 20 Myr) Lambert approximations are quite

accurate. The gravitational parameter of the central body can be derived from R and the

mean motion. Since R is different at start and arrival we have to somehow approximate the

gravitational parameter.

This approximation can be verified using an existing GTOCX solution as follows:

One term of the merit function is dVmax/dVused. Compute dVmax/dVused for good GTOCX solutions

using your Lambert approximation and compare with the real value.

b) Achieve speedups by implementing filters for valid star to star transfers:

A filter can further improve performance by sorting out infeasible transfers based on

the positions of the stars and the time of flight. You may verify such a filter by checking

if valid transfers of good GTOCX solutions are not filtered out.

c) Finetune the parameters of your algorithm

To explain this topic we need an example algorithm. Lets choose the simplest one I know

which is able to generate a reasonable (> 3000) score:

Prerequisites

-------------

You need an efficient incremental implementation of the merit function, both without and

with the dVmax/dVused part. Which means you have to maintain the sums for a given star/transfer

set to be able to compute the merit function fast if a star/transfer is added.

Base Algorithm

--------------

The base algorithm is based on star sets, it abstracts from the problem how to get from star A

to star B:

Given a set of settled stars setA, determine a disjoined set setB so that merit(setA + setB) is maximized.

We use the merit function without the dVmax/dVused part here. The incremental

algorithm works as follows:

a) Randomly choose a star S not in setA.

If merit(setA + S) + 0.2 > merit(setA) then add S to setA

b) Repeat a) until setA no longer grows

c) Randomly choose a star S added to setA by a),b),

randomly choose a star S2 not in setA.

If merit(setA + S2) > merit(setA + S)

then add S2 to setA and remove S from setA

d) Repeat c) until merit(setA) no longer grows

e) Repeat a), b), c) d) until merit(setA) no longer grows

**DietmarW**

With "randomly choose" we mean choose and retry for a configurable number of times until the condition

is met. In practice you can set hard limits to the number of repetitions in each step. Since the algorithm

is stochastic it can easily be parallelized: Distribute different instances of the algorithm

to your available CPU cores and choose the best result.

Interesting test star sets to be extended derived from a submitted solution can be:

a) the set of stars reached by mother/fast ships.

b) the set of stars reached before Myr=90

Considering valid transfers

---------------------------

In practice you cannot simply add a star S to your set of visited stars, you have to fulfill two

constraints:

a) Branching factor <= 3: Only 3 settler ships may start from a star

b) Valid transfer: There has to be a valid transfer between a star in treeA to S.

We always choose the earliest possible departure time = arrival time + 2 Myr. The targeted arrival time is

a parameter of the algorithm. Now we also need the full merit function using dVmax/dVused which

we name meritDV here.

The goal is now:

Given a tree of settled stars treeA, determine a disjoined tree treeB so that meritDV(treeA + treeB) is maximized,

treeB nodes are rooted in treeA nodes using valid transfers and the resulting tree

treeA + treeB fulfills the branching factor <= 3 constraint.

These valid transfer contraints are added to the merit constaints above. Only if the merit constraints

of the basic algorithm are fulfilled we need to check transfer constraints. Keep in mind, that the timings

of the transfers are fixed for now: departure time = arrival time + 2 Myr, arrival time at next star

is a parameter of the algorithm.

a) Iterate over stars S0 in treeA with less than 3 outgoing transfers.

b) Randomly choose a star S not in treeA. If merit(treeA + S) + 0.2 > merit(treeA)

and if there is a valid transfer from S0 to S

and if meritDV(treeA + S) + 0.2*dVmax/dVused > meritDV(treeA) add S to treeA.

c) Repeat a), b) until treeA no longer grows

d) Iterate over stars S0 in treeA with less than 3 outgoing transfers.

e) Randomly choose a star S added to treeA by a),b),c),

randomly choose a star S2 not in treeA. If merit(treeA + S2) > merit(treeA + S)

and if there is a valid transfer from S0 to S2

and if meritDV(treeA + S2) > meritDV(treeA + S) then add S2 to treeA and remove S from treeA

f) Repeat d), e) until meritDV(treeA) no longer grows

g) Repeat a), b), c), d), e), f) until merit(treeA) no longer grows

The order of the iteration in a) and d) needs to be optimized to cope with the branching factor <= 3 limit.

We maintain the sum of the number of added outgoing transfers for each of the stars we iterate over and

sort these stars according to this sum. This way stars which have less chance to be root of new settlements will

get higher priority.

**DietmarW**

Finetune the parameters of your algorithm

-----------------------------------------

As a first step take the subtree of a good solution including all stars reached before Myr=90.

Then apply the algorithm with a fixed arrival time of Myr=90. If you take for instance the

NUDT subtree you should reach a score > 3000 by adding Myr=90 nodes to the tree using the algorithm

above. If not your parameters need some tweaking.

How to compute a solution based on a root tree generated using only mother ships and fast ships

----------------------------------------------------------------------------------------------

If you start from a root tree you can use the algorithm with fixed arrival time of Myr=90

removing the branching factor <= 3 constraint to quickly evaluate the "quality" of the root tree.

But to compute a real solution, we cannot directly head for Myr=90, we need intermediate nodes to

grow the tree. We simply iterate over multiple invocations of the algorithm above incrementally

increasing the targeted arrival time. Something like

Tree treeA = baseTree;

double dt = 2.3;

for (double maxTime = 7; maxTime < 90; maxTime += dt) {

treeA = callAlgorithm(treeA, maxTime);

dt += 0.9;

}

callAlgorithm(treeA, 90);

which incrementally increases the step size dt. We used maxTime as an upper limit

randomly choosing the the arrival time between maxTime-0.5*dt and maxTime. Only

for maxTime=90 we always took arrivalTime=90. We used parallelization inside

callAlgorithm choosing the best result using all cores of a single NUMA node,

and at the level of the outer loop assigning full NUMA-Nodes to loop executions.

**alessandro.zavoli@uniroma1.it**

Dear Wolz,

Your idea seems very intriguing.

Concerning the point "b) Achieve speedups by implementing filters for valid star to star transfers", I would suggest you to check the simple solution we "developed" in Rome, that is essentially based on the solution of a linear impulsive rendzevous problem. Further details are provided in the conference paper.

Error in DV estimate are usually about 1-5 km/s. You may send me an email need further details.

Alessandro Zavoli

**DietmarW**

Dear Alessandro,

thanks for your reply,.

will check your paper and contact you via mail in case of questions.

Did some more experiments and noticed the scores above a a bit inflated:

a) Without further optimization the simple method above reaches about score 2800 when started from the NUDT tree

without the Myr=90 nodes and about 1500 when started from the NUDT Mothership/Fast ship root tree.

You need further optimizations as described in the papers from NUDT / ESA to proceed from here.

b) Instead of a fixed arrival time a fixed time of flight (incremented in subsequent applications of the algorithm) can be advantageous.

c) You may increase the number of reached stars (and decrease the dv ratio) by lowering the

time of flight if the dv is low. This may generate a better basis for further optimizations.

d) The algorithm may be further simplified by removing d) to g), the exchange of target stars, specially

if you plan to apply another optimization phase.

**DietmarW**

Dear Alessandro,

after checking your conference paper I noticed that our approach is very similar to yours.

You can approximate the non-keplerian multi-impulse spaceship transfer by two impulses and

a) a line

b) a circle

c) an ellipse

We thought although the stars itself travel on circular orbits, transfers can better be approximated using ellipses.

But I agree that probably circular transfers are accurate enough and easier/faster to compute. But thanks to Darios fast

open source Lambert transfer code, elliptical approximations are also quite efficient.

We handle the problem of single impulses exceeding the 175kms limit by adding a penalty value to the sum of the impulses.

Here is the reformulation of the algorithm using maximal time of flight instead of arrival time as parameter:

algoV2 ( maxTOF) =

a) Iterate over stars S0 in treeA with less than 3 outgoing transfers.

b) Randomly choose a star S not in treeA.

If merit(treeA + S) > merit(treeA) - 0.2

and if there is a valid transfer from S0 to S

and if meritDV(treeA + S) > meritDV(treeA) + 0.1 add S to treeA.

c) Repeat a), b) until treeA no longer grows

d) Iterate over stars S added to treeA by a),b),c) via a transfer from star S0

e) Randomly choose a star S2 not in treeA.

If merit(treeA - S + S2) > merit(treeA)

and if there is a valid transfer from S0 to S2.

and if meritDV(treeA - S2 + S0) > meritDV(treeA + S)

then remove S from treeA and add S2 to treeA

f) Repeat d), e) until meritDV(treeA) no longer grows

g) Repeat a), b), c), d), e), f) until merit(treeA) no longer grows

A transfer is valid if with tof (time of flight) = maxTOF and approximated dv < 400 kms.

If dv < 400 kms with tof = maxTOF also try tof = maxTOF * (dv / 400)^0.8 to reduce time of flight.

Adjust tof so that arrival time never exceeds 90 Myr.

You may use a loop to iteratively increase maxTOF like:

for (double maxTOF = 2.3; maxTOF < 60; maxTOF += 0.9)

algoV2 ( maxTOF)

Is there another basic algorithm as simple as this achieving a score around J = 1500?

ESAs concurrent search without refinement (which is quite similar) reaches J = 1177, a separate result for

NUDTs ACO for the CMSTDC problem is not given in their paper, Tsinghuas GA looks more complex

(but is quite successful). Our approach doesn't limit the number of available stars as NUDTs first GA step

does. NUDTs final result suggests this is a good idea. I am not sure about this.

Dietmar

**DietmarW**

small correction, should be:

and if meritDV(treeA - S2 + S0) > meritDV(treeA)

Please log in to leave a comment.