Finding optimal solution with random seed

Hello everyone,

I struggle now with several issues with JSprit.

  1. We found out that solution is not always, even not more likely to by optimal, or best ever. In fact we try calculate one VRP several times, with true Random from java utils and got several solutions. Some of them was excelent, some horrible. But the problem is, that we cannot tell if the solution provided by JSprit is good enough. Diferences between solutions can be almost 30%, so it must be considered.
    The result from this is, that if we provide “true” random, it can start the optimisation from random point in space, thus found out best ever solution faster, but it’s random. Next run can end with totaly diffrent result, most likely worse.
    I’m currently testing new idea with static seed, but bigger iteration threshold. My idea is, that if JSprit got enough time to search through a space, it can found out better solution. The result seems promissing, but what I doesn’t expect is that even with static seed I got different solutions after long run (cca 3000 iterations) for same problem. So calculations are not replicable, even with static seed.
    Have someone any experience with this behavior?

  2. Does anyone observe weird behavior in iteration phase wich changing performace from 1 thread to full thread count from setup? Like I have 15 threads for interations. But it repetitively drops from 15 to 1, then go to 15 again. I don’t know what this means, or where to look.

Dear Thomas,

we can share our finding with you that with static seed, which is the default implementation of the library, we get replicable (though maybe non-optimal) results.

Best Regards,
Stefan.

Unfortunatelly, that is no true. 10x computing same problem and got 10 different scores at same iteration step. This mean u cannot replicate same steps every time. Even if final solution seems alike. Thus inside JSprite is something what cause even with static seed, thus same random number sequence, different winner in selector strategies. But idk what is the cause of this behavior. How is even possible to get different solution in specific interation of specific problem on specific machine. I’m affraid this behavior is connected to load of the machine, which cause the randomness.

We have done some more testing also on our side.

We have to agree now that we do not get replicable results for all scenarios. We have some scenarios though with about 50-100 jobs that are perfectly replicable.

And we have some scenarios with > 300 jobs that are also not exactly replicable. We have tested mostly with the Li&Lim Benchmarks: Li & Lim benchmark

But also have one scenario (~60 jobs) that we created ourselves.
Also, we have no idea, how this can be explained. I am not sure, if load of the machine really explains this behaviour.

I’m currently testing scenarios with ~600 jobs. Currently I found out it looks like random generator is the sinner. I disabled all params which do something with random like NOISE_LEVEL, NOISE_PROB, CLUSTER_MAX/MIN_SHARER etc. Still got some random behavior. When I switch to SecureRandom with static seed, I finally got same results. Now I’m iterating back to optimal setup and checking results, step-by-step. But for now my conclusion is Random is the cause of weird behavior. I think that threads somehow share source of randomness and thus some threads start generating incompatible numbers. We will see, if I’m right. Stay tuned :+1:

1 Like

We can confirm your assumption that it has to do with threads. In our test scenarios, we get replicable results, if we use Jsprit.Parameter.THREADS = 1 (even with the built-in Random Number Generator)

If we Jsprit.Parameter.THREADS > 1, we get non-replicable results for scenarios with > ~100 jobs.

Thus, indeed it might indeed have to do with the Random Number Generator being used by multiple threads. I could even imagine that there is no simple work-around, since if you start using multiple threads to find the solution, the behvaviour, which thread will pick the next random number from the static sequence is not deterministic.

Btw, we have also tried a different Random Number generator (JDKRandomBridge (Apache Commons RNG Simple 1.0 API)), but found this did not change anything. However, we did not experiment with the parameters that you mention. They indeed might have additional influence.

However, would be happy to hear about your findings.

1 Like

We have done some more investigation on this in the mean time. We made tests with one Thread compare to 8 Threads. We found that the solution if one Thread is replicable. With 8 threads it is not. However, total costs show difference of about 1-2%, while computation speed is 20-60% (depending on the scenario) when using 8 Threads.
This shows that basically you can decide between speed of solution computation and (not) having minor divergences in the gained solutions.

1 Like

Totaly agree with your conclusion. In my case there was bigger difference in cost, because I’ve been using time termination. So more threads means better solution in shorter time. So now I’m just working on termination function which can take in account number of iteration, improvement of solution and variation coefficient. This termination function with huge maxIteration buffer should be able reach acceptable, almost “constant”, solution. So for now I’m ok with non-replicable solutions, but want to get at least similar solution. If you are interested in source code of the termination function, I’m happy to share.

Indeed, it would be interesting to see your solution. Perhaps, it is even interesting for other users. Therefore, maybe you could share the code for the termination function even here in forum (if it is not to much).

package cz.logio.jsprit.simulator;

import com.graphhopper.jsprit.core.algorithm.SearchStrategy;
import com.graphhopper.jsprit.core.algorithm.VehicleRoutingAlgorithm;
import com.graphhopper.jsprit.core.algorithm.listener.AlgorithmStartsListener;
import com.graphhopper.jsprit.core.algorithm.listener.IterationStartsListener;
import com.graphhopper.jsprit.core.algorithm.termination.PrematureAlgorithmTermination;
import com.graphhopper.jsprit.core.problem.VehicleRoutingProblem;
import com.graphhopper.jsprit.core.problem.solution.VehicleRoutingProblemSolution;
import org.apache.commons.math3.stat.StatUtils;
import org.apache.commons.math3.stat.descriptive.moment.StandardDeviation;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.Collection;
import java.util.Deque;
import java.util.LinkedList;

public class OptimalSolutionTermination implements
    PrematureAlgorithmTermination, AlgorithmStartsListener, IterationStartsListener {

    private static final Logger log = LoggerFactory.getLogger(OptimalSolutionTermination.class);
    private static final int MEMORY_SIZE = 20;
    private static final double VARIATION_THRESHOLD = 0.015;
    private static final double VARIATION_WEIGHT = 1.2;
    private static final double IMPROVEMENT_THRESHOLD = 0.125;
    private static final double IMPROVEMENT_WEIGHT = 2;
    private static final double PROGRESS_THRESHOLD = 0.25;
    private static final double PROGRESS_WEIGHT = 1.8;

    private final Deque<Double> memory = new LinkedList<>();
    private double best = Double.MAX_VALUE;
    private double worst;
    private int iteration;
    private int maxIteration;

    private VehicleRoutingProblemSolution getBest(Collection<VehicleRoutingProblemSolution> solutions) {
        VehicleRoutingProblemSolution worstBest = null;
        for (VehicleRoutingProblemSolution solution : solutions) {
            if (worstBest == null) {
                worstBest = solution;
            } else {
                if (solution.getCost() < worstBest.getCost()) {
                    worstBest = solution;
                }
            }
        }
        return worstBest;
    }

    private double progressWeight() {
        var progress = (double) iteration / maxIteration;
        if(progress > 0.) {
            return Math.min(
                progress / PROGRESS_THRESHOLD,
                PROGRESS_WEIGHT * Math.exp(-1. * Math.log(PROGRESS_WEIGHT) / (progress / PROGRESS_THRESHOLD))
            );
        }
        return 0.;
    }

    private double scoreWeight() {
        var improvement = ((worst - best) / worst);
        if(improvement > 0.) {
            return Math.min(
                improvement / IMPROVEMENT_THRESHOLD,
                IMPROVEMENT_WEIGHT * Math.exp(-1. * Math.log(IMPROVEMENT_WEIGHT) / (improvement / IMPROVEMENT_THRESHOLD))
            );
        }
        return 0.;
    }

    private double variationCoefficient() {
        if (memory.size() == MEMORY_SIZE) {
            var values = this.memory.stream().mapToDouble(i -> i).toArray();
            var mean = StatUtils.mean(values);
            var stdev = new StandardDeviation().evaluate(values, mean);
            return stdev / mean * 100;
        }
        return Double.MAX_VALUE;
    }

    private double variationWeight() {
        var variationCoefficient = variationCoefficient();
        return VARIATION_WEIGHT * Math.exp(-1. * Math.log(VARIATION_WEIGHT) * variationCoefficient / VARIATION_THRESHOLD);
    }

    private double currentThreshold() {
        var progress = progressWeight();
        var improvement = scoreWeight();
        var variation = variationWeight();
        log.info("Progress: {}, improvement: {}, variation: {}]",
            String.format("%.3f", progress),
            String.format("%.3f", improvement),
            String.format("%.3f", variation)
        );
        return progress * improvement * variation;
    }

    private void memorize(SearchStrategy.DiscoveredSolution discoveredSolution) {
        if (discoveredSolution.isAccepted()) {
            memory.add(discoveredSolution.getSolution().getCost());
            if (memory.size() > MEMORY_SIZE) {
                memory.remove();
            }
            if (best > discoveredSolution.getSolution().getCost()) {
                best = discoveredSolution.getSolution().getCost();
                if (log.isInfoEnabled()) {
                    log.info("Found new best score: {}.", String.format("%.2f", best));
                }
            }
        }
    }

    @Override
    public boolean isPrematureBreak(SearchStrategy.DiscoveredSolution discoveredSolution) {
        memorize(discoveredSolution);
        var threshold = currentThreshold();
        if (log.isInfoEnabled()) {
            log.info("Iteration: {}, threshold: {}.", iteration, String.format("%.5f", threshold));
        }
        if (threshold > 1) {
            log.info("Iteration terminated due too much iteration without significant improvement.");
            return true;
        }
        return false;
    }

    @Override
    public void informAlgorithmStarts(VehicleRoutingProblem problem, VehicleRoutingAlgorithm algorithm, Collection<VehicleRoutingProblemSolution> solutions) {
        var worstBest = getBest(solutions);
        worst = worstBest != null ? worstBest.getCost() : Double.MAX_VALUE;
        maxIteration = algorithm.getMaxIterations();
        log.info("Initialize {}", this);
    }

    @Override
    public void informIterationStarts(int i, VehicleRoutingProblem problem, Collection<VehicleRoutingProblemSolution> solutions) {
        iteration = i;
    }

    @Override
    public String toString() {
        return "OptimalSolutionTermination{" +
            "memorySize=" + MEMORY_SIZE +
            ", variationThreshold=" + VARIATION_THRESHOLD +
            ", variationWeight=" + VARIATION_WEIGHT +
            ", improvementThreshold=" + IMPROVEMENT_THRESHOLD +
            ", improvementWeight=" + IMPROVEMENT_WEIGHT +
            ", progressThreshold=" + PROGRESS_THRESHOLD +
            ", progressWeight=" + PROGRESS_WEIGHT +
            ", maxIteration=" + maxIteration +
            "}";
    }
}

For now I have maxIterations set to 20_000. For now improvement and progress weights are calculated by linear-logarithmic function. Variation is pure logarithmic. In next phase I’d like to use sigmoid for progress and improvement weights, but still cannot figure out how to make sigmoit work with threshold. But maybe this helps someone.

Thanks for sharing this. This approach is definitively interesting.