模拟退火算法(Simulated Annealing,SA)是一种基于概率的优化算法,其思
想来源于固体退火原理。在固体退火过程中,首先将固体加热至充分高的温
度,使其内部粒子随温度升高变为无序状态,内能增大。然后让其徐徐冷却,
粒子逐渐趋于有序,在每个温度都达到平衡态,最后在常温时达到基态,内能
减为最小。模拟退火算法就是模拟这样的过程来达到寻找全局最优解的目的。
模拟退火算法包含 Metropolis 算法和退火过程两部分,分别对应内循环和外循
环。内循环是在当前温度下,通过随机产生新解并计算目标函数差来接受或拒
绝新解,从而达到该温度下的平衡状态。外循环则是通过不断降低温度来控制
算法的进程,直至达到终止条件。
在模拟退火算法中,初始解是算法迭代的起点,可以任意选择一个初始解。然
后,通过不断迭代产生新解,并根据 Metropolis 准则来判断是否接受新解。
Metropolis 准则是一种基于概率的接受准则,它允许算法在搜索过程中以一定
的概率接受比当前解更差的解,从而避免陷入局部最优解。
模拟退火算法的优点是能够以一定的概率跳出局部最优解,寻找全局最优解。
但是,由于算法是基于随机搜索的,因此无法保证在有限的时间内找到全局最
优解。此外,算法的性能也受到初始温度、降温速率、终止条件等参数的影
响,需要根据具体问题进行调整。
以下为 MATLAB 语言的模拟退火算法, 实现了 tsp 问题的求解和绘图
function sa_tsp()
% 参数设置
numCities = 20; % 城市数量
maxIter = 2000; % 最大迭代次数
startTemp = 100; % 初始温度
endTemp = 0.01; % 结束温度
coolingRate = 0.99; % 冷却率
% 随机生成城市坐标
cities = rand(numCities, 2);
% 初始化
currentSolution = randperm(numCities); % 随机初始解
bestSolution = currentSolution;
bestCost = calculateTSPCost(cities, currentSolution);
costHistory = zeros(maxIter, 1);
currentCost = bestCost;
temp = startTemp;