搜索与优化

古典人工智能的主要研究内容就是用一般性的策略，在巨大的搜索空间里做智能决策。

形式化定义

在计算理论中，如果你能把问题 A 归约为问题 B，那么只要解决了 B，你就解决了 A。我们能否把任何人工智能问题都建模成一类问题，从而让人工智能和NP问题一样可以方便归约呢？人工智能先驱赫伯特·西蒙 (Herbert Simon) 和艾伦·纽厄尔 (Allen Newell) 在 1959 年开发的通用问题求解器GPS (General Problem Solver) 程序。它是历史上第一个试图将“搜索策略”与“领域知识”分离的 AI 程序，旨在模拟人类解决问题的思维方式。

在AIMA中，我们可以看到AI工程实践中将通用问题求解转化为一种受约束的搜索。换句话说，无论你的问题多么复杂，只要你想让计算机帮你解决，那么你最终就必须要把它变成一种搜索语言。换言之，只要建模水平足够高，那么世界上就没有搜索解决不了的通用难题。我们把AIMA中的这种搜索版本的通用问题求解器称为问题求解智能体（problem-solving agent）。

问题求解智能体主要解决状态空间搜索问题，其计算过程被称为搜索（search）。在后面的讨论中，我们说的搜索问题就是指通用问题。

首先，对于任何搜索问题，我们都要明确状态：

状态空间 state space，包含所有可能的环境状态
初始状态 initial state，智能体启动时的状态
目标状态 goal state，一个或者多个

从当前位置或任意位置到目标位置都会产生路径。具体而言：

路径 path，一个动作序列形成一根条路径
解 solution，一条从初始状态到某个目标状态的路径

我们用公式\(g(n)\)来表示从初始状态（Initial State）到达当前状态 \(n\)的路径总长度或总代价。AI 通过比较不同路径的 \(g(n)\) 来寻找最经济的方案。

构建路径代价的基础组件可以表示为单步代价函数：

\[ c(s, a, s') \]

其中：

\(s\)：当前所处的状态。
\(a\)：在该状态下采取的动作（Action）。
\(s'\)：采取动作后转移到的新状态。

我们用路径代价 (Path Cost)指从 初始状态开始 ，到达当前节点所经历的所有单步代价的总和。

在搜索问题中，AI 的目标通常是找到一条从初始状态到目标状态的路径，使得 总路径代价 \(g(n)\) 最小化 。在伪代码中，路径代价被记录为 node.PATH-COST。它的计算方式是累加的：child.PATH-COST = node.PATH-COST + action-cost。最佳优先搜索 （包括 UCS 和 A）在 reached 表中记录和比较的正是这个 累积的路径代价* ，以此来判断是否发现了一条更优的路线。

此外，动作和动作代价函数为：

行动 action，给定一个状态s，action(s) 将返回可执行动作集合
转移模型 transition model，RESULT(s, a) 返回在状态s下执行动作a所产生的状态
动作代价函数 action cost function，ACTION-COST(s, a, s')，给出了在状态s中执行动作a，进而转移到状态s'的数值代价。

我们假设动作代价是可累加的，也就是说，一条路径的总代价是各个动作代价的总和。最优解（optimal solution） 是所有解中路径代价最小的解。我们暂时假设所有动作代价都为正数，来减少复杂性。

状态空间可以用图来表示。图中的顶点表示状态，顶点之间的有向边表示动作。

1769214670133

在强化学习中，这种表达方式被保留了下来。这种形式化搜索的思路从未在AI发展中消失过，Alpha Go通过蒙特卡洛树搜索来看远一点，并通过神经网络评估当前状态的胜算，从而指导搜索往更有希望的方向走；OpenAI ChatGPT o1的思维链（CoT）本质上就是在予以空间里寻找解的路径，并通过搜索来尝试多种推理路径，在失败时回溯并尝试其他路径。

无信息搜索

在算法学习中我们一般都会学习BFS和DFS，这两种算法都属于无信息搜索（Uninformed Search）。

无信息搜索只知道：

起始点
合法的动作
目标

无信息搜索的局限性在于效率低下，由于不做剪枝，也没有任何策略，一旦状态空间很大，需要记录和搜索的状态数量就会非常大。因此，无信息搜索可以被视为一种暴力解法，其特点是只要时间和空间足够，一定能找到答案。

这里要注意，记录访问点（Explored Set） 仅仅是一种 优化手段 ，用来把“树搜索”变成“图搜索”。

树搜索的意思就是算法把搜索空间想象成一棵不断向下生长的“树”，它不关心某个状态（比如拼图的一个特定摆法）之前是否出现过。因此，如果你从 A 走到 B，再从 B 走回 A，树搜索会把第二个 A 当作一个全新的节点继续扩展。

图搜索在树搜索的基础上增加了一个“记事本”，也就是 Explored Set（已探索集合） 。每当算法彻底处理完一个节点，就会把它丢进 Explored Set。在生成新节点时，算法会先查阅账本。如果这个状态已经在 Explored Set（或者还在等待处理的 Frontier）里了，就直接扔掉，不再重复探索。这保证了算法不会在同一个坑里摔两次，极大地提升了效率，并解决了死循环问题。

BFS与Dijkstra

详见算法笔记。

双向搜索（Bidirectional Search） 同样是基于 BFS（广度优先搜索） 的思想，但它通过“两头堵”的方式极大地提升了搜索效率。

一致代价搜索

广度优先搜索假设每一步的代价都是相等的（比如都是 1）。在现实世界中，不同动作的代价往往不同（例如：走高速路快但贵，走小路慢但免费）。UCS 能够处理这种非等代价的情况，确保找到的是总成本最低的最优路径。

UCS的核心思路就是：总是优先expanding the cheapest path.

DFS与内存问题

回溯搜索是DFS的一种变体，使用的内存更少。

为了避免DFS陷入无限路径，可以使用深度受限搜索（depth-limited search）。

迭代加深搜索（iterative deepening search） 也是类似的道理。

启发式搜索

启发式搜索（Heuristic Search） 在无信息搜索的基础上增加了启发函数（heuristic function）。

启发函数

在算法与AI语境下，如果我们只说Heuristic，那么一般都是指启发函数（heuristic function），写作h(n)。这个词起源于希腊语 heuriskein （发现）。

我们用g(n)来表示实际代价，h(n)来表示从当前节点n到目标节点的估计代价。启发式搜索的评价函数中至少需要有h(n)。

这里要注意，启发式函数是可以看到“棋盘布局”的，但是这种布局并非实际的布局，而是一个先天设定的固定布局。比如说，对于地图导航来说，启发式搜索可以把a到b的直线距离作为启发函数。

Admissiblity

如果一个启发式函数 \(h(n)\) 被称为是 可容许的(Admissible)，它必须满足一个核心条件：永远不会高估（Never Overestimate）到达目标的实际最小代价，即：

\[ 0 \leq h(n) \le h^*(n) \]

对于任何节点 \(n\)， \(h^*(n)\) 是到达目标的真实最低成本。这是一个“乐观”的估计，认为路程最多还有这么远，甚至可能更近，但绝不会比实际更远。可采纳的启发式函数可以保证找到通往目标的最优解（即路径成本最低的解）。

如果一个启发式函数是一致的（Consistent），其必须满足：对于任意节点 \(n\) 及其后继节点 \(n'\)，从 \(n\) 到目标的预估代价，不大于“从 \(n\) 到 \(n'\) 的实际代价”与“从 \(n'\) 到目标的预估代价”之和，即：

\[ h(n) \le cost(n, a, n') + h(n') \]

这类似于几何学中的 三角不等式 。随着路径的推进，估计代价的下降速度不会超过实际消耗的代价。它是 A 算法在图搜索（Graph Search）中不需要重复访问已关闭节点（Closed Set）就能找到最优解的 充分条件* 。

对于树搜索，启发式函数必须满足Admissibility；对于图搜索，启发式函数必须满足Consistency。

最佳优先搜索

最佳优先搜索 (Best-First Search)的核心逻辑是：永远从待选区域中挑一个“看起来最好”的节点来处理。

算法通过两个关键容器来协同工作：

Frontier（边界） ：一个以 评价函数 \(f\) 排序的优先队列 。它保证每次弹出的节点都是当前 \(f(n)\) 值最小（即被认为“最佳”）的。
Reached（已到达） ：一个查找表（Hash Table），记录状态到节点的映射。它不仅用于去重，还存储了到达每个状态的最低路径代价。

其伪代码如下：

BEST-FIRST-SEARCH 最佳优先搜索
起始点s
frontier 优先队列，初始化加入起始点s，记录现在正在搜索的点集合，按评价函数f排序
reached 查找表，记录起始点s到其他点的距离，起始点s也放入其中（后续可能回到起始点）

当frontier不为空的时候：
    从frontier中弹出元素node
    如果node是目标点，结束搜索，return node.
    如果node不是目标点：
        看一下node这里能做什么动作
        对于每个能做的动作：
            子状态 s' = RESULT(s, action)
            计算s到s'的花费（路径代价）
            如果s'不在reached中，或者这个花费比已经记录的更小：
                更新reached[s']为这个新节点
                将s'作为一个新节点加入frontier队列

搜索结束后，如果还没有找到goal，则说明搜索失败，return Failure.

最佳优先搜索（Best-First Search）的意义在于它提供了一个 通用的算法框架 。通过简单地更换 评价函数 \(f(n)\)**** ，它就能在不同的搜索策略之间切换，从而应对不同类型的复杂问题。

它的核心价值是： 不再盲目地按固定顺序搜索，而是根据某种“标准”优先处理最有希望的节点 。

你可以通过调整 \(f(n)\) 的定义，让这个通用的“框架”变成你熟悉的具体算法：

f(n) = 节点深度 → BFS
f(n) = g(n) → 一致代价搜索UCS
f(n) = g(n) + h(n) → A-Star

贪心最佳优先搜索因为用到了h(n)，所以也算是启发式搜索。

A-Star

A*算法是complete且optimal的。

\[ \large \underbrace{f(n)}_{\text{Total cost of node}} = \underbrace{g(n)}_{\substack{\text{Path cost} \\ \text{(the true value)}}} + \underbrace{h(n)}_{\substack{\text{Heuristic} \\ \text{(estimate to goal)}}} \]

最经典的应用是8-Puzzle问题：8 数码问题 (8-Puzzle) 是一个经典的路径搜索难题，通常由一个 \(3 \times 3\) 的网格组成，其中包含 8 个带有数字（1-8）的方块和一个空位。

游戏的目标是通过滑动方块，将乱序的初始状态调整为特定的目标状态（通常是数字按 1 到 8 顺序排列，空位在最后）。你只能将与空位相邻的方块移动到空位中，这在视觉上等同于“移动空位”到上、下、左、右四个方向。

为了让 A* 运行得更快且保证找到最少步数（最优解），通常使用以下两种一致的启发函数：

错位棋子数 (Misplaced Tiles) ：计算当前棋盘上有多少个数字没有处在正确的目标位置上。
曼哈顿距离 (Manhattan Distance) ：计算每个棋子当前位置与目标位置之间的 水平和垂直距离之和 。这是最常用的启发函数，比错位棋子数更“精准”，能显著减少搜索的节点数量。

一般认为具有一直启发式函数的A搜索是效率最优（optimally efficient） 的，因为任何从初始状态扩展搜索路径并使用相同启发式信息的算法都必须扩展A的所有必然扩展节点。这种高效也来自于对寻找最优解没有帮助的搜索树节点进行剪枝（pruning）。

我们来看下面这个例子：

1769656921093

\(h\) 值（启发式值）只代表“当前节点到终点”的预估距离，它不具有累加性。因此在计算每个节点的\(f\)值（总评价分数）时：

\[ f(n) = g(n) + h(n) \]

A 算法的核心是维护一个优先队列，每次选择 \(f(n) = g(n) + h(n)\) 最小的节点进行 扩展（Expand）* 。

\(g(n)\)：从起点 A 到当前节点的实际代价。
\(h(n)\)：当前节点到目标节点的启发式估计值（图中圆圈内的值）。
Tie-breaking（破局规则） ：如果 \(f\) 值相同，按照从左到右的顺序访问。
终止条件 ：当目标节点被扩展时，算法停止并返回路径。

我们需要逐步跟踪优先队列（Open List/Frontier）的状态：

扩展 A : \(g(A)=0, h(A)=1 \Rightarrow f(A)=1\)。

生成子节点：B 和 C。
\(f(B) = g(B) + h(B) = 2 + 1 = 3\)
\(f(C) = g(C) + h(C) = 1 + 4 = 5\)
队列 : \([(B, f=3), (C, f=5)]\)

扩展 B :（因为 \(f=3\) 最小）

生成子节点：D, E, F。
\(f(D) = (2+13) + 2 = 17\)
\(f(E) = (2+2) + 5 = 9\)
\(f(F) = (2+8) + 0 = 10\)
队列 : \([(C, f=5), (E, f=9), (F, f=10), (D, f=17)]\)

扩展 C :（因为 \(f=5\) 最小）

生成子节点：G, H, I。
\(f(G) = (1+2) + 4 = 7\)
\(f(H) = (1+4) + 3 = 8\)
\(f(I) = (1+5) + 2 = 8\)
队列 : \([(G, f=7), (H, f=8), (I, f=8), (E, f=9), (F, f=10), (D, f=17)]\)

扩展 G :（因为 \(f=7\) 最小）

生成子节点：L。
\(f(L) = (1+2+10) + \infty = \infty\)
队列 : \([(H, f=8), (I, f=8), (E, f=9), (F, f=10), (D, f=17), (L, f=\infty)]\)

扩展 H :（\(H\) 和 \(I\) 的 \(f=8\) 相同，按左到右顺序先扩 \(H\)）

生成子节点：M。
\(f(M) = (1+4+10) + \infty = \infty\)
队列 : \([(I, f=8), (E, f=9), (F, f=10), (D, f=17), (L, f=\infty), (M, f=\infty)]\)

扩展 I :（因为 \(f=8\) 最小）

生成子节点：N。
\(f(N) = (1+5+3) + 0 = 9\)
队列 : \([(E, f=9), (N, f=9), (F, f=10), (D, f=17), \dots]\)

扩展 E :（\(E\) 和 \(N\) 的 \(f=9\) 相同，按左到右顺序先扩 \(E\)）

生成子节点：K。
\(f(K) = (2+2+5) + \infty = \infty\)
队列 : \([(N, f=9), (F, f=10), (D, f=17), \dots]\)

扩展 N :（\(f=9\) 最小。由于 N 是目标节点且被扩展，搜索终止）

被扩展的节点顺序为：A, B, C, G, H, I, E, N

算法返回的最终路径是从起点到被扩展的目标节点 N 的回溯：

N 的父节点是 I
I 的父节点是 C
C 的父节点是 A

最终路径：A \(\rightarrow\) C \(\rightarrow\) I \(\rightarrow\) N

最终路径的总成本即为 \(g(N)\)：

\(Cost(A, C) = 1\)
\(Cost(C, I) = 5\)
\(Cost(I, N) = 3\)
总成本 \(1 + 5 + 3 = 9\)****

IDA*

※ 滑动谜题（N-Puzzle）

滑动谜题（N-Puzzle）是算法领域的“果蝇”——通过研究它，我们可以窥探到搜索算法从简单到复杂的整个进化史。

规模	别名	状态空间	目标	最佳算法	核心启发式 (Heuristic)	难度评级
\(2 \times 3\)	LeetCode 773	720	最优解	BFS	无需 (或曼哈顿)	🟢 入门
\(3 \times 3\)	8-Puzzle	18万	最优解	A*	曼哈顿距离	🟢 简单
\(4 \times 4\)	15-Puzzle	10万亿	最优解	IDA*	曼哈顿 +线性冲突	🟡 进阶
\(5 \times 5\)	24-Puzzle	\(10^{25}\)	最优解	IDA*	模式数据库 (PDB)	🔴 困难
\(6 \times 6\)	35-Puzzle	\(10^{41}\)	可行解	加权 A*/ 贪婪	不相交 PDB / 深度学习	⚫ 地狱 (NP-Hard)

局部搜索

局部搜索 （Local Search）是一种用于解决组合优化问题的 启发式算法 （Heuristic Algorithm）。简单来说，它的核心思想是“ 走一步看一步，只选更好的 ”。算法从一个初始解开始，通过不断地在当前解的“邻居”中寻找更优解来逐步改进，直到达到一个局部最优状态或满足停止条件。

虽然从原理上来看，局部搜索并不能找到全局最优解，而会被困在局部最优上，但是由于局部搜索已经足够好，足够用于解决许多无法使用全局最优解的情况。同时，局部搜索通常是很多高级算法的“内核”。大家会利用它极快的搜索速度，配合一些“跳出陷阱”的机制。

爬山搜索

参见如下State Space Landscape：

1769655420744

爬山算法（Hill Climbing） 是一种 贪心算法 。它的逻辑极其简单：

随机上山 ：随机选一个点作为初始位置。
环顾四周 ：检查当前位置附近的相邻点（邻域）。
向上移动 ：如果有比现在更高（更好）的点，就迈过去。
止步巅峰 ：如果四周所有的点都比现在低，就认为到达了山顶，停止搜索。

由于爬山算法只看眼前、不走回头路，它经常会遇到以下三个尴尬的处境：

局部最大值（Local Maxima） ：正如你所说的，它爬上了一个小土丘，虽然不是整座山的最高峰，但由于四周都在下坡，它会误以为自己已经登顶。
高原/平原（Plateau） ：周围一片平坦。算法发现往哪走都一样，于是失去了方向，只能在平地上乱逛（随机游走）。
山脊（Ridge） ：这是一个很有趣的现象。山脊窄且陡峭，如果你只能沿东西或南北方向走，每一步都可能在下坡，导致算法在山脊两侧反复横跳，却很难顺着脊线向上。

爬山算法本身并不是一个很好的算法，但是我们可以以此为基础，扩展出实用的算法方案。

随机爬山法引入了随机（Stochastic） 概念：在所有向上的路中，随机选一条，而不是选最陡的。有一定概率避开那些窄小的局部巅峰。这里出现了Exploration vs. Exploitation的tradeoff，这一点在后来的强化学习中尤为重要。

基于随机性的随机重启爬山法 (Random-restart)是爬山算法中最实用的方案 。爬到一个山顶后，直接把自己传送到另一个随机起点重新爬。只要重启次数够多，找到最高峰的概率极大。

Min-Conflicts

※ N-Queens（可行解）

八皇后问题 （8-Queens Problem）中，一个“状态”就是棋盘上 8 个皇后的完整布局。我们可以很容易地定义 邻域（Neighbors） ：即移动其中一个皇后到同一列的其他行。八皇后问题有一个非常直观的 评价函数 \(h\)* ： *当前棋盘上互相攻击的皇后对数。我们的目标是最小化这个 \(h\)（在算法中可以理解为爬向海拔最低点，即“下山”）。

随机重启动爬山法在概率上是完备的。只要你重新启动的次数足够多，它几乎 100% 能找到八皇后的解（因为状态空间是有限的）。它的效率取决于“找到解的状态”在所有状态中的密度。对于八皇后（8x8），它很快；但对于八千皇后，随机重启的盲目性就会显现出来。

在八皇后（以及所有的 N 皇后）问题领域，最小冲突启发式（Min-Conflicts） 通常被认为比任何形式的爬山法都更接近“最优局部搜索解”：

随机重启爬山法： 每次可能要评估所有皇后的所有移动位置，选一个最好的（计算量大）。
Min-Conflicts： 只随机选一个有冲突的皇后，然后只为它寻找冲突最少的位置。
实测数据： 对于 1,000,000 皇后问题，随机重启动爬山法可能还在不断重置棋盘时，Min-Conflicts 通常在 50 步以内就能收敛到解。

N 的范围	最佳算法	核心逻辑	耗时
\(N \le 20\)	标准回溯	普通 DFS 就能搜到。	毫秒级
\(20 < N \le 10^4\)	局部搜索 (Min-Conflicts)	爬山法的变种。先乱放，然后每次移动冲突最多的皇后。	秒级 (极快)
\(N > 10^4\)	数学构造法	利用数学公式直接算出坐标（如\(N \pmod 6\)的规律）。	\(O(N)\)毫秒级

这里要注意，如果要求的是所有解，就是另外一个情况了，需要用回溯法和位运算回溯，并且在N>=20时无最佳算法，目前超级计算机最多能算到N=27。

元启发式算法

元启发式算法的核心在于处理探索（Exploration）与开发（Exploitation） 的矛盾：

全局搜索（Exploration）
局部寻优（Exploitation）

元启发通过某种机制（如模拟退火的温度、遗传算法的变异）动态地调节这两者的比例，从而让算法得以脱离局部最优，而向全局最优迈进。

常见的元启发算法包括：

模拟退火（Simulated Annealing） ：允许以一定的概率接受“变差”的解，从而有机会跳出小坑。
禁忌搜索（Tabu Search） ：通过建立一个“禁忌表”，防止算法在近期搜索过的地方反复徘徊。
变邻域搜索（Variable Neighborhood Search） ：当在一个邻域找不到更好解时，扩大搜索范围，改变邻域的定义。
进化算法
粒子群算法
蚁群算法

模拟退火

模拟退火算法（Simulated Annealing, SA） 是一种受物理学启发而产生的概率型全局寻优算法。它的核心直觉来源于金属冶炼中的 退火过程 ：将固体加热至高温后慢慢冷却，粒子会随着温度降低逐渐趋于稳定的低能态，最终形成完美的晶体（即全局最优解）。模拟退火的核心在于解决“局部最优解”陷阱。传统的爬山法（Greedy Search）只往好的方向走，容易困在山腰。而 SA 允许在一定概率下往坏的方向走，从而跳出局部坑洞。

1770239576035

模拟退火算法一般经过如下步骤：

算法从当前状态（state）出发，随机选择一个临近的状态（被称为后继 successor）。这种随机性是SA算法探索不同可能性的基础，而不是死板地只往一个方向走。
如果随机生成的后继状态比当前状态更好，算法百分百会移动到那个新的状态，即算法总是接受good moves。
如果随机生成的后继状态比当前状态更差，算法有一定概率接受，即算法以一定概率接受worse moves。这个概率一般遵循Boltzmann Distribution。
随着时间的推移，逐步降低worse moves的概率。这个核心变量就是温度（Temprature）。

简单来说，在初始阶段，就像是高温状态，算法非常“疯狂”，接受坏移动的概率很高，目的是在大范围内广泛探索。在后期阶段，就像是低温状态，算法变得越来越保守，接受坏移动的概率逐渐降低，最终趋于稳定，锁定在它发现的最佳区域。

1770239955547

在上图中，模拟退火算法在解决旅行商问题TSP的时候，可以看到路线非常混乱（左图），这代表算法正在进行“大范围搜索”。而在右图中，蓝色线剧烈波动，温度（黄色线）很高，即算法会故意接受那些更差的路径。

说明一下，在TSP问题中，Cost成本指的是算法试图最小化的目标函数值。一般来说，Cost指的就是旅行商走完所有城市并回到起点所经过的 总物理距离 。Cost 越低，说明当前的路线方案越优秀；反之，Cost 越高，说明路径越绕路、效率越低。

1770239975203

在上图中，路线已经清晰了很多，红色的虚线代表了目前找到的最佳路径（左图）。注意看右图的虚线方框：虽然红色线（最佳成本）已经降到了 2000 以下，但蓝色线依然在 2000 到 3000 之间大幅度上下跳动。——此时我们依然要探索更差的，因为在第 2000 次到第 5000 次迭代之间，算法可能陷入了一个“局部最优解”。如果不允许蓝色线往上跳（接受更差的解），它就永远无法跨越障碍，去发现第 5000 次迭代之后那个更低、更好的红色台阶。后期随着温度下降，蓝色线的波动幅度越来越小，最终紧紧跟随红色线，锁定在最优解附近。

模拟退火的核心数学逻辑是玻尔兹曼分布（Boltzmann distribution） 与 Metropolis 准则。

假设当前解为 \(x_{current}\)，产生了一个新解 \(x_{next}\)，能量（目标函数值）之差为 \(\Delta E = f(x_{next}) - f(x_{current})\)：

如果 \(\Delta E < 0\)（解变好了）： 100% 接受新解。
如果 \(\Delta E > 0\)（解变差了）： 以一定的概率 \(P\) 接受新解。

这个概率 \(P\) 的计算公式为：

\[ P = \exp\left(-\frac{\Delta E}{T}\right) \]

其中 \(T\) 是当前的“温度”：

高温阶段： \(P\) 接近 1。算法几乎以随机游走的方式在搜索空间横冲直撞，目的是 遍历全局 。
低温阶段： \(P\) 趋向 0。算法变得非常“保守”，只接受更好的解，目的是 精细收敛 。

Metropolis 准则是模拟退火算法的判定大脑，它决定了算法是否接受一个“变差了”的解。假设当前能量为 \(E_{curr}\)，新生成的能量为 \(E_{next}\)，变化量 \(\Delta E = E_{next} - E_{curr}\)。

接受新解的概率 \(P\) 为：

\[ P = \begin{cases} 1, & \text{if } \Delta E < 0 \text{ (解变好了)} \\ \exp\left(-\frac{\Delta E}{k T}\right), & \text{if } \Delta E \ge 0 \text{ (解变差了)} \end{cases} \]

注：在算法实践中，波尔兹曼常数 \(k\) 通常取 1 以简化计算。

这个准则源于统计力学。在一个恒温系统中，粒子处于能量为 \(E\) 的状态的概率符合玻尔兹曼分布。Metropolis 准则模拟了这种自然界的平衡过程：即使系统倾向于低能态，但在一定温度下，粒子仍然有概率跳到高能态。

模拟退火的伪代码如下：

算法：模拟退火解决旅行商问题 (Simulated Annealing for TSP)
-------------------------------------------------------

1.  【初始化阶段】
    - 读取地图：将所有城市坐标存入 CITIES 数组 (例如 CITIES[0] = [x0, y0])
    - 生成初始解：CURRENT_TOUR = [0, 1, 2, ..., N-1] (随机打乱顺序)
    - 计算代价：CURRENT_COST = 计算路径总距离(CURRENT_TOUR)
    - 记录最佳：BEST_TOUR = CURRENT_TOUR, BEST_COST = CURRENT_COST
    - 设定初始参数：温度 T = 1000, 冷却率 ALPHA = 0.995, 终止温度 = 0.01

2.  【迭代搜索阶段】
    当 温度 T > 终止温度 时：

        执行以下“扰动”步骤 (通常在每个温度下重复执行 L 次)：

        A. 开始扰动：
           - 随机抓取两个位置：i, j = random_index(0, N-1)
           - 复制当前路径：NEW_TOUR = CURRENT_TOUR.copy()
           - 交换城市编号：交换 NEW_TOUR[i] 和 NEW_TOUR[j]

        B. 计算代价：
           - NEW_COST = 计算路径总距离(NEW_TOUR)
           - 计算差值：DELTA_E = NEW_COST - CURRENT_COST

        C. 决定去留：
           - 如果 DELTA_E < 0 (新路径更短):
               - CURRENT_TOUR = NEW_TOUR
               - CURRENT_COST = NEW_COST
               - 如果 NEW_COST < BEST_COST (发现历史最优):
                   - BEST_TOUR = NEW_TOUR
                   - BEST_COST = NEW_COST
           - 否则 (新路径变长了):
               - 计算接受概率：P = exp(-DELTA_E / T)
               - 如果 random(0, 1) < P :
                   - CURRENT_TOUR = NEW_TOUR  <-- 概率性接受“烂路”
                   - CURRENT_COST = NEW_COST

    3.  【降温阶段】
        - 更新温度：T = T * ALPHA

4.  【结束阶段】
    - 输出 BEST_TOUR 和 BEST_COST

python代码参见本笔记所在文件夹（包含可视化过程）：

1770240987556

在实践的时候，我们要考虑以下几个常见的问题：

（1）地图怎么存储？

一般我们坐标矩阵或者距离矩阵（更高阶）来存储。

坐标矩阵就是存储一个 \(N \times 2\) 的列表（或数组），记录每个城市的 \((x, y)\) 坐标。比如 cities = [[0, 0], [10, 5], [2, 8]]，每次计算两个城市间的 Cost 时，用勾股定理算一下：\(\sqrt{(x_1-x_2)^2 + (y_1-y_2)^2}\)。

距离矩阵主要是为了省去重复计算，预先算好一个 \(N \times N\) 的表格。dist[i][j] 直接代表城市 \(i\) 到城市 \(j\) 的距离。

（2）当前状态怎么记录？

由于模拟退火不是完全盲目的纯随机的，而是基于当前位置的随机扰动，因此new path总是在当前位置尝试。那么我们怎么存储当前位置呢？

我们不需要一个变量记录“当前在哪个点”，而是用一个数组记录当前的访问顺序。这个数组就是算法操作的 唯一对象 。

假设有 5 个城市（索引为 0, 1, 2, 3, 4）：

Current_Tour (当前路径) : [0, 3, 1, 4, 2] 这代表旅行商的路线是：0 \(\to\) 3 \(\to\) 1 \(\to\) 4 \(\to\) 2 \(\to\) 回到0。
Best_Tour (历史最佳) : [0, 1, 2, 3, 4] 这是我们目前找到的最短路径。

如果用位置交换来作为扰动，那么其实就是改变数组中数字的排列。例如从 [0, 3, 2, 1] 变成 [0, 1, 2, 3]。

（3）关于计算代价的具体方法

计算总距离时，别忘了最后一个城市要连回第一个城市：

\[ Total\_Cost = \sum_{i=0}^{N-2} dist(Tour[i], Tour[i+1]) + dist(Tour[N-1], Tour[0]) \]

（4）关键变量

在代码运行的每一刻，内存里主要存着这几个关键变量：

变量名	类型	作用
`cities`	矩阵	固定的地图，存储所有城市的坐标。
`current_tour`	数组	核心变量。记录当前的城市排列顺序（如 `[2, 0, 1, 3]`）。
`new_tour`	数组	临时变量。对 `current_tour`随机交换两点后的副本。
`best_tour`	数组	救生圈。永远存着那个长度最短的排列，不随“坏解”改变。
`T`	浮点数	当前温度。控制我们接受 `new_tour`的“胆量”。

.

进化算法

进化算法 （Evolutionary Algorithms, EA）不是靠人类逻辑去“设计”解决方案，而是模拟 达尔文的生物进化论 ，让程序通过“优胜劣汰”自己演化出最优解。

进化算法把问题的每一个可能解看作一个“个体”，然后进行以下操作：

选择 (Selection): 就像“物竞天择”。算法会评估当前所有解的效果（适应度），表现越好的解，留下“后代”的机会就越大。
繁殖/交叉 (Reproduction/Crossover): 两个优秀的解会交换彼此的“基因”（一部分参数），合成一个新的解。正如幻灯片所说：两个好的状态结合，很有可能产生更好的状态。
变异 (Mutation): 为了防止算法陷入局部最优（死胡同），它会随机改变解的某些部分。这就像生物界的基因突变，有时会带来意想不到的突破。

1770241407442

上图是进化算法最经典的应用案例之一：NASA ST5宇宙飞船天线。人类工程师通常会设计出规则的几何形状（如圆形或棒状），计算机完全不考虑“美观”或“对称”，它只为了实现最强的信号增益进行数百万次模拟进化。最终，它生成了这个看起来像个扭曲回形针的怪异形状。这种看似杂乱的设计，在性能上远超人类顶级专家设计的任何传统天线。

遗传算法

遗传算法（Genetic Algorithms, GA）是进化算法的一种具体实现，但是不同于进化算法对变异（Mutation）和自然选择的强调，其极其强调交叉 (Crossover) 操作。

遗传算法最优应用主要在没有明确的数学公式的场景下，比如上面提到的信号针，或者优化飞机的机翼形状等。在这些场景下，你只能进行模拟测试。

对于八皇后问题，回溯法最快；如果N较大，比如N=1000的情况，回溯法无法使用，此时最优方法是locall search。因此遗传算法在八皇后问题上并非最优算法。

Fitness Function，又叫做适应度函数，是进化算法（如遗传算法、遗传编程等）中的核心组件。简单来说，适应度函数就是一个“打分器”，用来衡量一个候选方案（个体）距离解决目标的“优秀程度”。

比如说，对于 无界背包问题（Unbounded Knapsack Problem, UKP） ，由于每个物品可以无限次选取，适应度函数的设计不仅要考虑如何最大化价值，还要优雅地处理“超重”的情况。

最直接的适应度就是背包内物品的总价值。假设你选择了 \(n\) 种物品，每种物品的价值为 \(v_i\)，选择的数量为 \(x_i\)，则基础适应度（Raw Fitness）为：

\[ f_{raw} = \sum_{i=1}^{n} v_i \cdot x_i \]

Penalty Function，又叫做惩罚函数。同样以无界背包问题为例，在无界背包问题中唯一的硬性约束是 总重量不能超过背包容量 \(W\)**** 。如果一个解超重了，我们不能直接抛弃它（因为它的基因可能包含优秀的片段），但必须给它“降分”。你可以采用以下两种惩罚策略：

方案 A：线性惩罚（推荐）

如果总重量 \(\sum (w_i \cdot x_i) > W\)，则在总价值中扣除超重部分的代价。

\[ f_{final} = \begin{cases} \sum v_i x_i & \text{if } \text{weight} \le W \\ \sum v_i x_i - \alpha \cdot (\text{weight} - W) & \text{if } \text{weight} > W \end{cases} \]

注意：系数 \(\alpha\) 需要足够大，以确保超重的个体评分远低于不超重的个体。通常可以取所有物品中最大的单位价值（即 \(\max(v_i/w_i)\)）。

方案 B：死刑惩罚（简单但效果较差）

只要超重，适应度直接设为 0 或一个极小的负数。

缺点：在进化初期，如果随机生成的解全部超重，算法会因为找不到“比较好”的失败解而陷入盲目搜索。

※ 旅行商问题(TSP)

约束满足问题(CSP)

CSP建模

CSP 的建模主要围绕三个核心要素展开，通常表示为一个三元组 \((X, D, C)\)。

要对一个问题进行 CSP 建模，必须明确定义以下三个部分：

变量集合 \(X\) (Variables):
- 定义：\(X = \{X_1, X_2, \dots, X_n\}\)，即你需要求解的对象。
值域集合 \(D\) (Domains):
- 定义：\(D = \{D_1, D_2, \dots, D_n\}\)，每个变量 \(X_i\) 都有一个对应的取值范围 \(D_i\)。
约束集合 \(C\) (Constraints):
- 定义：\(C = \{C_1, C_2, \dots, C_m\}\)，描述了变量之间必须满足的关系。
- 每个约束由一个变量子集和一个 允许的关系 （即合法的赋值组合）组成。
- constraints最好是unary的。unary就是一元约束。