退火算法 ： 学习笔记

　

退火算法

退火算法解决旅行员问题（学习笔记）

给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。

退火算法：

1、随机改变路径

2、如果随机改变路径的目标函数对结果有利则接受这个改变

3、如果有害，就以“一定概率”接受这个改变

% 接受不好的结果是为了避开局部最优解

++++++++++++++++++++++++++++++++++++++++++++++++++++++

这个“一定概率”是模仿金属的退火过程确定的

---

p = exp(Δ/（k * count）)

---

这个Δ代表目标函数改变量 恒为负 k 值可以自己定 count代表迭代轮数（递减）

k 取较小的值的时候迭代后期越稳定

下面是Python代码

import numpy as np
import random
import math
def sumit(a,b):
    s = 0
    for i in range(9):
        s = s+ a[b[i],b[i+1]]
    s = s + a[b[9],b[0]]
    return s
a = np.array([[0 ,9 ,3 ,7 ,6, 3 ,5 ,5 ,8 ,6],
 [6 ,0 ,4 ,9 ,2 ,5 ,6 ,4 ,7 ,4],
 [2 ,7 ,0 ,1 ,5 ,1 ,6 ,8 ,6 ,7],
 [7 ,7 ,7 ,0 ,5 ,9 ,9 ,3 ,8 ,9],
 [8 ,1 ,7 ,6 ,0 ,8 ,6 ,2 ,1 ,3],
 [6 ,3 ,3 ,6 ,1 ,0 ,7 ,8 ,1 ,6],
 [8 ,2 ,6 ,4 ,1 ,1 ,0 ,3 ,6 ,2],
 [4 ,1 ,1 ,4 ,6 ,1 ,1 ,0 ,8 ,4],
 [3 ,6 ,4 ,9 ,8 ,7 ,1 ,9 ,0 ,4],
 [9 ,6 ,5 ,1 ,5 ,9 ,5 ,4 ,8 ,0]])
b = [i for i in range(10)]
count = 100000
while(count-1):
    count = count - 1
    s = sumit(a , b)
    rand1 = 0
    rand2 = 0
    while (rand1 == rand2):
        rand1 = random.randint(0,9)
        rand2 = random.randint(0,9)
    b1 = b[:]
    b1[rand1],b1[rand2] = b1[rand2],b1[rand1]
    
    s1 = sumit(a , b1)
    if s1 <= s:
        b = b1
    else:
        k = 0.0001
        p = math.exp((s - s1)/(k * count))
        rand3 =random.random()
        if rand3 < p:
            b = b1
    if (not count%100):
        print ('第'+str(count)+'的结果是'+str(s))

经过几次尝试后发现k值取 0.00001 比较好

算法的效果一方面取决于参数的选择

一方面取决于运气。

相关阅读

SPFA 算法详解( 强大图解，不会都难！)&&spfa优化——深度

https://blog.csdn.net/muxidreamtohit/article/details/7894298　　适用范围：给定的图存在负权边，这时类似Dijkstra等算法便没有了

A*算法和dijkstra算法

A*算法和dijkstra算法都是启发式搜索，dijkstra算法可以看成是广度优先搜索，而A*可以认为是深度优先搜索。 dijkstra就是保证当前节

RSA算法简介

RSA是目前最有影响力和最常用的公钥加密算法，它能够抵抗到目前为止已知的绝大多数密码攻击，已被ISO推荐为公钥数据加密标准。 RSA算

今天的新发现发现了一个关于算法的新网站 领扣

https://www.lintcode.com/这个网站上面有一些关于算法的题，可以进行日常的练习。

贪心算法Hufuman树问题

问题描述Huffman树在编码中有着广泛的应用。在这里，我们只关心Huffman树的构造过程。给出一列数{pi}={p0, p1, …, pn-1}，用这列