SolutionType
- solution type of the problems that may be solved using this search, required to extend Solution
public class MetropolisSearch<SolutionType extends Solution> extends SingleNeighbourhoodSearch<SolutionType>
Note that it is important to carefully choose the temperature, depending on the scale of the evaluations and expected deltas, as well as the landscape of the objective function. Setting a high temperature decreases the probability of ending in a local optimum, but also impedes convergence and generally slows down the search process. Vice versa, a low temperature aids convergence but yields a search that is more sensitive to local optima. It is therefore strongly advised to experiment with different temperatures for each specific problem so that an appropriate temperature can be selected.
The search usually does not terminate internally except in the rare event that no random neighbour can be selected. It generally depends on external stop criteria for termination.
Constructor and Description |
---|
MetropolisSearch(Problem<SolutionType> problem,
Neighbourhood<? super SolutionType> neighbourhood,
double temperature)
Creates a new Metropolis search, specifying the problem to solve, the applied neighbourhood and the temperature.
|
MetropolisSearch(String name,
Problem<SolutionType> problem,
Neighbourhood<? super SolutionType> neighbourhood,
double temperature)
Creates a new Metropolis search, specifying the problem to solve, the applied neighbourhood and temperature,
and a custom search name.
|
Modifier and Type | Method and Description |
---|---|
double |
getTemperature()
Get the temperature \(T\) of the system.
|
protected void |
searchStep()
Creates a random neighbour of the current solution and accepts it as the new current solution
if it is valid and either improves the current solution or
\[
e^{\frac{\Delta E}{T}} > R(0,1)
\]
where \(\Delta E\) is the difference between the evaluation of the neighbour and that of the
current solution, \(T\) is the temperature, and \(R(0,1)\) is a random number in the interval
\([0,1]\) sampled using the search's dedicated random generator.
|
void |
setTemperature(double temperature)
Set the temperature (\(T > 0\)).
|
getNeighbourhood, setNeighbourhood
accept, evaluate, getBestMove, getNumAcceptedMoves, getNumRejectedMoves, incNumAcceptedMoves, incNumRejectedMoves, init, isImprovement, reject, setEvaluatedMoveCache, updateCurrentSolution, validate
generateRandomInitialSolution, getCurrentSolution, getCurrentSolutionEvaluation, getCurrentSolutionValidation, setCurrentSolution, setCurrentSolution, updateCurrentAndBestSolution, updateCurrentAndBestSolution, updateCurrentSolution
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
public MetropolisSearch(Problem<SolutionType> problem, Neighbourhood<? super SolutionType> neighbourhood, double temperature)
null
, and the temperature should be strictly positive.
The search name defaults to "MetropolisSearch".problem
- problem to solveneighbourhood
- neighbourhood used to create neighbouring solutionstemperature
- temperature of the systemNullPointerException
- if problem
or neighbourhood
are null
IllegalArgumentException
- if temperature
is not strictly positivepublic MetropolisSearch(String name, Problem<SolutionType> problem, Neighbourhood<? super SolutionType> neighbourhood, double temperature)
null
, and the temperature
should be strictly positive. The search name can be null
in which case the default name
"MetropolisSearch" is assigned.name
- custom search nameproblem
- problem to solveneighbourhood
- neighbourhood used to create neighbouring solutionstemperature
- temperature of the systemNullPointerException
- if problem
or neighbourhood
are null
IllegalArgumentException
- if temperature
is not strictly positivepublic void setTemperature(double temperature)
temperature
- new temperatureIllegalArgumentException
- if temperature
is not strictly positivepublic double getTemperature()
protected void searchStep()
searchStep
in class Search<SolutionType extends Solution>
JamesRuntimeException
- if depending on malfunctioning components (problem, neighbourhood, ...)Copyright © 2016. All rights reserved.