Matlab模拟退火算法(2)

，最常用的接受准则是Metropo1is准则

若Δt′0则接受S′作为新的当前解S，否则以概率exp(-Δt′T)接受S′作为新的当前解S。

　　第四步是当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。

　　模拟退火算法与初始值无关，算法求得的解与初始解状态S(是算法迭代的起点)无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率l

收敛于全局最优解的全局优化算法；模拟退火算法具有并行性。

模拟退火算法的简单应用

　　作为模拟退火算法应用，讨论货郎担问题(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 ,…，wk , wk+1 ,…，wm ,…，wn)

　　变为：

　　(w1, w2 ,…，wm , wm-1 ,…，wk+1 , wk ,…，wn).

　　如果是km，则将

　　(w1, w2 ,…，wk , wk+1 ,…，wm ,…，wn)

　　变为：

　　(wm, wm-1 ,…，w1 , wm+1 ,…，wk-1 ,wn , wn-1 ,…，wk).

　　上述变换方法可简单说成是“逆转中间或者逆转两端”。

　　也可以采用其他的变换方法，有些变换有独特的优越性，有时也将它们交替使用，得到一种更好方法。

　　代价函数差 设将(w1, w2 ,……，wn)变换为(u1, u2 ,……，un), 则代价函数差为：

根据上述分析，可写出用模拟退火算法求解TSP
问题的伪程序：

Procedure TSPSA

　begin

　　init-of-T; { T为初始温度}

　　S={1，……，n}; {S为初始值}

　　termination=false;

　　while termination=false