Show Table of Contents
7.2.1.
7.2. Generic MoveSelectors
7.2.1. changeMoveSelector
For 1 planning variable, the
ChangeMove selects 1 planning entity and 1 planning value and assigns the entity's variable to that value.
Simplest configuration:
<changeMoveSelector/>
If there are multiple entity classes or multiple planning variables for 1 entity class, a simple configuration will automatically unfold into a union of
ChangeMove selectors for every planning variable.
Advanced configuration:
<changeMoveSelector>
... <!-- Normal selector properties -->
<entitySelector>
<entityClass>...Lecture</entityClass>
...
</entitySelector>
<valueSelector>
<variableName>room</variableName>
...
<nearbySelection>...</nearbySelection>
</valueSelector>
</changeMoveSelector>
A
ChangeMove is the finest grained move.
Important
Almost every
moveSelector configuration injected into a metaheuristic algorithm should include a changeMoveSelector or a custom implementation. This guarantees that every possible Solution can be reached through applying a number of moves in sequence (not taking score traps into account). Of course, normally it is unioned with other, more coarse grained move selectors.
7.2.2. swapMoveSelector
The
SwapMove selects 2 different planning entities and swaps the planning values of all their planning variables.
Although a
SwapMove on a single variable is essentially just 2 ChangeMoves, it's often the winning step where the first of the 2 ChangeMoves would not be the winning step because it leaves the solution in a state with broken hard constraints. For example: swapping the room of 2 lectures doesn't bring the solution in a intermediate state where both lectures are in the same room which breaks a hard constraint.
Simplest configuration:
<swapMoveSelector/>
If there are multiple entity classes, a simple configuration will automatically unfold into a union of
SwapMove selectors for every entity class.
Advanced configuration:
<swapMoveSelector>
... <!-- Normal selector properties -->
<entitySelector>
<entityClass>...Lecture</entityClass>
...
</entitySelector>
<secondaryEntitySelector>
<entityClass>...Lecture</entityClass>
...
<nearbySelection>...</nearbySelection>
</secondaryEntitySelector>
<variableNameInclude>room</variableNameInclude>
<variableNameInclude>...</variableNameInclude>
</swapMoveSelector>
The
secondaryEntitySelector is rarely needed: if it is not specified, entities from the same entitySelector are swapped.
If one or more
variableNameInclude properties are specified, not all planning variables will be swapped, but only those specified. For example for course scheduling, specifying only variableNameInclude room will make it only swap room, not period.
7.2.3. pillarChangeMoveSelector
A pillar is a set of planning entities which have the same planning value(s) for their planning variable(s). The
PillarChangeMove selects 1 entity pillar (or subset of those) and changes the value of 1 variable (which is the same for all entities) to another value.
In the example above, queen A and C have the same value (row 0) and are moved to row 2. Also the yellow and blue process have the same value (computer Y) and are moved to computer X.
Simplest configuration:
<pillarChangeMoveSelector/>
Advanced configuration:
<pillarSwapMoveSelector>
... <!-- Normal selector properties -->
<pillarSelector>
<entitySelector>
<entityClass>...Lecture</entityClass>
...
</entitySelector>
<subPillarEnabled>true</subPillarEnabled>
<minimumSubPillarSize>1</minimumSubPillarSize>
<maximumSubPillarSize>1000</maximumSubPillarSize>
</pillarSelector>
<valueSelector>
<variableName>room</variableName>
...
</valueSelector>
</pillarSwapMoveSelector>
A sub pillar is a subset of entities that share the same value(s) for their variable(s). For example if queen A, B, C and D are all located on row 0, they are a pillar and
[A, D] is one of the many sub pillars. If subPillarEnabled (defaults to true) is false, no sub pillars are selected. If sub pillars are enabled, the pillar itself is also included and the properties minimumSubPillarSize (defaults to 1) and maximumSubPillarSize (defaults to infinity) limit the size of the selected (sub) pillar.
Note
The number of sub pillars of a pillar is exponential to the size of the pillar. For example a pillar of size 32 has
(2^32 - 1) subpillars. Therefore a pillarSelector only supports JIT random selection (which is the default).
The other properties are explained in changeMoveSelector.
7.2.4. pillarSwapMoveSelector
A pillar is a set of planning entities which have the same planning value(s) for their planning variable(s). The
PillarSwapMove selects 2 different entity pillars and swaps the values of all their variables for all their entities.
Simplest configuration:
<pillarSwapMoveSelector/>
Advanced configuration:
<pillarSwapMoveSelector>
... <!-- Normal selector properties -->
<pillarSelector>
<entitySelector>
<entityClass>...Lecture</entityClass>
...
</entitySelector>
<subPillarEnabled>true</subPillarEnabled>
<minimumSubPillarSize>1</minimumSubPillarSize>
<maximumSubPillarSize>1000</maximumSubPillarSize>
</pillarSelector>
<secondaryPillarSelector>
<entitySelector>
...
</entitySelector>
...
</secondaryPillarSelector>
<variableNameInclude>room</variableNameInclude>
<variableNameInclude>...</variableNameInclude>
</pillarSwapMoveSelector>
The
secondaryPillarSelector is rarely needed: if it is not specified, entities from the same pillarSelector are swapped.
The other properties are explained in swapMoveSelector and pillarChangeMoveSelector.
7.2.5. tailChainSwapMoveSelector or 2-opt (chained variables only)
A tailChain is a set of planning entities with a chained planning variable which form a last part of a chain. The
tailChainSwapMove selects a tail chain and swaps it with the tail chain of another planning value (in a different or the same anchor chain). If the targeted planning value, doesn't have a tail chain, it swaps with nothing (resulting in a change like move). If it occurs within the same anchor chain, a partial chain reverse occurs. In academic papers, this is often called a 2-opt move.
Simplest configuration:
<tailChainSwapMoveSelector/>
Advanced configuration:
<subChainChangeMoveSelector>
... <!-- Normal selector properties -->
<entitySelector>
<entityClass>...Customer</entityClass>
...
</entitySelector>
<valueSelector>
<variableName>previousStandstill</variableName>
...
<nearbySelection>...</nearbySelection>
</valueSelector>
</subChainChangeMoveSelector>
The
entitySelector selects the start of the tail chain that is being moved. The valueSelector selects to where that tail chain is moved. If it has a tail chain itself, that is moved to the location of the original tail chain. It uses a valueSelector instead of a secondaryEntitySelector to be able to include all possible 2opt moves (such as moving to the end of a tail) and to work correctly with nearby selection (because of asymmetric distances and also swapped entity distance gives an incorrect selection probability).
Note
Although
subChainChangeMoveSelector and subChainSwapMoveSelector include almost every possible tailChainSwapMove, experiments have shown that focusing on tailChainSwapMoves increases efficiency.
7.2.6. subChainChangeMoveSelector (chained variables only)
A subChain is a set of planning entities with a chained planning variable which form part of a chain. The
subChainChangeMoveSelector selects a subChain and moves it to another place (in a different or the same anchor chain).
Simplest configuration:
<subChainChangeMoveSelector/>
Advanced configuration:
<subChainChangeMoveSelector>
... <!-- Normal selector properties -->
<entityClass>...Customer</entityClass>
<subChainSelector>
<valueSelector>
<variableName>previousStandstill</variableName>
...
</valueSelector>
<minimumSubChainSize>2</minimumSubChainSize>
<maximumSubChainSize>40</maximumSubChainSize>
</subChainSelector>
<valueSelector>
<variableName>previousStandstill</variableName>
...
</valueSelector>
<selectReversingMoveToo>true</selectReversingMoveToo>
</subChainChangeMoveSelector>
The
subChainSelector selects a number of entities, no less than minimumSubChainSize (defaults to 1) and no more than maximumSubChainSize (defaults to infinity).
Note
If
minimumSubChainSize is 1 (which is the default), this selector might select the same move as a ChangeMoveSelector, at a far lower selection probability (because each move type has the same selection chance by default (not every move instance) and there are far more SubChainChangeMove instances than ChangeMove instances). However, don't just remove the ChangeMoveSelector, because experiments show that it's good to focus on ChangeMoves.
Furthermore, in a
SubChainSwapMoveSelector, setting minimumSubChainSize prevents swapping a subchain of size 1 with a subchain of at least size 2.
The
selectReversingMoveToo property (defaults to true) enables selecting the reverse of every subchain too.
7.2.7. subChainSwapMoveSelector (chained variables only)
The
subChainSwapMoveSelector selects 2 different subChains and moves them to another place in a different or the same anchor chain.
Simplest configuration:
<subChainSwapMoveSelector/>
Advanced configuration:
<subChainSwapMoveSelector>
... <!-- Normal selector properties -->
<entityClass>...Customer</entityClass>
<subChainSelector>
<valueSelector>
<variableName>previousStandstill</variableName>
...
</valueSelector>
<minimumSubChainSize>2</minimumSubChainSize>
<maximumSubChainSize>40</maximumSubChainSize>
</subChainSelector>
<secondarySubChainSelector>
<valueSelector>
<variableName>previousStandstill</variableName>
...
</valueSelector>
<minimumSubChainSize>2</minimumSubChainSize>
<maximumSubChainSize>40</maximumSubChainSize>
</secondarySubChainSelector>
<selectReversingMoveToo>true</selectReversingMoveToo>
</subChainSwapMoveSelector>
The
secondarySubChainSelector is rarely needed: if it is not specified, entities from the same subChainSelector are swapped.
The other properties are explained in subChainChangeMoveSelector.
Where did the comment section go?
Red Hat's documentation publication system recently went through an upgrade to enable speedier, more mobile-friendly content. We decided to re-evaluate our commenting platform to ensure that it meets your expectations and serves as an optimal feedback mechanism. During this redesign, we invite your input on providing feedback on Red Hat documentation via the discussion platform.