Simulated annealing algorithm
The annealing algorithm is derived from the principle of solid annealing, and the solid is warmed to sufficiently high, and then slowly cool, when he is warmed, the internal particles are increased by the temperature of the temperature to increase, and the particles are gradually increasing. The tendy order, each temperature has a balance state, and finally reaches the ground state at normal temperature, and can be minimized. According to Metropolis guidelines, the probability that the particles tend to balance when the temperature T is E-ΔE / (KT), where E is internal energy at the temperature T, ΔE is a change amount, k is the Boltzmann constant. With solid annealing simulation combination, the internal energy E simulates the target function value F, and the temperature T evolves into a control parameter T, that is, analog annealing algorithm for solving combined optimization problem: starts with the initial solution I and the control parameter start, Iteration of current solution "Generates new solution → calculation target function → acceptance or discard", gradually attenuating the T value, the current solution when the algorithm terminates is an approximate optimal solution, which is based on Monte Carro to solve the solution. A heuristic random search process. The annealing process is controlled by the cooling schedule (COOLING SCHEDULE), including the initial value T of the control parameter and its attenuation factor ΔT, the iterative number L and the stop condition S when each T value is. 1. Model annealing algorithm of analog annealing algorithm can be broken down into solution space, target function, and initial solution. The basic idea of simulation annealing: (1) Initialization: The initial temperature T (sufficient), the initial solution state S (is the starting point of the algorithmrease), the number of iterations of each T value L (2) to k = 1, ..., L Substation (3) to 6: (3) Generate new solution S '(4) calculation increment ΔT' = c (s') - c (s), where c (s) is an evaluation function (5) If Δt '<0 accepted S' as a new current solution, the probability exp (-Δt '/ t) accepted S' as a new current solution. (6) If the termination condition is satisfied, the current solution is output as the optimal solution. End the program. Termination conditions are usually taken as a continuous number of new solutions that are not accepted. (7) T gradually decreases, and T-> 0, then turn step 2. Algorithm corresponds to dynamic demonstration diagram: The generation and acceptance of analog annealing algorithm new solution can be divided into the following four steps: The first step is to generate a new solution from the current solution from the current solution; for easy follow-up computing and acceptance , When reduced algorithm consumption, it is usually selected from the current new solution to generate new solutions, such as replacing, interchangeing, interchangeing, interchangeing, etc. constituting a new solution, etc., noted that the change method for generating new solution is determined The neighborhood structure of the current new solution is thus a certain impact on the selection of the cooling schedule. The second step is to calculate the difference between the target function corresponding to the new solution. Because the target function difference is only generated by the conversion portion, the calculation of the target function difference is preferably calculated by increment. The fact shows that this is the fastest way to calculate the difference between the target function. The third step is to determine if the new solution is accepted, the basis for judging is a acceptance criterion, the most common acceptance criterion is Metropo1IS Guidelines: If Δt '<0 accepts s' as a new current solution S, otherwise, in probability exp (- ΔT '/ t) Accept S' as a new current solution S. The fourth step is that when the new solution is determined, use the new solution to the current solution, this only needs to be implemented in the current solution corresponding to the change portion of the new solution, and correct the target function value. At this time, the current solution realizes one iteration. The next round of tests can be started on this basis. When the new solution is determined to be abandoned, the next round of test is continued on the basis of the original. The annealing algorithm is independent of the initial value, and the algorithm is independent of the initial solution state S (the starting point of the algorithm is ascended); the annealing algorithm has asymptotic convergence, which has been in theory is a probability L converged Global Optimization Algorithm; Simulated Annealing Algorithm has parallelism.
2 Simple application of an annealing algorithm as analog annealing algorithm application, discussing the carbarrative problem (TSP is tsp): It is available in N cities, using digital 1, ..., n. The distance between the city i and the city J is D (i, j) i, j = 1, ..., n. The TSP problem is to find a loop that travels every other city, and its total path is the shortest .. Solving the simulation annealing algorithm model of TSP can be described as follows: Solutions Space Space S is all loops that have access to each city, which is {1, ..., N}, all loop arrangements, members of S. (W1, W2, ..., WN) and remember WN 1 = W1. The initial solution can be selected as (1, ..., n) Target function At this time, the target function is to access the total length of the path of all cities or the price function: We request the minimum of this cost function. The new solution produces two phases of two phases between 1 and n, if K
According to the above analysis, a pseudo-schedule for solving TSP issues can be written for an annealing annealing algorithm: Procedure Tspsa: Begin init-of -t; {t is the initial temperature} S = {1, ..., n}; {s initial value } Termination = false; while termination = false begin for i = 1 to l do begin generate (s'Form s); {Generate a new loop S '}} Δt: = f (s')) - f (s ); {f (s) is the length of the path} IF (Δt <0) OR (EXP (-Δt / t)> Random-Of- [0, 1]) s = s'; if the-halt-condition-is -True THEN TERMINATION = True; End; T_Lower; END; END analog annealing algorithm is widely used, can solve the maximum cutoff problem (Max Cut Problem), 0-1 Backpack Problem (Zero One Knapsack Problem), Coloring problem, scheduling problem, and more.
3 The parameter control problem of the annealing algorithm is a wide range of applications, which can solve the NP full problem, but its parameters are difficult to control, and the main issues have the following three points: (1) The initial value setting of the temperature T. The initial value setting of temperature T is one of the important factors affecting the overall search performance of analog annealing algorithm. The initial temperature is high, and the global optimal solution is searched, but there is a large amount of calculation time; contrary, save Computation time, but global search performance may be affected. In the actual application process, the initial temperature generally needs several adjustments based on the experimental results. (2) Annealing speed problem. The global search performance of analog annealing algorithm is closely related to annealing speed. In general, "full" search (annealing) at the same temperature is quite necessary, but this requires calculation time. In practical applications, a reasonable annealing balance condition is set for the nature and characteristics of specific problems. (3) Temperature management problem. Temperature management issues are also one of the problems that are difficult to deal with an annealing algorithm. In practical applications, since the problem of calculation complexity must be considered, the cooling mode as shown below is often used: T (t 1) = k x t (t) formula is a constant that is slightly less than 1.00. , T is the number of times the temperature drop has just started research, and the program is implemented in progress, please pay attention (to be continued).
