To determine which move types might be missing in your implementation, run a Benchmarker for a short amount of time and configure it to write the best solutions to disk. Take a look at such a best solution: it will likely be a local optimum. Try to figure out if there’s a move that could get out of that local optimum faster.

If you find one, implement that coarse-grained move, mix it with the existing moves and benchmark it against the previous configurations to see if you want to keep it.

Instead of reusing the generic Moves (such as ChangeMove) you can also implement your own Moves. Generic and custom MoveSelectors can be combined as desired.

A custom Move can be tailored to work to the advantage of your constraints. For example, in examination scheduling, changing the period of an exam A also changes the period of all the exams that need to coincide with exam A.

A custom Move is also slightly faster than a generic Move. However, it’s far more work to implement and much harder to avoid bugs. After implementing a custom Move, make sure to turn on environmentMode FULL_ASSERT to check for score corruptions.

Your custom moves must implement the Move interface:

public interface Move {

    boolean isMoveDoable(ScoreDirector scoreDirector);

    Move createUndoMove(ScoreDirector scoreDirector);
    void doMove(ScoreDirector scoreDirector);

    Collection<? extends Object> getPlanningEntities();
    Collection<? extends Object> getPlanningValues();

}

Let’s take a look at the Move implementation for 4 queens which moves a queen to a different row:

public class RowChangeMove extends AbstractMove {

    private Queen queen;
    private Row toRow;

    public RowChangeMove(Queen queen, Row toRow) {
        this.queen = queen;
        this.toRow = toRow;
    }

    // ... see below

}

An instance of RowChangeMove moves a queen from its current row to a different row.

Planner calls the doMove(ScoreDirector) method to do a move, which calls doMoveOnGenuineVariables(ScoreDirector). The Move implementation must notify the ScoreDirector of any changes it makes to planning entity’s variables:

    public void doMoveOnGenuineVariables(ScoreDirector scoreDirector) {
        scoreDirector.beforeVariableChanged(queen, "row"); // before changes are made to the queen.row
        queen.setRow(toRow);
        scoreDirector.afterVariableChanged(queen, "row"); // after changes are made to the queen.row
    }

You need to call the scoreDirector.beforeVariableChanged(Object, String) and scoreDirector.afterVariableChanged(Object, String) methods directly before and after modifying the entity.

Planner automatically filters out non doable moves by calling the isMoveDoable(ScoreDirector) method on a move. A non doable move is:

In the n queens example, a move which moves the queen from its current row to the same row isn’t doable:

    public boolean isMoveDoable(ScoreDirector scoreDirector) {
        return !ObjectUtils.equals(queen.getRow(), toRow);
    }

Because we won’t generate a move which can move a queen outside the board limits, we don’t need to check it. A move that is currently not doable could become doable on the working Solution of a later step.

Each move has an undo move: a move (normally of the same type) which does the exact opposite. In the example above the undo move of C0 to C2 would be the move C2 to C0. An undo move is created from a Move, before the Move has been done on the current solution.

    public Move createUndoMove(ScoreDirector scoreDirector) {
        return new RowChangeMove(queen, queen.getRow());
    }

Notice that if C0 would have already been moved to C2, the undo move would create the move C2 to C2, instead of the move C2 to C0.

A solver phase might do and undo the same Move more than once. In fact, many solver phases will iteratively do and undo a number of moves to evaluate them, before selecting one of those and doing that move again (without undoing it this time).

A Move must implement the getPlanningEntities() and getPlanningValues() methods. They are used by entity tabu and value tabu respectively. When they are called, the Move has already been done.

    public List<? extends Object> getPlanningEntities() {
        return Collections.singletonList(queen);
    }

    public Collection<? extends Object> getPlanningValues() {
        return Collections.singletonList(toRow);
    }

If your Move changes multiple planning entities, return all of them in getPlanningEntities() and return all their values (to which they are changing) in getPlanningValues().

    public Collection<? extends Object> getPlanningEntities() {
        return Arrays.asList(leftCloudProcess, rightCloudProcess);
    }

    public Collection<? extends Object> getPlanningValues() {
        return Arrays.asList(leftCloudProcess.getComputer(), rightCloudProcess.getComputer());
    }

A Move must implement the equals() and hashCode() methods. 2 moves which make the same change on a solution, should be equal.

    public boolean equals(Object o) {
        if (this == o) {
            return true;
        } else if (o instanceof RowChangeMove) {
            RowChangeMove other = (RowChangeMove) o;
            return new EqualsBuilder()
                    .append(queen, other.queen)
                    .append(toRow, other.toRow)
                    .isEquals();
        } else {
            return false;
        }
    }

    public int hashCode() {
        return new HashCodeBuilder()
                .append(queen)
                .append(toRow)
                .toHashCode();
    }

Notice that it checks if the other move is an instance of the same move type. This instanceof check is important because a move will be compared to a move with another move type if you’re using more than 1 move type.

Implement the toString() method to keep Planner’s logs readable:

    public String toString() {
        return queen + " {" + queen.getRow() + " -> " + toRow + "}";
    }

Now that we can implement a single custom Move, let’s take a look at generating such custom moves.

The easiest way to generate custom moves is by implementing the interface MoveListFactory:

public interface MoveListFactory<S extends Solution> {

    List<Move> createMoveList(S solution);

}

For example:

public class RowChangeMoveFactory implements MoveListFactory<NQueens> {

    public List<Move> createMoveList(NQueens nQueens) {
        List<Move> moveList = new ArrayList<Move>();
        for (Queen queen : nQueens.getQueenList()) {
            for (Row toRow : nQueens.getRowList()) {
                moveList.add(new RowChangeMove(queen, toRow));
            }
        }
        return moveList;
    }

}

Simple configuration (which can be nested in a unionMoveSelector just like any other MoveSelector):

    <moveListFactory>
      <moveListFactoryClass>org.optaplanner.examples.nqueens.solver.move.factory.RowChangeMoveFactory</moveListFactoryClass>
    </moveListFactory>

Advanced configuration:

    <moveListFactory>
      ... <!-- Normal moveSelector properties -->
      <moveListFactoryClass>org.optaplanner.examples.nqueens.solver.move.factory.RowChangeMoveFactory</moveListFactoryClass>
    </moveListFactory>

Because the MoveListFactory generates all moves at once in a List<Move>, it does not support cacheType JUST_IN_TIME. Therefore, moveListFactory uses cacheType STEP by default and it scales badly in memory footprint.

Use this advanced form to generate custom moves by implementing the MoveIteratorFactory interface:

public interface MoveIteratorFactory {

    long getSize(ScoreDirector scoreDirector);

    Iterator<Move> createOriginalMoveIterator(ScoreDirector scoreDirector);

    Iterator<Move> createRandomMoveIterator(ScoreDirector scoreDirector, Random workingRandom);

}

The getSize() method must give an estimation of the size. It doesn’t need to be correct. The createOriginalMoveIterator method is called if the selectionOrder is ORIGINAL or if it is cached. The createRandomMoveIterator method is called for selectionOrder RANDOM combined with cacheType JUST_IN_TIME.

Simple configuration (which can be nested in a unionMoveSelector just like any other MoveSelector):

    <moveIteratorFactory>
      <moveIteratorFactoryClass>...</moveIteratorFactoryClass>
    </moveIteratorFactory>

Advanced configuration:

    <moveIteratorFactory>
      ... <!-- Normal moveSelector properties -->
      <moveIteratorFactoryClass>...</moveIteratorFactoryClass>
    </moveIteratorFactory>