net.sf.cpsolver.exam.heuristics

## Class ExamSimulatedAnnealing

- java.lang.Object
- - net.sf.cpsolver.exam.heuristics.ExamSimulatedAnnealing

- All Implemented Interfaces:
    NeighbourSelection<Exam,ExamPlacement>, LazyNeighbour.LazyNeighbourAcceptanceCriterion<Exam,ExamPlacement>, SolutionListener<Exam,ExamPlacement>

      public class ExamSimulatedAnnealing
      extends Object
      implements NeighbourSelection<Exam,ExamPlacement>, SolutionListener<Exam,ExamPlacement>, LazyNeighbour.LazyNeighbourAcceptanceCriterion<Exam,ExamPlacement>

  Simulated annealing. In each iteration, one of the following three neighbourhoods is selected first
  - random move (`ExamRandomMove`)
  - period swap (`ExamTimeMove`)
  - room swap (`ExamRoomMove`)
  , then a neighbour is generated and it is accepted with probability `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 `ExamSimpleNeighbour.value()` 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.
  Version:
    ExamTT 1.2 (Examination Timetabling)
    Copyright (C) 2008 - 2010 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/.

- - ### Constructor Summary

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

  - ### Method Summary

    All Methods Instance Methods Concrete Methods
    Modifier and Type | Method and Description
    --- | ---
    `boolean` | `accept(LazyNeighbour<Exam,ExamPlacement> neighbour, double value)` Accept lazy neighbour
    `protected boolean` | `accept(Solution<Exam,ExamPlacement> solution, Neighbour<Exam,ExamPlacement> neighbour)` True if the given neighboir is to be be accepted
    `void` | `bestCleared(Solution<Exam,ExamPlacement> solution)` Called by the solution when method `Solution.clearBest()` is called.
    `void` | `bestRestored(Solution<Exam,ExamPlacement> solution)` Called by the solution when method `Solution.restoreBest()` is called.
    `void` | `bestSaved(Solution<Exam,ExamPlacement> solution)` Memorize the iteration when the last best solution was found.
    `protected void` | `cool(Solution<Exam,ExamPlacement> solution)` Cool temperature
    `Neighbour<Exam,ExamPlacement>` | `genMove(Solution<Exam,ExamPlacement> solution)` Generate neighbour -- select neighbourhood randomly, select neighbour
    `void` | `getInfo(Solution<Exam,ExamPlacement> solution, Map<String,String> info)` Called by the solution when it is asked to produce info table, see `Solution.getInfo()`.
    `void` | `getInfo(Solution<Exam,ExamPlacement> solution, Map<String,String> info, Collection<Exam> variables)` Called by the solution when it is asked to produce info table, see `Solution.getInfo()`.
    `protected void` | `incIter(Solution<Exam,ExamPlacement> solution)` Increment iteration counter, cool/reheat/restoreBest if necessary
    `void` | `init(Solver<Exam,ExamPlacement> solver)` Initialization
    `protected double` | `prob(double value)` Neighbour acceptance probability
    `protected void` | `reheat(Solution<Exam,ExamPlacement> solution)` Reheat temperature
    `protected void` | `restoreBest(Solution<Exam,ExamPlacement> solution)` restore best ever found solution
    `Neighbour<Exam,ExamPlacement>` | `selectNeighbour(Solution<Exam,ExamPlacement> solution)` Select neighbour -- generate a move `genMove(Solution)` until an acceptable neighbour is found `accept(Solution, Neighbour)`, keep increasing iteration `incIter(Solution)`.
    `void` | `solutionUpdated(Solution<Exam,ExamPlacement> solution)` Called by the solution when it is updated, see `Solution.update(double)`.

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

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

- - ### Constructor Detail

    - #### ExamSimulatedAnnealing

          public ExamSimulatedAnnealing(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)
      Parameters:
        `properties` - problem properties

  - ### Method Detail

    - #### init

          public void init(Solver<Exam,ExamPlacement> solver)

      Initialization
      Specified by:
        `init` in interface `NeighbourSelection<Exam,ExamPlacement>`

    - #### cool

          protected void cool(Solution<Exam,ExamPlacement> solution)

      Cool temperature

    - #### reheat

          protected void reheat(Solution<Exam,ExamPlacement> solution)

      Reheat temperature

    - #### restoreBest

          protected void restoreBest(Solution<Exam,ExamPlacement> solution)

      restore best ever found solution

    - #### genMove

          public Neighbour<Exam,ExamPlacement> genMove(Solution<Exam,ExamPlacement> solution)

      Generate neighbour -- select neighbourhood randomly, select neighbour

    - #### prob

          protected double prob(double value)

      Neighbour acceptance probability
      Parameters:
        `value` - absolute or relative value of the proposed change (neighbour)
      Returns:
        probability of acceptance of a change (neighbour)

    - #### accept

          protected boolean accept(Solution<Exam,ExamPlacement> solution,
                                   Neighbour<Exam,ExamPlacement> neighbour)

      True if the given neighboir is to be be accepted
      Parameters:
        `solution` - current solution
        `neighbour` - proposed move
      Returns:
        true if generated random number is below `prob(double)`

    - #### accept

          public boolean accept(LazyNeighbour<Exam,ExamPlacement> neighbour,
                                double value)

      Accept lazy neighbour
      Specified by:
        `accept` in interface `LazyNeighbour.LazyNeighbourAcceptanceCriterion<Exam,ExamPlacement>`
      Parameters:
        `neighbour` - neighbour that was assigned
        `value` - change in overall solution value
      Returns:
        true if the neighbour can be accepted (false to undo the assignment)

    - #### incIter

          protected void incIter(Solution<Exam,ExamPlacement> solution)

      Increment iteration counter, cool/reheat/restoreBest if necessary

    - #### selectNeighbour

          public Neighbour<Exam,ExamPlacement> selectNeighbour(Solution<Exam,ExamPlacement> solution)

      Select neighbour -- generate a move `genMove(Solution)` until an acceptable neighbour is found `accept(Solution, Neighbour)`, keep increasing iteration `incIter(Solution)`.
      Specified by:
        `selectNeighbour` in interface `NeighbourSelection<Exam,ExamPlacement>`
      Parameters:
        `solution` - given solution
      Returns:
        a neighbour assignment

    - #### bestSaved

          public void bestSaved(Solution<Exam,ExamPlacement> solution)

      Memorize the iteration when the last best solution was found.
      Specified by:
        `bestSaved` in interface `SolutionListener<Exam,ExamPlacement>`
      Parameters:
        `solution` - source solution

    - #### solutionUpdated

          public void solutionUpdated(Solution<Exam,ExamPlacement> solution)

      Description copied from interface: `SolutionListener`
      Called by the solution when it is updated, see `Solution.update(double)`.
      Specified by:
        `solutionUpdated` in interface `SolutionListener<Exam,ExamPlacement>`
      Parameters:
        `solution` - source solution

    - #### getInfo

          public void getInfo(Solution<Exam,ExamPlacement> solution,
                              Map<String,String> info)

      Description copied from interface: `SolutionListener`
      Called by the solution when it is asked to produce info table, see `Solution.getInfo()`. A listener can also add some its info into this table.
      Specified by:
        `getInfo` in interface `SolutionListener<Exam,ExamPlacement>`
      Parameters:
        `solution` - source solution
        `info` - produced info table

    - #### getInfo

          public void getInfo(Solution<Exam,ExamPlacement> solution,
                              Map<String,String> info,
                              Collection<Exam> variables)

      Description copied from interface: `SolutionListener`
      Called by the solution when it is asked to produce info table, see `Solution.getInfo()`. A listener can also add some its info into this table.
      Specified by:
        `getInfo` in interface `SolutionListener<Exam,ExamPlacement>`
      Parameters:
        `solution` - source solution
        `info` - produced info table
        `variables` - only variables from this set are included

    - #### bestCleared

          public void bestCleared(Solution<Exam,ExamPlacement> solution)

      Description copied from interface: `SolutionListener`
      Called by the solution when method `Solution.clearBest()` is called.
      Specified by:
        `bestCleared` in interface `SolutionListener<Exam,ExamPlacement>`
      Parameters:
        `solution` - source solution

    - #### bestRestored

          public void bestRestored(Solution<Exam,ExamPlacement> solution)

      Description copied from interface: `SolutionListener`
      Called by the solution when method `Solution.restoreBest()` is called.
      Specified by:
        `bestRestored` in interface `SolutionListener<Exam,ExamPlacement>`
      Parameters:
        `solution` - source solution