public class DisjointMultiSwapNeighbourhood extends SubsetNeighbourhood
A subset neighbourhood that generates moves performing a fixed number of simultaneous swaps of selected and
unselected IDs. Generated moves are of type GeneralSubsetMove
which is a subtype of SubsetMove
.
When applying moves generated by this neighbourhood to a given subset solution, the set of selected IDs will
always remain of the same size. Therefore, this neighbourhood is only suited for fixed size subset selection
problems. If desired, a set of fixed IDs can be provided which are not allowed to be swapped.
If it happens to be impossible to perform the desired number of swaps (e.g. because the current selection is too small or too large) a lower, maximum number of swaps will be performed.
Note that the number of possible moves quickly becomes very large when the size of the full set and/or selected subset increase. For example, generating all combinations of 2 simultaneous swaps already yields \[ \frac{s(s-1)}{2} \times \frac{(n-s)(n-s-1)}{2} \] possibilities, where \(n\) is the size of the full set and \(s\) is the subset size. When selecting e.g. 30 out of 100 items, this value already exceeds one million. Because of the large number of possible moves, this advanced neighbourhood should be used with care, especially in combination with searches that inspect all moves in every step. Furthermore, searches that inspect random moves may have few chances to find an improvement in case of a huge amount of possible neighbours.
This neighbourhood is thread-safe: it can be safely used to concurrently generate moves in different searches running in separate threads.
Constructor and Description |
---|
DisjointMultiSwapNeighbourhood(int numSwaps)
Creates a multi swap neighbourhood without fixed IDs, indicating the number of (simultaneous)
swaps performed by any generated move.
|
DisjointMultiSwapNeighbourhood(int numSwaps,
Set<Integer> fixedIDs)
Creates a multi swap neighbourhood with a given set of fixed IDs which are not allowed to be swapped.
|
Modifier and Type | Method and Description |
---|---|
List<SubsetMove> |
getAllMoves(SubsetSolution solution)
Generates the list of all possible moves that perform exactly \(k\) swaps, where \(k\) is the desired number
of swaps specified at construction.
|
int |
getNumSwaps()
Get the fixed number of swaps performed by generated moves.
|
SubsetMove |
getRandomMove(SubsetSolution solution,
Random rnd)
Generates a move for the given subset solution that removes a random subset of \(k\) IDs from the current
selection and replaces them with an equally large random subset of the currently unselected IDs, where
\(k\) is the number of swaps specified at construction.
|
getAddCandidates, getRemoveCandidates
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
getRandomMove
public DisjointMultiSwapNeighbourhood(int numSwaps)
numSwaps
is 1, this neighbourhood
generates exactly the same moves as the SingleSwapNeighbourhood
so in such case
it is advised to use the latter neighbourhood which has been optimized for this specific
scenario.numSwaps
- number of swaps performed by any generated move (> 0)IllegalArgumentException
- if maxSwaps
is not strictly positivepublic DisjointMultiSwapNeighbourhood(int numSwaps, Set<Integer> fixedIDs)
numSwaps
pairs of IDs. If numSwaps
is 1, this neighbourhood generates
exactly the same moves as the SingleSwapNeighbourhood
so in such case it is advised
to use the latter neighbourhood which has been optimized for this specific scenario.numSwaps
- number of swaps performed by any generated move (> 0)fixedIDs
- set of fixed IDs which are not allowed to be swappedIllegalArgumentException
- if numSwaps
is not strictly positivepublic int getNumSwaps()
public SubsetMove getRandomMove(SubsetSolution solution, Random rnd)
null
is returned.solution
- solution for which a random multi swap move is generatedrnd
- source of randomness used to generate random movenull
if no swaps can be performedpublic List<SubsetMove> getAllMoves(SubsetSolution solution)
Generates the list of all possible moves that perform exactly \(k\) swaps, where \(k\) is the desired number of swaps specified at construction. Possible fixed IDs are not considered to be swapped. If \(m < k\) IDs are currently selected or unselected (excluding any fixed IDs), no swaps can be performed and the returned list will be empty.
solution
- solution for which all possible multi swap moves are generatedCopyright © 2016. All rights reserved.