JBoss.orgCommunity Documentation
Because the move B0 to B3 has the highest score (-3
), it is picked
as the next step. Notice that C0 to C3 (not shown) could also have been picked because it
also has the score -3
. If multiple moves have the same highest score, one is picked randomly,
in this case B0 to B3.
The step is made and from that new solution, the local search solver tries all the possible moves again, to decide the next step after that. It continually does this in a loop, and we get something like this:
Notice that the local search solver 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 possible 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 you can see, the local search solver solves the 4 queens problem by starting with the starting solution and make the following steps sequentially:
B0 to B3
D0 to B2
A0 to B1
If we turn on debug
logging for the category org.optaplanner
, then
those steps are shown into the log:
INFO Solving started: time spend (0), score (-6), new best score (-6), random seed (0). DEBUG Step index (0), time spend (20), score (-3), new best score (-3), accepted/selected move count (12/12) for picked step (col1@row0 => row3). DEBUG Step index (1), time spend (31), score (-1), new best score (-1), accepted/selected move count (12/12) for picked step (col0@row0 => row1). DEBUG Step index (2), time spend (40), score (0), new best score (0), accepted/selected move count (12/12) for picked step (col3@row0 => row2). INFO Phase (0) localSearch ended: step total (3), time spend (41), best score (0). INFO Solving ended: time spend (41), best score (0), average calculate count per second (1780).
Notice that the logging uses the toString()
method of our Move
implementation: col1@row0 => row3
.
The local search solver 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. Note: with construction heuristics it's even a lot more efficient.
The local search solver decides the next step with the aid of 3 configurable components:
In the above example the selector generated the moves shown with the blue lines, the acceptor accepted all of them and the forager picked the move B0 to B3.
If we turn on trace
logging for the category org.optaplanner
, then
the decision making is shown in the log:
INFO Solver started: time spend (0), score (-6), new best score (-6), random seed (0). TRACE Ignoring not doable move (col0@row0 => row0). TRACE Move index (1), score (-4), accepted (true) for move (col0@row0 => row1). TRACE Move index (2), score (-4), accepted (true) for move (col0@row0 => row2). TRACE Move index (3), score (-4), accepted (true) for move (col0@row0 => row3). ... TRACE Move index (6), score (-3), accepted (true) for move (col1@row0 => row3). ... TRACE Move index (9), score (-3), accepted (true) for move (col2@row0 => row3). ... TRACE Move index (12), score (-4), accepted (true) for move (col3@row0 => row3). DEBUG Step index (0), time spend (6), score (-3), new best score (-3), accepted/selected move count (12/12) for picked step (col1@row0 => row3). ...
Because the last solution can degrade (especially in tabu search and simulated annealing), 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.
<acceptor>
<solutionTabuSize>1000</solutionTabuSize>
</acceptor>
Move tabu makes recent steps tabu. It does not accept a move equal to one of those steps.
<acceptor>
<moveTabuSize>7</moveTabuSize>
</acceptor>
Undo move tabu makes the undo move of recent steps tabu.
<acceptor>
<undoMoveTabuSize>7</undoMoveTabuSize>
</acceptor>
<acceptor>
<planningEntityTabuSize>7</planningEntityTabuSize>
</acceptor>
<acceptor>
<planningValueTabuSize>7</planningValueTabuSize>
</acceptor>
You can even combine tabu types:
<acceptor>
<solutionTabuSize>1000</solutionTabuSize>
<moveTabuSize>7</moveTabuSize>
</acceptor>
A tabu search acceptor should be combined with a high subset selection, such as
1000
.
<acceptor>
<simulatedAnnealingStartingTemperature>2hard/100soft</simulatedAnnealingStartingTemperature>
</acceptor>
<forager>
<minimalAcceptedSelection>4</minimalAcceptedSelection>
</forager>
<acceptor>
<simulatedAnnealingStartingTemperature>10.0</simulatedAnnealingStartingTemperature>
<planningEntityTabuSize>5</planningEntityTabuSize>
</acceptor>
<forager>
<minimalAcceptedSelection>4</minimalAcceptedSelection>
</forager>
You can implement your own Forager
, although the build-in forager should suffice for most
needs.