单候选优化算法详解

### 单候选优化算法详解 #### 1. 优化的基本概念 优化是一个确定一个或多个变量的函数的最大值或最小值的过程。在许多情况下，优化问题被视为确定最小值，此时被最小化的函数称为成本函数，它通常是期望输出与实际输出之间的差异或误差。另一种观点是将优化看作是最大化一个函数的值，这个函数被称为适应度函数。 实际上，这两种方法是等价的。适应度 \(f_i\) 和成本 \(c_i\) 之间的关系可以表示为： - \(f_i = k - c_i\)（式 6.1），其中 \(k\) 是一个可选的正常数，用于确保成本和适应度都为正。 - \(f_i = \frac{1}{c_i}\)（式 6.2） 无论选择哪种关系，适应度总是随着成本的降低而增加。目标函数涵盖了适应度和成本，优化目标函数可能意味着最小化成本或最大化适应度。 优化方法分为确定性方法和随机方法： - 确定性方法使用可预测和可重复的步骤，只要起始条件相同，总是能找到相同的解。例如，线性规划提供了一种代数方法来找到线性缩放变量的最优组合。 - 随机方法包含随机性元素，不能保证可重复性。但它们的优点是，即使潜在解的数量非常庞大，也能在可接受的时间范围内找到接近最优的解。 单候选优化算法在整个过程中始终只有一个试验解，算法会不断改进这个解，直到达到停止标准。 #### 2. 搜索空间 搜索空间或参数空间由搜索问题的潜在解组成。如果只寻找一个变量的值，搜索空间是一维的；如果同时寻找 \(n\) 个变量的值，搜索空间就是 \(n\) 维的。无效的参数值组合可以明确地从搜索空间中排除，或者假设它们会被优化算法拒绝而包含在内。 搜索空间可以分为组合问题和排列问题： - **组合问题**：搜索空间由值的组合组成，只要每个值的含义已知，组合的顺序就没有特别的意义。例如，在钢铁轧机中，可以优化描述轧辊轮廓的参数组合，以最大化制造钢材的平整度。每个可能的参数值组合代表搜索空间中的一个点，搜索空间的范围受到变量限制的约束。 - **排列问题**：涉及某些属性的排序。最著名的例子是旅行商问题，旅行商必须找到在已知位置的城市之间的最短路线，且每个城市只访问一次。对于每个城市排列（称为行程），可以将成本函数评估为旅行距离的总和。每个可能的行程代表搜索空间中的一个点，排列问题通常是循环的，例如行程 ABCDE 被认为与 BCDEA 相同。 搜索空间中不同点之间的距离可以用不同的方式衡量。在旅行商问题中，可以用将一个行程转换为另一个行程所需的成对交换次数来直观地衡量；对于二进制模式，通常用汉明距离来衡量，即包含不同值的位位置的数量。 我们可以为搜索空间中的每个点关联一个适应度值。对于二维搜索空间，通过绘制适应度值可以得到适应度景观。在更高维度的搜索空间中，适应度景观仍然存在，但难以可视化。合适的优化算法需要在适应度景观中找到峰值或在成本景观中找到谷值。然而，无论搜索空间的维度如何，都存在找到局部最优而非全局最优的风险。全局最优是搜索空间中适应度最高的点，局部最优是其适应度高于所有近邻但低于全局最优的点。 如果搜索空间中相邻点的适应度相似，则景观被称为平滑或相关的；如果相邻点的适应度差异很大，则景观被称为崎岖的。崎岖的景观通常有大量的局部最优，搜索空间中单个点的适应度不一定反映其邻居的适应度。 在许多问题中，搜索变量并非完全独立，一个变量的变化会导致另一个变量的变化，这种现象称为上位性，搜索空间被称为上位性搜索空间。 #### 3. 搜索参数空间 确定多变量目标函数的最优值并非易事，即使景观是静态的。虽然详尽地评估搜索空间中每个点的适应度总是能揭示最优值，但由于搜索空间的巨大规模，这通常是不可行的。因此，所有数值优化技术的本质是通过只检查所有可能候选解的一小部分来确定搜索空间中的最优解。 这里描述的技术都基于选择一个起始点，然后改变一个或多个变量，以尝试增加适应度或降低成本。本章描述的所有方法都维护一个“到目前为止的最佳解”，并不断改进它，直到无法再增加适应度为止。 这些方法从起始点逐步进行，因此每个新的候选解在搜索空间中永远不会离当前解太远。迭代改进过程会持续进行，直到搜索到达全局最优或局部最优。为了避免错过全局最优，建议从搜索空间中的不同点多次重复该过程。 #### 4. 爬山和梯度下降算法 ##### 4.1 爬山算法 爬山算法意味着将优化视为在适应度景观中寻找最大值的过程。但该方法同样适用于成本景观，在这种情况下，更合适的名称可能是山谷下降。它是这里描述的优化程序中最简单的一种。算法易于实现，但效率低下，并且不能防止找到局部最小值而非全局最小值。 算法步骤如下： 1