public class MultiDeletionNeighbourhood extends SubsetNeighbourhood
A subset neighbourhood that generates moves which simultaneously remove up to \(k\) items from the selection,
where \(k\) is specified at construction (or unlimited). Generated moves are of type GeneralSubsetMove
,
which is a subtype of SubsetMove
, and always only remove IDs from the selection. If desired, a set of
fixed IDs can be provided which are not allowed to be removed. Also, a minimum size can be imposed so that
it is guaranteed that the subset size will not drop below this minimum after application of a move generated
by this neighbourhood.
Note that a very large amount of moves may be generated when the subset size increases. Therefore, 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 |
---|
MultiDeletionNeighbourhood()
Creates a multi deletion neighbourhood that may remove an unlimited number of IDs from the selection.
|
MultiDeletionNeighbourhood(int maxDeletions)
Creates a multi deletion neighbourhood that may simultaneously remove up to the specified number of
IDs from the selection.
|
MultiDeletionNeighbourhood(int maxDeletions,
int minSubsetSize)
Creates a multi deletion neighbourhood that may simultaneously remove up to the specified number of
IDs from the selection, taking into account that the subset size may not drop below the given minimum.
|
MultiDeletionNeighbourhood(int maxDeletions,
int minSubsetSize,
Set<Integer> fixedIDs)
Creates a multi deletion neighbourhood that may simultaneously remove up to the specified number of
IDs from the selection, taking into account that the subset size may not drop below the given minimum
and that the given set of fixed IDs are not allowed to be deselected.
|
Modifier and Type | Method and Description |
---|---|
List<SubsetMove> |
getAllMoves(SubsetSolution solution)
Generates the list of all possible moves that perform 1 up to \(k\) deletions, where \(k\) is the maximum number
of deletions specified at construction.
|
int |
getMaxDeletions()
Get the maximum number of deletions performed by generated moves.
|
int |
getMinSubsetSize()
Get the minimum subset size specified at construction.
|
SubsetMove |
getRandomMove(SubsetSolution solution,
Random rnd)
Generates a move for the given subset solution that deselects a random subset of currently selected IDs.
|
getAddCandidates, getRemoveCandidates
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
getRandomMove
public MultiDeletionNeighbourhood()
public MultiDeletionNeighbourhood(int maxDeletions)
maxDeletions
is 1, this neighbourhood generates exactly the
same moves as the SingleDeletionNeighbourhood
so in such case it is advised to use the latter
neighbourhood which has been optimized for this specific scenario.maxDeletions
- maximum number of removed IDs (> 0)IllegalArgumentException
- if maxDeletions
is not strictly positivepublic MultiDeletionNeighbourhood(int maxDeletions, int minSubsetSize)
maxDeletions
is 1, this neighbourhood generates exactly the same moves as the
SingleDeletionNeighbourhood
so in such case it is advised to use the latter neighbourhood
which has been optimized for this specific scenario.maxDeletions
- maximum number of removed IDs (> 0)minSubsetSize
- minimum subset size (≥ 0)IllegalArgumentException
- if maxDeletions
is not strictly positive
or minSubsetSize
is negativepublic MultiDeletionNeighbourhood(int maxDeletions, int minSubsetSize, Set<Integer> fixedIDs)
maxDeletions
is 1, this neighbourhood generates exactly the same moves as the SingleDeletionNeighbourhood
so in such case it is advised to use the latter neighbourhood which has been optimized for this
specific scenario.maxDeletions
- maximum number of removed IDs (> 0)minSubsetSize
- minimum subset size (≥ 0)fixedIDs
- set of fixed IDs which are not allowed to be removed from the selectionIllegalArgumentException
- if maxDeletions
is not strictly positive
or minSubsetSize
is negativepublic int getMaxDeletions()
Integer.MAX_VALUE
.public int getMinSubsetSize()
public SubsetMove getRandomMove(SubsetSolution solution, Random rnd)
Generates a move for the given subset solution that deselects a random subset of currently selected IDs.
Possible fixed IDs are not considered to be deselected. The maximum number of deletions \(k\) and minimum
allowed subset size are respected. If no items can be removed, null
is returned.
Note that first, a random number of deletions is picked (uniformly distributed) from the valid range and then, a random subset of this size is sampled from the currently selected IDs, to be removed (again, all possible subsets are uniformly distributed, within the fixed size). Because the amount of possible moves increases with the number of performed deletions, the probability of generating each specific move thus decreases with the number of deletions. In other words, randomly generated moves are not uniformly distributed across different numbers of performed deletions, but each specific move performing fewer deletions is more likely to be selected than each specific move performing more deletions.
solution
- solution for which a random multi deletion move is generatedrnd
- source of randomness used to generate random movenull
if no items can be removedpublic List<SubsetMove> getAllMoves(SubsetSolution solution)
Generates the list of all possible moves that perform 1 up to \(k\) deletions, where \(k\) is the maximum number of deletions specified at construction. Possible fixed IDs are not considered to be removed and the minimum allowed subset size is respected.
May return an empty list if no moves can be generated.
solution
- solution for which all possible multi deletion moves are generatedCopyright © 2016. All rights reserved.