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 minimized. Annealing is the process of heating a solid to a high enough temperature so that the molecules are randomly arranged, then cooling it gradually to cool it, and finally the molecules are arranged in a low energy state so that the solid reaches some stable state.

2 physical annealing process heating process — enhance the thermal movement of particles, eliminate the system may exist in the original non-uniform state; Isothermal process — for the closed system with constant temperature and heat exchange with the environment, the spontaneous change of the system state is always in the direction of free energy reduction, when the free energy reaches the minimum, the system reaches the equilibrium state; Cooling process – to weaken the thermal motion of particles and gradually become orderly, the energy of the system is gradually reduced, so as to obtain a low energy crystal structure.

Annealing in thermodynamics refers to the physical phenomenon that occurs when the object gradually cools down: the lower the temperature, the lower the energy state of the object, and when it reaches a low enough point, the liquid begins to condense and crystallize. In the crystallized state, the energy state of the system is the lowest. When cooling slowly, the lowest energy state can be reached. But if it is cooled too fast, it can lead to an amorphous form that is not the lowest energy state.

By imitating the annealing phenomenon in nature, the similarity between the annealing process of solid matter in physics and the general optimization problem is used to find the global optimal solution randomly in the solution space, starting from a certain initial temperature, with the continuous drop of temperature, combined with the probability jump characteristic.

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

4. Calculation steps of simulated annealing algorithm

Ii. Source code

clc;
clear;
close all;
%%
tic
T0=1000; % Initial temperature Tend=1e-3; % termination temperature L=500; % Number of iterations (chain length) at each temperature q=0.9; % cooling rate %% Loading data Load CityPosition1; %% D=Distanse(X); % calculate distance matrix N=size(D,1); Initial solution S1= Randperm (N); DrawPath(S1,X) DrawPath(S1,X)0.0001) %% Output path and total distance of random solution disp('A random value in the initial population :')
OutputPath(S1);
Rlength=PathLength(D,S1);
disp(['Total distance:',num2str(Rlength)]); %% Number of iterations Time Time=ceil(double(solve(['1000 * (0.9) ^ x =',num2str(Tend)])));
count=0; % iteration count Obj=zeros(Time,1); % Target value matrix initialization track=zeros(Time,N); % The optimal path matrix initializes %% iteration per generationwhile T0>Tend
    count=count+1; % Update iterations Temp =zeros(L,N+1);
    for k=1:L %% generate new solution S2=NewAnswer(S1); The Metropolis rule determines whether to accept a new solution [S1,R]=Metropolis(S1,S2,D,T0); %Metropolis sampling algorithm temp(k,:)=[S1 R]; % Record a route and its distance end %% optimization process iteration diagramfigure
plot(1:count,Obj)
xlabel('Number of iterations')
ylabel('distance')
title('Optimization process')%% optimal solution path graphDrawPath(track(end,:),X)%% outputs the route and total distance of the optimal solutiondisp('Optimal solution :')
S=track(end,:);
p=OutputPath(S);
disp(['Total distance:',num2str(PathLength(D,S))]);
disp('-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -') toc function D=Distanse(a) %% D=Distanse(a) %% D=Distanse(a) %% D=Distanse(a) %% D=Distanse(a) %%1);
D=zeros(row,row);
for i=1:row
    for j=i+1:row
        D(i,j)=((a(i,1)-a(j,1)) ^2+(a(i,2)-a(j,2)) ^2) ^0.5;
        D(j,i)=D(i,j);
    end
end
function varargout = dsxy2figxy(varargin)
if length(varargin{1= =})1 && ishandle(varargin{1})... &&strcmp(get(varargin{1},'type'),'axes')   
    hAx = varargin{1};
    varargin = varargin(2:end);
else
    hAx = gca;
end;
if length(varargin) = =1
    pos = varargin{1};
else
    [x,y] = deal(varargin{:});
end
axun = get(hAx,'Units');
set(hAx,'Units'.'normalized'); 
axpos = get(hAx,'Position');
axlim = axis(hAx);
axwidth = diff(axlim(1:2));
axheight = diff(axlim(3:4));
if exist('x'.'var')
    varargout{1} = (x - axlim(1)) * axpos(3) / axwidth + axpos(1);
    varargout{2} = (y - axlim(3)) * axpos(4) / axheight + axpos(2);
else
    pos(1) = (pos(1) - axlim(1)) / axwidth * axpos(3) + axpos(1);
    pos(2) = (pos(2) - axlim(3)) / axheight * axpos(4) + axpos(2);
    pos(3) = pos(3) * axpos(3) / axwidth;
    pos(4) = pos(4) * axpos(4 )/ axheight;
    varargout{1} = pos;
end
set(hAx,'Units',axun)

Copy the code

3. Operation results

Fourth, note

Version: 2014 a