模拟退火算法,其实是受到了物理里面退火过程的启发。退火,说的是金属或者玻璃加热后再慢慢冷却,这样做能让材料更稳定,结构更完美。那这个算法就借鉴了这一点,目的是为了解决一些特别复杂的优化问题,比如说要在一大堆可能的方案中找到最好的那一个。
有时候我们要解决的问题就像是在一个多山的地图上找一个最低的点,这个点就代表了最好的解决方案。但问题是,这图上的山峰和山谷多得很,我们很容易就困在一个小山谷里出不来,以为这里就是最低点了,其实不是,外面可能还有更低的。
这时候模拟退火算法就派上用场了。它开始的时候会允许自己跳得比较随意,甚至有时候往更高的地方跳,这样就不容易被困在小山谷里。随着时间的推移,它跳来跳去的幅度会慢慢变小,这样它就能细致地在一个小区域内找到真正的最低点。就像是退火过程中,温度慢慢降低,金属的内部结构逐渐稳定下来一样。
这个算法特别适合用在那些标准的方法不好使,或者解决方案特别多、特别复杂的问题上。比如说旅行商问题,就是要找一个最短的路线让旅行商拜访所有城市,再比如说电路板设计里的布线问题,还有很多其他的工程和科学问题也都可以用。总之,当你面对的问题像一座座山峰让你头大,不知道从哪下手的时候,模拟退火算法就能出马,帮你找到一个不错的解决方案。
你刚搬到一个新城市,这个城市里有成千上万家餐厅。你的目标很简单:找到全城最好吃的那家餐厅。但问题是,你不可能一家一家去试,那样太费时间也费钱了。
这时候,模拟退火算法就像是你的一位聪明的朋友,一开始他可能会提议说:“咱们随便选一个区域,先去那儿的一家餐厅试试。”你们可能会去一家评价还不错的餐厅,尝尝菜品。吃完之后,这位朋友可能会说:“这家还行,不过我听说隔壁区有一家更好的,要不要试试看?”即便这家餐厅已经很不错,他依然会鼓励你尝试新的地方,哪怕有时候可能会遇到不那么好的餐厅。
随着你们尝试的餐厅越来越多,你的这位朋友会越来越有感觉,他开始更有针对性地推荐:“咱们这次就在这附近找找吧,感觉好餐厅应该就在这一块。”慢慢地,他带你的尝试范围开始变小,你们开始在最有潜力的那几个区域反复尝试不同的餐厅。
最终,经过多次的尝试和比较,你们发现了那家口味最符合你心意的餐厅。这个过程里,你的朋友就像模拟退火算法一样,一开始允许一些随机和大范围的尝试,然后逐渐变得更加专注和精确,直至找到最满意的结果。
这个过程跟你在城市中寻找最好的餐厅的经历很相似,模拟退火算法就是通过这样一种逐渐收敛的探索过程,帮助解决复杂的优化问题。
你要组织一个社区的迷你马拉松比赛。你手头有一张社区的地图,上面有很多条街道,而你需要规划出一条既不太长也不太短,恰到好处的跑步路线。
你首先可能会随便画一条路线出来,但这条路线可能会有些问题,比如说太长了,或者绕圈子了,不是很理想。这个时候,如果你只是小修小改,可能会发现自己总是在同一个区域转悠,改进不大。这就像是你困在了一个小山谷里,以为这就是最好的路线了,其实不是,还有更好的可能性。
你可以大胆地尝试一些完全不同的路线,甚至是看起来有点疯狂的路线。这就好比你有时候故意绕远路,只是为了看看有没有更好的选择。
随着每次的尝试,你开始减少大幅度的变动,而是更加专注于细节的调整。你可能会发现,其实通过调整某几个转角,或者缩短某个直道,你就能得到一条更加完美的跑步路线。这个过程就像是你逐渐降低了飞行的高度,开始更加仔细地观察地面的细节,直到最后找到一个最合适的路线。
到最后,当你确定了最终的路线,这条路线就像是经过精心设计的马拉松赛道,既考虑了距离的合理性,又兼顾了游览社区的风景,达到了你组织比赛的初衷。模拟退火算法就是通过这样不断的尝试和调整,帮你在看似复杂难解的问题中找到一个既满意又实用的解决方案。
模拟退火算法(Simulated Annealing,SA)是一种启发式算法,用来寻找在大搜索空间内的全局最优解。这种算法的设计灵感来源于金属退火的过程。在物理学中,当金属加热后再慢慢冷却时,原子会逐渐排列成最低能量的结构,这就是最稳定的状态。
通过以上步骤,模拟退火算法能够在可能接受较差的解的同时寻找最优解,这有助于它跳出局部最优并朝向全局最优解前进。随着“温度”逐渐降低,算法接受较差解的能力也会减弱,从而使解趋向稳定。就像金属冷却后原子逐渐稳定在最低能量的状态,算法最终也能找到问题的一个非常好的解。
给定一系列城市和每对城市之间的距离,寻找一条最短的路径,使得旅行商开始于某城市,经过所有其他城市恰好一次,并在结束该路径时回到原始城市。
1from simanneal import Annealer
2import random
3import numpy as np
4import matplotlib.pyplot as plt
5
6class TravelingSalesmanProblem(Annealer):
7
8 def move(self):
9 a = random.randint(0, len(self.state) - 1)
10 b = random.randint(0, len(self.state) - 1)
11 self.state[a], self.state[b] = self.state[b], self.state[a]
12
13 def energy(self):
14 e = sum(
15 dist_matrix[self.state[i-1]][self.state[i]]
16 for i in range(city_num)
17 )
18 return e
19
20# 初始解(即初始城市访问顺序),随机产生
21init_state = list(range(city_num))
22random.shuffle(init_state)
23
24tsp = TravelingSalesmanProblem(init_state)
25tsp.set_schedule(tsp.auto(minutes=.2))
26state, e = tsp.anneal()
27
28print('最短总距离为:', e)
29print('最佳路径为:', state)
30
31# 使用 matplotlib 绘图
32order_by_best = list(map(int, state)) + [int(state[0])]
33plt.plot([cities[i][0] for i in order_by_best], [cities[i][1] for i in order_by_best], 'xb-')
34for city, pos in cities.items():
35 plt.text(pos[0], pos[1], str(city))
36plt.show()
1from simanneal import Annealer
2import random
3import numpy as np
4import matplotlib.pyplot as plt
5
6class TravelingSalesmanProblem(Annealer):
7
8 def move(self):
9 a = random.randint(0, len(self.state) - 1)
10 b = random.randint(0, len(self.state) - 1)
11 self.state[a], self.state[b] = self.state[b], self.state[a]
12
13 def energy(self):
14 e = sum(
15 dist_matrix[self.state[i-1]][self.state[i]]
16 for i in range(city_num)
17 )
18 return e
19
20# 初始解(即初始城市访问顺序),随机产生
21init_state = list(range(city_num))
22random.shuffle(init_state)
23
24tsp = TravelingSalesmanProblem(init_state)
25tsp.set_schedule(tsp.auto(minutes=.2))
26state, e = tsp.anneal()
27
28print('最短总距离为:', e)
29print('最佳路径为:', state)
30
31# 使用 matplotlib 绘图
32order_by_best = list(map(int, state)) + [int(state[0])]
33plt.plot([cities[i][0] for i in order_by_best], [cities[i][1] for i in order_by_best], 'xb-')
34for city, pos in cities.items():
35 plt.text(pos[0], pos[1], str(city))
36plt.show()
输出结果:
1最短总距离为: 296.249882020428
2最佳路径为: [3, 4, 6, 9, 8, 2, 0, 1, 5, 7]
1最短总距离为: 296.249882020428
2最佳路径为: [3, 4, 6, 9, 8, 2, 0, 1, 5, 7]
优点:
缺点: