KIE Community

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:

• NQueens
• A simplified lesson schedule with teachers, groups, lessons and timeslots.
• Traveling Tournament Problem (TTP) (only breaking old records at the moment though)

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
  }
}