正文

tsp基于matlab模拟退火算法求解31城市旅行商问题含matlab源码1148期(代码片段)

紫极神光  紫极神光  2022-12-11  787

关键词：

一、简介

1 模拟退火算法原理
模拟退火算法来源于固体退火原理，是一种基于概率的算法，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，固体达到某种稳定状态。

2 物理退火过程
加温过程——增强粒子的热运动，消除系统原先可能存在的非均匀态；
等温过程——对于与环境换热而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态；
冷却过程——使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。

热力学中的退火现象指物体逐渐降温时发生的物理现象：温度越低，物体的能量状态越低，到达足够的低点时，液体开始冷凝与结晶，在结晶状态时，系统的能量状态最低。缓慢降温时，可达到最低能量状态；但如果快速降温，会导致不是最低能态的非晶形。

模仿自然界退火现象而得，利用了物理中固体物质的退火过程与一般优化问题的相似性从某一初始温度开始，伴随温度的不断下降，结合概率突跳特性在解空间中随机寻找全局最优解。

3 模拟退火算法的模拟要求
1 初始温度足够高
2 降温过程足够慢
3 终止温度足够低

4 模拟退火算法的计算步骤

二、源代码

%%%%%%%%%%%%%%%%%%%%%%模拟退火算法解决TSP问题%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%初始化%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
clear all;                      %清除所有变量
close all;                      %清图
clc;                            %清屏
C=[1304 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];                  %31个省会城市坐标
n=size(C,1);                     %TSP问题的规模,即城市数目
T=100*n;                         %初始温度
L=100;                           %马可夫链长度
K=0.99;                          %衰减参数
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%城市坐标结构体%%%%%%%%%%%%%%%%%%%%%%%%%%

for i=1:n
    city(i).x=C(i,1);
    city(i).y=C(i,2);
end
l=1;                             %统计迭代次数
len(l)=func3(city,n);            %每次迭代后的路线长度
figure(1); 
while T>0.001                    %停止迭代温度
    %%%%%%%%%%%%%%%%多次迭代扰动，温度降低之前多次实验%%%%%%%%%%%%%%%
    for i=1:L            
        %%%%%%%%%%%%%%%%%%%计算原路线总距离%%%%%%%%%%%%%%%%%%%%%%%%%
        len1=func3(city,n);         
        %%%%%%%%%%%%%%%%%%%%%%%%%产生随机扰动%%%%%%%%%%%%%%%%%%%%%%%
        %%%%%%%%%%%%%%%%随机置换两个不同的城市的坐标%%%%%%%%%%%%%%%%%
        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;
      
        %%%%%%%%%%%%新路线好于旧路线，用新路线代替旧路线%%%%%%%%%%%%%%  
        if delta_e<0        
            city=tmp_city;
        else
            %%%%%%%%%%%%%%%%%%以概率选择是否接受新解%%%%%%%%%%%%%%%%%
            if exp(-delta_e/T)>rand()
                city=tmp_city;      
            end
        end
    end
    
    %%%%%%%%%%%%%%%%%%%%%%%%%计算新路线距离%%%%%%%%%%%%%%%%%%%%%%%%%%
    len(l)=func3(city,n); 
    %%%%%%%%%%%%%%%%%%%%%%%%%%%温度不断下降%%%%%%%%%%%%%%%%%%%%%%%%%%
   
    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(['优化最短距离:',num2str(len(l))]);
    hold off;
    pause(0.005);
end

三、运行结果

四、备注

版本：2014a

tsp基于matlabgui模拟退火算法求解旅行商问题含matlab源码1083期

一、TSP简介旅行商问题，即TSP问题（TravelingSalesmanProblem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次... 查看详情

tsp基于matlabgui模拟退火+蚁群+遗传算法求解旅行商问题含matlab源码1611期(代码片段)

一、TSP简介旅行商问题，即TSP问题（TravelingSalesmanProblem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是... 查看详情

tsp基于matlab模拟退火算法求解旅行商问题含matlab源码1129期(代码片段)

...算法原理模拟退火算法来源于固体退火原理，是一种基于概率的算法，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，... 查看详情

tsp基于matlab遗传算法求解31城市旅行商问题含matlab源码1150期(代码片段)

一、简介1遗传算法概述遗传算法（GeneticAlgorithm，GA）是进化计算的一部分，是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。该算法简单、通... 查看详情

tsp基于matlab免疫算法求解31城市旅行商问题含matlab源码1149期(代码片段)

一、简介任何一个优化问题可以转化为一个函数问题，因此生物智能算法广泛应用，同样生物免疫算法（AIA）也是一种模拟达尔文生物进化的一个新型智能算法，生物免疫算法（AIA）根据生物系统抗体... 查看详情

tsp基于matlab蚁群算法求解31城市旅行商问题含matlab源码1147期(代码片段)

一、简介1概要模拟蚂蚁觅食行为（最短路径原理）设计的算法。讲蚂蚁群觅食的特点抽象出来转化成数学描述。•蚁群算法(AntColonyAlgorithm,ACA)由MarcoDorigo于1992年在他的博士论文中首次提出。•蚂蚁在寻找食物源时，... 查看详情

毕设题目：matlab智能算法tsp（旅行商）

...重点。2现成案例（代码+参考文献）1.【MTSP】基于matlabGUI遗传算法求解多旅行商问题【含Matlab源码935期】2.【MTSP】基于matlab遗传和粒子群算法求解多旅行商问题【含Matlab源码1156期】3.【MTSP】基于matlab遗传算法求解多旅... 查看详情

模拟退火算法求解tsp问题(python)(代码片段)

...多，比如贪婪算法、Dijkstra算法等等，本文参考《MATLAB智能算法30个案例分析（第2版）》中第19章的内容，利用模拟退火算法求解TSP问题并给出了python实现版本TSP问题描述如下：👉TSP模拟退火查看详情

tsp基于matlab禁忌搜索算法求解31城市旅行商问题含matlab源码1143期(代码片段)

一、简介1局部领域搜索又称爬山启发式算法，从当前的节点开始，和周围的邻居节点的值进行比较。如果当前节点是最大的，那么返回当前节点，作为最大值(即山峰最高点)；反之就用最高的邻居节点替换当... 查看详情

tsp基于matlab遗传算法求解13城市旅行商问题含matlab源码1255期

tsp基于matlab遗传算法求解中国35省会城市旅行商问题含matlab源码1222期

tsp基于matlab蜜蜂算法求解旅行商问题含matlab源码1248期

tsp基于matlab遗传算法求解旅行商问题含matlab源码1337期

tsp基于matlabgui遗传算法求解旅行商问题含matlab源码1333期

tsp基于matlab改进的人工鱼群算法求解旅行商问题含matlab源码1479期

tsp基于matlabgui粒子群算法求解旅行商问题含matlab源码1334期

matlab模拟退火算法（sa）求解tsp问题(代码片段)

...心1.2.1三个函数1.2.2两个准则1.3SA优缺点1.3.1优点1.3.2缺点2.基于SA解决TSP问题2.1tsp.m2.2CalDist.m2.3drawTSP.m2.4simulated_annealing.m2.5结果1.SA概述1.1SA介绍SA的提出：模拟退火算法最早的思想由Metropolies等（1953&# 查看详情