10.2. Local Search Concepts

10.2.1. Step by Step

A step is the winning Move. Local Search tries a number of moves on the current solution and picks the best accepted move as the step:

Figure 10.1. Decide the next step at step 0 (4 queens example)

Decide the next step at step 0 (4 queens example)
Because the move B0 to B3 has the highest score (-3), it is picked as the next step. If multiple moves have the same highest score, one is picked randomly, in this case B0 to B3. Note that C0 to C3 (not shown) could also have been picked because it also has the score -3.
The step is applied on the solution. From that new solution, Local Search tries every move again, to decide the next step after that. It continually does this in a loop, and we get something like this:

Figure 10.2. All steps (4 queens example)

All steps (4 queens example)
Notice that Local Search doesn't use a search tree, but a search path. The search path is highlighted by the green arrows. At each step it tries all selected moves, but unless it's the step, it doesn't investigate that solution further. This is one of the reasons why Local Search is very scalable.
As shown above, Local Search solves the 4 queens problem by starting with the starting solution and make the following steps sequentially:
  1. B0 to B3
  2. D0 to B2
  3. A0 to B1
Turn on debug logging for the category org.optaplanner to show those steps in the log: 
INFO  Solving started: time spent (0), best score (-6), random (JDK with seed 0).
DEBUG     LS step (0), time spent (20), score (-3), new best score (-3), accepted/selected move count (12/12), picked move (Queen-1 {Row-0 -> Row-3}).
DEBUG     LS step (1), time spent (31), score (-1), new best score (-1), accepted/selected move count (12/12), picked move (Queen-3 {Row-0 -> Row-2}).
DEBUG     LS step (2), time spent (40), score (0), new best score (0), accepted/selected move count (12/12), picked move (Queen-0 {Row-0 -> Row-1}).
INFO  Local Search phase (0) ended: step total (3), time spent (41), best score (0).
INFO  Solving ended: time spent (41), best score (0), average calculate count per second (1780).
Notice that a log message includes the toString() method of the Move implementation which returns for example "Queen-1 {Row-0 -> Row-3}".
A naive Local Search configuration solves the 4 queens problem in 3 steps, by evaluating only 37 possible solutions (3 steps with 12 moves each + 1 starting solution), which is only fraction of all 256 possible solutions. It solves 16 queens in 31 steps, by evaluating only 7441 out of 18446744073709551616 possible solutions. By using a Construction Heuristics phase first, it's even a lot more efficient.

10.2.2. Decide the Next Step

Local Search decides the next step with the aid of 3 configurable components:
  • A MoveSelector which selects the possible moves of the current solution. See the chapter move and neighborhood selection.
  • An Acceptor which filters out unacceptable moves.
  • A Forager which gathers accepted moves and picks the next step from them.
The solver phase configuration looks like this: 
  <localSearch>
    <unionMoveSelector>
      ...
    </unionMoveSelector>
    <acceptor>
      ...
    </acceptor>
    <forager>
      ...
    </forager>
  </localSearch>
In the example below, the MoveSelector generated the moves shown with the blue lines, the Acceptor accepted all of them and the Forager picked the move B0 to B3.
Turn on trace logging to show the decision making in the log: 
INFO  Solver started: time spent (0), score (-6), new best score (-6), random (JDK with seed 0).
TRACE         Move index (0) not doable, ignoring move (Queen-0 {Row-0 -> Row-0}).
TRACE         Move index (1), score (-4), accepted (true), move (Queen-0 {Row-0 -> Row-1}).
TRACE         Move index (2), score (-4), accepted (true), move (Queen-0 {Row-0 -> Row-2}).
TRACE         Move index (3), score (-4), accepted (true), move (Queen-0 {Row-0 -> Row-3}).
...
TRACE         Move index (6), score (-3), accepted (true), move (Queen-1 {Row-0 -> Row-3}).
...
TRACE         Move index (9), score (-3), accepted (true), move (Queen-2 {Row-0 -> Row-3}).
...
TRACE         Move index (12), score (-4), accepted (true), move (Queen-3 {Row-0 -> Row-3}).
DEBUG     LS step (0), time spent (6), score (-3), new best score (-3), accepted/selected move count (12/12), picked move (Queen-1 {Row-0 -> Row-3}).
...
Because the last solution can degrade (for example in Tabu Search), the Solver remembers the best solution it has encountered through the entire search path. Each time the current solution is better than the last best solution, the current solution is cloned and referenced as the new best solution.

10.2.3. Acceptor

An Acceptor is used (together with a Forager) to active Tabu Search, Simulated Annealing, Late Acceptance, ... For each move it checks whether it is accepted or not.
By changing a few lines of configuration, you can easily switch from Tabu Search to Simulated Annealing or Late Acceptance and back.
You can implement your own Acceptor, but the build-in acceptors should suffice for most needs. You can also combine multiple acceptors.

10.2.4. Forager

A Forager gathers all accepted moves and picks the move which is the next step. Normally it picks the accepted move with the highest score. If several accepted moves have the highest score, one is picked randomly to break the tie. Breaking ties randomly leads to better results.
Note
It is possible to disable breaking ties randomly by explicitly setting breakTieRandomly to false, but that's almost never a good idea:
  • If an earlier move is better than a later move with the same score, the score calculator should add an extra softer score level to score the first move as slightly better. Don't rely on move selection order to enforce that.
  • Random tie breaking does not affect reproducibility.

10.2.4.1. Accepted Count Limit

When there are many possible moves, it becomes inefficient to evaluate all of them at every step. To evaluate only a random subset of all the moves, use:
  • An acceptedCountLimit integer, which specifies how many accepted moves should be evaluated during each step. By default, all accepted moves are evaluated at every step. 
      <forager>
    <acceptedCountLimit>1000</acceptedCountLimit>
  </forager>
Unlike the n queens problem, real world problems require the use of acceptedCountLimit. Start from an acceptedCountLimit that takes a step in less then 2 seconds. Turn on INFO logging to see the step times. Use the Benchmarker to tweak the value.
Important
With a low acceptedCountLimit (so a fast stepping algorithm), it is recommended to avoid using selectionOrder SHUFFLED because the shuffling generates a random number for every element in the selector, taking up a lot of time, but only a few elements are actually selected.

10.2.4.2. Pick Early Type

A forager can pick a move early during a step, ignoring subsequent selected moves. There are 3 pick early types for Local Search:
  • NEVER: A move is never picked early: all accepted moves are evaluated that the selection allows. This is the default. 
        <forager>
      <pickEarlyType>NEVER</pickEarlyType>
    </forager>
  • FIRST_BEST_SCORE_IMPROVING: Pick the first accepted move that improves the best score. If none improve the best score, it behaves exactly like the pickEarlyType NEVER. 
        <forager>
      <pickEarlyType>FIRST_BEST_SCORE_IMPROVING</pickEarlyType>
    </forager>
  • FIRST_LAST_STEP_SCORE_IMPROVING: Pick the first accepted move that improves the last step score. If none improve the last step score, it behaves exactly like the pickEarlyType NEVER. 
        <forager>
      <pickEarlyType>FIRST_LAST_STEP_SCORE_IMPROVING</pickEarlyType>
    </forager>