public class MultiSwapNeighbourhood extends SubsetNeighbourhood
A subset neighbourhood that generates moves performing up to \(k\) simultaneous swaps of selected and
unselected IDs, where \(k\) is specified when creating the neighbourhood (or unlimited). 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.
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 1 or 2 simultaneous swaps already yields \[ s(n-s) + \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 desired 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 |
|---|
MultiSwapNeighbourhood()
Creates a multi swap neighbourhood that may perform an unlimited number of swaps.
|
MultiSwapNeighbourhood(int maxSwaps)
Creates a multi swap neighbourhood without fixed IDs, indicating the desired maximum number
of (simultaneous) swaps performed by any generated move.
|
MultiSwapNeighbourhood(int maxSwaps,
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 1 up to \(k\) swaps, where \(k\) is the maximum number
of swaps specified at construction.
|
int |
getMaxSwaps()
Get the maximum 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 IDs from the current selection
and replaces them with an equally large random subset of the currently unselected IDs.
|
getAddCandidates, getRemoveCandidatesclone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, waitgetRandomMovepublic MultiSwapNeighbourhood()
public MultiSwapNeighbourhood(int maxSwaps)
maxSwaps 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.maxSwaps - maximum number of swaps performed by any generated move (> 0)IllegalArgumentException - if maxSwaps is not strictly positivepublic MultiSwapNeighbourhood(int maxSwaps,
Set<Integer> fixedIDs)
maxSwaps pairs of IDs. If maxSwaps 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.maxSwaps - maximum number of swaps performed by any generated move (> 0)fixedIDs - set of fixed IDs which are not allowed to be swappedIllegalArgumentException - if maxSwaps is not strictly positivepublic int getMaxSwaps()
Integer.MAX_VALUE.public SubsetMove getRandomMove(SubsetSolution solution, Random rnd)
Generates a move for the given subset solution that removes a random subset of IDs from the current selection
and replaces them with an equally large random subset of the currently unselected IDs. Possible fixed IDs are
not considered to be swapped. The maximum number of swaps \(k\) specified at construction is respected. If
\(m < k\) IDs are currently selected or unselected (excluding any fixed IDs), generated moves will perform
up to \(m\) swaps only, as it is impossible to perform more than this amount of swaps. If no swaps can be
performed, null is returned.
Note that first, a random number of swaps is picked (uniformly distributed) from the valid range and then, a random subset of this size is sampled from the currently selected and unselected IDs, to be swapped (again, all possible subsets are uniformly distributed, within the fixed size). Because the amount of possible moves increases with the number of performed swaps, the probability of generating each specific move thus decreases with the number of swaps. In other words, randomly generated moves are not uniformly distributed across different numbers of performed swaps, but each specific move performing fewer swaps is more likely to be selected than each specific move performing more swaps.
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 1 up to \(k\) swaps, where \(k\) is the maximum 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), generated moves will perform up to \(m\) swaps only, as it is impossible to perform more than this amount of swaps.
May return an empty list if no swap moves can be generated.
solution - solution for which all possible multi swap moves are generatedCopyright © 2016. All rights reserved.