org.cpsolver.ifs.algorithms

## Class SimulatedAnnealing<V extends Variable<V,T>,T extends Value<V,T>>

- java.lang.Object
- - org.cpsolver.ifs.assignment.context.NeighbourSelectionWithContext<V,T,NeighbourSearch.NeighbourSearchContext>
  - - org.cpsolver.ifs.algorithms.NeighbourSearch<V,T>
    - - org.cpsolver.ifs.algorithms.SimulatedAnnealing<V,T>

- Type Parameters:
    `V` - Variable
    `T` - Value
  All Implemented Interfaces:
    CanHoldContext, HasAssignmentContext<V,T,NeighbourSearch.NeighbourSearchContext>, NeighbourSelection<V,T>, LazyNeighbour.LazyNeighbourAcceptanceCriterion<V,T>, SolutionListener<V,T>

      public class SimulatedAnnealing<V extends Variable<V,T>,T extends Value<V,T>>
      extends NeighbourSearch<V,T>

  Simulated annealing. In each iteration, one of the given neighbourhoods is selected first, then a neighbour is generated and it is accepted with probability `SimulatedAnnealing.SimulatedAnnealingContext.prob(double)`. The search is guided by the temperature, which starts at SimulatedAnnealing.InitialTemperature. After each SimulatedAnnealing.TemperatureLength iterations, the temperature is reduced by SimulatedAnnealing.CoolingRate. If there was no improvement in the past SimulatedAnnealing.ReheatLengthCoef * SimulatedAnnealing.TemperatureLength iterations, the temperature is increased by SimulatedAnnealing.ReheatRate. If there was no improvement in the past SimulatedAnnealing.RestoreBestLengthCoef * SimulatedAnnealing.TemperatureLength iterations, the best ever found solution is restored.
  If SimulatedAnnealing.StochasticHC is true, the acceptance probability is computed using stochastic hill climbing criterion, i.e., `1.0 / (1.0 + Math.exp(value/temperature))`, otherwise it is cumputed using simlated annealing criterion, i.e., `(value<=0.0?1.0:Math.exp(-value/temperature))`. If SimulatedAnnealing.RelativeAcceptance neighbour value `Neighbour.value(Assignment)` is taken as the value of the selected neighbour (difference between the new and the current solution, if the neighbour is accepted), otherwise the value is computed as the difference between the value of the current solution if the neighbour is accepted and the best ever found solution.
  Custom neighbours can be set using SimulatedAnnealing.Neighbours property that should contain semicolon separated list of `NeighbourSelection`. By default, each neighbour selection is selected with the same probability (each has 1 point in a roulette wheel selection). It can be changed by adding @n at the end of the name of the class, for example:

       SimulatedAnnealing.Neighbours=org.cpsolver.ifs.algorithms.neighbourhoods.RandomMove;org.cpsolver.ifs.algorithms.neighbourhoods.RandomSwapMove@0.1

  Selector RandomSwapMove is 10× less probable to be selected than other selectors. When SimulatedAnnealing.Random is true, all selectors are selected with the same probability, ignoring these weights.
  When SimulatedAnnealing.Update is true, `NeighbourSelector.update(Assignment, Neighbour, long)` is called after each iteration (on the selector that was used) and roulette wheel selection that is using `NeighbourSelector.getPoints()` is used to pick a selector in each iteration. See `NeighbourSelector` for more details.
  Version:
    IFS 1.3 (Iterative Forward Search)
    Copyright (C) 2014 Tomáš Müller
    muller@unitime.org
    http://muller.unitime.org
    This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.
    This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.
    You should have received a copy of the GNU Lesser General Public License along with this library; if not see http://www.gnu.org/licenses/.
  Author:
    Tomáš Müller

- - ### Nested Class Summary

    Nested Classes
    Modifier and Type | Class and Description
    --- | ---
    `class` | `SimulatedAnnealing.SimulatedAnnealingContext`

    - ### Nested classes/interfaces inherited from class org.cpsolver.ifs.algorithms.NeighbourSearch

      `NeighbourSearch.NeighbourSearchContext`

  - ### Field Summary

    - ### Fields inherited from class org.cpsolver.ifs.algorithms.NeighbourSearch

      `iDF2, iPhase`

    - ### Fields inherited from class org.cpsolver.ifs.assignment.context.NeighbourSelectionWithContext

      `iContextOverride`

    - ### Fields inherited from interface org.cpsolver.ifs.assignment.context.CanHoldContext

      `sMaxSize`

  - ### Constructor Summary

    Constructors
    Constructor and Description
    `SimulatedAnnealing(DataProperties properties)` Constructor.

  - ### Method Summary

    All Methods Instance Methods Concrete Methods
    Modifier and Type | Method and Description
    --- | ---
    `NeighbourSearch.NeighbourSearchContext` | `createAssignmentContext(Assignment<V,T> assignment)` Create a new assignment context for the given assignment.
    `String` | `getParameterBaseName()` Parameter base name.

    - ### Methods inherited from class org.cpsolver.ifs.algorithms.NeighbourSearch

      `accept, accept, addNeighbourSelection, bestCleared, bestRestored, bestSaved, generateMove, getInfo, getInfo, getNeighbours, info, init, isMaster, logNeibourStatus, nextNeighbourSelection, selectNeighbour, setHCMode, setProgress, setProgressPhase, solutionUpdated`

    - ### Methods inherited from class org.cpsolver.ifs.assignment.context.NeighbourSelectionWithContext

      `getAssignmentContextReference, getContext, getContext, hasContextOverride, isSingleContextSolver, setAssignmentContextReference`

    - ### Methods inherited from class java.lang.Object

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

- - ### Constructor Detail

    - #### SimulatedAnnealing

          public SimulatedAnnealing(DataProperties properties)

      Constructor. Following problem properties are considered:
      - SimulatedAnnealing.InitialTemperature ... initial temperature (default 1.5)
      - SimulatedAnnealing.TemperatureLength ... temperature length (number of iterations between temperature decrements, default 25000)
      - SimulatedAnnealing.CoolingRate ... temperature cooling rate (default 0.95)
      - SimulatedAnnealing.ReheatLengthCoef ... temperature re-heat length coefficient (multiple of temperature length, default 5)
      - SimulatedAnnealing.ReheatRate ... temperature re-heating rate (default (1/coolingRate)^(reheatLengthCoef*1.7))
      - SimulatedAnnealing.RestoreBestLengthCoef ... restore best length coefficient (multiple of re-heat length, default reheatLengthCoef^2)
      - SimulatedAnnealing.StochasticHC ... true for stochastic search acceptance criterion, false for simulated annealing acceptance (default false)
      - SimulatedAnnealing.RelativeAcceptance ... true for relative acceptance (different between the new and the current solutions, if the neighbour is accepted), false for absolute acceptance (difference between the new and the best solutions, if the neighbour is accepted)
      - SimulatedAnnealing.Neighbours ... semicolon separated list of classes implementing `NeighbourSelection`
      - SimulatedAnnealing.AdditionalNeighbours ... semicolon separated list of classes implementing `NeighbourSelection`
      - SimulatedAnnealing.Random ... when true, a neighbour selector is selected randomly
      - SimulatedAnnealing.Update ... when true, a neighbour selector is selected using `NeighbourSelector.getPoints()` weights (roulette wheel selection)
      Parameters:
        `properties` - problem properties

  - ### Method Detail

    - #### getParameterBaseName

          public String getParameterBaseName()

      Description copied from class: `NeighbourSearch`
      Parameter base name. This can be used to distinguish between parameters of different search algorithms.
      Specified by:
        `getParameterBaseName` in class `NeighbourSearch<V extends Variable<V,T>,T extends Value<V,T>>`
      Returns:
        solver parameter base name for this search technique

    - #### createAssignmentContext

          public NeighbourSearch.NeighbourSearchContext createAssignmentContext(Assignment<V,T> assignment)

      Description copied from interface: `HasAssignmentContext`
      Create a new assignment context for the given assignment. If there are already some variables assigned in the value, the method should make sure that the context is appropriately initialized.
      Parameters:
        `assignment` - an assignment for which there needs to be an assignment context
      Returns:
        a new instance of the assignment context, filled according to the given assignment