Deterministic Annealing

Deterministic Annealing operates in a way that is similar to SA, except that a deterministic rule is used for the acceptance of a move. Two standard implementations of this technique are threshold accepting [Dueck and Scheurer 1990] and record to record travel [Dueck 1993].

At iteration t of a threshold accepting algorithm, solution ${x_{i+1}}$ is accepted if ${f(x_{i+1}) \le f(x_{i})+ \theta_{1}}$, where ${\theta_{1}}$ is a user controlled parameter. In record-to-record travel a record is the best solution ${x^{*}}$ encountered during the search. At iteration t, solution ${x_{i+1}}$ is accepted if ${f(x_{i+1}) \le \theta_{2}f(x_{i})}$, where ${\theta_{2}}$ is a user controlled parameter slightly larger then 1.