[rules-users] Planner: weighting moves & adaptive foragers

[Geoffrey De Smet]

Op 16-04-12 22:31, Christopher Dolan schreef:
> Three related questions about Drools Planner:
>
> My planning problem involves distributing N jobs into M job queues. The optimal queue ordering depends on a large number of factors, but most important are job priority and job age. Priority usually wins, but old jobs can trump to avoid starvation.
>
> If N x M is large, the collection of possible moves becomes large. But I know a priori that some moves are more likely to help than others. For example, I can promote the high-priority and old jobs first, because they will have the largest score impact.
For FIRST_FIT_DECREASING, you probably want to multiply highPriority * 
oldJobAge to determine entity difficulty.
> 1) Can I weight the selector to pick the better moves first? It looks like I'd make a custom AbstractSelector subclass that shuffled differently from MoveFactorySelector, maybe lazily finding moves via a pick function.
Not yet, if I find enough time, this is something I want to do for 
5.5.0.Beta1 as part of this refactor:
   https://issues.jboss.org/browse/JBRULES-3371

Try adding your a custom Selector (see manual) to see how that works out.
If you do, please mail me the results of these experiments.
I am always interested in how these kind of experiments turn out 
(successes and failures!).
> Of course, selecting better moves first is worthless if the forager doesn't use shortcuts, like FIRST_BEST_SCORE_IMPROVING.
No, it's not. with minimalAcceptedSelection 1000, that means you 'll be 
looking at more favorited moves more in that 1000 set.
Important: you still want to be looking at the non-favorited moves, as 
they will be better in some iterations.
>   But the existing AcceptingForager implementation is very binary: it either takes the first good score or it ignores score and waits for a total number of moves.
>
> 2) Has anyone built a generic Forager that looks at the distribution of scores and stops early if it finds a fantastic outlier? In particular, early in the solver there are lots of very easy improvements to make. Taking the first good one may be premature, but going through 1000 moves is a waste of time. I'd like a forager that just tries a few moves early and then tries more moves later on when it's harder to make gains. On the other hand, is putting a lot of work into a perfect forager just redundant with the acceptor?
Haven't tried that yet. Try adding your own Forager and see how that 
experiment works out.
Note: Make sure your custom Selectors and Foragers are configurable 
through xml, so you can easily run lots of different benchmarks of it 
with the Benchmarker and compare it to vanilla configurations.
> 3) Has anyone employed the undocumented TopListSelector? I'm intrigued that it feeds the forager's best moves back into the selector. How does it work? I think you need to combine it with a move factory to seed the solutions, but then it's redundant with that factory's output. Are selectors allowed to return the same move twice??
The topListSelector is one of my undocumented experiments (like 
partialTabu and greatDeluge).
The idea is that if you evaluate 1000 moves out of 1000000 possible 
moves and take the best one as step 11,
it could be interesting to check the runner up too for step 12 (as it 
might be better then a 1000 new ones).
I haven't done many benchmarker experiments with it (and it might even 
be bugged, as there is no unit test for it), but I haven't seen an 
improvement with it yet.
> Chris
>
> _______________________________________________
> rules-users mailing list
> rules-users at lists.jboss.org
> https://lists.jboss.org/mailman/listinfo/rules-users
>

-- 
With kind regards,
Geoffrey De Smet