org.jamesframework.core.search.algo

Class RandomDescent<SolutionType extends Solution>

java.lang.Object

org.jamesframework.core.search.Search<SolutionType>

org.jamesframework.core.search.LocalSearch<SolutionType>

org.jamesframework.core.search.NeighbourhoodSearch<SolutionType>

org.jamesframework.core.search.SingleNeighbourhoodSearch<SolutionType>

org.jamesframework.core.search.algo.RandomDescent<SolutionType>

Type Parameters:

SolutionType - solution type of the problems that may be solved using this search, required to extend Solution

All Implemented Interfaces:

Runnable

public class RandomDescent<SolutionType extends Solution>
extends SingleNeighbourhoodSearch<SolutionType>

Basic random descent algorithm. In every search step, a random neighbour is created by applying a random move to the current solution. If this neighbour is a valid improvement over the current solution, it is accepted as the new current solution; else, it is rejected. The random descent algorithm usually does not come to a natural end, and therefore fully depends on stop criteria for termination, except in the unusual case when the current solution does not have any valid neighbours.

Author:

Herman De Beukelaer

Constructor Summary

Constructors

Constructor and Description
RandomDescent(Problem<SolutionType> problem, Neighbourhood<? super SolutionType> neighbourhood) Creates a new random descent search, specifying the problem to solve and the neighbourhood used to modify the current solution.
RandomDescent(String name, Problem<SolutionType> problem, Neighbourhood<? super SolutionType> neighbourhood) Creates a new random descent search, specifying the problem to solve, the neighbourhood used to modify the current solution, and a custom search name.

Method Summary

Modifier and Type	Method and Description
protected void	searchStep() Creates a random neighbour of the current solution and accepts it if it improves over the current solution.

Methods inherited from class org.jamesframework.core.search.SingleNeighbourhoodSearch

getNeighbourhood, setNeighbourhood

Methods inherited from class org.jamesframework.core.search.NeighbourhoodSearch

accept, evaluate, getBestMove, getNumAcceptedMoves, getNumRejectedMoves, incNumAcceptedMoves, incNumRejectedMoves, init, isImprovement, reject, setEvaluatedMoveCache, updateCurrentSolution, validate

Methods inherited from class org.jamesframework.core.search.LocalSearch

generateRandomInitialSolution, getCurrentSolution, getCurrentSolutionEvaluation, getCurrentSolutionValidation, setCurrentSolution, setCurrentSolution, updateCurrentAndBestSolution, updateCurrentAndBestSolution, updateCurrentSolution

Methods inherited from class org.jamesframework.core.search.Search

addSearchListener, addStopCriterion, assertIdle, clearSearchListeners, clearStopCriteria, computeDelta, dispose, getBestSolution, getBestSolutionEvaluation, getBestSolutionValidation, getID, getMinDelta, getName, getProblem, getRandom, getRuntime, getSearchListeners, getStatus, getStatusLock, getSteps, getStepsWithoutImprovement, getTimeWithoutImprovement, removeSearchListener, removeStopCriterion, run, searchDisposed, searchStarted, searchStopped, setRandom, setStopCriterionCheckPeriod, start, stop, toString, updateBestSolution, updateBestSolution

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

RandomDescent

public RandomDescent(Problem<SolutionType> problem,
                     Neighbourhood<? super SolutionType> neighbourhood)

Creates a new random descent search, specifying the problem to solve and the neighbourhood used to modify the current solution. Neither arguments can be null. The search name defaults to "RandomDescent".

Parameters:

problem - problem to solve

neighbourhood - neighbourhood used to create neighbouring solutions

Throws:

NullPointerException - if problem or neighbourhood are null

RandomDescent

public RandomDescent(String name,
                     Problem<SolutionType> problem,
                     Neighbourhood<? super SolutionType> neighbourhood)

Creates a new random descent search, specifying the problem to solve, the neighbourhood used to modify the current solution, and a custom search name. The problem and neighbourhood can not be null. The search name can be null in which case the default name "RandomDescent" is assigned.

Parameters:

problem - problem to solve

neighbourhood - neighbourhood used to create neighbouring solutions

name - custom search name

Throws:

NullPointerException - if problem or neighbourhood are null

Method Detail

searchStep

protected void searchStep()

Creates a random neighbour of the current solution and accepts it if it improves over the current solution.

Specified by:

searchStep in class Search<SolutionType extends Solution>

Throws:

JamesRuntimeException - if depending on malfunctioning components (problem, neighbourhood, ...)