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