达人原创手把手教你使用C实现模拟退_c#发展_c#学习

1SA算法思想

模拟退火算法（SA,SimulatedAnnealing）实际上是通过模拟热力学系统中的退火过程给局部搜索算法添加一个随机跳变因素，避免算法局部贪心而陷于局部最优解。SA实际上是一种随机搜索算法，诸如蚁群算法、遗传算法、鱼群算法等启发式算法一样，都会加入一种随机“创新”因子，并且因子随算法的收敛而逐渐增强或减弱。通俗的来讲：“当算法找到一个局部最优解后，仍然会以一定的概率来接受一个比该局部最优解差的解作为临时最优解，这样就可能跳出局部最优的怪圈，从而达到全局“创新”的目的，这个跳变的概率就来自于模拟退火的热力学计算“。

2模拟退火算法描述

若J(Y(i+1))=J(Y(i))，即产生的新解更优，则总是接受新解；

若J(Y(i+1))J(Y(i))，即产生的新解比当前解要差，则以一定的概率P接受新解，而且这个概率随着时间推移逐渐降低，以至于不再跳变，从而收敛。

这个跳变概率的计算来自于退火思想，在热力学中的退火过程大致是变温物体缓慢降温而达到分子之间能量最低的状态。根据热力学的原理，这个变化概率可以表示为：

该公式表示：第m次降温后，当温度降为T(m)时，处于热力状态i的能量差为dE(i)，由此产生的跳变概率为P(m,i)。其中，dE0，exp表示自然指数，P的取值范围为(0,1)。该公式表示：初期温度较高的时候，出现能量差dE的跳变概率也就越大；随着温度的降低，出现跳变的概率就越小；随着温度T的降低，P(dE)会逐渐降低。

这里并没有说明新解如何得到，我们可以借助遗传算法中的交换、交叉、逆序、移动等方法得到，后面我们会以实例说明。

3模拟退火TSP伪代码描述

旅行商问题(TSP,TravelingSalesmanProblem)具有N-P难度：有N个城市，要求从其中某个城市出发，每个城市只允许经历一次，遍历完所有城市，再回到出发的城市，求最短的路径。

使用模拟退火解决TSP问题有以下几个主要步骤：

◆Step1：生成初始路径。随机选择一条路径作为初始解L(P(i))。

◆Step2：产生变异路径。使用交换、逆序、交叉、移动等方法产生新解L(P(i))→L(P(i+1))。若L(P(i+1))L(P(i))，则接受L(P(i+1))为新的路径，否则计算跳变概率P(i+1)并和随即概率比较，决定是否接受跳变路径。

◆Step3：开始降温迭代。

其伪代码（C#版）表示如下：

//***生成初始路径

Ini_Path=Init_Group();

//***初始路径赋值

Current_Path=Ini_Path;//每次迭代中当前接受路径

New_Path=Ini_Path;//变异产生的新路径

Best_Path=Ini_Path;//最优路径集合

//***降温迭代

while(T=T_em=M)

{

n=0;

while(nN){

New_Path=GetNewPath(Current_Path);//通过交换、逆序等方法得到新路径

dE=Current_Path.length-New_Path.length;//能量差

//如果能量差大于0，表示新路径更短，总是接受新路径为当前路径

if(dE=0)

{

Current_Path=New_Path;

}

//否则跳变计算

else

{

cp=Math.Exp(dE/(K*T));//跳变概率

p=ran.NextDouble();//随机概率(0,1)

if(cppcp1)

{

Current_Path=New_Path;

}

n++;

}

//搜集最优解

if(Current_Path.lengthBest_Path.length)

{

Best_Path=Current_Path;

best_T=m;//最优解产生的代数

}

m++;

}

下面，我将使用C#实现SA-TSP，并进行可视化演示。

作者介绍

枫鸽

数据分析师；

量化软件工程师

本文系作者原创，转载请获得我们的同意或作者授权！