关于「退火、重启与 Metropolis 准则:逃离局部最优的经典配方」,《量子启发与猜想证伪》给出的定量结论是什么?
结论:第二章在受挫自旋玻璃上比较贪心、随机重启与退火:贪心命中率停在 0.060,随机重启随预算升到 0.985,切碎预算的多段短退火同样可达。
数据口径:书中参数为示意,全部计算由书中程序生成。 本书不构成投资、学术评审或量子硬件方面的建议。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 0.060, 0.985
| instance: 20 spins, 40 couplings, ground energy -49 | ||||
| hit rate = share of 200 trials ending at the ground energy | ||||
| budget | greedy | restarts | annealing | (mean final E) |
| 300 | 0.060 | 0.385 | 0.235 | (-42.39 -47.58 -46.05) |
| 1,000 | 0.060 | 0.840 | 0.340 | (-42.39 -48.68 -46.98) |
| 3,000 | 0.060 | 0.985 | 0.530 | (-42.39 -48.97 -47.92) |
查看完整验算程序
# Chapter 2. p22: greedy, random-restart and annealing on a spin glass.
# A frustrated Ising instance (equivalently a signed max-cut): 20 spins on
# a ring plus 20 random chords, couplings J in +-1, +-2, +-3 with a fixed
# seed (illustrative, not a benchmark). Energy E = -sum J_ij s_i s_j.
# The exact ground energy comes from a Gray-code sweep of all 2^19 states
# with spin 0 fixed. Each method gets the same budget of single-flip
# evaluations; the hit rate is the share of 200 seeded trials that end at
# the ground energy. Everything is a classical computation.
import math
import random
N, CHORDS, TRIALS = 20, 20, 200
WEIGHTS = (-3, -2, -1, 1, 2, 3)
BUDGETS = (300, 1000, 3000)
def build(rng):
edges = {}
for i in range(N):
edges[(i, (i + 1) % N)] = rng.choice(WEIGHTS)
while len(edges) < N + CHORDS:
a, b = sorted(rng.sample(range(N), 2))
if (a, b) not in edges and (b, a) not in edges:
edges[(a, b)] = rng.choice(WEIGHTS)
nb = [[] for _ in range(N)]
for (a, b), j in sorted(edges.items()):
nb[a].append((b, j))
nb[b].append((a, j))
return edges, nb
def energy(s, edges):
e = 0
for (a, b), j in edges.items():
e -= j * s[a] * s[b]
return e
def delta(s, nb, i):
# energy change if spin i flips
acc = 0
for k, j in nb[i]:
acc += j * s[k]
return 2 * s[i] * acc
def ground(edges, nb):
s = [1] * N
e = energy(s, edges)
best = e
for g in range(1, 2 ** (N - 1)):
i = (g & -g).bit_length() # spin 1 to N-1 flips
e += delta(s, nb, i)
s[i] = -s[i]
best = min(best, e)
return best
def descend(s, nb, rng, budget):
used = 0
while used < budget:
order = list(range(N))
rng.shuffle(order)
moved = False
for i in order:
used += 1
if delta(s, nb, i) < 0:
s[i] = -s[i]
moved = True
if used >= budget:
break
if not moved:
break
return used
def greedy(edges, nb, rng, budget):
s = [rng.choice((-1, 1)) for _ in range(N)]
descend(s, nb, rng, budget)
return energy(s, edges)
def restarts(edges, nb, rng, budget):
left, best = budget, 10 ** 9
while left > 0:
s = [rng.choice((-1, 1)) for _ in range(N)]
left -= descend(s, nb, rng, left)
best = min(best, energy(s, edges))
return best
def anneal(edges, nb, rng, budget, t0=2.0, t1=0.1):
s = [rng.choice((-1, 1)) for _ in range(N)]
e = energy(s, edges)
best = e
ratio = (t1 / t0) ** (1.0 / budget)
t = t0
for _ in range(budget):
i = rng.randrange(N)
d = delta(s, nb, i)
if d <= 0 or rng.random() < math.exp(-d / t):
s[i] = -s[i]
e += d
best = min(best, e)
t *= ratio
return best
if __name__ == "__main__":
edges, nb = build(random.Random(20261120))
e0 = ground(edges, nb)
print("instance: {} spins, {} couplings, ground energy {}".format(
N, len(edges), e0))
print("hit rate = share of {} trials ending at the ground energy".format(
TRIALS))
print(" budget greedy restarts annealing (mean final E)")
for budget in BUDGETS:
cells, means = [], []
for fn in (greedy, restarts, anneal):
rng = random.Random(7)
res = [fn(edges, nb, rng, budget) for _ in range(TRIALS)]
hits = 0
for r in res:
if r == e0:
hits += 1
cells.append(hits / TRIALS)
means.append(math.fsum(res) / TRIALS)
fmt = " {:>6,} {:.3f} {:.3f} {:.3f}"
fmt += " ({:.2f} {:.2f} {:.2f})"
print(fmt.format(budget, *cells, *means))唯一数据源与引用
范雅福(Fan, Y.). (2026). 《量子启发式组合寻优、拉马努金式直觉猜想与突破性著作推演母典》第 2 章「退火、重启与 Metropolis 准则:逃离局部最优的经典配方」(版本 1.0.0). 5D Library. DOI 待发布
DOI 待发布 · 专著页正式发布后上线(本站暂无专著页) · 5DL-B-364 · v1.0.0 · CC-BY-NC-ND-4.0
BibTeX
@book{fan2026364,
author = {Fan, Yafu},
title = {Quantum-Inspired Combinatorial Search, Abductive Intuition and Computationally Verified Breakthrough Monograph Engineering},
year = {2026},
publisher = {5D Library},
edition = {1.0.0},
note = {DOI pending}
}