模拟退火算法的应用

一：退火算法的应用领域及示例

作为模拟退火算法应用，讨论旅行商问题(Travelling Salesman Problem,简记为TSP)：设有n个城市，用数码1,…,n代表。城市i和城市j之间的距离为d(i,j) i,j=1,…,n．TSP问题是要找遍访每个域市恰好一次的一条回路，且其路径总长度为最短.。求解TSP的模拟退火算法模型可描述如下：解空间 解空间S是遍访每个城市恰好一次的所有回路，是{1,……,n}的所有循环排列的集合,S中的成员记为(w1,w2,……,wn)，并记wn+1= w1。初始解可选为(1,……,n)目标函数 此时的目标函数即为访问所有城市的路径总长度或称为代价函数：我们要求此代价函数的最小值。新解的产生 随机产生1和n之间的两相异数k和m,若km,则将(w1,w2,…,wm,wm+1,…,wk,…,wn)变为：(wm,wm-1,…,w1,wm+1,…,wk-1,wn,wn-1,…,wk).上述变换方法可简单说成是“逆转中间或者逆转两端”。也可以采用其他的变换方法，有些变换有独特的优越性，有时也将它们交替使用，得到一种更好方法。代价函数差 设将(w1,w2,……,wn)变换为(u1,u2,……,un)，则代价函数差为：根据上述分析，可写出用模拟退火算法求解TSP问题的伪程序：Procedure TSPSA:begininit-of-T; { T为初始温度}S={1,……,n}; {S为初始值}termination=false;while termination=falsebeginfor i=1 to L dobegingenerate(S′form S); { 从当前回路S产生新回路S′}Δt:=f(S′））-f(S);{f(S)为路径总长}IF（Δt<0) OR (EXP(-Δt/T)>Random-of-[0,1])S=S′；IF the-halt-condition-is-TRUE THENtermination=true;End;T_lower;End;End模拟退火算法的应用很广泛，可以较高的效率求解最大截问题(Max Cut Problem)、0-1背包问题(Zero One Knapsack Problem)、图着色问题(Graph Colouring Problem)、调度问题(Scheduling Problem)等等。 模拟退火算法的应用很广泛，可以求解NP完全问题，但其参数难以控制，其主要问题有以下三点：⑴ 温度T的初始值设置问题。温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一、初始温度高，则搜索到全局最优解的可能性大，但因此要花费大量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响。实际应用过程中，初始温度一般需要依据实验结果进行若干次调整。⑵ 退火速度问题。模拟退火算法的全局搜索性能也与退火速度密切相关。一般来说，同一温度下的“充分”搜索（退火）是相当必要的，但这需要计算时间。实际应用中，要针对具体问题的性质和特征设置合理的退火平衡条件。⑶ 温度管理问题。温度管理问题也是模拟退火算法难以处理的问题之一。实际应用中，由于必须考虑计算复杂度的切实可行性等问题，常采用如下所示的降温方式：T(t+1)=k×T(t)式中k为正的略小于1.00的常数,t为降温的次数 优点：计算过程简单，通用，鲁棒性强，适用于并行处理，可用于求解复......余下全文>>

二：模拟退火算法的简介

模拟退火算法(Simulated Annealing，SA)最早的思想是由N. Metropolis 等人于1953年提出。1983 年,S. Kirkpatrick 等成功地将退火思想引入到组合优化领域。它是基于Monte-Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法从某一较高初温出发，伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。模拟退火算法是一种通用的优化算法，理论上算法具有概率的全局优化性能,目前已在工程中得到了广泛应用，诸如VLSI、生产调度、控制工程、机器学习、神经网络、信号处理等领域。模拟退火算法是通过赋予搜索过程一种时变且最终趋于零的概率突跳性，从而可有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法。

三：改进模拟退火算法与传统模拟退火算法相比优缺点是什么，如有缺点该如何改进

该算法是一种新的随机搜索方法,它是近年来提出的一种适合于解决大规模组合优化问题的通用而有效的近似算法。与以往的近似算法相比,模拟退火算法具有描述简单、使用灵活、运用广泛、运行效率高和较少受到初始条件约束等优点

四：模拟退火和遗传算法都可以解决什么问题啊

模拟退火算法和遗传算法，包括禁忌搜索算法，蚁群算法等都可以用来求解优化问题。这些算法的一个特点是虽然对于一些复杂问题，比如说DP难题，可能不好找到最优解（理论上找到最优解是可以的），但是可以以较高的效率找到满意解。

五：实际问题中可以用到模拟退火算法的有哪些

模拟退火是一种优化算法，它本身是不能独立存在的，需要有一个应用场合，其中温度就是模拟退火需要优化的参数，如果它应用到了聚类分析中，那么就是说聚类分析中有某个或者某几个参数需要优化，而这个参数，或者参数集就是温度所代表的。它可以是某项指标，某项关联度，某个距离等等

六：谁能给我举一个模拟退火算法MATLAB源代码的简单例子 15分

clear

clc

a = 0.95

k = [5;10;13;4;3;11;13;10;8;16;7;4];

k = -k;% 模拟退火算法是求解最小值，故取负数

d = [2;5;18;3;2;5;10;4;11;7;14;6];

restriction = 46;

num = 12;

sol_new = ones(1,num); % 生成初始解

E_current = inf;E_best = inf;

% E_current是当前解对应的目标函数值（即背包中物品总价值）；

% E_new是新解的目标函数值；

% E_best是最优解的

sol_current = sol_new; sol_best = sol_new;

t0=97; tf=3; t=t0;

p=1;

while t>=tf

for r=1:100

%产生随机扰动

tmp=ceil(rand.*num);

sol_new(1,tmp)=~sol_new(1,tmp);

%检查是否满足约束

while 1

q=(sol_new*d <= restriction);

if ~q

p=~p;%实现交错着逆转头尾的第一个1

tmp=find(sol_new==1);

if p

sol_new(1,tmp)=0;

else

sol_new(1,tmp(end))=0;

end

else

break

end

end

% 计算背包中的物品价值

E_new=sol_new*k;

if E_new

E_current=E_new;

sol_current=sol_new;

if E_new

% 把冷却过程中最好的解保存下来

E_best=E_new;

sol_best=sol_new;

end

else

if rand

E_current=E_new;

sol_current=sol_new;

else

sol_new=sol_current;

end

end

end

t=t.*a;

end

disp('最优解为：')

sol_best

disp('物品总价值等于：')

val=-E_best;

disp(val)

disp('背包中物品重量是：')

disp(sol_best * d)...余下全文>>

七：为什么说模拟退火算法优于局部搜索算法

该算法是一种新的随机搜索方法,它是近年来提出的一种适合于解决大规模组合优化问题的通用而有效的近似算法。与以往的近似算法相比,模拟退火算法具有描述简单、使用灵活、运用广泛、运行效率高和较少受到初始条件约束等优点

八：模拟退火算法和粒子群算法的优缺点有那些？具体点，谢啦

退火优点：计算过程简单，通用，鲁棒性强，适用于并行处理，可用于求解复杂的非线性优化问题。缺点：收敛速度慢，执行时间长，算法性能与初始值有关及参数敏感等缺点。

PSO:演化计算的优势在于可以处理一些传统方法不能处理的例子例如不可导的节点传递函数或者没有梯度信息存在。但是缺点在于：在某些问题上性能并不是特别好。2. 网络权重的编码而且遗传算子的选择有时比较麻烦

九：模拟退火算法matlab怎样找到下一个新解

我刚刚回答了一个额。

从代码角度来说，就是2个循环，一个总温度外循环（足够大，并逐渐减小），另一个内部循环（使其达到该特定温度下的平衡，怎么算平衡自己定义的）。很多书都说外部的总温度外循环，却忽略了内部循环，内部循环值应该多大，我也很模糊。

十：遗传算法、数值算法、爬山算法、模拟退火 各自的优缺点

遗传算法：优点是能很好的处理约束，能很好的跳出局部最优，最终得到全局最优解，全局搜索能力强；缺点是收敛较慢，局部搜索能力较弱，运行时间长，且容易受参数的影响。

模拟退火：优点是局部搜索能力强，运行时间较短；缺点是全局搜索能力差，容易受参数的影恭。

爬山算法：显然爬山算法较简单，效率高，但是处理多约束大规模问题时力不从心，往往不能得到较好的解。

数值算法：这个数值算法的含义太广，你说的是哪一种数值算法？多数数组算法与爬山算法的有优缺点类似。

PS：望采纳！