Move and neighborhood selection
1. Move and neighborhood introduction
1.1. What is a Move
?
A Move
is a change (or set of changes) from a solution A to a solution B.
For example, the move below changes queen C
from row 0
to row 2
:
The new solution is called a neighbor of the original solution, because it can be reached in a single Move
.
Although a single move can change multiple queens, the neighbors of a solution should always be a very small subset of all possible solutions.
For example, on that original solution, these are all possible changeMove
s:
If we ignore the four changeMove
s that have no impact and are therefore not doable, we can see that the number of moves is n * (n - 1) = 12
.
This is far less than the number of possible solutions, which is n ^ n = 256
.
As the problem scales out, the number of possible moves increases far less than the number of possible solutions.
Yet, in four changeMove
s or less we can reach any solution.
For example we can reach a very different solution in three changeMove
s:
There are many other types of moves besides A |
All optimization algorithms use Move
s to transition from one solution to a neighbor solution.
Therefore, all the optimization algorithms are confronted with Move
selection: the craft of creating and iterating moves efficiently and the art of finding the most promising subset of random moves to evaluate first.
1.2. What is a MoveSelector
?
A MoveSelector
's main function is to create Iterator[Move]
when needed.
An optimization algorithm will iterate through a subset of those moves.
Here’s an example how to configure a changeMoveSelector
for the optimization algorithm Local Search:
<localSearch>
<changeMoveSelector/>
...
</localSearch>
Out of the box, this works and all properties of the changeMoveSelector
are defaulted sensibly (unless that fails fast due to ambiguity). On the other hand, the configuration can be customized significantly for specific use cases.
For example: you might want to configure a filter to discard pointless moves.
1.3. Subselecting of entities, values, and other moves
To create a Move
, a MoveSelector
needs to select one or more planning entities and/or planning values to move.
Just like MoveSelector
s, EntitySelector
s and ValueSelector
s need to support a similar feature set (such as scalable just-in-time selection). Therefore, they all implement a common interface Selector
and they are configured similarly.
A MoveSelector is often composed out of EntitySelector
s, ValueSelector
s or even other MoveSelector
s, which can be configured individually if desired:
<unionMoveSelector>
<changeMoveSelector>
<entitySelector>
...
</entitySelector>
<valueSelector>
...
</valueSelector>
...
</changeMoveSelector>
<swapMoveSelector>
...
</swapMoveSelector>
</unionMoveSelector>
Together, this structure forms a Selector
tree:
The root of this tree is a MoveSelector
which is injected into the optimization algorithm implementation to be (partially) iterated in every step.
2. Generic MoveSelectors
2.1. Generic MoveSelectors
overview
Name | Description | __str__ example |
---|---|---|
Change 1 entity’s variable |
|
|
Swap all variables of 2 entities |
|
|
Change a set of entities with the same value |
|
|
Swap 2 sets of entities with the same values |
|
|
Swap 2 tails chains |
|
|
Cut a subchain and paste it into another chain |
|
|
Swap 2 subchains |
|
2.2. ChangeMoveSelector
For one planning variable, the ChangeMove
selects one planning entity and one 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 one 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">
...
<nearbySelection>...</nearbySelection>
</valueSelector>
</changeMoveSelector>
A ChangeMove
is the finest grained move.
Almost every |
This move selector only supports phase or solver caching if it doesn’t apply on a chained variable.
2.3. SwapMoveSelector
The SwapMove
selects two different planning entities and swaps the planning values of all their planning variables.
Although a SwapMove
on a single variable is essentially just two ChangeMove
s,
it’s often the winning step in cases that the first of the two ChangeMove
s would not win
because it leaves the solution in a state with broken hard constraints.
For example: swapping the room of two lectures doesn’t bring the solution in an 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>
<variableNameIncludes>
<variableNameInclude>room</variableNameInclude>
<variableNameInclude>...</variableNameInclude>
</variableNameIncludes>
</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.
This move selector only supports phase or solver caching if it doesn’t apply on any chained variables.
2.4. Pillar-based move selectors
A pillar is a set of planning entities which have the same planning value(s) for their planning variable(s).
2.4.1. PillarChangeMoveSelector
The PillarChangeMove
selects one entity pillar (or subset of those) and changes the value of one 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:
<pillarChangeMoveSelector>
<subPillarType>SEQUENCE</subPillarType>
... <!-- Normal selector properties -->
<pillarSelector>
<entitySelector>
<entityClass>...ShiftAssignment</entityClass>
...
</entitySelector>
<minimumSubPillarSize>1</minimumSubPillarSize>
<maximumSubPillarSize>1000</maximumSubPillarSize>
</pillarSelector>
<valueSelector variableName="room">
...
</valueSelector>
</pillarChangeMoveSelector>
For a description of subPillarType
and related properties, please refer to Subpillars.
The other properties are explained in changeMoveSelector. This move selector does not support phase or solver caching and step caching scales badly memory wise.
2.4.2. PillarSwapMoveSelector
The PillarSwapMove
selects two different entity pillars and swaps the values of all their variables for all their entities.
Simplest configuration:
<pillarSwapMoveSelector/>
Advanced configuration:
<pillarSwapMoveSelector>
<subPillarType>SEQUENCE</subPillarType>
... <!-- Normal selector properties -->
<pillarSelector>
<entitySelector>
<entityClass>...ShiftAssignment</entityClass>
...
</entitySelector>
<minimumSubPillarSize>1</minimumSubPillarSize>
<maximumSubPillarSize>1000</maximumSubPillarSize>
</pillarSelector>
<secondaryPillarSelector>
<entitySelector>
...
</entitySelector>
...
</secondaryPillarSelector>
<variableNameIncludes>
<variableNameInclude>employee</variableNameInclude>
<variableNameInclude>...</variableNameInclude>
</variableNameIncludes>
</pillarSwapMoveSelector>
For a description of subPillarType
and related properties, please refer to sub pillars.
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. This move selector does not support phase or solver caching and step caching scales badly memory wise.
2.4.3. Sub pillars
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.
There are several ways how sub pillars can be selected by the subPillarType
property:
-
ALL
(default) selects all possible sub pillars. -
SEQUENCE
limits selection of sub pillars to Sequential sub pillars. -
NONE
never selects any sub pillars.
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.
The number of sub pillars of a pillar is exponential to the size of the pillar.
For example a pillar of size 32 has |
Sequential sub pillars
Sub pillars can be sorted with a Comparator
. A sequential sub pillar is a continuous subset of its sorted base pillar.
For example if a nurse has shifts on Monday (M
), Tuesday (T
), and Wednesday (W
), they are a pillar and only the following are its sequential sub pillars: [M], [T], [W], [M, T], [T, W], [M, T, W]
.
But [M, W]
is not a sub pillar in this case, as there is a gap on Tuesday.
Sequential sub pillars apply to both Pillar change move and Pillar swap move. A minimal configuration looks like this:
<pillar...MoveSelector>
<subPillarType>SEQUENCE</subPillarType>
</pillar...MoveSelector>
In this case, the entity being operated on must implement the comparisons methods (__lt__
, __gt__
, etc). The size of sub pillars will not be limited in any way.
An advanced configuration looks like this:
<pillar...MoveSelector>
...
<subPillarType>SEQUENCE</subPillarType>
<pillarSelector>
...
<minimumSubPillarSize>1</minimumSubPillarSize>
<maximumSubPillarSize>1000</maximumSubPillarSize>
</pillarSelector>
...
</pillar...MoveSelector>
The size of the sub pillars is limited in length of up to 1000 entities.
2.5. Move selectors for chained variables
2.5.1. TailChainSwapMoveSelector
or 2-opt
A tailChain is a set of planning entities with a chained planning variable which form the 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:
<tailChainSwapMoveSelector>
... <!-- Normal selector properties -->
<entitySelector>
<entityClass>...Customer</entityClass>
...
</entitySelector>
<valueSelector variableName="previousStandstill">
...
<nearbySelection>...</nearbySelection>
</valueSelector>
</tailChainSwapMoveSelector>
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).
Although |
This move selector does not support phase or solver caching.
2.5.2. SubChainChangeMoveSelector
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">
...
</valueSelector>
<minimumSubChainSize>2</minimumSubChainSize>
<maximumSubChainSize>40</maximumSubChainSize>
</subChainSelector>
<valueSelector variableName="previousStandstill">
...
</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
).
If Furthermore, in a |
The selectReversingMoveToo
property (defaults to true) enables selecting the reverse of every subchain too.
This move selector does not support phase or solver caching and step caching scales badly memory wise.
2.5.3. SubChainSwapMoveSelector
The subChainSwapMoveSelector
selects two 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">
...
</valueSelector>
<minimumSubChainSize>2</minimumSubChainSize>
<maximumSubChainSize>40</maximumSubChainSize>
</subChainSelector>
<secondarySubChainSelector>
<valueSelector variableName="previousStandstill">
...
</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. This move selector does not support phase or solver caching and step caching scales badly memory wise.
3. Combining multiple MoveSelector
s
3.1. unionMoveSelector
A unionMoveSelector
selects a Move
by selecting one of its MoveSelector
children to supply the next Move
.
Simplest configuration:
<unionMoveSelector>
<...MoveSelector/>
<...MoveSelector/>
<...MoveSelector/>
...
</unionMoveSelector>
Advanced configuration:
<unionMoveSelector>
... <!-- Normal selector properties -->
<changeMoveSelector>
<fixedProbabilityWeight>...</fixedProbabilityWeight>
...
</changeMoveSelector>
<swapMoveSelector>
<fixedProbabilityWeight>...</fixedProbabilityWeight>
...
</swapMoveSelector>
<...MoveSelector>
<fixedProbabilityWeight>...</fixedProbabilityWeight>
...
</...MoveSelector>
...
<selectorProbabilityWeightFactoryClass>...ProbabilityWeightFactory</selectorProbabilityWeightFactoryClass>
</unionMoveSelector>
The selectorProbabilityWeightFactory
determines in selectionOrder
RANDOM
how often a MoveSelector
child is selected to supply the next Move.
By default, each MoveSelector
child has the same chance of being selected.
Custom selectorProbabilityWeightFactory
functions are currently not supported in OptaPy.
Change the fixedProbabilityWeight
of such a child to select it more often.
For example, the unionMoveSelector
can return a SwapMove
twice as often as a ChangeMove
:
<unionMoveSelector>
<changeMoveSelector>
<fixedProbabilityWeight>1.0</fixedProbabilityWeight>
...
</changeMoveSelector>
<swapMoveSelector>
<fixedProbabilityWeight>2.0</fixedProbabilityWeight>
...
</swapMoveSelector>
</unionMoveSelector>
The number of possible ChangeMove
s is very different from the number of possible SwapMove
s and furthermore it’s problem dependent.
To give each individual Move
the same selection chance (as opposed to each MoveSelector
), use the FairSelectorProbabilityWeightFactory
:
<unionMoveSelector>
<changeMoveSelector/>
<swapMoveSelector/>
<selectorProbabilityWeightFactoryClass>org.optaplanner.core.impl.heuristic.selector.common.decorator.FairSelectorProbabilityWeightFactory</selectorProbabilityWeightFactoryClass>
</unionMoveSelector>
3.2. cartesianProductMoveSelector
A cartesianProductMoveSelector
selects a new CompositeMove
.
It builds that CompositeMove
by selecting one Move
per MoveSelector
child and adding it to the CompositeMove
.
Simplest configuration:
<cartesianProductMoveSelector>
<...MoveSelector/>
<...MoveSelector/>
<...MoveSelector/>
...
</cartesianProductMoveSelector>
Advanced configuration:
<cartesianProductMoveSelector>
... <!-- Normal selector properties -->
<changeMoveSelector>
...
</changeMoveSelector>
<swapMoveSelector>
...
</swapMoveSelector>
<...MoveSelector>
...
</...MoveSelector>
...
<ignoreEmptyChildIterators>true</ignoreEmptyChildIterators>
</cartesianProductMoveSelector>
The ignoreEmptyChildIterators
property (true by default) will ignore every empty childMoveSelector
to avoid returning no moves.
For example: a cartesian product of changeMoveSelector
A and B, for which B is empty (because all it’s entities are pinned) returns no move if ignoreEmptyChildIterators
is false
and the moves of A if ignoreEmptyChildIterators
is true
.
To enforce that two child selectors use the same entity or value efficiently, use mimic selection, not move filtering.
4. EntitySelector
Simplest configuration:
<entitySelector/>
Advanced configuration:
<entitySelector>
... <!-- Normal selector properties -->
<entityClass>optapy.examples.curriculumcourse.domain.Lecture</entityClass>
</entitySelector>
The entityClass
property is only required if it cannot be deduced automatically because there are multiple entity classes.
5. ValueSelector
Simplest configuration:
<valueSelector/>
Advanced configuration:
<valueSelector variableName="room">
... <!-- Normal selector properties -->
</valueSelector>
The variableName
property is only required if it cannot be deduced automatically because there are multiple variables (for the related entity class).
In exotic Construction Heuristic configurations, the entityClass
from the EntitySelector
sometimes needs to be downcasted, which can be done with the property downcastEntityClass
:
<valueSelector variableName="period">
<downcastEntityClass>...LeadingExam</downcastEntityClass>
</valueSelector>
If a selected entity cannot be downcasted, the ValueSelector
is empty for that entity.
6. General Selector
features
6.1. CacheType
: create moves ahead of time or just in time
A Selector
's cacheType
determines when a selection (such as a Move
, an entity, a value, …)
is created and how long it lives.
Almost every Selector
supports setting a cacheType
:
<changeMoveSelector>
<cacheType>PHASE</cacheType>
...
</changeMoveSelector>
The following cacheType
s are supported:
-
JUST_IN_TIME
(default, recommended): Not cached. Construct each selection (Move
, …) just before it’s used. This scales up well in memory footprint. -
STEP
: Cached. Create each selection (Move
, …) at the beginning of a step and cache them in a list for the remainder of the step. This scales up badly in memory footprint. -
PHASE
: Cached. Create each selection (Move
, …) at the beginning of a solver phase and cache them in a list for the remainder of the phase. Some selections cannot be phase cached because the list changes every step. This scales up badly in memory footprint, but has a slight performance gain. -
SOLVER
: Cached. Create each selection (Move
, …) at the beginning of aSolver
and cache them in a list for the remainder of theSolver
. Some selections cannot be solver cached because the list changes every step. This scales up badly in memory footprint, but has a slight performance gain.
A cacheType
can be set on composite selectors too:
<unionMoveSelector>
<cacheType>PHASE</cacheType>
<changeMoveSelector/>
<swapMoveSelector/>
...
</unionMoveSelector>
Nested selectors of a cached selector cannot be configured to be cached themselves, unless it’s a higher cacheType
.
For example: a STEP
cached unionMoveSelector
can contain a PHASE
cached changeMoveSelector
,
but it cannot contain a STEP
cached changeMoveSelector
.
6.2. SelectionOrder
: original, sorted, random, shuffled, or probabilistic
A Selector
's selectionOrder
determines the order in which the selections (such as Move
s, entities, values, …) are iterated.
An optimization algorithm will usually only iterate through a subset of its MoveSelector
's selections, starting from the start, so the selectionOrder
is critical to decide which Move
s are actually evaluated.
Almost every Selector
supports setting a selectionOrder
:
<changeMoveSelector>
...
<selectionOrder>RANDOM</selectionOrder>
...
</changeMoveSelector>
The following selectionOrder
s are supported:
-
ORIGINAL
: Select the selections (Move
s, entities, values, …) in default order. Each selection will be selected only once.-
For example: A0, A1, A2, A3, …, B0, B1, B2, B3, …, C0, C1, C2, C3, …
-
-
SORTED: Select the selections (
Move
s, entities, values, …) in sorted order. Each selection will be selected only once. RequirescacheType >= STEP
. Mostly used on anentitySelector
orvalueSelector
for construction heuristics. See sorted selection.-
For example: A0, B0, C0, …, A2, B2, C2, …, A1, B1, C1, …
-
-
RANDOM (default): Select the selections (
Move
s, entities, values, …) in non-shuffled random order. A selection might be selected multiple times. This scales up well in performance because it does not require caching.-
For example: C2, A3, B1, C2, A0, C0, …
-
-
SHUFFLED: Select the selections (
Move
s, entities, values, …) in shuffled random order. Each selection will be selected only once. RequirescacheType >= STEP
. This scales up badly in performance, not just because it requires caching, but also because a random number is generated for each element, even if it’s not selected (which is the grand majority when scaling up).-
For example: C2, A3, B1, A0, C0, …
-
-
PROBABILISTIC: Select the selections (
Move
s, entities, values, …) in random order, based on the selection probability of each element. A selection with a higher probability has a higher chance to be selected than elements with a lower probability. A selection might be selected multiple times. RequirescacheType >= STEP
. Mostly used on anentitySelector
orvalueSelector
. See probabilistic selection.-
For example: B1, B1, A1, B2, B1, C2, B1, B1, …
-
A selectionOrder
can be set on composite selectors too.
When a |
6.3. Recommended combinations of CacheType
and SelectionOrder
6.3.1. Just in time random selection (default)
This combination is great for big use cases (10 000 entities or more), as it scales up well in memory footprint and performance.
Other combinations are often not even viable on such sizes.
It works for smaller use cases too, so it’s a good way to start out.
It’s the default, so this explicit configuration of cacheType
and selectionOrder
is actually obsolete:
<unionMoveSelector>
<cacheType>JUST_IN_TIME</cacheType>
<selectionOrder>RANDOM</selectionOrder>
<changeMoveSelector/>
<swapMoveSelector/>
</unionMoveSelector>
Here’s how it works.
When the root MoveSelector
yields a value, a child MoveSelector
is randomly selected (1), which creates a random Move
(2, 3, 4) and is then returned (5):
Notice that it never creates a list of Move
s and it generates random numbers only for Move
s that are actually selected.
6.3.2. Cached shuffled selection
This combination often wins for small use cases (1000 entities or less). Beyond that size, it scales up badly in memory footprint and performance.
<unionMoveSelector>
<cacheType>PHASE</cacheType>
<selectionOrder>SHUFFLED</selectionOrder>
<changeMoveSelector/>
<swapMoveSelector/>
</unionMoveSelector>
Here’s how it works: At the start of the phase (or step depending on the cacheType
), all moves are created (1) and cached (2). When the root MoveSelector
is created, the moves are shuffled (3). When the root MoveSelector
yields a value, the next element in the shuffled list is returned (4):
Notice that each Move will only be selected once, even though they are selected in random order.
Use cacheType PHASE if none of the (possibly nested) Selectors require STEP
.
Otherwise, do something like this:
<unionMoveSelector>
<cacheType>STEP</cacheType>
<selectionOrder>SHUFFLED</selectionOrder>
<changeMoveSelector>
<cacheType>PHASE</cacheType>
</changeMoveSelector>
<swapMoveSelector>
<cacheType>PHASE</cacheType>
</swapMoveSelector>
<pillarSwapMoveSelector/><!-- Does not support cacheType PHASE -->
</unionMoveSelector>
6.3.3. Cached random selection
This combination is often a worthy competitor for medium use cases, especially with fast stepping optimization algorithms (such as Simulated Annealing). Unlike cached shuffled selection, it doesn’t waste time shuffling the moves list at the beginning of every step.
<unionMoveSelector>
<cacheType>PHASE</cacheType>
<selectionOrder>RANDOM</selectionOrder>
<changeMoveSelector/>
<swapMoveSelector/>
</unionMoveSelector>
6.4. Filtered selection
OptaPy currently does not support filtered selection, but will in a future version.
6.4.1. Filtered move selection
OptaPy currently does not support filtered move selection, but will in a future version.
6.5. Sorted selection
Sorted selection can happen on any Selector in the selector tree, including any MoveSelector
, EntitySelector
or ValueSelector
.
It does not work with cacheType
JUST_IN_TIME
and it only works with selectionOrder
SORTED
.
It’s mostly used in construction heuristics.
If the chosen construction heuristic implies sorting, for example |
6.5.1. Sorted selection by SorterManner
Some Selector
types implement a SorterManner
out of the box:
-
EntitySelector
supports:-
DECREASING_DIFFICULTY
: Sorts the planning entities according to decreasing planning entity difficulty. Requires that planning entity difficulty is annotated on the domain model.<entitySelector> <cacheType>PHASE</cacheType> <selectionOrder>SORTED</selectionOrder> <sorterManner>DECREASING_DIFFICULTY</sorterManner> </entitySelector>
-
-
ValueSelector
supports:-
INCREASING_STRENGTH
: Sorts the planning values according to increasing planning value strength. Requires that planning value strength is annotated on the domain model.<valueSelector> <cacheType>PHASE</cacheType> <selectionOrder>SORTED</selectionOrder> <sorterManner>INCREASING_STRENGTH</sorterManner> </valueSelector>
-
6.5.2. Sorted selection by comparison function
OptaPy currently does not support sorted selection by comparison function, but will in a future version.
6.6. Probabilistic selection
OptaPy currently does not support custom probabilistic selection, but will in a future version.
6.7. Limited selection
Selecting all possible moves sometimes does not scale well enough, especially for construction heuristics (which don’t support acceptedCountLimit).
To limit the number of selected selection per step, apply a selectedCountLimit
on the selector:
<changeMoveSelector>
<selectedCountLimit>100</selectedCountLimit>
</changeMoveSelector>
To scale Local Search, setting acceptedCountLimit is usually better than using |
6.8. Mimic selection (record/replay)
During mimic selection, one normal selector records its selection and one or multiple other special selectors replay that selection. The recording selector acts as a normal selector and supports all other configuration properties. A replaying selector mimics the recording selection and supports no other configuration properties.
The recording selector needs an id
.
A replaying selector must reference a recorder’s id with a mimicSelectorRef
:
<cartesianProductMoveSelector>
<changeMoveSelector>
<entitySelector id="entitySelector"/>
<valueSelector variableName="period"/>
</changeMoveSelector>
<changeMoveSelector>
<entitySelector mimicSelectorRef="entitySelector"/>
<valueSelector variableName="room"/>
</changeMoveSelector>
</cartesianProductMoveSelector>
Mimic selection is useful to create a composite move from two moves that affect the same entity.