更改

==Overview==

==概述Overview==

The [[thermodynamic state|state]] of some [[physical system]]s, and the function ''E''(''s'') to be minimized, is analogous to the [[internal energy]] of the system in that state. The goal is to bring the system, from an arbitrary ''initial state'', to a state with the minimum possible energy.

The [[thermodynamic state|state]] of some [[physical system]]s, and the function ''E''(''s'') to be minimized, is analogous to the [[internal energy]] of the system in that state. The goal is to bring the system, from an arbitrary ''initial state'', to a state with the minimum possible energy.

===The basic iteration===

===基本迭代The basic iteration===

At each step, the simulated annealing heuristic considers some neighboring state ''s*'' of the current state ''s'', and [[probabilistic]]ally decides between moving the system to state ''s*'' or staying in-state ''s''.  These probabilities ultimately lead the system to move to states of lower energy.  Typically this step is repeated until the system reaches a state that is good enough for the application, or until a given computation budget has been exhausted.

At each step, the simulated annealing heuristic considers some neighboring state ''s*'' of the current state ''s'', and [[probabilistic]]ally decides between moving the system to state ''s*'' or staying in-state ''s''.  These probabilities ultimately lead the system to move to states of lower energy.  Typically this step is repeated until the system reaches a state that is good enough for the application, or until a given computation budget has been exhausted.

===The neighbours of a state===

===城市的邻居The neighbours of a state===

Optimization of a solution involves evaluating the neighbours of a state of the problem, which are new states produced through conservatively altering a given state. For example, in the [[travelling salesman problem]] each state is typically defined as a [[permutation]] of the cities to be visited, and its neighbours are the set of permutations produced by reversing the order of any two successive cities. The well-defined way in which the states are altered to produce neighbouring states is called a "move", and different moves give different sets of neighbouring states. These moves usually result in minimal alterations of the last state, in an attempt to progressively improve the solution through iteratively improving its parts (such as the city connections in the traveling salesman problem).

Optimization of a solution involves evaluating the neighbours of a state of the problem, which are new states produced through conservatively altering a given state. For example, in the [[travelling salesman problem]] each state is typically defined as a [[permutation]] of the cities to be visited, and its neighbours are the set of permutations produced by reversing the order of any two successive cities. The well-defined way in which the states are altered to produce neighbouring states is called a "move", and different moves give different sets of neighbouring states. These moves usually result in minimal alterations of the last state, in an attempt to progressively improve the solution through iteratively improving its parts (such as the city connections in the traveling salesman problem).

===Acceptance probabilities===

===接受概率Acceptance probabilities===

The probability of making the [[state transition|transition]] from the current state <math>s</math> to a candidate new state <math>s'</math> is specified by an ''acceptance probability function'' <math>P(e, e', T)</math>, that depends on the energies <math>e = E(s)</math> and <math>e' = E(s')</math> of the two states, and on a global time-varying parameter <math>T</math> called the ''temperature''.  States with a smaller energy are better than those with a greater energy.  The probability function <math>P</math> must be positive even when <math>e'</math> is greater than <math>e</math>.  This feature prevents the method from becoming stuck at a local minimum that is worse than the global one.

The probability of making the [[state transition|transition]] from the current state <math>s</math> to a candidate new state <math>s'</math> is specified by an ''acceptance probability function'' <math>P(e, e', T)</math>, that depends on the energies <math>e = E(s)</math> and <math>e' = E(s')</math> of the two states, and on a global time-varying parameter <math>T</math> called the ''temperature''.  States with a smaller energy are better than those with a greater energy.  The probability function <math>P</math> must be positive even when <math>e'</math> is greater than <math>e</math>.  This feature prevents the method from becoming stuck at a local minimum that is worse than the global one.

考虑到这些性质，因为温度<math>T</math>对系统能量变化很敏感，所以它在控制系统状态<math>s</math>的演化方面起着至关重要的作用。准确地说，对于一个庞大的<math>T</math>来说，<math>s</math>的变化对比粗略的能量变化更为敏感，当<math>T</math>很小时，它对精细能量变化更为敏感。

考虑到这些性质，因为温度<math>T</math>对系统能量变化很敏感，所以它在控制系统状态<math>s</math>的演化方面起着至关重要的作用。准确地说，对于一个庞大的<math>T</math>来说，<math>s</math>的变化对比粗略的能量变化更为敏感，当<math>T</math>很小时，它对精细能量变化更为敏感。

===The annealing schedule===

===退火时间表The annealing schedule===

{{multiple image

{{multiple image