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
Powered by Discourse