Re: [rules-users] Planner: weighting moves & adaptive foragers
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(a)lists.jboss.org
https://lists.jboss.org/mailman/listinfo/rules-users
--
With kind regards,
Geoffrey De Smet