Swift 算法俱乐部：模拟退火算法（Simulated Annealing）原理、Swift 实现与 TSP 实战-平芜编程栈

示例工程
教程

【免费下载链接】swift-algorithm-club

Algorithms and data structures in Swift, with explanations!

项目地址：https://gitcode.com/gh_mirrors/sw/swift-algorithm-club

模拟退火（Simulated Annealing）是一种受金属退火工艺启发的全局优化元启发式算法，用于在（通常是离散的）大型搜索空间中逼近全局最优解。本指南以 Swift Algorithm Club 仓库中Simulated annealing/目录下的实现为核心，系统讲解其原理、伪代码、通用 Swift 框架，并结合 20 城市旅行商问题（TSP）的完整示例，帮助你掌握该算法的参数含义、接受准则与调优思路。读完本文，你将能够独立使用仓库中的SimulatedAnnealing泛型框架求解自己的组合优化问题。

算法思想：从冶金退火到组合优化

模拟退火的名字源自冶金学中的"退火"工艺：材料被加热到高温后，在受控条件下缓慢冷却，从而消除内部缺陷、提升强度与耐久性。这一过程在数学上被类比为在一个巨大的搜索空间中寻找最小代价解——算法通过利用热力学系统的特性（温度、能量、随机扰动）来逼近全局最优。

从计算角度看，它属于元启发式算法（metaheuristic），核心目标是在往往包含大量局部最优解的搜索空间中，以可接受的计算代价近似求得全局最优解。仓库根目录的 README.markdown 将其概括为"用于在（通常是离散的）大型搜索空间中逼近全局最大值的概率技术"。

与爬山法（Hill Climbing）的本质差异

爬山法是一类经典的局部搜索技术，它不允许向下的移动（即只接受使目标函数变差的解不合法），因此极易陷入局部最优解而无法自拔。模拟退火的关键突破在于：允许一定概率接受"更差"的解（向下移动），从而具备逃出局部最优的能力。

这种允许向下移动的概率具有鲜明的温度依赖特性：

高温阶段：接受"差解"的概率很高。此时接受函数表现出类似混沌的行为，搜索空间被大幅放宽，有助于大范围探索、跳出局部最优；
低温阶段：接受"差解"的概率逐渐降低。搜索空间被收窄，算法把注意力集中在局部改进上，趋于稳定收敛。

简言之，温度相当于一个"调节旋钮"：高温负责全局探索（exploration），低温负责局部开发（exploitation），二者在同一套接受准则下平滑过渡。

算法流程与伪代码

原文档给出了完整的伪代码骨架，其输入为四个要素：初始解、初始温度、冷却速率和接受函数；输出为搜索到的最优解Sbest：

Input: initial, temperature, coolingRate, acceptance Output: Sbest Scurrent <- CreateInitialSolution(initial) Sbest <- Scurrent while temperature is not minimum: Snew <- FindNewSolution(Scurrent) if acceptance(Energy(Scurrent), Energy(Snew), temperature) > Rand(): Scurrent = Snew if Energy(Scurrent) < Energy(Sbest): Sbest = Scurrent temperature = temperature * (1-coolingRate)

逐步拆解这段伪代码，可以看到算法由四个核心环节构成：

初始化：基于输入构造一个初始可行解Scurrent，并暂记为当前最优Sbest；
邻域扰动：在当前解附近随机生成新解Snew（在 TSP 示例中体现为交换两个城市的位置）；
概率接受：调用接受函数，将其返回值与随机数Rand()比较，若满足条件则接受新解为当前解——这是模拟退火区别于爬山法的关键一步；
降温调度：每轮迭代末尾按temperature = temperature * (1 - coolingRate)降低温度，直到温度降至最小值（仓库实现中的终止条件为temp > 1）为止。

值得注意，伪代码中if Energy(Scurrent) < Energy(Sbest)这一步保证了Sbest只记录历史最优，因此即便算法在高温阶段频繁接受差解导致当前解变差，最优解也不会丢失——这是模拟退火工程实现中的标准防御手段。

常见接受准则：Metropolis 判据

模拟退火的接受准则有多种形式，原文档给出的是最经典的基于指数分布的判据：

P(accept) <- exp((e - ne) / T)

其中：

符号	含义
`e`	当前解的能量（当前解对应的代价，如 TSP 中的总路程）
`ne`	新解的能量（新解对应的代价）
`T`	当前温度

该公式的物理直觉非常清晰：

当新解更优（ne < e）时，(e - ne) > 0，指数大于 1，接受概率被截断为 1，即无条件接受改进；
当新解更差（ne > e）时，指数为负，接受概率落在(0, 1)区间内，且温度越高、代价差距越小，接受概率越大——这正是高温阶段容忍"坏移动"、低温阶段拒绝"坏移动"的数学来源。

仓库示例代码中的接受函数实现（见 simann_example.swift）与上述公式完全一致：

let acceptance : AcceptanceFunc = { (e: Double, ne: Double, te: Double) -> Double in if ne < e { return 1.0 } return exp((e - ne) / te) }

注意其与伪代码的对应关系：e对应当前能量e，ne对应新能量ne，te对应当前温度T。

仓库源码剖析：通用泛型框架 simann.swift

仓库将模拟退火的核心逻辑抽象为一个与具体问题解耦的泛型函数，定义在 simann.swift 中。理解这套抽象，你就能把算法复用到任何"可以衡量能量、可以随机扰动"的问题上。

三个关键抽象

protocol Clonable { init(current: Self) } protocol SAObject: Clonable { var count: Int { get } func randSwap(a: Int, b: Int) func currentEnergy() -> Double func shuffle() } typealias AcceptanceFunc = (Double, Double, Double) -> Double

Clonable：通过init(current:)从现有实例克隆出新实例。由于模拟退火每轮都要在"当前解副本"上做扰动、并在接受时替换当前解，深拷贝是保证迭代正确性的前提。扩展中还为Array提供了clone()支持（元素同样须为Clonable），用于复制整个解序列；
SAObject：定义了算法对"解对象"的全部要求——元素个数count、随机交换两个位置的randSwap(a:b:)、计算当前能量的currentEnergy()、随机洗牌的shuffle()。任何满足该协议的类型都可以作为算法的输入；
AcceptanceFunc：接受函数的类型别名，签名为(当前能量, 新能量, 温度) -> Double，返回一个概率值，供主循环与随机数比较。

主循环实现

func SimulatedAnnealing<T: SAObject>(initial: T, temperature: Double, coolingRate: Double, acceptance: AcceptanceFunc) -> T { var temp: Double = temperature var currentSolution = initial.clone() currentSolution.shuffle() var bestSolution = currentSolution.clone() while temp > 1 { let newSolution: T = currentSolution.clone() let pos1: Int = Int.random(in: 0 ..< newSolution.count) let pos2: Int = Int.random(in: 0 ..< newSolution.count) newSolution.randSwap(a: pos1, b: pos2) let currentEnergy: Double = currentSolution.currentEnergy() let newEnergy: Double = newSolution.currentEnergy() if acceptance(currentEnergy, newEnergy, temp) > Double.random(in: 0 ..< 1) { currentSolution = newSolution.clone() } if currentSolution.currentEnergy() < bestSolution.currentEnergy() { bestSolution = currentSolution.clone() } temp *= 1-coolingRate } return bestSolution }

对照伪代码，逐条对应实现细节：

伪代码步骤	Swift 实现位置	说明
初始化解	`initial.clone()`+`shuffle()`	先克隆输入，再随机洗牌生成随机可行解
记录最优	`bestSolution = currentSolution.clone()`	以随机初始解作为首个候选最优
邻域扰动	`randSwap(a:pos1, b:pos2)`	随机选取两个下标并交换，`pos1/pos2`均为`0..<count`内均匀随机
概率接受	`acceptance(...) > Double.random(in: 0..<1)`	接受函数输出与`[0,1)`均匀随机数比较，与伪代码`> Rand()`一一对应
更新最优	`currentSolution.currentEnergy() < bestSolution.currentEnergy()`	能量越低越好，仅记录改进
降温	`temp *= 1-coolingRate`	与伪代码`temperature * (1-coolingRate)`完全一致

两个值得注意的实现细节：

终止条件：仓库实现以while temp > 1作为停止条件，即"温度降至 1 以下视为冷却完毕"。这是一个隐式的"最小温度"设定，你也可以根据问题规模调整该阈值；
能量缓存：示例中的Tour.currentEnergy()使用了energy属性缓存，首次计算后复用结果，避免重复遍历整条回路（详见下文）。

实战案例：20 城市旅行商问题（TSP）

原文档指出，仓库用该算法求解了一个包含20 个城市的旅行商问题实例，完整代码位于 simann_example.swift。TSP 的目标是找到一条访问所有城市恰好一次并返回起点的最短回路——它是一个经典的 NP 难组合优化问题，也是模拟退火最经典的应用场景之一。

数据结构：Point 与 Tour

class Point: Clonable { var x: Int var y: Int init(x: Int, y: Int) { self.x = x; self.y = y } required init(current: Point){ self.x = current.x self.y = current.y } }

Point用整数坐标(x, y)表示一个城市，并实现Clonable协议。两点间的欧几里得距离通过自定义中缀运算符<->计算（采用平方和开方，等价于两点间的直线距离）：

infix operator <->: AdditionPrecedence extension Point { static func <-> (left: Point, right: Point) -> Double { let xDistance = (left.x - right.x) let yDistance = (left.y - right.y) return Double((xDistance * xDistance) + (yDistance * yDistance)).squareRoot() } }

Tour则是SAObject的具体实现，内部以Points（即[Point]）保存城市访问顺序：

class Tour: SAObject { var tour: Points var energy: Double = 0.0 var count: Int { return self.tour.count } ... }

其三个协议方法的实现如下：

func randSwap(a: Int, b: Int) -> Void { let (cpos1, cpos2) = (self[a], self[b]) self[a] = cpos2 self[b] = cpos1 } func currentEnergy() -> Double { if self.energy == 0 { var tourEnergy: Double = 0.0 for i in 0..<self.count { let fromCity = self[i] var destCity = self[0] if i+1 < self.count { destCity = self[i+1] } let e = fromCity<->destCity tourEnergy = tourEnergy + e } self.energy = tourEnergy } return self.energy } func shuffle() { self.tour.shuffle() }

randSwap交换两个下标位置的城市，即"2-opt"式的最小邻域扰动；
currentEnergy从第 0 个城市出发，依次累加相邻城市间距，最后一个城市与首城相连（destCity = self[0]兜底），得到整条回路的总路程；该值即"能量"，越小越好；
shuffle直接复用 Swift 标准库的Array.shuffle()打乱访问顺序，用于生成随机初始解。

20 个城市的输入数据

示例中的城市坐标如下（共 20 个点，分布在 20×200 的平面区域内）：

let points: [Point] = [ (60 , 200), (180, 200), (80 , 180), (140, 180), (20 , 160), (100, 160), (200, 160), (140, 140), (40 , 120), (100, 120), (180, 100), (60 , 80) , (120, 80) , (180, 60) , (20 , 40) , (100, 40) , (200, 40) , (20 , 20) , (60 , 20) , (160, 20) , ].map{ Point(x: $0.0, y: $0.1) }

注意其中出现了三处重复坐标（(60, 200)与(60, 20)不同，但(60, 200)与列表末段的(60, 20)之外，(100, 160)与(100, 120)等均不重复；真正重复的是(20, 160)与(20, 40)？——实际上按坐标逐一核对，所有 20 个点坐标均互不相同）。从源码结构看，这里直接以元组字面量配合map构造点集，坐标布局接近均匀网格，便于直观验证最终回路形态。

参数设定与运行

示例以如下参数调用算法：

let result: Tour = SimulatedAnnealing(initial : Tour(points: points), temperature : 100000.0, coolingRate : 0.003, acceptance : acceptance)

初始温度100000.0：足够高，保证初期几乎接受任意扰动，充分探索解空间；
冷却速率0.003：每轮降温0.3%。以temp > 1为终止条件推算，从 100000 降到 1 需要约ln(100000)/0.003 ≈ 3837轮迭代；
接受函数：即上文展示的指数判据。

运行后，SimulatedAnnealing会在入口与出口分别打印初始解与最优解的能量：

Initial solution: <随机初始回路的总路程> Best solution: <退火搜索后的最优总路程>

由于初始解来自随机洗牌，两次运行的结果会有所不同，但最终能量通常显著低于初始随机解——这正是模拟退火在有限迭代内逼近较优解的证据。该示例文件顶部包含平台适配代码（os(OSX)引入Foundation/Cocoa，os(Linux)引入Glibc），因此既可在 macOS 也可在 Linux 上使用 Swift 直接运行：swift simann_example.swift。

参数调优：四个输入如何影响收敛

原文档强调算法有四个输入参数，理解它们对工程实践至关重要：

参数	作用	仓库示例取值	调优方向
`initial`（初始解）	退火起点，示例中为随机洗牌后的 20 城市回路	`Tour(points: points)`	可用贪心解等更优起点加速收敛
`temperature`（初始温度）	控制初期接受差解的概率，决定探索强度	`100000.0`	过小易早熟陷入局部最优；过大则浪费大量迭代在纯随机徘徊上
`coolingRate`（冷却速率）	每轮降温比例，决定降温快慢与总迭代数	`0.003`	过大会降温过快、来不及收敛；过小则迭代次数剧增
`acceptance`（接受函数）	决定"差解"的接受概率，`(e, ne, T) -> 概率`	Metropolis 指数判据	可替换为其他准则以适配不同问题

从 simann.swift 的实现可以看到三者如何协同：初始温度与冷却速率共同决定总迭代轮数（约ln(最小温度/初始温度) / coolingRate），接受函数则决定每一轮是否接受扰动。若冷却速率过慢而迭代上限不足，算法可能尚未冷却即被截断；若初始温度过低，接受函数在初期就趋于拒绝差解，退化回爬山法。

适用场景与注意事项

模拟退火的优势使其特别适合以下场景：

解空间巨大且离散的组合优化问题，如 TSP、排程、布局、图划分等；
目标函数可计算、邻域结构可定义，但无法保证多项式时间内求出精确最优解的问题；
对解质量要求较高、但可接受"近似最优"的应用（原文档将其明确定位为"逼近全局最优"的元启发式）。

使用时的注意事项同样值得强调：

结果具有随机性：初始解洗牌与每轮的随机数均引入不确定性，正式使用时应多次运行取最优，或引入固定随机种子便于复现；
参数高度依赖问题规模：仓库示例中100000的初始温度与0.003的冷却速率是针对 20 城市实例调出的，换用更大规模问题需重新标定；
能量函数需单调可比：算法依赖"能量越低越好"这一约定（currentEnergy() < bestSolution.currentEnergy()），若你的目标是最大化，需将目标函数取负或取倒数。

延伸阅读与相关资源

算法的通用框架与协议抽象见 simann.swift，完整 TSP 示例见 simann_example.swift，原始说明文档见 Simulated annealing/README.md；
仓库中还收录了另一类"模拟生物进化"的元启发式算法——遗传算法（Genetic），其文档同样以旅行商问题为示例，可与模拟退火对照学习；
TSP 属于指数级复杂度的代表问题，关于其计算复杂度的讨论可参考 Big-O Notation.markdown 中对O(2^n)的介绍。

本文介绍的实现由 Mike Taghavi（mitghi）为 Swift Algorithm Club 编写，采用 MIT 许可协议（见 simann.swift 文件头声明），你可以在遵守协议的前提下将其复用到自己的项目中。