A list,

Given the longitude and latitude of 34 provincial capitals (including municipalities directly under the central Government) in China, it is required to travel from Beijing to 34 cities and finally return to Beijing. The simulated annealing algorithm is used to find the shortest path.

Application background of simulated annealing algorithm

Simulated annealing algorithm was proposed in 1982. Kirkpatrick et al. were the first to recognize the similarities between solid annealing processes and optimization problems. They were also inspired by Metropolis et al. ‘s simulation of the process by which solids reach thermal equilibrium at constant temperature. By introducing Metropolis algorithm into the optimization process, we finally get an iterative optimization algorithm to Metropolis algorithm, which is similar to solid annealing process and is called “simulated annealing algorithm”.

Simulated annealing algorithm is a random search algorithm suitable for solving large-scale combinatorial optimization problems. At present, simulated annealing algorithm has achieved satisfactory results in solving TSP, VLSI circuit design and other combinatorial optimization problems. The combination of simulated annealing algorithm with other computational intelligence methods in modeling and optimization of various complex systems has been paid more and more attention, and has gradually become an important direction of development.

2 introduction to simulated annealing algorithm









3 parameters of simulated annealing algorithm

Simulated annealing is a kind of optimization algorithm, it can’t exist independently, needs to have a applications, of which temperature is simulated annealing to optimize the parameters, if it is applied to clustering analysis, so the clustering analysis has a certain or a few parameters are optimized, and the parameters, or parameter set is represented by the temperature. It could be some index, some correlation, some distance, etc.

Ii. Source code

clc
clear;
%% 
load('china.mat'); plotcities(province, border, city); % draw map cityAccount =length(city); Dis =distancematrix(city)% distancematrix route =randperm(cityaccount); % Path format temperature=1000; % Initialization temperature cooling_rate=0.95; % Temperature drop rate item=1; % Number of cycles used to control cooling distance= totalDistance (route,dis); % Total path length temperature_iterations =1;
% This is a flag used to plot the current route after 200 iterations
plot_iterations = 1; plotroute(city, route, distance,temperature); % draw the route %%while temperature>1.0% temp_route=change(route,'reverse'); % produces a disturbance. Molecular sequence change %fprintf("%d\n",temp_route(1)); temp_distance=totaldistance(temp_route,dis); Dist =temp_distance-distance; % The difference between two pathsif(dist<0)||(rand < exp(-dist/(temperature)))
        route=temp_route;
        distance=temp_distance;
        item=item+1;
        temperature_iterations=temperature_iterations+1;
        plot_iterations=plot_iterations+1;
    end
    if temperature_iterations>=10
        temperature=cooling_rate*temperature;
        temperature_iterations=0;
    end
    
    if plot_iterations >= 20plotroute(city, route, distance,temperature); % Go to plot_iterations =0;
    end
%     fprintf("it=%d",item); End function totaldis = TotalDistance (route,dis)% Pass in the distance matrix and the current route % totalDistancefprintf("%d\n",route(1));
totaldis=dis(route(end),route(1));
% totaldis=dis(route(end),route(1));
for k=1:length(route)- 1
    totaldis=totaldis+dis(route(k),route(k+1)); End function h = plotCities (province, border, city) % plotCities % h = plotCities (province, border, border, city) draw themap of China, and return 
% the route handle.

global h;
% draw the map of China
plot(province.long, province.lat, 'color'[0.7.0.7.0.7])
hold on
plot(border.long  , border.lat  , 'color'[0.5.0.5.0.5].'linewidth'.1.5);
 

% plot a NaN route, and global the handle h.
h = plot(NaN, NaN, 'b-'.'linewidth'.1);

% plot cities as green dots
plot([city(2:end).long], [city(2:end).lat], 'o'.'markersize'.3.'MarkerEdgeColor'.'b'.'MarkerFaceColor'.'g');
% plot Beijing as a red pentagram
 
axis([70 140 15 55]);
Copy the code

3. Operation results

Fourth, note

Version: 2014 a