lecture notes on evolutionary computation on expensive optimization problems: a survey

1 总优化成本

昂贵优化问题（Expensive optimization problem, EOP）是指以高昂甚至难以承担的成本来评估候选解的问题，并广泛存在于许多重要现实应用中。进化计算（Evolutionary computation, EC）算法因能在无需梯度信息的情况下高效寻找到令人满意的解而被广泛应用以解决昂贵优化问题。

其中每次昂贵评估所花费的 平均计算成本 为O(C)；而求解该问题的进化计算算法所需的时间复杂度为O(N)（其中N代表总评估次数的数量级）。此外，并行与分布式计算技术提供了 性能提升的关键手段 。
在昂贵优化中面临的最核心挑战在于高昂的适应度函数计算与约束条件验证（如式1所示），即当式(1)中的O(C)变得非常庞大时，则会导致整体规模无法承受——Total_cost将急剧上升。然而式(1)也提示我们可以通过三个主要方向来更加高效地解决昂贵优化问题：减少每次评估的成本（即减小C）、减少总的评估次数（即减小N），以及提高性能加速能力（即增大P）。具体而言，在实际应用中可以从以下几个方面入手：首先利用问题近似或简化方法降低计算开