Two Dimensional Drift Analysis: Optimizing Two Functions Simultaneously Can Be Hard

The performance of Evolutionary Algorithms (EAs) in dynamic environments, that is, environments in which the fitness function changes over time, has recently been studied (e.g., [Lengler, Meier, 2020]). In this talk, we developand analyze a minimal example of a dynamic environment called TwoLinear that can be hard for EAs. The environment consists of two linear functions f_1 and f_2 with positive weights 1 and n, and in each generation, the selection of the algorithm is based onone of them at random. The functions 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 χ. To obtain the above result, we apply drift analysis in two dimensions. Drift analysis is one of the most powerful techniques to analyze the performance and behavior of EAs. Previously, it has only been applied in one dimension. Here, we have two random variables,X_1, X_2, and the drift is approximatively given by A·(X_1, X_2)^T for a matrix A. More precisely, we are in the case where X_1 and X_2 impede each other’s progress, and we give a full characterization of this case.