Hide Forgot
Description of problem: I've made up my own TSP problem which contains from nodes in one line. CH founds best solution, ofc, but I am testing next pick planner figures out. I am forcing planner to start with first entity in chain and then pick move from block distribution (see attach. ). How blockDistribution with nearbySelection should work: - it gets entity and pick value for this entity with constant probability from first N values(entities) specified in config file. It means, that if I specify in solver config as <blockDistributionSizeMaximum>2</blockDistributionSizeMaximum> planner should be able to do only two moves from that first entity. ok well, I have PRODUCTION mode in my solver config and I run 100_000 solvers on same initialized soluton, collecting all first moves in map and it's counts. after all solvers are finished, I have in map stored 3 types of moves: "2(after1) => 3(after2)" cca 62% "2(after1) => 4(after3)" cca 25% "2(after1) => 5(after4)" cca 13% the last move shouldn't be there at all. Also, first two moves should be both generated with P[0.5], but I need to examine distribution issue more, there may be mistake on my side. (I am not sure with settings I have in config)
Note: Geoffrey, could you double-check the config file, please?
The config file looks good. I agree that this looks like a genuine bug.
To make a reproducer, it's possible to configure a with a randomSeed: <solver><randomSeed>123</randomSeed></solver>.
Created attachment 1005792 [details] anti reproducer I cannot reproduce this. See attached txt file antireproducer. I tried a different 1000 randomSeeds (even random randomSeeds, but also just 0 to 1000), and I never got a ChangeMove other than the 2 nearest cities (Paris or London) from the selected entity (Dublin). I was wondering if it might be because of UndoMove's that got counted too in your code, but even those would never involve Brussels. Weird. Let's investigate further. I did use a TSP with 40 locations.
Created attachment 1008520 [details] reproducer just run mvn clean install without changes, test should pass. when you switch europe.xml to line.xml (there is commented line) and run mvn agian, test should fail. If doesn't you may try to run more solver instances, but I suppose it should be fine. another interesting part is, that on europe the scale is 1:1 in moves, but there it is 60:27:13. Which is also wrong. I suppose that fixing bug should also solve this issue.
Reproduced with reproducer. It looks like a bug in the mimic selection probably. 5 is too far from 2, yet it gets selected as a value. When it creates the move "2 => 5", the RandomEntityNearbyValueIterator believes that the origin is 4, not 2.
btw when you run reproducer with blockSize == 1, it picks only one correct move "2(after 1) => 3(after 2)", so it goes wrong when blockSize > 1, just making a note, it might help you find a bug.
Problem found. It's not a runtime bug, it's a misconfiguration (that should throw a fail fast exception at bootstrap): <changeMoveSelector> <selectionOrder>ORIGINAL</selectionOrder> <entitySelector><!-- Should have an ID --> <selectionOrder>ORIGINAL</selectionOrder><!-- Obsolete btw --> </entitySelector> <valueSelector> <selectionOrder>RANDOM</selectionOrder> <nearbySelection> <originEntitySelector><!-- Should mimic the entitySelector above --> <selectionOrder>ORIGINAL</selectionOrder> </originEntitySelector> <nearbyDistanceMeterClass>org.optaplanner.examples.tsp.domain.solver.nearby.VisitNearbyDistanceMeter</nearbyDistanceMeterClass> <blockDistributionSizeMaximum>2</blockDistributionSizeMaximum> </nearbySelection> </valueSelector> </changeMoveSelector> What happened: - The config above first selects an entity (for example Madrid), then it selects a nearby value. When it selects that nearby value it looks for values which are nearby... a newly selected entity Ankarra (but it should look for values which are nearby Madrid, the original entity!). - Why did it work most of the time? Because of the ORIGINAL order: the first entity selector starts with Dublin and so those the second. If we turn on trace logging we see that with the randomSeed that triggers the exception, first 2 undoable moves are selected, causing the first entity selector to be past Dublin already. I hope that clears things up :) I 'll add the fail fast now.
Fail fast fixed on master for optaplanner 6.3.0.Beta1: http://github.com/droolsjbpm/optaplanner/commit/c95be1609 No plans to backport currently.
Verified with 6.2.0ER3