关于「退火、重启与 Metropolis 准则:逃离局部最优的经典配方」,《量子启发与猜想证伪》给出的定量结论是什么?

结论:第二章在受挫自旋玻璃上比较贪心、随机重启与退火:贪心命中率停在 0.060,随机重启随预算升到 0.985,切碎预算的多段短退火同样可达。

数据口径:书中参数为示意,全部计算由书中程序生成。 本书不构成投资、学术评审或量子硬件方面的建议。

English version

对照数据表

下表数字由本章 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
budgetgreedyrestartsannealing(mean final E)
3000.0600.3850.235(-42.39 -47.58 -46.05)
1,0000.0600.8400.340(-42.39 -48.68 -46.98)
3,0000.0600.9850.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}
}

本书其他章节结论