新闻资讯

新闻资讯 行业动态

南京大学提出高效演化算法 EAMC:可更好解决子集选择问题(四)

编辑:005     时间:2020-02-15

理论分析

这一节为 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)。

郑重声明:本文版权归原作者所有,转载文章仅为传播更多信息之目的,如作者信息标记有误,请第一时间联系我们修改或删除,多谢。

回复列表