How to properly terminate an algorithm using Iteration Without Improvement Termination

jsprit
1

I am running an optimisation with 600+ shipments and 60 (infinite) vehicles. Since this takes quite a long time to run, I’ve introduced a IterationWithoutImprovementTermination with a value of 10. However, the algorithm is never terminated early even though I can see from my logs that there are more than 10 iterations without finding an improvement on the best result.

When looking at the code IterationWithoutImprovementTermination for I see:

if (discoveredSolution.isAccepted()) iterationsWithoutImprovement = 0;
else iterationsWithoutImprovement++;
return (iterationsWithoutImprovement > noIterationWithoutImprovement);

In my case at every iteration discoveredSolution.isAccepted() returns true.

What determines whether a solution is “accepted”?

EDIT: please excuse the spaces in the title - it won’t let me post if I put IterationWithoutImprovmentTermination

2

The behavior of IterationWithoutImprovementTermination depends on the SolutionAcceptor which is used.

For instance, GreedyAcceptance accepts a solution if the new one is better than the worst stored, so it depends on the size of your memory. This can lead to keep solving even if a new best solution is not found.

1 Like