Opened 12 years ago

Closed 12 years ago

Last modified 10 years ago

#513 closed enhancement (done)

Implement Simulated Annealing

Reported by: abeham Owned by: abeham
Priority: medium Milestone: HeuristicLab 3.3.0
Component: ZZZ OBSOLETE: SA Version: 3.2
Keywords: Cc:

Description

Simulated Annealing is one of the oldest metaheuristic and was described by Kirkpatrick et al in 1983 in an article in Science.

It is a trajectory-based metaheuristic that accepts uphill move in the beginning of the search. In later stages it is gradually restricting the search more and more to downhill moves (minimization problem). The next possible solution in each iteration is drawn from a neighborhood around the current solution, thus a neighborhood function is necessary. Typically this is similar to ES mutation. It has been proven that with the right annealing method and an infinite amount of time SA is able to find the global optimum. Practically this is irrelevant though and recently the importance of SA has decreased in the light of a multitude of other metaheuristics being developed and improved.

SA is a fast metaheuristic that is able to converge quickly into a local minimum. To achieve good solutions in short time it's possible to apply multistart techniques from different starting points. The annealing scheme and thus temperature curve, as well as the neighborhood function are crucial to its performance.

A general SA definition also includes an inner loop where, at the same temperature, multiple solutions are created. This can be as simple as a for loop or a maximum number of iterations for finding a better solution at each temperature.

Change History (5)

comment:1 Changed 12 years ago by abeham

  • Status changed from new to assigned

comment:2 Changed 12 years ago by abeham

done in r1289

The stop criterion regarding the temperature could still be parametrized to allow to set any minimium temperature as stop criterion. Currently it will abort when the temperature becomes 0 or less.

comment:3 Changed 12 years ago by abeham

  • Resolution set to fixed
  • Status changed from assigned to closed

added minimum temperature as additional stop criterion in r1353

comment:4 Changed 10 years ago by swagner

  • Milestone changed from Iteration 2 to Current

Milestone Iteration 2 deleted

comment:12 Changed 10 years ago by swagner

  • Milestone changed from Current to HeuristicLab 3.3.0

Milestone Current deleted

Note: See TracTickets for help on using tickets.