示例工程教程【免费下载链接】swift-algorithm-clubAlgorithms 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二者在同一套接受准则下平滑过渡。算法流程与伪代码原文档给出了完整的伪代码骨架其输入为四个要素初始解、初始温度、冷却速率和接受函数输出为搜索到的最优解SbestInput: 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对应当前能量ene对应新能量nete对应当前温度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) - DoubleClonable通过init(current:)从现有实例克隆出新实例。由于模拟退火每轮都要在当前解副本上做扰动、并在接受时替换当前解深拷贝是保证迭代正确性的前提。扩展中还为Array提供了clone()支持元素同样须为Clonable用于复制整个解序列SAObject定义了算法对解对象的全部要求——元素个数count、随机交换两个位置的randSwap(a:b:)、计算当前能量的currentEnergy()、随机洗牌的shuffle()。任何满足该协议的类型都可以作为算法的输入AcceptanceFunc接受函数的类型别名签名为(当前能量, 新能量, 温度) - Double返回一个概率值供主循环与随机数比较。主循环实现func SimulatedAnnealingT: 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 与 Tourclass 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 i1 self.count { destCity self[i1] } 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/Cocoaos(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 Taghavimitghi为 Swift Algorithm Club 编写采用 MIT 许可协议见 simann.swift 文件头声明你可以在遵守协议的前提下将其复用到自己的项目中。赞分享示例工程教程【免费下载链接】swift-algorithm-clubAlgorithms and data structures in Swift, with explanations!项目地址https://gitcode.com/gh_mirrors/sw/swift-algorithm-club点击查看免费下载相关推荐Swift 算法俱乐部Swift 实现深度优先搜索Depth-First SearchSwift 算法俱乐部Swift 实现深度优先搜索Depth First Search 深度优先搜索DFS是图与树数据结构中最基础的遍历与搜索算法之一示例工程教程Swift 算法俱乐部布隆过滤器Bloom Filter完整实现与原理剖析Swift 算法俱乐部布隆过滤器Bloom Filter完整实现与原理剖析 布隆过滤器Bloom Filter是一种节省内存的概率型数据结构用固定长示例工程教程Swift 算法俱乐部最大公约数GCD与最小公倍数LCM的三种 Swift 实现Swift 算法俱乐部最大公约数GCD与最小公倍数LCM的三种 Swift 实现 本文基于 Swift Algorithm Club 仓库中的 GCD示例工程教程上一篇3分钟掌握专业电路绘图Draw.io电子工程库完整指南下一篇Qwen Code IDE 集成实战通过 MCP 协议把终端 Agent 接入 VS Code 生态创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
Swift 算法俱乐部：模拟退火算法（Simulated Annealing）原理、Swift 实现与 TSP 实战
示例工程教程【免费下载链接】swift-algorithm-clubAlgorithms 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二者在同一套接受准则下平滑过渡。算法流程与伪代码原文档给出了完整的伪代码骨架其输入为四个要素初始解、初始温度、冷却速率和接受函数输出为搜索到的最优解SbestInput: 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对应当前能量ene对应新能量nete对应当前温度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) - DoubleClonable通过init(current:)从现有实例克隆出新实例。由于模拟退火每轮都要在当前解副本上做扰动、并在接受时替换当前解深拷贝是保证迭代正确性的前提。扩展中还为Array提供了clone()支持元素同样须为Clonable用于复制整个解序列SAObject定义了算法对解对象的全部要求——元素个数count、随机交换两个位置的randSwap(a:b:)、计算当前能量的currentEnergy()、随机洗牌的shuffle()。任何满足该协议的类型都可以作为算法的输入AcceptanceFunc接受函数的类型别名签名为(当前能量, 新能量, 温度) - Double返回一个概率值供主循环与随机数比较。主循环实现func SimulatedAnnealingT: 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 与 Tourclass 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 i1 self.count { destCity self[i1] } 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/Cocoaos(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 Taghavimitghi为 Swift Algorithm Club 编写采用 MIT 许可协议见 simann.swift 文件头声明你可以在遵守协议的前提下将其复用到自己的项目中。赞分享示例工程教程【免费下载链接】swift-algorithm-clubAlgorithms and data structures in Swift, with explanations!项目地址https://gitcode.com/gh_mirrors/sw/swift-algorithm-club点击查看免费下载相关推荐Swift 算法俱乐部Swift 实现深度优先搜索Depth-First SearchSwift 算法俱乐部Swift 实现深度优先搜索Depth First Search 深度优先搜索DFS是图与树数据结构中最基础的遍历与搜索算法之一示例工程教程Swift 算法俱乐部布隆过滤器Bloom Filter完整实现与原理剖析Swift 算法俱乐部布隆过滤器Bloom Filter完整实现与原理剖析 布隆过滤器Bloom Filter是一种节省内存的概率型数据结构用固定长示例工程教程Swift 算法俱乐部最大公约数GCD与最小公倍数LCM的三种 Swift 实现Swift 算法俱乐部最大公约数GCD与最小公倍数LCM的三种 Swift 实现 本文基于 Swift Algorithm Club 仓库中的 GCD示例工程教程上一篇3分钟掌握专业电路绘图Draw.io电子工程库完整指南下一篇Qwen Code IDE 集成实战通过 MCP 协议把终端 Agent 接入 VS Code 生态创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
