lecture.txt

模拟退火算法求解TSP问题.求解TSP问题的模拟退火算法

趣题活跃一下气氛。


物流管理中，怎样合理的安排管理，制定计划，最节省成本。成为首要的问题。
这些问题条件与限制很多，难以入手。但我利用模拟物理中的固体降温过程，设计出了解决的通用的近似算法。
下面就来看看，一个这类问题的例子吧。
旅行商问题,TSP

直观的讲,就是用一笔将n个城市连接起来,使得这笔最短.

历史悠久,早在1759年欧拉就提出了骑士周游问题.用骑士遍历国际象棋棋盘每个格子一次,返回.

TSP是一个NP问题.所谓NP问题,就是一个不能在多项式时间内,解决的问题.如TSP,求其精确解,100个城市要万年.
NP是新千年急待解决的7大数学问题之首.
当然,在现时生活应用中,高效的求问题近似解就可以了.例如,100元.

其实这些问题抽象成数学模型,就是求一个复杂函数的最小值.这个函数值就是所谓成本.

注意到 物质总是趋于最低的能态 这个自然规律. 物质会”自动”地趋向的最低能态。
猜想,左图的最低能态,与右图的函数最小值之间.是否有相似性呢?
能否设计一个算法使得求函数最小值如同水向低处流,电子向最低能级的轨道排布那样自动呢?

观察固体降温过程,专业一点叫退火.

可以将固体中的粒子看成是有限的定义域内的一个值,自变量.
这个粒子由于要受其他粒子的影响会扰动.
对应的,这样对那个自变量随机的进行变换,产生新的自变量.
若新的自变量的函数值优于原来的或满足一定的热平衡概率,则接受它,否则就像蒸发一样抛弃它.
不断的进行这个过程,整个系统的内能就会不断减小,最终达到热平衡.

这就是我的模拟退火算法.很简单.

大家决的这很夸张,只是凭空说说.但是用大规模的测试试验,效果很好.
解以1的概率接近最优.还具有全局性.

TSP的效果.

优化的余地

特点

思路