org.jamesframework.core.subset.neigh

## Class SinglePerturbationNeighbourhood

• All Implemented Interfaces:
Neighbourhood<SubsetSolution>

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.

Author:
Herman De Beukelaer
• ### Constructor Summary

Constructors
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.
• ### Method Summary

All Methods
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.
• ### Methods inherited from class org.jamesframework.core.subset.neigh.SubsetNeighbourhood

getAddCandidates, getRemoveCandidates
• ### Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
• ### Methods inherited from interface org.jamesframework.core.search.neigh.Neighbourhood

getRandomMove
• ### Constructor Detail

• #### SinglePerturbationNeighbourhood

public SinglePerturbationNeighbourhood()
Creates a new single perturbation neighbourhood without size limits.
• #### SinglePerturbationNeighbourhood

public SinglePerturbationNeighbourhood(int minSubsetSize,
int maxSubsetSize)
Creates a new single perturbation neighbourhood with given minimum and maximum subset size. Only moves that result in a valid solution size after application to the current solution will ever be generated. Positive values are required for the minimum and maximum size, with minimum smaller than or equal to maximum; else, an exception is thrown.
Parameters:
minSubsetSize - minimum subset size (≥ 0)
maxSubsetSize - maximum subset size (> 0)
Throws:
IllegalArgumentException - if minimum size is not positive, maximum size is not strictly positive, or minimum > maximum
• #### SinglePerturbationNeighbourhood

public 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. Only moves that result in a valid solution size after application to the current solution will ever be generated. Positive values are required for the minimum and maximum size, with minimum smaller than or equal to maximum; else, an exception is thrown.
Parameters:
minSubsetSize - minimum subset size (≥ 0)
maxSubsetSize - maximum subset size (> 0)
fixedIDs - set of fixed IDs
Throws:
IllegalArgumentException - if minimum size is not positive, maximum size is not strictly positive, or minimum > maximum
• ### Method Detail

• #### getRandomMove

public 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.

Parameters:
solution - solution for which a random move is generated
rnd - source of randomness used to generate random move
Returns:
random move, null if no valid move can be generated
• #### getAllMoves

public 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. The returned list may be empty, if no valid moves exist. If any fixed IDs have been specified, these will not be considered for deletion nor addition.
Parameters:
solution - solution for which a set of all valid moves is generated
Returns:
list of all valid swap, deletion and addition moves
• #### getMinSubsetSize

public int getMinSubsetSize()
Get the minimum subset size specified at construction. If no minimum size has been set this method returns 0.
Returns:
minimum subset size
• #### getMaxSubsetSize

public int getMaxSubsetSize()
Get the maximum subset size specified at construction. If no maximum size has been set this method returns Integer.MAX_VALUE.
Returns:
maximum subset size