## Class MultiSwapNeighbourhood

• All Implemented Interfaces:
Neighbourhood<SubsetSolution>

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.

Author:
Herman De Beukelaer
• ### Constructor Summary

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

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

• #### MultiSwapNeighbourhood

public MultiSwapNeighbourhood()
Creates a multi swap neighbourhood that may perform an unlimited number of swaps. The actual number of performed swaps is then only limited by the minimum of the number of selected and unselected items in a given subset solution, as it is impossible to swap more items.
• #### MultiSwapNeighbourhood

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

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

• #### getMaxSwaps

public int getMaxSwaps()
Get the maximum number of swaps performed by generated moves. If no limit has been set this method returns Integer.MAX_VALUE.
Returns:
maximum 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 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.

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

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