org.jamesframework.core.search.algo

## Class ParallelTempering<SolutionType extends Solution>

• 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 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:

1. Every replica performs a fixed number of steps (defaults to 500) in an attempt to improve its own solution.
2. Solutions of adjacent replica (ordered by temperature) are considered to be swapped. Solutions of replicas $$R_1$$ and $$R_2$$ with temperatures $$T_1$$ and $$T_2$$ ($$T_1 \lt T_2$$) and current solution evaluation $$E_1$$ and $$E_2$$, respectively, are always swapped if $$\Delta E \ge 0$$, where $$\Delta E$$ is defined as the improvement of $$E_2$$ over $$E_1$$ (see 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.

Author:
Herman De Beukelaer
• ### Constructor Summary

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

All Methods
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.
• ### Methods inherited from class org.jamesframework.core.search.SingleNeighbourhoodSearch

getNeighbourhood
• ### Methods inherited from class org.jamesframework.core.search.NeighbourhoodSearch

accept, evaluate, getBestMove, getNumAcceptedMoves, getNumRejectedMoves, incNumAcceptedMoves, incNumRejectedMoves, isImprovement, reject, setEvaluatedMoveCache, updateCurrentSolution, validate
• ### Methods inherited from class org.jamesframework.core.search.LocalSearch

generateRandomInitialSolution, getCurrentSolution, getCurrentSolutionEvaluation, getCurrentSolutionValidation, 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, 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

• #### ParallelTempering

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.

Parameters:
problem - problem to solve
neighbourhood - neighbourhood used inside Metropolis search replicas
numReplicas - number of Metropolis replicas
minTemperature - minimum temperature of Metropolis replicas
maxTemperature - maximum temperature of Metropolis replicas
Throws:
NullPointerException - if problem or neighbourhood are null
IllegalArgumentException - if numReplicas, minTemperature or maxTemperature are not strictly positive, or if minTemperature ≥ maxTemperature
• #### ParallelTempering

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.

Parameters:
problem - problem to solve
neighbourhood - neighbourhood used inside Metropolis search replicas
numReplicas - number of Metropolis replicas
minTemperature - minimum temperature of Metropolis replicas
maxTemperature - maximum temperature of Metropolis replicas
metropolisFactory - custom factory used to create Metropolis searches
Throws:
NullPointerException - if problem or neighbourhood are null
IllegalArgumentException - if numReplicas, minTemperature or maxTemperature are not strictly positive, or if minTemperature ≥ maxTemperature
• #### ParallelTempering

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.

Parameters:
name - custom search name
problem - problem to solve
neighbourhood - neighbourhood used inside Metropolis search replicas
numReplicas - number of Metropolis replicas
minTemperature - minimum temperature of Metropolis replicas
maxTemperature - maximum temperature of Metropolis replicas
metropolisFactory - custom factory used to create Metropolis searches
Throws:
NullPointerException - if problem or neighbourhood are null
IllegalArgumentException - if numReplicas, minTemperature or maxTemperature are not strictly positive, or if minTemperature ≥ maxTemperature
• ### Method Detail

• #### setReplicaSteps

public 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. Defaults to 500. The specified number of steps should be strictly positive.
Parameters:
steps - number of steps performed by replicas in each iteration
Throws:
IllegalArgumentException - if steps is not strictly positive
• #### getReplicaSteps

public long getReplicaSteps()
Get the number of steps performed by each replica in every iteration of the global parallel tempering algorithm, before considering solution swaps. Defaults to 500 and can be changed using setReplicaSteps(long).
Returns:
number of steps performed by replicas in each iteration
• #### setNeighbourhood

public void setNeighbourhood(Neighbourhood<? super SolutionType> neighbourhood)
Set the same neighbourhood for each replica. Note that neighbourhood can not be null and that this method may only be called when the search is idle.
Overrides:
setNeighbourhood in class SingleNeighbourhoodSearch<SolutionType extends Solution>
Parameters:
neighbourhood - neighbourhood to be set for each replica
Throws:
NullPointerException - if neighbourhood is null
SearchException - if the search is not idle
• #### setCurrentSolution

public void setCurrentSolution(SolutionType solution)
Set a custom current solution, of which a copy is set as the current solution in each replica. Note that solution can not be null and that this method may only be called when the search is idle.
Overrides:
setCurrentSolution in class LocalSearch<SolutionType extends Solution>
Parameters:
solution - current solution to be set for each replica
Throws:
NullPointerException - if solution is null
SearchException - if the search is not idle
• #### init

public void init()
When initializing a parallel tempering search, the replicas are initialized as well (in parallel).
Overrides:
init in class NeighbourhoodSearch<SolutionType extends Solution>
• #### searchStep

protected void searchStep()
In each search step, every replica performs several steps after which solutions of adjacent replicas may be swapped.
Specified by:
searchStep in class Search<SolutionType extends Solution>
Throws:
SearchException - if an error occurs during concurrent execution of the Metropolis replicas
JamesRuntimeException - if depending on malfunctioning components (problem, neighbourhood, replicas, ...)
• #### searchDisposed

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.
Overrides:
searchDisposed in class Search<SolutionType extends Solution>