理论分析

这一节为 EAMC 的一般近似界给出了证明，如定理 3 所示。相比于定理 2，EAMC 能实现与 POMC 同样的近似保证，即

，但预期的运行时间是多项式的上限。其证明依赖于引理 1，可以直观地看到，这意味着对于任意子集，某个特定项的包含都至少能将 f 提升一定量，这个量与离最佳结果的当前距离成比例。这里假设 v ∈ V : c () ≤ B；因为在优化前可以将任意 c () > B 的 v 直接移除。

证明。通过分析如下定义的量 J_max，可以证明该定理。

令 P_max 表示 EAMC 运行期间种群 P 的最大规模。研究者首先表明，在至多 enP_max 个预期数量的迭代后，J_max ≥ 1。很容易看到，解 0^n 将总是位于 P 中，因为只有同样规模大小的解可以进行比较，而 0^n 是大小为 0 为唯一解。根据引理 1，翻转一个 0^n 的一个特定 0 位（即添加一个特定项）可以生成一个新的解 x'，使得：

其中由于 r ∈ R : 1 r ≤ e^ r，后一个不等号是成立的。在每轮迭代中，x' 都至少能以

的概率生成，其中 1/P_max 是从解群选出 0^n 的概率的下界，是在保持其它位不变的同时翻转 0^n 的特定比特的概率。因此，生成 x' 的预期迭代次数至多为 enP_max。注意，根据式 (6) 和 (7)，。如果 x' 包含在 P 中，则有 J_max ≥ 1；否则，bin(1) 中必然存在一个 g 值更大的解，这意味着 J_max ≥ 1。

假设当前的 J_max = i。根据算法 3 的行 11-13 和行 17，bin(i) 中解的最大 g 值不会减小，因此 J_max 也不会减小。这说明总是存在满足的x ∈ bin(i)。

接下来考虑 J_max 增大，直到找到一个 f 值至少为

的解。令 x 表示有最大 g 值的解。根据引理 1，翻转 x 的特定 0 位可以生成一个满足 |x'| = i + 1 的解 x'，且

其中，由于 J_max = i，根据，第一个不等式成立；而根据 r ∈ R : 1 r ≤ e^ r，最后一个不等式也成立。因此，可以得到。在每轮迭代中，x' 能以至少

的概率生成，这说明在生成满足 |x'| = i + 1 和的 x' 之前的预期迭代数量至多为 enP_max。然后，考虑 c (x') 的两种情况：

（1）如果 c (x') > B，则式 (8) 说明

。令，则有：

其中，根据定义 1，第一个不等式成立；根据 α_f ∈ [0, 1]，最后一个不等式成立。在每轮迭代中，可通过选择 0^n 并翻转特定的 0 位来生成 y（以至少 1/enP_max 的概率发生）。因此，在至多 enP_max 个预期迭代轮数中可以生成 y。根据行 7-10 和 14-17 中 P 的更新流程，可以知道一旦生成了 y，P 总是包含一个满足 f(z) ≥ f(y) 的解 z ∈ bin(1)。可以验证，总是存在一个满足 f(z') ≥ f(x) 的解 z' ∈ bin(i)。根据算法 3 的行 22，最后返回的解会是 f 值最大的解。因此，EAMC 输出的解的 f 值至少为：

（2）如果 c (x') ≤ B，根据行 7-13 和 17 的更新流程，可知 x' 将被加入到 P 中，因为不存在满足 g(z) ≥ g(x') 的 z ∈ bin(i + 1)；否则 g(z) ≥ g(x') ≥ f(X )，这与 J_max 的定义相矛盾。现在，J_max = i + 1.

重复以上分析，EAMC 将输出满足的解 z，这意味着达到了所需的近似保证，或者 J_max 将继续增大，直到到达最大值 n。后面的情况意味着 c (1^n) ≤ B，而 EAMC 将输出 1^n；因为 f 单调，所以这是最优的。

现在来看看预期的迭代总数。要使 J_max ≥ 1，预期的迭代数量最大为 enP_max；为了将 J_max 从 1 增大到 n，预期的迭代数量至多为 (n-1) · enP_max；为了生成 y，预期的迭代数量至多为 enP_max。因为 bin(i) 中最多有两个解，其中 1 ≤ i ≤ n – 1（算法 3 的行 17）；而 bin(0) 和 bin(n) 最多只有一个解，有 P_max ≤ 2n。因此，预期的迭代总数至多为。

当对 α_f 的确切计算很困难时，在 α_f 上的下界（用 α 表示）可以用在替代目标 g 中，EAMC 能实现

的近似比，如推论 1 所示。在定理 3 的证明中，近似比中包含第一个 α_f 的因子（即α_f/2）是从式（9）推导出来的，这不依赖于 g。因此，这个因子会保持不变。包含第二个 α_f 的因子（即）是从式（8）推导的，这会应用于 g 的定义。因为现在 α 被用在 g 中，这个因子中的 α_f 会相应地变为 α。

推论 1。对于定义 3 中的问题，当在 α_f 上的下界（用 α 表示）应用于式（6）中的替代目标 g 上时，满足

的 EAMC 可找到一个子集 X V，其满足条件

其中 f(X ) 的定义见式 (4)。