## Class DisjointMultiSwapNeighbourhood

• All Implemented Interfaces:
Neighbourhood<SubsetSolution>

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.

Author:
Herman De Beukelaer
• ### Constructor Summary

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

All Methods
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.
• ### 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

• #### DisjointMultiSwapNeighbourhood

public DisjointMultiSwapNeighbourhood(int numSwaps)
Creates a multi swap neighbourhood without fixed IDs, indicating the number of (simultaneous) swaps performed by any generated move. 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.
Parameters:
numSwaps - number of swaps performed by any generated move (> 0)
Throws:
IllegalArgumentException - if maxSwaps is not strictly positive
• #### DisjointMultiSwapNeighbourhood

public 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. None of the generated moves will add nor remove any of these fixed IDs. All generated moves will swap exactly 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.
Parameters:
numSwaps - number of swaps performed by any generated move (> 0)
fixedIDs - set of fixed IDs which are not allowed to be swapped
Throws:
IllegalArgumentException - if numSwaps is not strictly positive
• ### Method Detail

• #### getNumSwaps

public int getNumSwaps()
Get the fixed number of swaps performed by generated moves.
Returns:
fixed number of swaps
• #### getRandomMove

public 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. If it is not possible to swap $$k$$ items a smaller, maximum number of swaps will be performed. Possible fixed IDs are not considered to be swapped. If no swaps can be performed, null is returned.
Parameters:
solution - solution for which a random multi swap move is generated
rnd - source of randomness used to generate random move
Returns:
random multi swap move, null if no swaps can be performed
• #### getAllMoves

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

Parameters:
solution - solution for which all possible multi swap moves are generated
Returns:
list of all multi swap moves, may be empty