运筹学之模拟退火

一、汗青

• 问：谁在什么时候提出模拟退火？
  
• 答：模拟退火算法（Simulated Annealing，SA）是由斯图尔特·柯尔斯基（Scott Kirkpatrick） 等人在 1983年 提出的。
  
• 论文：“Optimization by Simulated Annealing”, published in Science, Vol. 220
  
• 动机：办理组合优化题目
  
  
  
  

二、精髓头脑

• 精髓就两字：退火！
  
• 表明：字面意思就是模拟打铁的退火过程，刚开始打铁吧温度比较高，铁烧的红红的容易打出各种外形，随着时间变长，温度徐徐冷却下来，铁更硬了，外形大方向基本确定。
  

不禁感叹，从前的物理学家、数学家灵感泉源都是自然征象！

总结下来实在就3个step：

• 拿一块铁过来淬火
  
• 打一次看看如何
  
• 给我打到定型
  

三、案例与代码实现

• 题干：
  6艘船靠3个港口，已知达到时间arrival和卸货时长handling，求最优停靠方案，即等待时长最短。
  
• 数据：
  

1. ships = {
2.     'S1': {'arrival': 0.1, 'handling': 4},
3.     'S2': {'arrival': 2.1, 'handling': 3},
4.     'S3': {'arrival': 4.2, 'handling': 2},
5.     'S4': {'arrival': 6.3, 'handling': 3},
6.     'S5': {'arrival': 5.5, 'handling': 2},
7.     'S6': {'arrival': 3.9, 'handling': 4},
8.     'S7': {'arrival': 3.7, 'handling': 4},
9.     'S8': {'arrival': 3.4, 'handling': 4},
10. }

复制代码

• 实现：
  step1：拿一块铁过来淬火
  

1. # 随机初始化一块铁（船舶调度顺序）
2. initial_order = list(ships.keys()) # 船舶原始顺序['S1', 'S2', 'S3', 'S4', 'S5', 'S6', 'S7', 'S8']
3. random.shuffle(initial_order)        #        打乱顺序 ，可能是['S2', 'S7', 'S6', 'S5', 'S1', 'S3', 'S4', 'S8']

复制代码

• step2：打一次看看如何
  

首先，先评价一下原始边幅如何？用等待时间作为衡量，如下：

1. current_cost = evaluate(current)
2. NUM_BERTHS = 3  # 泊位数量
3. # 评价函数：计算某个调度顺序的总等待时间
4. def evaluate(order):
5.     berth_times = [0] * NUM_BERTHS
6.     total_wait = 0
7.     for ship_id in order:
8.         arrival = ships[ship_id]['arrival']
9.         handling = ships[ship_id]['handling']
10.         # 找到最早可用泊位
11.         berth_index = min(range(NUM_BERTHS), key=lambda i: max(arrival, berth_times[i]))
12.         # start_time = 开始卸货时间 = max(到达时间, 泊位可用时间)。
13.         # 解释：要卸货的话，船先到达了没有泊位可用也得等，反之，有空泊位了船还没到也得等。
14.         start_time = max(arrival, berth_times[berth_index])
15.         wait_time = start_time - arrival
16.         total_wait += wait_time
17.         berth_times[berth_index] = start_time + handling
18.     return total_wait

复制代码

然后，开始下锤子了（称之为扰动）

1. # 生成邻域解（随机交换两艘船顺序）
2. def neighbor(order):
3.     new_order = order.copy()
4.     i, j = random.sample(range(len(order)), 2)
5.     new_order[i], new_order[j] = new_order[j], new_order[i]
6.     return new_order

复制代码

紧接着，评估下现在边幅和上一次区别，如下：

1. new = neighbor(current)
2. new_cost = evaluate(new)
3. delta = new_cost - current_cost        # 扰动之后的区别

复制代码

末了，做决定是接着现在边幅往下继续打，还是恢复回原来边幅

1. # 情况1：delta < 0 说明等待时间变短了呀，打铁打得更好了，欣然接受。
2. # 情况2：delta >= 0 说明等待时间变长了，糟糕打偏了，不过没关系，这是艺术啊！不完美也是一种美！看心情决定~
3. # 于是有了 random.random() < math.exp(-delta / T)这一项
4. # 解释：random.random()就是一个随机值（类比于当时心情），值域范围[0.0, 1.0)
5. # math.exp(-delta / T)和delta、T有关系，这么来看吧，假设现在超级无敌高温，那么-delta / T趋于0，那么math.exp(-delta / T)趋于1，说明有很大概率接受比较差的解。假设现在温度快降到0了，那么-delta / T趋于负无穷，那么math.exp(-delta / T)趋于0，说明有极小概率接受比较差的解。
6. if delta < 0 or random.random() < math.exp(-delta / T):
7.         current = new
8.     current_cost = new_cost

复制代码

• step3：给我打到定型
  

循环的过程，就是往复step2的过程，持续下去直到定型，如下：

1. # 模拟退火主过程
2. # 初始顺序：initial_order, 温度：T=100.0, 冷却率：cooling_rate=0.95, 最低温度：T_min=1e-3
3. def simulated_annealing(initial_order, T=100.0, cooling_rate=0.95, T_min=1e-3):
4.     current = initial_order
5.     current_cost = evaluate(current)
6.     best = current
7.     best_cost = current_cost
9.     while T > T_min:
10.         for _ in range(100):  # 每个温度尝试多次扰动
11.             new = neighbor(current)
12.             new_cost = evaluate(new)
13.             delta = new_cost - current_cost
14.             if delta < 0 or random.random() < math.exp(-delta / T):
15.                 current = new
16.                 current_cost = new_cost
17.                 if current_cost < best_cost:
18.                     best = current
19.                     best_cost = current_cost
20.         T *= cooling_rate  # 降温
21.     return best, best_cost

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。