用MATLAB实现模拟退火算法

模

拟

退

火

算

法

及

其

MATLAB实现模拟退火6.1算法基

本

理

论6.2算

法

的MATLAB

实

现6.3应用实例模

拟

退

火

算

法

及其MATLAB第

6

章实

现简

单

了

解

退

火

算

法

特

点介绍

模

拟退

火

前，

先

介

绍

爬山

算

法

。爬山算法是一种简单的贪心搜索算法，

该算法每次从当前解的临近解空间中选择一个最优解作为当前解，

直到达到

一

个

局

部

最

优

解

。简

单

了

解

退

火

算

法

特

点爬

山

算

法如图所示：

假设C

点为当前解，爬山算法搜索到A

点这个局部最优解就会停止搜索，

因为在A

点无

论向那个方向小幅度移动都不能得到更优的解。模拟退火

算

法在搜索到局部最优解A

后，会以一定的概率接受到E

的移动。也许经过几次这样的不是局部最优的移动后会

到

达D点，于是就跳

出

了局部最大值A。6.1

算法基本理论一、算法概述工程中许多实际优化问题的目标函数都是非凸的，

存在许多局部最优解。求解全

局

优

化问题的方法可

分

为

两

类

：确定性方法和随机性方法。确定性算法适用于求解具有一些特殊特征的问题，

而梯度法和一般的随机搜索方法则沿着目标函数下降方

向搜索，

因此常常陷入局部而非全局最优解

。6.1

算法基本理论一

、

算

法

概

述模拟退火算法(

SA)

是一种通用概率算法。用来

在一个大的搜索空间内寻找问题的最优解。1953年

，Metropolis等提出了模拟退火的思想。1983

年，Kirkpatrick等将SA引入组合优化领域。6.1

算法基本理论二

、

基

本

思

想退火

，俗称

固体降

温先把固体加热至足够高温，使固体中所有粒子处于无序的状态，

然后将温度缓慢下降，

粒子渐渐有序，

这样只要温度上升得足够高，冷却过程足够慢，则所

有粒子

最

终

会处于

最

低能

态

。算法试图随着控制参数T的降低，

使目标函

数

值f

(

内

能E)

也逐渐降低，

直至趋于全局最小

值

(

退

火

中

低

温

时

的

最

低

能

量

状

态

)

,

算

法

工

作

过

程

就

像

固

体

退

火

过

程

一

样

。模拟退火退火解粒子状态最优解能

量

最

低的

状

态目

标

函

数

f内能控制参数温度T6.1

算法基本理论模拟退火算法的由来6.1

算法基本理论Metropolis准

则—

以

概

率

接

受

新

状

态若在温度T,当前状态i(解1)

→新状态

j(解2)随机数，则仍接受状态j

为当前状态；若不

成

立，则保

留

状

态I

为当前状态

。若E;(目标函数f₂)<Ei(fi),若E;>E₁,

概率则接受j为当前状态；大于(0,1)区间的6.1

算法基本理论Ej>Ei(

更差的解)时，O<P<1,P随着T

的减小而减小；Ej-EiKTP

二

e当前状态的内能新状态的内能温度在高温下，

可接受与当前状态能量差

较

大的新

状

态；

在低温下，

只接受与当前状态能量差较小的新状态。当初始温度足

够高时，

概

率P

接近于

1,所

以

当前

解经过扰动产生的新解，

无论好坏，

基本都可以被接受为当前解。即不受制于当前解，

不会困在局部最优解中，

可以遍及解空间的各个区域，

当然也不会保持在最优解处。随着温度降低，概率降低，

较差解被接受的次数减少，

当前解逐渐停留到最优解周围。温度达到终止温度前，

概率足够低，使得只有最优解被接受，较差解都不接受。最优解即为最后接受的当前解。算

法

总

结6.1

算法基本理论6.1

算法基本理论三、算法其他参数的说明退火过程由一组初始参数，

即冷却进度表控

制

，它的核心是尽量使系统达到准平衡，

以使算法在有限

的时间内逼近最优解。冷却进度表包括：1.控制参数的初值To:冷却开始的温度；2.控制参数T的衰减函数：

要将连续的降温过程，

离散成降温过程中的一系列温度点，

衰减函数即计算这一系列温度的表达式；3.控制参数T

的终值Tr(停止准则);4.Markov

链的长度Lx:任意温度T

的迭代次数。6.1

算法基本理论四、算法基本步骤1、令T

=To,随机生成一个初始解xo,

并计算相应的目标函数值E(xo)

;2、

令T等于冷却进度表中的下一个值T:;3、

根据当前解xi进行扰动，产生一个新解xj,计相应

的目标函数值E(xj),得到

△e=E(xj)-E(xi);4、△e

<0,

则新解x;被接受，作为新的当前解；

△e

>0,则新解x;按概率接

受

；5、

在温度T

下，重复Lg次的扰动和接受过程，即执行步

骤

(

3

)

、(4);6、

判断T

是否已达到T,

是，则终止算法；否则转到(2

)

继

续

执

行△y

>o平

Y计算概

率

与[o,1]随

机

数之间的差

值差

值

大于ON

结束

，输

出

当前

解Tk+i

=aTk初

始

温

度，

随机

产

生

初

始

解

。T>Tr当前解x扰动

次数>Lp业

N扰动，产生新解xi+1计算两解的目标函数差值△y接受

新

解

作

为

当前

解NYYN6.1

算法基本理论四、算法基本步骤算法实质分为两层循环，

在任一温度下随机扰动产生新解

，

计算

目标函数值的变化，

决定

是

否接

受

。

由

于

算

法初始温度比较高，这样使E增大的新解在初始时也可能被

接受，因此能跳出局部极小值，

然后通过缓慢地降低温度，

算法可能收敛到全局最优解。虽然在低温时接受函数已经非常小了，但仍不排除有接受更差解得可能，

因此一般都会把退火过程中碰到的最好的可行解(历史最优解)也记录下来，与终止算法前最后被

接受

解一并

输出

。6.1

算法基本理论五

、

几

点

说

明1、

新解

的

产

生要求尽可能地遍及解空间的各个区域，这样，在某一

恒定温度下，

不断产生新解时，

就可能跳出局部最优解。

2、

收

敛的一

般条

件

：·

初始温

度

足

够高

；·

热平

衡时间足够长

；●终止温度

足

够

低

；●

降温

过程足

够

缓

慢

；6.1

算法基本理论五

、

几

点

说

明3

、参数的选

择

：(1)初始值ToT₀

越大越好，但为了减少计算量，要根据实际情况选择；(2)控制参数T的衰减函数常用Te+1=aTx,a的取值范围：

0.5~0.99;(3)Mark

ov链长度Lk=100n,n为问题规模。6.1

算法基本理论六

、

算

法

优

缺

点优点

：计算过程简单，

通用，

鲁棒性强，

适用于并行处理，可用于求解复杂的非线性优化问题。缺点

：收敛速度慢，

执行时间长，算法性能与初始值有关及参数敏感等缺点。6.

2算法的MATLAB

实现旅行商问题一

名商人要到n个不同的城市去推销商品，每2个城市/和j

之间的距离为d,

如何选择

一

条

路径使得商人每

个

城市走

一

遍

后回到起点所走

的路径最短。例

：有

5

2

座城市，

已知

每

座

城

市的

坐

标，

求

每

个

城

市

走

一

遍

后回

到

起点，

所

走的

路

径

最

短

。N结束，输出当前解Tk+1=0.99Tk犹动次数>10000r

下扰动，产生新解Xi+1△y

>oY计算概率与[o,1]

随机

数之间的差值计算两解的目标函数差值Ay(两条路径之差)初始温度(93),随

机产生初始解(1到

52的随机排列)。随机产生

0～1的数亚数

>

0

.

5二变换法

三变换法接受新解作为

当前解T

>3当前解x;差值大于ONY扰动：YNYN1.TS

P

问题的解空间和初始解TSP问题的解空间s是遍访每个城市恰好一次的所有回

路，

是所有城市的排列的集合。

即S={(c₁,c₂,…,cn)|(c₁,c₂,…,cn)为{1,2,…,n}的排列}Si:遍访n

个城市

的一条

路

径；Ci=j:

第i次访问城市j。因为最优解和初始状态没有强的依赖关系，所以

sO={1,2,…,n

}的随机排列6.

2算法的MATLAB

实现一、算法设计步骤2.

新

解的产

生(扰动

)(1)二变换法：任选序号u,v

(

设u<v<n),的访问顺序。(

2)三变换法：任选序号u,v,w

(

设u≤v<w),的路径

插

到w

之

后

访

问6.

2算法的MATLAB

实现一、算法设计步骤交

换u,v

之间将u,v

之

间else%否则，三变换i

ii

1

=

;

==ind3)

…i

d1(i

il(

i;nd1-ind2)==1)

p1=ind1;tmp2

=ind2;tmp3

=ind3;mndtea3dnran==inl102)d3dni0ndnd2ile=0h1while

t>=tffor

r

1

ngth%随机产生0~1的数，若小于0.5,

则二变换i

d1

==i

)

_p

_d

(ind2);sol_new(ind2)=tmp1;w;n1olinn_d1l

nwse=n1olmndsted20;ind2hile1=0;iwnd5)ledrknaraMif=6.

2算法的MATLAB

实现一、算法设计步骤ind2

=ceil(rand.*amount);ind3

=ceil(rand.*amount);ind1=ceil(rand.*amount);ind2

=ceil(rand.*amount);6.

2算法的MATLAB

实现一、算法设计步骤if(ind1<ind2)&&(ind2<ind3)end%ind1<ind2<ind3tmplist1=sol_new((ind1+1):(ind2-1));%u

、v之间的城市sols_ol

((

):1(

)d);3-ind2+

)将:i

城市移到u后面tmplist1;

%u

、v之间的城市移到w后面end2%n3+iindnd(iinwwenen_elseif

(ind1<ind3)&&(ind3<ind2)

ind2=tmp3;ind3=tmp2;elseif

(ind2<ind1)&&(ind1<ind3)

ind1=tmp2;ind2=tmp1;sol_new((ind1+1):(ind1+ind3-ind2+1))=

…elseif

(ind2<ind3)&&(ind3<ind1)ind1=tmp2;ind2

=tmp3;ind3

=tmp1;elseif

(ind3<ind1)&&(ind1<ind2)ind1=tmp3;ind2

=tmp1;ind3

=tmp2;elseif

(ind3<ind2)&&(ind2<ind1)ind1=tmp3;ind2=tmp2;ind3

=tmp1;3.目标

函

数访问所有城市的路径总长度：模拟退火算法求出目标函数的最小值一、算法设计步骤6.

2算法的MATLAB

实现6.

2算法的MATLAB

实现一、算法设计步骤%计算目标函数即内能

1

-1)E_new=E_new+

…end%从第一个城市到最后一个城市的距离E_new

=E_new+

…mount;a0inefo_rEdist_matrix(sol_new(amount),sol_new(1));dist_matrix(sol_new(i),sol_new(i+1));4.

目

标函数差计算变换前的解和变换后目标函数的差值△c¹=c(s')-c(s)5.Metropolis

接

受准则以新解与当前解的目标函数差定义接受概率，

即一、算法设计步骤6.

2算法的MATLAB实现6.

2算法的MATLAB

实