Saturday, June 09, 2007

Local search 101 (Geoffrey De Smet)

I am working on a local search implementation on top of Drools.
My proof of concept is already able to tackle planning problems such as:
Local search and Drools turns out to be a really nice combination because:
  • A rule engine such as Drools is great for calculating the score of a solution of a planning problem. They make it easy to add additional soft or hard constraints such as "a teacher shouldn't teach more then 7 hours a day". However it tends to be too complex to use to actually find new solutions.
  • Local search is great at finding new solutions for a planning problem, without brute-forcing every possibility. However it needs to know the score of a solution and offers no support in calculating that score.
So combining the two, I created Taseree, which will probably be accepted as Drools Solver (Local Search) once it's no longer just a proof of concept. But there's a bunch of work to be done meanwhile though.
You can find it at SourceForge for now, under the same license as Drools. As far as I know I am the first one to think of making a hybrid of local search and a rule engine.

I 'll attempt to open the black box a bit, to get some feed-back on my implementation.

I 'll start with explaining some terms used in the current implementation:
  • Solution: A state of the problem which can be evaluated into a score. The solver will try to find a solution with the highest score it can find. The initial solution's facts are asserted into the Drools WorkingMemory.
  • Score: Calculated on a solution. Higher is better. Many planning problems tend to use negative scores (the amount of constraints being broken) with an impossible perfect score of 0.
  • Move: A migration path from a solution A to a solution B. Some moves are small (move the French lesson to an hour earlier), others are large (switch all lessons on monday with those on friday). Each move has an undo move: a move from solution B back to solution A. A move notifies the Drools WorkingMemory of its changes.
  • Local search: A solver that starts from an initial solution and takes steps to evolve it. It remembers the best solution it comes across.
  • Step: The decided move. Every step taken by a local search solver is picked by the decider from a number of possible moves.
  • Decider: Decides which move is the next step. A decider uses a selector to find moves, a score calculator to calculate the score of each selected move and an accepter to decide whether or not to accept the move as the next step.
  • Selector: Figures out which moves can be made on the current solution.
  • Accepter: Accepts or rejects a move. Implementations can turn the local search into tabu search, simulated annealing, great deluge, ...
  • Tabu search: A specific local search which does not accept moves which evolve the solution into an already encountered solution. Most of the examples use tabu search.
  • Score calculator: Calculates the score for a given solution. It uses the Drools WorkingMemory.
  • Finish: Decides when it's time to give up in trying new steps to find a better solution. Implementations can check time, number of steps, feasibility of best score, ... A local search never knows that it found the perfect solution, so a finish needs to be set. However even small planning problems tend to be so complicated to solve that trying every combination (even with pruning) takes too long (TTP level 10 is a great example of that).
Now, let's take a look at some pseudo code for the local search algoritm combined with a rule engine:

workingMemory.assert(solution.getFacts());
// continue searching until our time is up
while (!finish.isFinished()) {
Move step = decider.decideNextStep() {
for (Move move : selector) {
doMove(workingMemory);
scoreCalculator.calculateScore(workingMemory);
if (accepter.calculateAcceptChance() is accepted) {
return move;
}
undoMove(workingMemory);
}
}
doStep(workingMemory);
if (stepScore > bestScore) {
// remember bestSolution and bestScore
}
}

8 comments:

  1. BTW, if anyone is attempting to test Taseree in it's current state from svn, note that only the SmartTravelingTournament example currently the works out-of-the-box. I am doing some shotgun surgery and only focusing on that example at the moment.
    Also, you might need to use the latest Drools 4.x snapshot.

    ReplyDelete
  2. I find this very exciting! I've worked a little with Choco (http://choco.sourceforge.net) but I've had problems wrapping my head around their abstractions. I came across your blog entry because I was thinking of using JBoss Rules to infer Choco constraints from my domain model (e.g. if a person is male, then x must be between 800 and 1800.) Now it looks like maybe I can do it in one system!

    I'm curious to see how flexible Taseree is in allowing me to guide the search. I am attempting a large problem with thousands of variables and tens of constraints. I think I'll need to bring in a lot of domain heuristics to solve the problem.

    ReplyDelete
  3. In which way would you like to guide the search?
    Currently the local search implementation tries every move at every step, but I investigating several ways to avoid that:
    - only check a portion of the moves each step, along with the top20 of the last step
    - only recalculate "dirty moves", but I am still looking into ways of detecting those.

    ReplyDelete
  4. I'm thinking of search strategies like Limited Discrepancy Search. Choco talks about how you would do it using their library.
    http://choco-solver.net/index.php?title=User_guide#LDS_.28Limited_discrepancy_search.29

    I might be asking too much to think that Taseree would be a general search engine when you've billed it as a local search engine. One thing that concerns me (with respect to my problem domain) is that all moves must be enumerated, then the best one is chosen. This is clearly thinking locally, not globally. Plus, I anticipate having ~6K possible moves, and although the computation time should be in evaluating the moves, I'm thinking there might be a lot in just making those large lists of moves.

    Can you say more about the intended use cases of Taseree?

    ReplyDelete
  5. LDS doesn't look like a local search (as far as I understand it now), so that will be hard. Nevertheless it would be interesting to see a LdsSolver one day, which can reuse some of the concepts already in the framework, such as using drools for score evaluation.

    I share your concerns about evaluating all moves for each step.
    TTP10 already has 1.5k I believe. I am currently investigating 2 ways of avoiding that:
    1) only evaluate a subset of the moves (and possibly also re-evaluate the top 20 unmade moves of all time)
    2) only evaluate the moves of which the score delta it represents has changed with the last step. (code name "holy grail of localsearch":)

    I am mainly focusing on 1) for now, as 2) is ok for NTowers or NQueens, but difficult as hell for anything more complicated.

    ReplyDelete
  6. Here's some code which might be able to do 2) dirty move checking:



    class Tower {
    int y;
    }

    // assert 8 towers, starting all with y = 0;
    ...

    // score calculation
    query twoTowersWithSameY
    Tower($id : id, $y : y);
    Tower(id > $id, y == $y);
    end

    class TowerMove {
    Tower t;
    int y;
    }

    // Generate the moves with drools
    rule moveGenerator
    when
    $y >= 0;
    $y < 8;
    $tower : Tower(y != $y);
    then
    assertLogical(new TowerMove ($tower, $y));
    end

    I pick a move which I do, which becomes $lastMove,
    which changes one of the tower.y's to a new number (between 0 and 8).

    ok, now I 'd like a really special rule to detect dirty moves:
    moves which score calculation is dirty.
    I know the $lastMove, so I can put that into a global variable.
    (note: $lastMove should actually be $lastUndoMove)

    rule twoTowersWithSameYDirty
    when
    $move : Move(id != $lastMove.id);
    $move.tower.y == $lastMove.tower.y
    OR $move.tower.y == $lastMove.y
    OR $move.y == $lastMove.tower.y
    OR $move.y == $lastMove.tower.y
    then
    assertLogical(new Dirty($move));
    end

    ReplyDelete
  7. Hello!Hi..anyone can help me to write a tabu search code for MAX-2-SAT problem with large variables.
    Thank you.
    Urgent!

    ReplyDelete
  8. Hi! which package can be used to solve Patient Admission Scheduling

    ReplyDelete