数值优化算法：模拟退火与遗传算法解析

# 数值优化算法：模拟退火与遗传算法解析 ## 1. 模拟退火算法概述 模拟退火算法是一种基于概率的优化算法，其核心思想是通过模拟物理退火过程来寻找全局最优解。在该算法中，$\Delta E$ 用于衡量新的试验解对成本函数的影响。若新解使成本函数增加，$\Delta E$ 为正；若使成本函数降低，$\Delta E$ 为负。当 $\Delta E$ 为正时，接受新解的概率 $P$ 在 0 - 0.5 范围内；当 $\Delta E$ 为负时，$P$ 在 0.5 - 1 范围内。在高温阶段，无论新解的适应性如何，$P$ 都接近 0.5。当温度 $T = 0$ 时，模拟退火算法等同于爬山算法。 ### 1.1 多目标优化问题 需要优化多个参数组合的问题被称为多目标优化问题。在这类问题的多维搜索空间中，试验步的方向选择是关键。通过使用选择步长方向的算法，性能得到了显著提升。此外，引入可变步长也是一种有效的改进方法。在特定应用中，随着迭代次数的增加，逐渐减小最大允许步长，能够得到更优的解。 ### 1.2 模拟退火算法的改进 模拟退火算法还有其他改进方式，例如使用过去试验解的存档。在评估是否跳转到新的试验解时，会将存档与当前试验解一同考虑。 ### 1.3 模拟退火算法的应用 模拟退火算法已成功应用于众多领域，包括： - 电子电路设计 - 等离子体诊断专用设备的调优 - 天气模式的聚类分析 - 机器分配到制造单元 - 钢板轧制精轧机的参数设置 ### 1.4 数值优化与基于知识的搜索对比 数值优化技术通常基于最小化成本或最大化适应性，成本常被定义为输出与期望输出之间的误差。与基于知识的搜索不同，数值优化中我们虽知道解应满足的适应性要求，但不清楚解在搜索空间中的具体位置，问题的关键在于在搜索空间中寻找满足适应性要求的位置。 ### 1.5 模拟退火算法的优势 所有数值优化技术都存在找到局部最优解而非全局最优解的风险。模拟退火算法通过在搜索早期引入探索阶段来克服这一问题。在高温阶段，算法可以自由地在搜索空间中探索优质区域。随着温度降低，算法从探索阶段过渡到利用阶段，即寻找当前试验解所在区域的峰值适应性，该区域被假定包含全局最优解。 ## 2. 遗传算法简介 遗传算法是一类特殊的优化算法，它维护一组候选解，而不是像之前的技术那样只改进单个试验解。整个种群朝着最优解进化，尽管在进化早期可能包含许多较差的解。与模拟退火算法类似，遗传算法通常从探索阶段开始，在这个阶段，种群在搜索空间中寻找优质区域。随着进化的进行，算法从探索过渡到利用，即寻找假定包含全局最优解的区域的峰值适应性。 ### 2.1 遗传算法的生物学灵感 遗传算法受自然进化的启发，自然进化是动植物通过世代更迭逐渐接近最优形态的过程。每个后代与父母具有不同的特征，若新特征有利，后代更有可能繁衍并将特征传递给下一代；若特征不利，则可能无法繁殖。这些思想被应用于数学优化，使一组候选解“进化”向最优解。 ### 2.2 遗传算法的设计决策 要实现遗传算法，需要做出以下设计决策： - 如何使用称为染色体的数字序列来表示候选解。 - 种群的大小。 - 如何评估种群中每个成员的适应性。 - 如何根据适应性信息选择用于繁殖的个体（反之，确定哪些适应性较差的个体不繁殖）。 - 如何繁殖候选解，即如何从现有种群创建新一代候选解。 - 何时停止进化过程。 ## 3. 基本遗传算法 ### 3.1 染色体表示 搜索空间中的每个点都可以用由基因组成的唯一染色体表示。例如，要找到适应度函数 $f(x, y)$ 的最大值，且搜索空间变量 $x$ 和 $y$ 被限制在 0 - 15 的 16 个整数值内，搜索空间中的任何点都可以用两个基因表示的染色体来表示。如点 $(2, 6)$ 对应的染色体为： ```plaintext 2 6 ``` 基因的可能值称为等位基因，在这个例子中，每个基因有 16 个等位基因。染色体上的每个位置称为位点，在上述例子中有两个位点。在遗传算法中，位点只能存储二进制值。因此，染色体可以用由二进制数 0010 和 0110 组成的八个位点表示： ```plaintext 0 0 1 0 0 1 1 0 ``` 一般来说，一个 $N$ 位宽的二进制编码基因有 $2^N$ 个等位基因。 ### 3.2 算法流程 基本遗传算法的流程图如下： ```mermaid graph TD; A[随机生成初始种群] --> B[评估每个个体的适应度]; B --> C[选择要交配的个体]; C --> D[以概率 $P_c$ 进行交叉操作生成后代]; D --> E{是否终止?}; E -- 否 --> F[以概率 $P_m$ 进行变异操作生成后代]; F --> G[用新种群替换旧种群]; G --> B; E -- 是 --> H[停止]; ``` 在基本算法中，有以下假设： - 初始种群是随机生成的。 - 个体根据适应度函数进行评估。 - 个体根据适应度被选择用于繁殖，适应度越高，被选中的可能性越大。 - 通过染色体对之间的“繁殖”（使用交叉算子），然后对每个后代应用变异算子，来产生下一代染色体。交叉和变异算子的平衡是遗传算法设计者需要考虑的另一个决策。 ### 3.3 交叉操作 交叉操作是通过对齐两个父染色体，随机选择一个位置，并以概率 $P_c$ 交换尾部来产生子染色体。常见的交叉方式包括： - **单点交叉**：只指定一个分离交换和未交换位点的位置，第二个交叉位置默认为染色体的末尾。 - **两点交叉**：将染色体视为圆形，$m_1$ 和 $m_8$ 被视为相邻位点。 - **多点交叉**：只要交叉点数量为偶数即可