SolutionType
- solution type of the problems that may be solved using this search,
required to extend Solution
public class ParallelTempering<SolutionType extends Solution> extends SingleNeighbourhoodSearch<SolutionType>
The parallel tempering algorithm uses several Metropolis search replicas with different temperatures in a given range, where good solutions are pushed towards cool replicas for the sake of convergence, while bad solutions are pushed towards hot replicas in an attempt to find further improvements. Each step of parallel tempering consists of the following two actions:
Search.computeDelta(Evaluation, Evaluation)
).
If \(\Delta E \lt 0\), solutions are swapped with probability
\[
e^{(\frac{1}{T_1}-\frac{1}{T_2})\Delta E}.
\]
All replicas use the same neighbourhood, which is specified when creating the parallel tempering
search. By default, each replica starts from an independently generated random solution. A custom
initial solution can be set by calling setCurrentSolution(Solution)
on the parallel tempering
algorithm before starting the search; in this case, a copy of this solution is set as initial solution
in each replica. Note that this cancels the built-in multi-start of the parallel tempering algorithm.
Setting an independent custom initial solution in each replica can be achieved by providing a custom
Metropolis search factory at construction.
The overall best solution found by all replicas is tracked and eventually returned by the parallel tempering algorithm. The main algorithm does not actively generate nor apply any moves to its current solution, but simply updates it when a replica has found a new global improvement, in which case the best solution is also updated.
The reported number of accepted and rejected moves (see NeighbourhoodSearch.getNumAcceptedMoves()
and
NeighbourhoodSearch.getNumRejectedMoves()
) correspond to the sum of the number of accepted and rejected
moves in all replicas, during the current run of the parallel tempering search. These values
are updated with some delay, whenever a Metropolis replica has completed its current run.
When creating the parallel tempering algorithm, the number of replicas and a minimum and maximum temperature have to be specified. Temperatures assigned to the replicas are unique and equally spaced in the desired interval. The number of replica steps defaults to 500 but it is strongly advised to fine tune this parameter for specific problems, e.g. in case of a computationally expensive objective function, a lower number of steps may be more appropriate.
Note that every replica runs in a separate thread so that they will be executed in parallel on multi-core processors or multi-processor machines. Therefore, it is important that the problem (including all of its components such as the objective, constraints, etc.) and neighbourhood specified at construction are thread-safe.
Constructor and Description |
---|
ParallelTempering(Problem<SolutionType> problem,
Neighbourhood<? super SolutionType> neighbourhood,
int numReplicas,
double minTemperature,
double maxTemperature)
Creates a new parallel tempering algorithm, specifying the problem to solve,
the neighbourhood used in each replica, the number of replicas, and the minimum
and maximum temperature.
|
ParallelTempering(Problem<SolutionType> problem,
Neighbourhood<? super SolutionType> neighbourhood,
int numReplicas,
double minTemperature,
double maxTemperature,
MetropolisSearchFactory<SolutionType> metropolisFactory)
Creates a new parallel tempering algorithm, specifying the problem to solve,
the neighbourhood used in each replica, the number of replicas, the minimum
and maximum temperature, and a custom Metropolis search factory.
|
ParallelTempering(String name,
Problem<SolutionType> problem,
Neighbourhood<? super SolutionType> neighbourhood,
int numReplicas,
double minTemperature,
double maxTemperature,
MetropolisSearchFactory<SolutionType> metropolisFactory)
Creates a new parallel tempering algorithm, specifying the problem to solve,
the neighbourhood used in each replica, the number of replicas, the minimum
and maximum temperature, a custom search name, and a custom Metropolis search
factory.
|
Modifier and Type | Method and Description |
---|---|
long |
getReplicaSteps()
Get the number of steps performed by each replica in every iteration of the global parallel
tempering algorithm, before considering solution swaps.
|
void |
init()
When initializing a parallel tempering search, the replicas are initialized as well (in parallel).
|
protected void |
searchDisposed()
When disposing a parallel tempering search, it will dispose each contained Metropolis replica and will
shut down the thread pool used for concurrent execution of replicas.
|
protected void |
searchStep()
In each search step, every replica performs several steps after which solutions of adjacent
replicas may be swapped.
|
void |
setCurrentSolution(SolutionType solution)
Set a custom current solution, of which a copy is set as the current solution in each replica.
|
void |
setNeighbourhood(Neighbourhood<? super SolutionType> neighbourhood)
Set the same neighbourhood for each replica.
|
void |
setReplicaSteps(long steps)
Sets the number of steps performed by each replica in every iteration of the global parallel tempering
algorithm, before considering solution swaps.
|
getNeighbourhood
accept, evaluate, getBestMove, getNumAcceptedMoves, getNumRejectedMoves, incNumAcceptedMoves, incNumRejectedMoves, isImprovement, reject, setEvaluatedMoveCache, updateCurrentSolution, validate
generateRandomInitialSolution, getCurrentSolution, getCurrentSolutionEvaluation, getCurrentSolutionValidation, 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, searchStarted, searchStopped, setRandom, setStopCriterionCheckPeriod, start, stop, toString, updateBestSolution, updateBestSolution
public ParallelTempering(Problem<SolutionType> problem, Neighbourhood<? super SolutionType> neighbourhood, int numReplicas, double minTemperature, double maxTemperature)
Creates a new parallel tempering algorithm, specifying the problem to solve,
the neighbourhood used in each replica, the number of replicas, and the minimum
and maximum temperature. The problem and neighbourhood can not be null
,
the number of replicas and both temperature bounds should be strictly positive, and
the minimum temperature should be smaller than the maximum temperature. The default
name "ParallelTempering" is assigned to the search.
Note that it is important that the given problem (including all of its components such as the objective, constraints, etc.) and neighbourhood are thread-safe, because they will be accessed concurrently from several Metropolis searches running in separate threads.
problem
- problem to solveneighbourhood
- neighbourhood used inside Metropolis search replicasnumReplicas
- number of Metropolis replicasminTemperature
- minimum temperature of Metropolis replicasmaxTemperature
- maximum temperature of Metropolis replicasNullPointerException
- if problem
or neighbourhood
are
null
IllegalArgumentException
- if numReplicas
, minTemperature
or maxTemperature
are not strictly positive,
or if minTemperature ≥ maxTemperature
public ParallelTempering(Problem<SolutionType> problem, Neighbourhood<? super SolutionType> neighbourhood, int numReplicas, double minTemperature, double maxTemperature, MetropolisSearchFactory<SolutionType> metropolisFactory)
Creates a new parallel tempering algorithm, specifying the problem to solve,
the neighbourhood used in each replica, the number of replicas, the minimum
and maximum temperature, and a custom Metropolis search factory. The Metropolis
search factory can be used to customize the replicas, e.g. to set a custom initial
solution per replica. The factory should always respect the contract as defined in
the interface MetropolisSearchFactory
. Else, the algorithm may not function
correctly and exceptions might be thrown during search.
The problem, neighbourhood and Metropolis factory can not be null
,
the number of replicas and both temperature bounds should be strictly positive,
and the minimum temperature should be smaller than the maximum temperature.
Note that it is important that the given problem (including all of its components such as the objective, constraints, etc.) and neighbourhood are thread-safe, because they will be accessed concurrently from several Metropolis searches running in separate threads.
problem
- problem to solveneighbourhood
- neighbourhood used inside Metropolis search replicasnumReplicas
- number of Metropolis replicasminTemperature
- minimum temperature of Metropolis replicasmaxTemperature
- maximum temperature of Metropolis replicasmetropolisFactory
- custom factory used to create Metropolis searchesNullPointerException
- if problem
or neighbourhood
are
null
IllegalArgumentException
- if numReplicas
, minTemperature
or maxTemperature
are not strictly positive,
or if minTemperature ≥ maxTemperature
public ParallelTempering(String name, Problem<SolutionType> problem, Neighbourhood<? super SolutionType> neighbourhood, int numReplicas, double minTemperature, double maxTemperature, MetropolisSearchFactory<SolutionType> metropolisFactory)
Creates a new parallel tempering algorithm, specifying the problem to solve,
the neighbourhood used in each replica, the number of replicas, the minimum
and maximum temperature, a custom search name, and a custom Metropolis search
factory. The Metropolis search factory can be used to customize the replicas,
e.g. to set a custom initial solution per replica. The factory should always
respect the contract as defined in the interface MetropolisSearchFactory
.
Else, the algorithm may not function correctly and exceptions might be thrown
during search.
The problem, neighbourhood and Metropolis factory can not be null
,
the number of replicas and both temperature bounds should be strictly positive,
and the minimum temperature should be smaller than the maximum temperature. The
search name can be null
in which case the default name "ParallelTempering"
is assigned.
Note that it is important that the given problem (including all of its components such as the objective, constraints, etc.) and neighbourhood are thread-safe, because they will be accessed concurrently from several Metropolis searches running in separate threads.
name
- custom search nameproblem
- problem to solveneighbourhood
- neighbourhood used inside Metropolis search replicasnumReplicas
- number of Metropolis replicasminTemperature
- minimum temperature of Metropolis replicasmaxTemperature
- maximum temperature of Metropolis replicasmetropolisFactory
- custom factory used to create Metropolis searchesNullPointerException
- if problem
or neighbourhood
are
null
IllegalArgumentException
- if numReplicas
, minTemperature
or maxTemperature
are not strictly positive,
or if minTemperature ≥ maxTemperature
public void setReplicaSteps(long steps)
steps
- number of steps performed by replicas in each iterationIllegalArgumentException
- if steps
is not strictly positivepublic long getReplicaSteps()
setReplicaSteps(long)
.public void setNeighbourhood(Neighbourhood<? super SolutionType> neighbourhood)
neighbourhood
can not
be null
and that this method may only be called when the search is idle.setNeighbourhood
in class SingleNeighbourhoodSearch<SolutionType extends Solution>
neighbourhood
- neighbourhood to be set for each replicaNullPointerException
- if neighbourhood
is null
SearchException
- if the search is not idlepublic void setCurrentSolution(SolutionType solution)
solution
can not be null
and that this method may only be
called when the search is idle.setCurrentSolution
in class LocalSearch<SolutionType extends Solution>
solution
- current solution to be set for each replicaNullPointerException
- if solution
is null
SearchException
- if the search is not idlepublic void init()
init
in class NeighbourhoodSearch<SolutionType extends Solution>
protected void searchStep()
searchStep
in class Search<SolutionType extends Solution>
SearchException
- if an error occurs during concurrent execution of the Metropolis replicasJamesRuntimeException
- if depending on malfunctioning components (problem,
neighbourhood, replicas, ...)protected void searchDisposed()
searchDisposed
in class Search<SolutionType extends Solution>
Copyright © 2016. All rights reserved.