Threshold acceptance

from Wikipedia, the free encyclopedia

Acceptance threshold (English threshold accepting , TA ) is a heuristic optimization algorithm . Techniques of this type are mostly used when the complexity of the problem, i. H. the number of possible solutions is so great that simply trying it out is unsuccessful. In addition, due to their simple structure, such methods are often used when it is unclear how a solution can be determined more easily than by trying out all possibilities - i.e. when no "clever" solution exists or is known.

The threshold acceptance algorithm was presented in 1990 by Dueck and Scheuer in Threshold accepting: a general purpose optimization algorithm appearing superior to simulated annealing (Journal of Computational Physics, 90 (1): 161-175, 1990) as a modification of the simulated cooling method (English simulated annealing ).

Another approach, the average-accepting-procedure, was developed by Bogatzki in 1998 in Factory Planning, Processes for Optimizing Machine Setup (Theory and Research Economics, Vol. 534, page 249).

algorithm

Wähle einen anfänglichen Schwellwert T > 0
Wähle einen Schwellwertfaktor TF (0 < TF < 1)
Wähle eine anfängliche Konfiguration C
C_best := C
Wiederhole bis Abbruchbedingung erfüllt
   Wähle neue Konfiguration C' (ausgehend von C)
   Falls Qualität(C') > Qualität(C_best)
      C_best := C'
   Falls Qualität(C') > Qualität(C) - T
      C := C'
   T := T * TF
Gib C_best aus

A configuration represents a possible solution to the optimization problem. The algorithm repeatedly selects a new configuration C 'by means of a small random change in the current configuration C. The suitable choice of the initial threshold value T and the factor TF with which the threshold value can be adjusted is also important shrunk every step. Here a compromise has to be made between the quality of the solution found and the computing time used.

Various criteria are conceivable as termination conditions, for example the duration of the optimization process or the quality of the solution to be achieved, or it is terminated if a minimum threshold value has been reached or if no improvement in C_best has been found within the last N steps.

Differences to simulated cooling

The difference with the simulated annealing ( simulated annealing ) is in the treatment of deterioration of the configuration found.

While the simulated annealing deterioration in the assessment of an intermediate result only with a certain - in the course of optimization shrinking - accepted probability threshold acceptance does this always the deterioration unless greater than a predetermined threshold value ( threshold ) is. This threshold value is also reduced in the course of the optimization.

The advantages of threshold acceptance compared to simulated cooling therefore arise primarily with regard to the running time. The threshold acceptance dispenses with the determination of a random number and the complex calculation of the exponential function and can therefore try out different configurations more quickly.

A general superiority of the threshold acceptance with regard to the solution quality compared to the simulated cooling could not be shown under comparable conditions.

literature

  • G. Dueck and T. Scheuer: Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing . In: Journal of Computational Physics . tape 90 , 1990, pp. 161-175 , doi : 10.1016 / 0021-9991 (90) 90201-B .
  • I. Althöfer and K.-U. Koschnick: On the convergence of “Threshold Accepting” . In: Applied Mathematics and Optimization . tape 24 , 1991, pp. 183-195 , doi : 10.1007 / BF01447741 .
  • Bogatzki, Arnd: Factory planning - method for optimizing the machine installation. S. Roderer Verlag, Regensburg 1998, ISBN 3-89073-234-8
  • Kinnebrock, Werner: Optimization with genetic and selective algorithms , Oldenbourg Verlag, Munich 1994, ISBN 3-486-22697-5