SJTU 课程学习笔记🔨优化
type
status
date
slug
summary
tags
category
icon
password
引入
什么是优化
优化（Optimization）是指在给定限制条件或满足一定约束的情况下，从所有可能选择中找出最好的那个，或通过调整决策变量使某个目标函数达到最大值或最小值的过程。例如：
- 路径规划：从城市 到 应选择怎样的路线才能时间最短或者油耗最小？
- 资源分配：在有限预算下如何投资才能获得最大的回报？
- 产品设计：在满足设计容积的前提下，如何设计容器才能最省材料？
- 生产计划：如何安排生产流程才能降低成本或提高利润？
这些都属于优化问题，需要在众多可能解中寻找最优解。
目标函数、约束与解空间
- 目标函数（Objective function）：我们想要最大化或最小化的函数，可以是利润、距离、成本等。
- 约束（Constraints）：限制解的可行性，如预算、时间、资源等限制。
- 解空间（State space）：所有可行解的集合，也称为状态空间。在优化中，每个状态对应一个解，其“高度”或“深度”对应目标函数的值。
0. 局部搜索
在大多数人工智能问题中，解空间规模巨大，无法穷举所有可能的解。局部搜索（Local Search）是一类从一个初始状态（节点/解）出发，通过在其邻域内移动、搜索、迭代，以寻找更优解的算法。
局部搜索不关心如何获得初始解，也不关心移动多少步；它只关注能否找到一个满意的解。
模拟退火这样的元启发式算法在理论上一定可以找到最优解，但是可能会花费很多时间。而局部搜索可以在节省计算资源的情况下，找到一个不是最佳、但是已经“足够好”的解决方案。
状态、邻居和目标函数
- 当前状态（Current state）：算法当前正在考虑的解。
- 邻居状态（Neighbor state）：通过合法操作从当前状态可以达到的状态。
- 目标/代价函数：给每个状态分配一个数值，用于比较状态的优劣。 一般地，当我们想要最小化目标时称为代价函数；想要最大化目标时称为目标函数。
全局最优与局部最优
- 全局最大值/最小值（Global maximum/minimum）：整个解空间中目标函数值最高或最低的状态。
- 局部最大值/最小值（Local maximum/minimum）：比所有邻居状态都更好但不一定是全局最优的状态。这些陷阱让局部搜索算法容易停留在非最优解上。
1. 爬山算法
爬山算法（Hill Climbing）是一种简单的局部搜索方法，适用于求解连续或离散优化问题。核心思想是：从当前状态出发，选择一个邻居状态，如果邻居比当前更好则移动过去；当没有更好的邻居时停止。对于最大化问题算法倾向“爬高”，对于最小化问题则“往低处走”。
算法步骤
- 选择一个 初始状态 作为当前状态 。在许多应用中，这个初始状态可随机生成。
- 重复以下步骤：
- 找出当前状态的所有邻居状态；
- 在这些邻居中选择一个目标函数值更优的状态（对于最大化问题选择值更高的邻居，对于最小化问题选择值更低的邻居）；
- 如果选出的邻居比当前状态更好，就令其成为新的当前状态；否则，当前状态就是局部最优，算法结束。
伪代码如下：
示例：社区医院选址问题
假设某城市需要在地图上建两个社区医院，为居民区提供服务。我们用 表示地图上的坐标，
- 状态：两个社区医院的放置位置集合。
- 代价函数：所有居民区到最近医院的曼哈顿距离之和； 曼哈顿距离定义为 。
- 邻居：移动某个医院到相邻的一个空格（不与其他医院或房屋重叠）。
初始状态随机生成两个医院位置。然后重复选择能降低总距离的邻居，直到无法改进为止。通过这种方法可能找到一个较优的选址，但算法会陷入局部最优。例如，图中展示的几个迭代中代价从 下降到 ；这已经比初始状态好，但仍不一定是全局最优。
示例：旅行商问题的建模
Answered by ChatGPT 5 Thinking ① 状态（state）是什么？一次完整的投递顺序（路径），把 、、、、 五个点各访问一次。为了避免“等价的旋转”造成重复，常把起点固定（例如以 开始）；是否需要回到起点视任务而定：
- 开线路径（只派送，不回起点）：序列如 。
- 环线路径（巡回）：序列如 。
② 代价函数（cost function）是什么？总行程长度（或总耗时）。设 是访问顺序， 为已知的两点最短路径距离：
- 开线：
- 环线：
局部搜索/爬山算法目标是最小化该代价。③ 相邻状态（neighbor）是什么？在当前顺序上做一次“小改动”得到的新顺序。可选但等价的邻域定义很多，任选其一即可保持“合法路径”：
- 交换（swap）：交换任意两个点的位置（例如 ）。
- 插入（insert）：把某一点取出，插入到另一个位置（如 ）。
- 2-opt：选两条边，断开后反转中间段并重连，常用于旅行商问题。
小提示（有助于实现）：
- 固定起点 A 后，合法顺序的数量是 （开线）；若按环线并把“逆时针/顺时针”和“起点平移”视为同一条路线，则唯一巡回路线数为 。
- 由于题目给的是“每两点之间的最短路径”， 满足三角不等式；在这种图上，2-opt 这类邻域往往收敛更快、效果更好。
- 若用爬山算法：从一个随机顺序出发，枚举（或采样）邻域，选择代价更小的邻居前进，直到没有更优邻居为止。
代码实现：使用爬山算法解决社区医院选址问题
- 将问题抽象（让计算机明白选址问题）
- 模拟地图数据以测试算法效果
- 地点用 表示
- 设施类型：
hospital、houses
- 按照解优化问题的步骤编写代码
- 输出结果
题目：实现 hill_climb() 函数 (W3-Optimization-E4)
找到放置2个社区医院的位置，是的每个房子到达最近医院的曼哈顿距离之和最小
输出为2个社区医院的坐标几何，如
{(3, 2), (2, 7)}代码
from e03 import * 已经将练习#3中的 available_spaces, get_neighbors, get_cost 函数导入，并且已经放置了初始的 houses答案：实现 hill_climb() 函数 (W3-Optimization-E4)
潜在问题
尽管简单高效，爬山算法存在下列缺陷，并不能总是找到全局最优解：
- 局限于局部最优：算法容易停留在比邻居状态更好但不一定是全局最优的状态。
- 平坦高原局部极值（Flat local maximum/minimum）：若一大片邻居状态具有相同的目标值，算法无法判断前进方向，可能随机停滞。
- 肩部（Shoulder）：部分邻居更好、部分更差，算法可能在局部高地上徘徊。
变种
为了改善上述缺陷，人们提出了多种改进的爬山算法变种：
- 最抖爬山（Steepest-ascent hill climbing）：在所有邻居中选择最优的那个，确保每一步提升最大。
- 随机爬山（Stochastic hill climbing）：从比当前状态更好的邻居中随机挑选一个，增加多样性。
- 首选爬山（First‑choice hill climbing）：按某个顺序遍历邻居，遇到一个更好就立即跳过去，不用评估全部邻居。
- 随机重启爬山（Random‑restart hill climbing）：重复多次运行爬山算法，每次从新初始状态开始，最后取最优结果。此方法常能跳出局部最优，但计算开销较大。
代码实现：使用随机重启爬山算法找到最佳选址地点
2. 梯度下降法
在连续优化问题中，状态可以用实值向量 表示，我们希望最小化某个可微函数 。
梯度的概念
梯度是函数沿各坐标轴方向的偏导数组成的向量：
梯度矢量指向函数值增长最快的方向；其反方向 则是下降最快的方向。在单变量情况下，梯度就是导数。例如函数 的导数为 ，在 处导数为 。
梯度下降算法
梯度下降（Gradient Descent）是一种迭代式优化算法，用来最小化可微函数。
- 随机初始化：选择一个随机的初始向量 。
- 迭代更新：
其中 是学习率（Learning rate）或步长，控制每次移动的尺度。
- 停止条件：当梯度的范数足够小（接近零），或达到最大迭代次数时，认为已经到达局部最小值并停止。
选择合适的步长非常重要：太大可能越过最优解甚至发散，太小则收敛缓慢。在实际应用中，可采用固定步长或在优化过程中动态调整。
示例：单变量函数最小化
对函数 ，其导数为 。初始状态取 ，步长 。
- 计算梯度 。
- 更新 ：。
- 重复上述步骤，直到导数接近零（退出条件常设置为 ，或固定循环次数）。
这一过程与爬山算法类似，但利用梯度提供的方向信息比枚举邻居更高效。
代码实现：构建梯度下降算法
题目：实现 gradient 和 gradient_descent (W3-Optimization-E6)
多维示例：Rosenbrock 函数
Rosenbrock 函数是一种经典的测试函数，形状像香蕉，定义为：
其全局最小值为 ，梯度下降可以找到这一点。课堂演示代码中通过数值计算偏导，使用学习率 控制更新步长，反复迭代直到梯度范数小于某个阈值。
3. 模拟退火算法
爬山算法只能接受更好的邻居，因此容易困在局部最优。模拟退火（Simulated annealing, SA）通过引入“温度”参数，允许偶尔接受更差的状态，从而有概率跳出局部最优，随着温度降低逐渐转向精细搜索。
金属材料加热后，内部粒子处于高能量状态；缓慢降温时，粒子逐渐排列成低能量的稳定结构。模拟退火算法借鉴这一思想：
- 高温阶段：算法更容易接受比当前状态更差的邻居（随机性大），可以探索广泛区域。
- 低温阶段：算法倾向于接受更好的邻居，随机性降低，更像爬山算法。
算法步骤
- 初始化：从一个初始状态 开始，设定初始温度 。
- 迭代直到温度降低到终止条件：
- 从当前状态的领域解中随机选一个 ：。
- 计算目标函数差值 。 对于最小化问题， 表示邻居更好。（能量较小的状态优于能量较大的状态。）
- 如果邻居更优（），则接受它作为新的当前状态。
- 如果邻居更差（），则以概率 接受更差的状态，其中 是当前温度。
- 设置全局随时间变化的参数 。
- 随时间递减温度，常见的衰减函数是 。
- 输出：返回当前的最终状态作为近似全局最优解。
示例：模拟退火算法
- 找不到全局最大，只会停在边界点 这一局部最大（值为 ）。
- ，
- 很接近于 0，几乎不可能。
- 理论上，只有在“极慢”的冷却下，模拟退火才有以概率 1 收敛到全局最优的保证。
代码实现：模拟退火算法
题目：实现 simulated_annealing(maximum) (W3-Optimization-E8)
找到放置2个社区医院的位置，是的每个房子到达最近医院的曼哈顿距离之和最小
输出为坐标几何，如
{(3, 2), (2, 7)}Temperature(t)为剩余时间的比例注意：我们想找最小值，所以需要正确计算
ΔE代码
from e03 import * 已经将练习 #3 中的 available_spaces, get_neighbors, get_cost函数导入，并且已经放置了初始的 houses。答案：实现 simulated_annealing(maximum) (W3-Optimization-E8)
与爬山算法的比较
- 爬山算法始终选择更好的邻居；模拟退火在高温阶段允许“退步”以避免局部最优。
- 在理论上，如果温度下降得足够慢且随机性充分，模拟退火能够以概率 1 找到全局最优解。但实际问题中需要在计算时间与精度之间权衡。
应用
模拟退火和局部搜索在很多领域有重要应用，如：
- 设施选址与城市规划：解决选址问题、物流中心定位等。
- 数据分析与机器学习：用于特征选择和模型参数调优。
- 组合优化：解决旅行商问题、排课表、投资组合等复杂问题。
编程实践
课堂的 Jupyter Notebook 中提供了社区选址问题的代码实现，下面总结一些关键函数和经验：
- 生成随机房屋和医院的位置：使用
random.seed()固定随机性，便于复现。房屋位置通常保存在houses集合，医院位置保存在hospitals集合。
- 寻找可放置医院的位置：
available_spaces()函数遍历地图并排除已有房屋和医院的位置，返回可选坐标集合。它是爬山算法初始状态和邻居生成的基础。
- 获取邻居：
get_neighbors(row, col)返回指定坐标上下左右四个不越界、且没有房屋或医院的位置。
- 计算代价函数：
get_cost(potential_hospitals)遍历所有房屋，计算其到最近医院的曼哈顿距离并求和。若没有医院，则返回空字符串。
- 深拷贝与浅拷贝：在生成邻居或更新状态时要注意复制集合/列表，否则直接修改会影响原状态。Python 的
.copy()方法可以生成浅拷贝。
- 随机重启和模拟退火实现：在随机重启中记录所有运行的最优结果，最后返回最优解；模拟退火中根据温度与差值计算接受概率。
- 梯度计算：数值梯度可用导数定义近似，
h取较小数值如 。
总结
- 局部搜索（包括爬山算法）适用于解空间巨大而无法穷举的优化问题。通过迭代改进邻居，它可以快速找到一个“足够好”的解，但可能陷入局部最优。
- 随机重启、随机爬山等改进提供了跳出局部最优的方法，但不能保证一定找到全局最优。
- 梯度下降将搜索推广到连续空间，通过梯度提供的方向信息快速逼近极小点。学习率的选择与梯度计算的精确性影响收敛速度。
- 模拟退火借鉴物理退火过程，引入温度控制搜索的随机性，在理论上可以找到全局最优，但实际应用中需平衡效率与精度。
- 这些算法在设施选址、组合优化、机器学习等领域有广泛应用，学习它们可以为解决复杂决策问题提供有力工具。
上一篇
Python 常用速查表
下一篇
机器学习
Loading...
