模拟退火算法

模拟退火算法来源于固体退火原理。

物理退火: 将材料加热后再经特定速率冷却，目的是增大晶粒的体积，并且减少晶格中的缺陷。材料中的原子原来会停留在使内能有局部最小值的位置，加热使能量变大，原子会离开原来位置，而随机在其他位置中移动。退火冷却时速度较慢，使得原子有较多可能可以找到内能比原先更低的位置。

模拟退火: 其原理也和固体退火的原理近似。模拟退火算法从某一较高初温出发，伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。

爬山算法

爬山算法是一种简单的贪心搜索算法，该算法每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解。这种算法思想很单纯，但是也存在一个很大的缺陷。在搜索选择的过程中有可能会陷入局部最优解，而这个局部最优解不一定是全局最优解。比如下面这个问题：

假设A是当前解，爬山算法往前继续搜索，当搜索到B这个局部最优解时就会停止搜索了。因为此时在B点无论是往哪边走都不会得到更优的解了。但是，全局最优解在C点。

模拟退火算法

爬山法是完完全全的贪心法，这种贪心是很鼠目寸光的，只把眼光放在局部最优解上，因此只能搜索到局部的最优值。模拟退火其实也是一种贪心算法，只不过与爬山法不同的是，模拟退火算法在搜索过程引入了随机因素。模拟退火算法以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。从上图来说，模拟退火算法在搜索到局部最优解B后，会以一定的概率接受向右的移动。也许经过几次这样的不是局部最优的移动后会到达BC之间的峰点D，这样一来便跳出了局部最优解B，继续往右移动就有可能获得全局最优解C。

对比上面两种算法，对于模拟退火算法我们提到了一个很重要的概念--一定的概率，关于这个一定的概率是如何计算的。这里还是参考了固体的物理退火过程。

根据热力学的原理，在温度为T时，出现能量差为dE的降温的概率为P(dE)，表示为：

P(dE)=edEkTP(dE)=e^{\frac{dE}{kT}}

其中k是一个常数，exp表示自然指数，且dE<0(温度总是降低的)。这条公式指明了：

温度越高，出现一次能量差为dE的降温的概率就越大；
温度越低，则出现降温的概率就越小。又由于dE总是小于0（不然怎么叫退火），因此dE/kT < 0 ，exp(dE/kT)取值是(0,1),那么P(dE)的函数取值范围是(0,1) 。

随着温度T的降低，P(dE)会逐渐降低。我们将一次向较差解的移动看做一次温度跳变过程，我们以概率P(dE)来接受这样的移动。也就是说，在用固体退火模拟组合优化问题，将内能E模拟为目标函数值 f，温度T演化成控制参数 t，即得到解组合优化问题的模拟退火演算法：由初始解 i 和控制参数初值 t 开始，对当前解重复“产生新解→计算目标函数差→接受或丢弃”的迭代，并逐步衰减 t 值，算法终止时的当前解即为所得近似最优解。

因此我们归结起来就是以下几点：

若f( Y(i+1) ) <= f( Y(i) ) (即移动后得到更优解)，则总是接受该移动；
若f( Y(i+1) ) > f( Y(i) ) (即移动后的解比当前解要差)，则以一定的概率接受移动，而且这个概率随着时间推移逐渐降低（逐渐降低才能趋向稳定）相当于上图中，从B移向BC之间的小波峰D时，每次右移(即接受一个更糟糕值)的概率在逐渐降低。如果这个坡特别长，那么很有可能最终我们并不会翻过这个坡。如果它不太长，这很有可能会翻过它，这取决于衰减 t 值的设定。

算法流程

代码实现

import random
import numpy as np
import math

num_city=30#城市总数
initial_t=120#初始温度
lowest_t=0.001#最低温度
M=150#当连续多次都不接受新的状态，开始改变温度
iteration=300#设置迭代次数



location=np.loadtxt('./city_location.txt')



#==========================================
#对称矩阵，两个城市之间的距离
def distance_p2p_mat():
    dis_mat=[]
    for i in range(30):
        dis_mat_each=[]
        for j in range(30):
            dis=math.sqrt(pow(location[i][0]-location[j][0],2)+pow(location[i][1]-location[j][1],2))
            dis_mat_each.append(dis)
        dis_mat.append(dis_mat_each)
   # print(dis_mat)
    return dis_mat

#计算所有路径对应的距离
def cal_newpath(dis_mat,path):
    dis=0
    for j in range(num_city-1):
        dis=dis_mat[path[j]][path[j+1]]+dis
    dis=dis_mat[path[29]][path[0]]+dis#回家
    return dis

#==========================================
#点对点距离矩阵
dis_mat=distance_p2p_mat()
#初始路径
path=list(range(30))
#初始距离
dis=cal_newpath(dis_mat,path)
#初始温度
t_current=initial_t

while (t_current>lowest_t):#外循环，改变温度
    count_m=0#M的计数
    count_iter=0#迭代次数计数
    while (count_m<M and count_iter<iteration):#内循环，连续多次不接受新的状态或者是迭代多次,跳出内循环        
        i=0
        j=0
        while(i==j):#防止随机了同一城市
            i=random.randint(1,29)
            j=random.randint(1,29)
        path_new=path.copy()
        path_new[i],path_new[j]=path_new[j],path_new[i]#任意交换两个城市的位置,产生新解
        #计算新解的距离
        dis_new=cal_newpath(dis_mat,path_new)
        #求差
        dis_delta=dis_new-dis
        #取0-1浮点随机数
        rand=random.random()
        #计算指数函数的值
        exp_d=math.exp(-dis_delta/t_current)
        #选择
        if dis_delta<0:
            path=path_new
            dis=dis_new
        elif exp_d>rand:
            path=path_new
            dis=dis_new    
        else:
            count_m=count_m+1
        count_iter=count_iter+1
    t_current=0.99*t_current#改变温度
#外循环结束
dis_min=dis
path_min=path
print('最短距离：',dis_min)
print('最短路径：',path_min)

city_location.txt内容如下：