org.jamesframework.core.subset.neigh

Class SingleDeletionNeighbourhood

java.lang.Object

org.jamesframework.core.subset.neigh.SubsetNeighbourhood

org.jamesframework.core.subset.neigh.SingleDeletionNeighbourhood

All Implemented Interfaces:

Neighbourhood<SubsetSolution>

public class SingleDeletionNeighbourhood
extends SubsetNeighbourhood

A subset neighbourhood that generates deletion moves only (see DeletionMove). A deletion move is a subtype of SubsetMove that removes a single ID from the selection of a subset solution. If desired, a set of fixed IDs can be provided which are not allowed to be removed from the selection. Also, a size limit can be imposed so that no moves are generated when the current solution has minimum size.

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
SingleDeletionNeighbourhood() Create a single deletion neighbourhood without minimum subset size.
SingleDeletionNeighbourhood(int minSubsetSize) Create a single deletion neighbourhood with a given minimum subset size.
SingleDeletionNeighbourhood(int minSubsetSize, Set<Integer> fixedIDs) Create a single deletion neighbourhood with a given minimum subset size and a set of fixed IDs which are not allowed to be deselected.

Method Summary

Modifier and Type	Method and Description
List<SubsetMove>	getAllMoves(SubsetSolution solution) Generates a list of all possible deletion moves that remove a single ID from the selection of a given subset solution.
int	getMinSubsetSize() Get the minimum subset size.
SubsetMove	getRandomMove(SubsetSolution solution, Random rnd) Generates a random deletion move for the given subset solution that removes a single ID from the selection.

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

SingleDeletionNeighbourhood

public SingleDeletionNeighbourhood()

Create a single deletion neighbourhood without minimum subset size. All items are candidates to be deselected.

SingleDeletionNeighbourhood

public SingleDeletionNeighbourhood(int minSubsetSize)

Create a single deletion neighbourhood with a given minimum subset size. No moves will be generated if the current solution has minimum size. All items are candidates to be deselected.

Parameters:

minSubsetSize - minimum subset size (≥ 0)

Throws:

IllegalArgumentException - if minimum subset size is negative

SingleDeletionNeighbourhood

public SingleDeletionNeighbourhood(int minSubsetSize,
                                   Set<Integer> fixedIDs)

Create a single deletion neighbourhood with a given minimum subset size and a set of fixed IDs which are not allowed to be deselected. None of the generated deletion moves will remove any of these IDs from the selection.

Parameters:

minSubsetSize - minimum subset size (≥ 0)

fixedIDs - set of fixed IDs which are not allowed to be removed from the selection

Throws:

IllegalArgumentException - if minimum subset size is negative

Method Detail

getMinSubsetSize

public int getMinSubsetSize()

Get the minimum subset size. If no size limit has been applied this method returns 0.

Returns:

minimum subset size

getRandomMove

public SubsetMove getRandomMove(SubsetSolution solution,
                                Random rnd)

Generates a random deletion move for the given subset solution that removes a single ID from the selection. Possible fixed IDs are not considered to be removed and the minimum subset size is taken into account. If no deletion move can be generated, null is returned.

Parameters:

solution - solution for which a random deletion move is generated

rnd - source of randomness used to generate random move

Returns:

random deletion move, null if no move can be generated

getAllMoves

public List<SubsetMove> getAllMoves(SubsetSolution solution)

Generates a list of all possible deletion moves that remove a single ID from the selection of a given subset solution. Possible fixed IDs are not considered to be removed and the minimum subset size is taken into account. May return an empty list if no deletion moves can be generated.

Parameters:

solution - solution for which all possible deletion moves are generated

Returns:

list of all deletion moves, may be empty