EAMC 算法

这一节介绍研究者为最大化有单调成本限制的单调函数所提出的一种简单演化算法：EAMC。EAMC 不会最大化式（3）中的 f，而是引入了一个替代目标 g，并对其进行最大化，用数学表示为：

可以看到，g 同时纳入了原有的目标函数 f 以及成本 c 。更小的 c 值和更大的 f 值都会导致 g 的值更大。

在优化过程中，EAMC 会保留一个种群 P，然后新生成的解 x' 只会与 bin(|x'|) 中解进行比较。bin(|x'|) 的定义为：

也就是说，x' 只与 P 中与 x' 有同样大小的解相比。这样的设置会让这个解群 P 更加多样化，由此能够提升该算法的搜索能力。由于问题式 (3) 需要在满足预算限制的同时实现 f 的最大化，所以 EAMC 只会考虑满足 c (x')≤B 的 x'；在运行过程中，除了有最大 g 值的解之外，每个 bin 都保留有截至目前所生成的最大 f 值的解。

算法 3 描述了 EAMC 的执行过程。从空集 0^n 开始（行 1），不断尝试改善每个 bin 中的解的 g 值（行 2-21）。在每次迭代中，通过随机翻转从当前 P 中选出的解 x 来生成一个新的解 x'（行 3-4）；而且只有当 x' 满足限制条件时才会被包含进 P 中（行 5）。如果 bin(|x'|) = ，则将 x' 添加进 P，并将 u^|x'| 和 v^|x'| 分别用于保留有目前所生成的最大 g 和 f 值的大小为 |x'| 的两个解（行 7-9）；否则，x' 与 bin(|x'|) 中的解进行比较，如果截至目前生成的最大 g 或 f 得到提升，则更新 bin(|x'|)（行 10-18）。可以看到，每个 bin(i) 都只包含解 u^i 和 v^i，它们可能是一样的。在 T 轮迭代后，P 中有最大 f 值的解被输出（行 22）。注意，因为行 5，P 中的所有解都必须满足约束。

EAMC 需要知道子模比 α_f，因为替代目标 g 需要使用它。对于子模的 f，α_f = 1。对于非子模的 f，精确计算 α_f 可能需要指数级的时间，不过可以在 α_f 上使用一个下限来替代。注意，α_f 的这个下限在一些单调非子模应用中已被推导出来，比如贝叶斯实验设计和行列式函数最大化。