非线性规划中的自适应模拟退火算法（Adaptive Simulated Annealing, ASA）基础题

字数 4578 2025-12-17 00:03:50

非线性规划中的自适应模拟退火算法（Adaptive Simulated Annealing, ASA）基础题

题目描述

考虑以下约束非线性优化问题：

最小化
\(f(x) = (x_1 - 2)^4 + (x_2 - 3)^2 + 5 \sin(\pi x_1 x_2)\)

满足约束：

\[\begin{aligned} g_1(x) &= x_1^2 + x_2^2 - 5 \le 0, \\ g_2(x) &= -x_1 + 0.5 \le 0, \\ g_3(x) &= -x_2 + 1 \le 0, \\ & -3 \le x_1 \le 3, \quad -2 \le x_2 \le 4. \end{aligned} \]

这个问题的目标函数是一个非凸、非线性、多峰（存在多个局部极小点）的函数，并包含非线性不等式约束和简单边界约束。我们将通过自适应模拟退火算法（Adaptive Simulated Annealing, ASA） 来求解此问题，该算法是一种全局优化启发式方法，能够有效跳出局部最优，在搜索过程中自适应地调整温度下降计划和搜索邻域半径，以提高搜索效率和精度。

解题过程循序渐进讲解

模拟退火算法（SA）源于物理中固体退火过程：加热固体至熔化，再缓慢冷却，使其原子排列达到能量最低的稳定状态。优化中，我们将目标函数视为“能量”，通过引入“温度”参数，以一定概率接受比当前解差的解，从而在解空间中进行探索，避免陷入局部最优。自适应模拟退火（ASA）在经典SA基础上，根据搜索进程自动调整温度下降速率、步长等参数，以平衡全局探索和局部开发。

我们将求解过程分解为以下步骤：

步骤1：算法框架初始化

ASA的基本迭代框架与经典SA类似，但参数更新策略不同。给定初始点 \(x^{(0)}\)，初始温度 \(T_0\)，初始步长（或邻域半径）\(\sigma_0\)，最大迭代次数 \(K_{max}\)，每个温度下的马尔可夫链长度 \(L\)。算法主循环为：

初始化 \(x = x^{(0)}\)，计算 \(f(x)\)。
对于温度 \(T_k\) （\(k = 0, 1, 2, \dots\)），重复以下步骤 \(L\) 次（内循环）：
a. 在当前点 \(x\) 的邻域内随机生成一个新候选点 \(x'\)。
b. 根据 Metropolis 准则判断是否接受 \(x'\)。
c. 如果接受，更新 \(x \leftarrow x'\)。
根据自适应策略降低温度 \(T_{k+1} = \alpha(T_k, \text{历史接受率}) \times T_k\) 并调整步长 \(\sigma\)。
检查终止条件（如温度低于阈值 \(T_{min}\)，或连续若干温度无改善），满足则停止，否则回到步骤2。

我们的任务是将此框架具体化，并处理约束。

步骤2：初始点与参数设置

初始点可随机生成或在可行域内选择，例如 \(x^{(0)} = (0, 2)\)。初始温度 \(T_0\) 应足够高，使得大多数差解能被接受，常用方法是进行若干随机采样，令 \(T_0 = \sigma_f / \ln(p_0^{-1})\)，其中 \(\sigma_f\) 是采样目标函数值的标准差，\(p_0\) 是初始接受概率（例如0.8）。初始步长 \(\sigma_0\) 可设为变量范围的10%-20%，例如 \(\sigma_0 = (0.6, 0.6)\) 对应每个维度。设置 \(L = 20 \cdot n\)（n为变量数，这里n=2，所以L=40），\(K_{max} = 100\)。

步骤3：处理约束——罚函数法

模拟退火通常处理无约束问题。我们将约束通过罚函数转化为目标函数的一部分。定义惩罚函数：

\[P(x) = \mu \sum_{i=1}^{3} \max(0, g_i(x))^2 \]

其中 \(\mu > 0\) 是惩罚因子（可设为较大常数，如1000）。则转化为无约束问题：
最小化

\[F(x) = f(x) + P(x) \]

边界约束 \(-3 \le x_1 \le 3, -2 \le x_2 \le 4\) 在生成新点时通过反射或截断处理。

步骤4：生成新候选点（扰动）

在温度 \(T_k\) 下，从当前点 \(x\) 生成新点 \(x'\)：

\[x' = x + \sigma \cdot d \]

其中 \(d\) 是一个随机方向向量，通常从均匀分布或正态分布采样。常用方法是每个分量独立采样自均匀分布 \(U(-1, 1)\) 后归一化，再乘以当前步长向量 \(\sigma = (\sigma_1, \sigma_2)\)。即：

\[d_i = \frac{r_i}{\sqrt{r_1^2 + r_2^2}}, \quad r_i \sim U(-1,1) \]

则

\[x'_i = x_i + \sigma_i \cdot d_i \]

生成后，若 \(x'_i\) 超出边界，则将其投影到边界上（例如，若 \(x'_1 < -3\)，则设 \(x'_1 = -3\)）。

步骤5：Metropolis接受准则

计算新点与当前点的目标函数差值：

\[\Delta F = F(x') - F(x) \]

若 \(\Delta F \le 0\)（改善），则一定接受 \(x'\)。
若 \(\Delta F > 0\)（变差），则以概率

\[p = \exp\left( -\frac{\Delta F}{T_k} \right) \]

接受 \(x'\)。实现时，生成随机数 \(u \sim U(0,1)\)，若 \(u < p\) 则接受。

步骤6：自适应调整策略（ASA的核心）

自适应体现在两个方面：

温度自适应下降：
经典SA使用固定降温率，如 \(T_{k+1} = 0.95 T_k\)。ASA根据搜索进程调整。一个常见策略是监视接受率（每个温度下接受新点的比例）。设目标接受率为 \(p_{target}\)（如0.3）。若当前温度下的实际接受率 \(p_{acc} > p_{target}\)，说明温度可能过高，搜索太随机，可加快降温（用更小的降温因子 \(\alpha < 0.9\)）；若 \(p_{acc} < p_{target}\)，则减慢降温（用较大的 \(\alpha > 0.95\)），以进行更多局部搜索。具体可设为：

\[ \alpha = \max(0.5, \exp\left( \frac{p_{target} - p_{acc}}{p_{target}} \right) ) \]

然后 \(T_{k+1} = \alpha T_k\)。

步长自适应调整：
步长 \(\sigma\) 控制搜索邻域大小。若接受率较高，说明步长可能偏小，可适当增大以探索更广区域；若接受率太低，应减小步长以便精细搜索。调整规则示例：

\[ \sigma_{i, new} = \sigma_i \cdot \left( 1 + \beta \frac{p_{acc} - p_{target}}{p_{target}} \right) \]

其中 \(\beta\) 是调节系数（如0.1），并限制 \(\sigma_i\) 在预设的最小最大步长之间。

步骤7：终止条件

常用终止条件组合：

温度低于极小阈值 \(T_{min}\)（如 \(10^{-6}\)）。
连续若干温度（如5个）最优解未改善。
达到最大迭代次数 \(K_{max}\)。
满足任一条件则停止，输出历史最优解 \(x^*\) 和 \(F(x^*)\)。

步骤8：算法流程总结

设置初始参数 \(x^{(0)}, T_0, \sigma_0, L, K_{max}, p_{target}, \mu\)。
将约束问题转化为无约束问题 \(F(x) = f(x) + \mu \sum \max(0, g_i(x))^2\)。
令当前点 \(x = x^{(0)}\)，当前最优解 \(x^* = x, F^* = F(x)\)。
对于 \(k = 0\) 到 \(K_{max}-1\)：
a. 初始化该温度接受计数器 \(accept = 0\)。
b. 对于 \(t = 1\) 到 \(L\)：
i. 按步骤4生成新点 \(x'\)，并投影边界。
ii. 计算 \(\Delta F = F(x') - F(x)\)。
iii. 若 \(\Delta F \le 0\) 或随机数 \(u < \exp(-\Delta F / T_k)\)，则接受：\(x \leftarrow x'\)，\(accept \leftarrow accept+1\)。
iv. 若 \(F(x) < F^*\)，更新最优解：\(x^* \leftarrow x, F^* \leftarrow F(x)\)。
c. 计算该温度接受率 \(p_{acc} = accept / L\)。
d. 根据 \(p_{acc}\) 和 \(p_{target}\) 按步骤6自适应更新温度 \(T_{k+1}\) 和步长 \(\sigma\)。
e. 检查终止条件，若满足则跳出循环。
输出 \(x^*\) 和 \(F(x^*)\)，从 \(F^*\) 中减去惩罚项（若 \(x^*\) 可行，惩罚项为0）得 \(f(x^*)\)。

步骤9：针对本题的简要数值实验思路

由于是解析讲解，我们不做完整编程，但可描述预期行为：

初始高温时，算法接受许多差解，在解空间广泛游走。
随着温度下降，接受差解概率降低，搜索逐渐聚焦在低能区域。
自适应机制会使温度下降在“探索”与“开发”间取得平衡，例如前期若接受率持续高，降温会减慢，允许更多探索；若很快陷入局部区域，接受率低，步长减小，温度下降也变慢，使其有足够时间局部精细搜索。
最终，算法有很大概率找到全局最优或一个高质量的近似全局最优解。对于此多峰函数，传统梯度法易陷入局部最优，而ASA能跳出。

总结：自适应模拟退火算法通过引入温度参数和概率接受机制实现全局搜索，并通过自适应调整温度和步长来优化搜索效率。处理约束时，常用罚函数法将其转化为无约束问题。ASA适用于目标函数复杂、多峰、非凸的优化问题，虽然不能保证理论上的全局最优，但在实践中常能得到很好的近似解。

非线性规划中的自适应模拟退火算法（Adaptive Simulated Annealing, ASA）基础题题目描述考虑以下约束非线性优化问题：最小化 \( f(x) = (x_ 1 - 2)^4 + (x_ 2 - 3)^2 + 5 \sin(\pi x_ 1 x_ 2) \) 满足约束： \[ \begin{aligned} g_ 1(x) &= x_ 1^2 + x_ 2^2 - 5 \le 0, \\ g_ 2(x) &= -x_ 1 + 0.5 \le 0, \\ g_ 3(x) &= -x_ 2 + 1 \le 0, \\ & -3 \le x_ 1 \le 3, \quad -2 \le x_ 2 \le 4. \end{aligned} \] 这个问题的目标函数是一个非凸、非线性、多峰（存在多个局部极小点）的函数，并包含非线性不等式约束和简单边界约束。我们将通过自适应模拟退火算法（Adaptive Simulated Annealing, ASA）来求解此问题，该算法是一种全局优化启发式方法，能够有效跳出局部最优，在搜索过程中自适应地调整温度下降计划和搜索邻域半径，以提高搜索效率和精度。解题过程循序渐进讲解模拟退火算法（SA）源于物理中固体退火过程：加热固体至熔化，再缓慢冷却，使其原子排列达到能量最低的稳定状态。优化中，我们将目标函数视为“能量”，通过引入“温度”参数，以一定概率接受比当前解差的解，从而在解空间中进行探索，避免陷入局部最优。自适应模拟退火（ASA）在经典SA基础上，根据搜索进程自动调整温度下降速率、步长等参数，以平衡全局探索和局部开发。我们将求解过程分解为以下步骤：步骤1：算法框架初始化 ASA的基本迭代框架与经典SA类似，但参数更新策略不同。给定初始点 \( x^{(0)} \)，初始温度 \( T_ 0 \)，初始步长（或邻域半径）\( \sigma_ 0 \)，最大迭代次数 \( K_ {max} \)，每个温度下的马尔可夫链长度 \( L \)。算法主循环为：初始化 \( x = x^{(0)} \)，计算 \( f(x) \)。对于温度 \( T_ k \) （\( k = 0, 1, 2, \dots \)），重复以下步骤 \( L \) 次（内循环）： a. 在当前点 \( x \) 的邻域内随机生成一个新候选点 \( x' \)。 b. 根据 Metropolis 准则判断是否接受 \( x' \)。 c. 如果接受，更新 \( x \leftarrow x' \)。根据自适应策略降低温度 \( T_ {k+1} = \alpha(T_ k, \text{历史接受率}) \times T_ k \) 并调整步长 \( \sigma \)。检查终止条件（如温度低于阈值 \( T_ {min} \)，或连续若干温度无改善），满足则停止，否则回到步骤2。我们的任务是将此框架具体化，并处理约束。步骤2：初始点与参数设置初始点可随机生成或在可行域内选择，例如 \( x^{(0)} = (0, 2) \)。初始温度 \( T_ 0 \) 应足够高，使得大多数差解能被接受，常用方法是进行若干随机采样，令 \( T_ 0 = \sigma_ f / \ln(p_ 0^{-1}) \)，其中 \( \sigma_ f \) 是采样目标函数值的标准差，\( p_ 0 \) 是初始接受概率（例如0.8）。初始步长 \( \sigma_ 0 \) 可设为变量范围的10%-20%，例如 \( \sigma_ 0 = (0.6, 0.6) \) 对应每个维度。设置 \( L = 20 \cdot n \)（n为变量数，这里n=2，所以L=40），\( K_ {max} = 100 \)。步骤3：处理约束——罚函数法模拟退火通常处理无约束问题。我们将约束通过罚函数转化为目标函数的一部分。定义惩罚函数： \[ P(x) = \mu \sum_ {i=1}^{3} \max(0, g_ i(x))^2 \] 其中 \( \mu > 0 \) 是惩罚因子（可设为较大常数，如1000）。则转化为无约束问题：最小化 \[ F(x) = f(x) + P(x) \] 边界约束 \( -3 \le x_ 1 \le 3, -2 \le x_ 2 \le 4 \) 在生成新点时通过反射或截断处理。步骤4：生成新候选点（扰动）在温度 \( T_ k \) 下，从当前点 \( x \) 生成新点 \( x' \)： \[ x' = x + \sigma \cdot d \] 其中 \( d \) 是一个随机方向向量，通常从均匀分布或正态分布采样。常用方法是每个分量独立采样自均匀分布 \( U(-1, 1) \) 后归一化，再乘以当前步长向量 \( \sigma = (\sigma_ 1, \sigma_ 2) \)。即： \[ d_ i = \frac{r_ i}{\sqrt{r_ 1^2 + r_ 2^2}}, \quad r_ i \sim U(-1,1) \] 则 \[ x'_ i = x_ i + \sigma_ i \cdot d_ i \] 生成后，若 \( x'_ i \) 超出边界，则将其投影到边界上（例如，若 \( x'_ 1 < -3 \)，则设 \( x'_ 1 = -3 \)）。步骤5：Metropolis接受准则计算新点与当前点的目标函数差值： \[ \Delta F = F(x') - F(x) \] 若 \( \Delta F \le 0 \)（改善），则一定接受 \( x' \)。若 \( \Delta F > 0 \)（变差），则以概率 \[ p = \exp\left( -\frac{\Delta F}{T_ k} \right) \] 接受 \( x' \)。实现时，生成随机数 \( u \sim U(0,1) \)，若 \( u < p \) 则接受。步骤6：自适应调整策略（ASA的核心）自适应体现在两个方面：温度自适应下降：经典SA使用固定降温率，如 \( T_ {k+1} = 0.95 T_ k \)。ASA根据搜索进程调整。一个常见策略是监视接受率（每个温度下接受新点的比例）。设目标接受率为 \( p_ {target} \)（如0.3）。若当前温度下的实际接受率 \( p_ {acc} > p_ {target} \)，说明温度可能过高，搜索太随机，可加快降温（用更小的降温因子 \( \alpha < 0.9 \)）；若 \( p_ {acc} < p_ {target} \)，则减慢降温（用较大的 \( \alpha > 0.95 \)），以进行更多局部搜索。具体可设为： \[ \alpha = \max(0.5, \exp\left( \frac{p_ {target} - p_ {acc}}{p_ {target}} \right) ) \] 然后 \( T_ {k+1} = \alpha T_ k \)。步长自适应调整：步长 \( \sigma \) 控制搜索邻域大小。若接受率较高，说明步长可能偏小，可适当增大以探索更广区域；若接受率太低，应减小步长以便精细搜索。调整规则示例： \[ \sigma_ {i, new} = \sigma_ i \cdot \left( 1 + \beta \frac{p_ {acc} - p_ {target}}{p_ {target}} \right) \] 其中 \( \beta \) 是调节系数（如0.1），并限制 \( \sigma_ i \) 在预设的最小最大步长之间。步骤7：终止条件常用终止条件组合：温度低于极小阈值 \( T_ {min} \)（如 \( 10^{-6} \)）。连续若干温度（如5个）最优解未改善。达到最大迭代次数 \( K_ {max} \)。满足任一条件则停止，输出历史最优解 \( x^* \) 和 \( F(x^* ) \)。步骤8：算法流程总结设置初始参数 \( x^{(0)}, T_ 0, \sigma_ 0, L, K_ {max}, p_ {target}, \mu \)。将约束问题转化为无约束问题 \( F(x) = f(x) + \mu \sum \max(0, g_ i(x))^2 \)。令当前点 \( x = x^{(0)} \)，当前最优解 \( x^* = x, F^* = F(x) \)。对于 \( k = 0 \) 到 \( K_ {max}-1 \)： a. 初始化该温度接受计数器 \( accept = 0 \)。 b. 对于 \( t = 1 \) 到 \( L \)： i. 按步骤4生成新点 \( x' \)，并投影边界。 ii. 计算 \( \Delta F = F(x') - F(x) \)。 iii. 若 \( \Delta F \le 0 \) 或随机数 \( u < \exp(-\Delta F / T_ k) \)，则接受：\( x \leftarrow x' \)，\( accept \leftarrow accept+1 \)。 iv. 若 \( F(x) < F^* \)，更新最优解：\( x^* \leftarrow x, F^* \leftarrow F(x) \)。 c. 计算该温度接受率 \( p_ {acc} = accept / L \)。 d. 根据 \( p_ {acc} \) 和 \( p_ {target} \) 按步骤6自适应更新温度 \( T_ {k+1} \) 和步长 \( \sigma \)。 e. 检查终止条件，若满足则跳出循环。输出 \( x^* \) 和 \( F(x^ ) \)，从 \( F^ \) 中减去惩罚项（若 \( x^* \) 可行，惩罚项为0）得 \( f(x^* ) \)。步骤9：针对本题的简要数值实验思路由于是解析讲解，我们不做完整编程，但可描述预期行为：初始高温时，算法接受许多差解，在解空间广泛游走。随着温度下降，接受差解概率降低，搜索逐渐聚焦在低能区域。自适应机制会使温度下降在“探索”与“开发”间取得平衡，例如前期若接受率持续高，降温会减慢，允许更多探索；若很快陷入局部区域，接受率低，步长减小，温度下降也变慢，使其有足够时间局部精细搜索。最终，算法有很大概率找到全局最优或一个高质量的近似全局最优解。对于此多峰函数，传统梯度法易陷入局部最优，而ASA能跳出。总结：自适应模拟退火算法通过引入温度参数和概率接受机制实现全局搜索，并通过自适应调整温度和步长来优化搜索效率。处理约束时，常用罚函数法将其转化为无约束问题。ASA适用于目标函数复杂、多峰、非凸的优化问题，虽然不能保证理论上的全局最优，但在实践中常能得到很好的近似解。