目录

• 一、概念
• 二、算法的优点
• 三、基本流程和公式
• 四、例题+python代码
• • 已知背包的装载量为 c=10，现有 n=5 个物品，它们的重量和价值分别是 (2, 3, 5, 1, 4) 和 (2, 5, 8, 3, 6)。试使用模拟退火算法求解该背包问题。
  • python 代码

一、概念

模拟退火算法采用类似于物理退火的过程，先在一个高温状态下，然后逐渐退火，在每个温度下徐徐冷却，最终达到物理基态。

高温相当于算法随机搜索。
反复退火则是状态转移，然后进行算法的局部搜索。
冷却则是找到最优解的时候。

加热时，会给铁分子小球一个力，就在曲面上自由滚动，冷却下来可能就停在了某个小凹槽（即得到局部最优解），但不一定是最深的那个坑（最优解），所以要反复加热。

二、算法的优点

1、克服初值依赖性。
2、克服陷入局部最优解的情况。

三、基本流程和公式

(1) 初始化：初温t=t0，随机产生初始状态X0 ，令Xbest＝X0，k=0;
(2) Repeat:
(2.1) Repeat:
(2.1.1) 产生新的状态 Xnew= Generate (Xk); // 状态产生函数
(2.1.2) if random[0,1] ≤ min{1, exp[-(f(Xnew)-f(X)) / tk]}
Xk = Xnew; f(Xk) = f(Xnew); // f(X)表示X的目标函数值
(2.2) Until 抽样稳定准则满足
(2.3) 退温 tk+1 = update(tk),并令 k=k+1;
(3) Until 算法终止准则满足;
(4) 输出结果

2.1.2的公式对应下图的坐标系：
当 f(Xk) >= f(Xnew)，就是对应函数值大于等于1的部分（就是x>=0的部分）
反之，就是x<0的部分。

四、例题+python代码

已知背包的装载量为 c=10，现有 n=5 个物品，它们的重量和价值分别是 (2, 3, 5, 1, 4) 和 (2, 5, 8, 3, 6)。试使用模拟退火算法求解该背包问题。

python 代码

导入包：

import random
import math
import numpy as np

1、初始化

# 背包容量c, 有n个物品
# time 迭代次数, balance平衡次数
# best 记录全局最优  T 温度  rate退火率
# wsum 当前重量总和    vsum 当前价值总和
n = 5
T = 200.0
rate = 0.95
time = 10
balance = 100
global c, best, wsum, vsum
# best_way 记录全局最优解方案   now_way 记录当前解方案
best_way = [0] * n     # 将[0]复制了m遍，变成[0,0,...,0]
now_way=[0] * n

加入题目数据：

weight = [2, 3, 5, 1, 4]
value = [2, 5, 8, 3, 6]def init():global c, bestc = 10best = -1produce()

2.1.1 状态产生函数

def produce():  # 用于产生新解while(1):for k in range(n):if(random.random() < 0.5):now_way[k] = 1else:now_way[k] = 0calc(now_way)if (wsum < c):breakglobal bestbest = calc(now_way)cop(best_way, now_way, n)

2.1.2 退火过程
计算当前背包的价值，比较是否是较优解，是的话就接受！如果当前是较差的解，就按照公式去计算接受的概率 P，P大的话也接受该解。

def anneal():  # 退火函数global best, T, balancetest = [0] * nvalue_current = 0     # 当前背包价值for i in range(balance):value_current = calc(now_way)    # 计算当前背包的价值cop(test, now_way, n)  # 记录当前方案ob = random.randint(0, n-1)   # 随机选取某个物品if (test[ob] == 1):# 在背包中则将其拿出，并加入其它物品put(test)test[ob] = 1else:if(random.random()< 0.5): #接受新解的概率test[ob] = 1else:get(test)test[ob] = 1value_new = calc(test)if(wsum > c):    # 超重，则跳过continueif (value_new > value_current): # 接受该解cop(now_way, test, n)if (value_new > best):best = value_newcop(best_way, test, n) # 更新全局最优else:  # 按一定的概率接受该解g = 1.0 * (value_new - value_current) / Tif (random.random() < math.exp(g)): # 概率接受劣解cop(now_way, test, n)

3、中间使用到的将物品取出和放入背包的函数，和计算背包价值的函数

def cop(a, b, len):   # 把 b数组的值赋值a数组for i in range(len):a[i] = b[i]def calc(x):        # 计算背包价值global c, wsumvsum = 0wsum = 0for i in range(n):vsum += x[i] * value[i]wsum += x[i] * weight[i]return vsumdef put(x):     # 往背包随机放入物品while(1):ob = random.randint(0, n-1);if (x[ob] == 0):   # 当前情况下物品还不在包里面x[ob] = 1breakdef get(x):     # 往背包随机拿出物品while(1):ob = random.randint(0, n-1);if (x[ob] == 1):x[ob] = 0break

4、主函数

if __name__ == '__main__':init()flag = 0;          # 找到最优解for i in range(time):anneal()T = T * rate   # 温度下降print('找到最终解：', best, '迭代次数', time);print('方案为：', best_way);

END