A list,

1 principle of simulated annealing algorithm, simulated annealing algorithm is derived from the principle of solid annealing is a kind of algorithm based on probability, high solid heating to fully, then let it slowly cooling, heating, inside the solid particles with the temperature rise to disorder, internal energy increase, and slowly cooling particles become more orderly, and in each temperature to reach the equilibrium state, finally reach the ground state in normal temperature, The internal energy is reduced to the minimum. Annealing refers to the heating of a solid to a high enough temperature so that the molecules are arranged in a random state, and then gradually cooling to cool it, and finally the molecules are arranged in a low energy state, and the solid reaches a certain stable state.

2. Physical annealing process and heating process — enhance the thermal motion of particles and eliminate the non-uniform state that may exist in the system; Isothermal process — For a closed system with constant temperature and heat exchange with the environment, the spontaneous change of system state always goes in the direction of reducing free energy. When the free energy reaches the minimum, the system reaches equilibrium state. The cooling process makes the thermal motion of particles weaken and become orderly, and the energy of the system decreases gradually, so as to obtain the low energy crystal structure.

The annealing phenomenon in thermodynamics refers to the physical phenomenon that occurs when the object gradually cools down: the lower the temperature is, the lower the energy state of the object is. When the low point reaches enough, the liquid begins to condense and crystallizes. In the crystallization state, the energy state of the system is the lowest. Slow cooling, can reach the lowest energy state; But if you cool it quickly, you get an amorphous form that is not the lowest energy state.

Based on the similarity between the annealing process of solid substance in physics and the general optimization problem, the global optimal solution is found randomly in the solution space with the decreasing temperature and the probability jump characteristic.

3 Simulation requirements of simulated annealing algorithm 1 initial temperature is high enough 2 cooling process is slow enough 3 termination temperature is low enough

4 Calculation steps of simulated annealing algorithm

Ii. Source code

% % % % % % % % % % % % % % % % % % % % % % simulated annealing algorithm to solve TSP problem % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % initialization % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % clear all; % clear all variables close all; % qing figure CLC; C = [% CLS1304 2312;3639 1315;4177 2244;3712 1399;3488 1535;3326 1556; .3238 1229;4196 1044;4312  790;4386  570;3007 1970;2562 1756; .2788 1491;2381 1676;1332  695;3715 1678;3918 2179;4061 2370; .3780 2212;3676 2578;4029 2838;4263 2931;3429 1908;3507 2376; .3394 2643;3439 3201;2935 3240;3140 3550;2545 2357;2778 2826; .2370 2975];                  %31N =size(C,1); %TSP The size of the problem, i.e. the number of cities T=100*n; % Initial temperature L=100; % Markov chain length K=0.99; Attenuation parameter % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % city coordinate structure % % % % % % % % % % % % % % % % % % % % % % % % % %for i=1:n
    city(i).x=C(i,1);
    city(i).y=C(i,2);
end
l=1; % Number of statistical iterations len(l)=func3(city,n); Route length after each iteration1); 
while T>0.001% iteration temperature % % % % % % % % % % % % % % % % iterative perturbation for many times, temperature reducing experiment many times before % % % % % % % % % % % % % % %for i=1: L % % % % % % % % % % % % % % % % % % % to calculate the original route total distance % % % % % % % % % % % % % % % % % % % % % % % % % len1 = func3 - a non-class function (city, n); % % % % % % % % % % % % % % % % % % % % % % % % % produces random disturbance % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % random permutation of the coordinates of the two different cities % % % % % % % % % % % % % % % % % p1 =floor(1+n*rand());
        p2=floor(1+n*rand());
        while p1==p2
            p1=floor(1+n*rand());
            p2=floor(1+n*rand()); end tmp_city=city; tmp=tmp_city(p1); tmp_city(p1)=tmp_city(p2); tmp_city(p2)=tmp; %%%%%%%%%%%% New route is better than old route, replace old route with new route %%%%%%%%%%%%%%if delta_e<0        
            city=tmp_city;
        else%%%%%%%%%%%%%%%%%% Choose whether to accept the new solution with probability %%%%%%%%%%%%%%%%%if exp(-delta_e/T)>rand() city=tmp_city; End end end % % % % % % % % % % % % % % % % % % % % % % % % % new route distance computed % % % % % % % % % % % % % % % % % % % % % % % % % % len (l) = func3 - a non-class function (city, n); % % % % % % % % % % % % % % % % % % % % % % % % % % % temperature falling % % % % % % % % % % % % % % % % % % % % % % % % % %for i=1:n- 1
        plot([city(i).x,city(i+1).x],[city(i).y,city(i+1).y],'bo-');
        hold on;
    end
    plot([city(n).x,city(1).x],[city(n).y,city(1).y],'ro-');
    title(['Optimize the shortest distance :',num2str(len(l))]);
    hold off;
    pause(0.005);
end

Copy the code

Third, the operation result

Fourth, note

Version: 2014 a