public class SinglePerturbationNeighbourhood extends SubsetNeighbourhood
A subset neighbourhood that generates swap moves (see SwapMove), addition moves (see AdditionMove)
and deletion moves (see DeletionMove). All three generated move types are subtypes of SubsetMove.
Applying an addition or deletion move to a given subset solution will increase, respectively decrease, the number
of selected items. Therefore, this neighbourhood is also suited for variable size subset selection problems, in
contrast to a SingleSwapNeighbourhood.
When sampling random moves from this neighbourhood, every individual move is generated with equal probability, taking into account the different number of possible moves of each type. In general this means that more swap moves will be generated because there are usually more possible swaps compared to deletions or additions. If it is desired to change this behaviour, take a look at the composite neighbourhood which is provided in the extensions module and allows to combine any set of neighbourhoods with custom weights.
A single perturbation neighbourhood respects the optional minimum and maximum subset size specified at construction. When the given subset solution has minimal size, no deletion moves will be generated. Similarly, when the current solution has maximum size, no addition moves will be generated.
If desired, a set of fixed IDs can be provided which are not allowed to be added, deleted nor swapped. None of the moves generated by this neighbourhood will ever select nor deselect any of these fixed IDs.
Note that this neighbourhood is thread-safe: it can be safely used to concurrently generate moves in different searches running in separate threads.
| Constructor and Description |
|---|
SinglePerturbationNeighbourhood()
Creates a new single perturbation neighbourhood without size limits.
|
SinglePerturbationNeighbourhood(int minSubsetSize,
int maxSubsetSize)
Creates a new single perturbation neighbourhood with given minimum and maximum subset size.
|
SinglePerturbationNeighbourhood(int minSubsetSize,
int maxSubsetSize,
Set<Integer> fixedIDs)
Creates a new single perturbation neighbourhood with given minimum and maximum subset size,
providing a set of fixed IDs which are not allowed to be added, deleted nor swapped.
|
| Modifier and Type | Method and Description |
|---|---|
List<SubsetMove> |
getAllMoves(SubsetSolution solution)
Generate all valid swap, deletion and addition moves that transform the given subset solution into
a neighbour within the minimum and maximum allowed subset size.
|
int |
getMaxSubsetSize()
Get the maximum subset size specified at construction.
|
int |
getMinSubsetSize()
Get the minimum subset size specified at construction.
|
SubsetMove |
getRandomMove(SubsetSolution solution,
Random rnd)
Generates a random swap, deletion or addition move that transforms the given subset solution into
a neighbour within the minimum and maximum allowed subset size.
|
getAddCandidates, getRemoveCandidatesclone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, waitgetRandomMovepublic SinglePerturbationNeighbourhood()
public SinglePerturbationNeighbourhood(int minSubsetSize,
int maxSubsetSize)
minSubsetSize - minimum subset size (≥ 0)maxSubsetSize - maximum subset size (> 0)IllegalArgumentException - if minimum size is not positive, maximum size is not strictly
positive, or minimum > maximumpublic SinglePerturbationNeighbourhood(int minSubsetSize,
int maxSubsetSize,
Set<Integer> fixedIDs)
minSubsetSize - minimum subset size (≥ 0)maxSubsetSize - maximum subset size (> 0)fixedIDs - set of fixed IDsIllegalArgumentException - if minimum size is not positive, maximum size is not strictly
positive, or minimum > maximumpublic SubsetMove getRandomMove(SubsetSolution solution, Random rnd)
Generates a random swap, deletion or addition move that transforms the given subset solution into
a neighbour within the minimum and maximum allowed subset size. If no valid move can be generated,
null is returned. If any fixed IDs have been specified, these will not be considered
for deletion nor addition.
Note that every individual move is generated with equal probability, taking into account the different number of possible moves of each type.
solution - solution for which a random move is generatedrnd - source of randomness used to generate random movenull if no valid move can be generatedpublic List<SubsetMove> getAllMoves(SubsetSolution solution)
solution - solution for which a set of all valid moves is generatedpublic int getMinSubsetSize()
public int getMaxSubsetSize()
Integer.MAX_VALUE.Copyright © 2016. All rights reserved.