Matlab-模拟退火

Posted on | In , | Visitors:

This is my blog.
第一次数模的时候
就是做了模拟退火的算法
那时候受高人指点
就知道要用此算法
单纯敲完就很开心
出来的图形震惊自己
现在看看这明显是误差大的图呀！！！


模拟退火（SA）是三大非经典算法之一，与优化问题相结合。可以避免陷入局部最优的情况。

步骤

由于流程图不可显示，看来也不是支持所有语言么

  1. 令\(T=T_0\)，即开始退火的初始温度，随机生成一个初始解\(x_0\)，并计算相应的目标函数值\(E(x_0)\)
  2. 令\(T\(等于冷却进度表中的下一个值\(T_i\(\)
  3. 根据当前解\(x_i\)进行扰动，产生一个新解\(x_j\)，并计算相应的目标函数值\(E(x_j)\)，得到\(\delta E=E(x_j)-E(x_i)\)
  4. 若\(\delta E<0\)，则接受新解；否则，以\(e^{-\frac{\delta E}{T_i}}\)接受，\(T_i\)为当前温度
  5. 重复\(L_k\)次扰动和接受，即重复3，4
  6. 判断\(T\)是否已达到\(T_f\)。若是，则终止算法；否则，转到2

应用

TSP（旅行商问题）

注 遗传算法也可以解
也可用贪心的算法解，貌似模拟退火的准确度较高，且花费时间较少

新解产生

1）二变换法：任选序号\(u,v （设u<v<n）\)，交换访问顺序。
2）三变换法：任选序号\(u,v,w （设u\leq v<w）\)，将\(u\)和\(v\)之间的路径插到\(w\)之后

Maekov链长度

一般来说，可简单令\(L_k=100n\)

代码

0-1背包问题

代码类似

ASA工具箱

貌似最近的都有工具箱么。。。
可惜没找到可用的工具箱。。。
有一个怪怪的
之后再看看吧

后记

今天雪还是没有停的趋势
泡了茶
教室的人也越来越少了
我也只有下午出门了
怕是都窝在被窝里吧
只可惜没有网 没有灯
终归不舒服
发现最近上传的很多细节都没有处理好
昨天的流程图不行
看来以后还得慢慢研究
至于内容 本来blog也只是我一时兴起
既是作为一个日记
也是作为一个笔记吧
若真要好好做的话
那些原创的东西又有些难
倒是为难我了
暂且这样吧
也许之后会改变想法
那再归类整理一下 之后重头再来
倒也未尝不可

转载请注明出处，谢谢。

愿 我是你的小太阳



买糖果去喽