论文标题
二维漂移分析：同时优化两个功能可能很难
Two-Dimensional Drift Analysis: Optimizing Two Functions Simultaneously Can Be Hard
论文作者
论文摘要
在本文中，我们将在两个随机变量$ x_1，x_2 $的情况下展示如何使用漂移分析，当矩阵$ a $的$ a \ cdot（x_1，x_2）^t $在$ a \ cdot（x_1，x_2）^t $上近似时。非平凡的情况是，$ x_1 $和$ x_2 $妨碍了彼此的进度，我们给出了这种情况的全部表征。作为应用，我们开发和分析了可能很难的动态环境的最小示例。环境由两个线性函数$ f_1 $和$ f_2 $组成，具有正权重$ 1 $和$ n $，并且在每个一代中，选择都是基于其中的一个。它们在重量$ 1 $和$ n $的一组职位上只有不同。我们表明，$（1+1）$ - 具有突变速率$χ/n $的$（1+1）$对于TwoLinear的小$χ$有效，但在多项式时间内没有找到大$χ$的共享最佳。
In this paper we show how to use drift analysis in the case of two random variables $X_1, X_2$, when the drift is approximatively given by $A\cdot (X_1,X_2)^T$ for a matrix $A$. The non-trivial case is that $X_1$ and $X_2$ impede each other's progress, and we give a full characterization of this case. As application, we develop and analyze a minimal example TwoLinear of a dynamic environment that can be hard. The environment consists of two linear function $f_1$ and $f_2$ with positive weights $1$ and $n$, and in each generation selection is based on one of them at random. They only differ in the set of positions that have weight $1$ and $n$. We show that the $(1+1)$-EA with mutation rate $χ/n$ is efficient for small $χ$ on TwoLinear, but does not find the shared optimum in polynomial time for large $χ$.
