数学建模----TSP&&模拟退火&&蚁群算法

1.旅行商问题（TSP）

旅行商问题是一个运筹学范围的问题，就是一个旅行商从1城市出发，依次经过2，3，4...............城市去推销货物，最后返回1城市，城市之间的路程一直，如何规划最优的路线？

这个在当今的应用例如物流公司，如何规划物流的路线，以及手机导航路线的规划都是旅行商问题的缩影；

2.模拟退火算法

这个算法的思想就是先给一个比较高的温度，逐渐降低温度，达到平衡，在每一个温度下面进行N轮搜索，每一轮对旧解添加随机扰动生成新解，按照一定的概率接受新解；

很多其他的算法，可能会陷入局部的极小值点，但是模拟退火不会，他会在全局找解，他会在某一步骤取一个稍微差点的解，反而会在最后得到更好的解；

模拟退火是一个双循环的过程，外循环是温度的控制，内循环的是每个温度的搜索最优的排列状态，就是因为他可以接受局部的次优解，所以最后反而可能得到全局的最优解；

每次进行扰动的时候，都会得到新解，新解比旧的解好，就会接受新解，如果新解比旧解差，我们不会舍去，而是按照一定的概率（这个概率和温度有关，温度越高，概率越大）接受旧解，这样就可能跳出局部最优解，找到全局最优解；

马尔可夫链的长度就是内循环的次数；上面的概率是根据分子的能量物理模型给出的；

模拟退火的缺陷是温度降低的幅度，降低的过快可能会漏掉某些解，降低的过慢就会增加我们的计算量，所以这个温度的控制很重要；

3.蚁群算法

这个算法模拟蚂蚁寻找食物，蚂蚁没有视力，却能够找到最优路径；

代码部分来自该公众号（非本人）：

运行结果如下：