How symmetry constrains evolutionary optimizers

摘要

Black box optimization begins with the assumption that if nothing is known about the objective function, then there is no justifiable reason for an optimization algorithm to, e.g. preferentially search in one direction, or to favor one coordinate system orientation over another. This paper investigates whether or not classic differential evolution (DE/rand/1/bin) satisfies these black-box constraints and if not, what it takes to bring the algorithm into conformity with them. The result is an exceptionally simple algorithm, black box differential evolution (BBDE), whose performance is invariant under a coordinate system translation, an orthogonal rotation, a reflection and a permutation of parameters. Performance is also invariant under both the addition of a function bias and an order-preserving transform of the objective function. On the family of ellipsoids, its performance is invariant to both scaling and high-conditioning (eccentricity). Additionally, BBDE is free of both selection and generating drift biases. Furthermore, selection, mutation and recombination are decoupled to become independent operations, as they should be, since each performs a distinctly different function that ought not to be duplicated by another. BBDE also satisfies a few algorithm-specific, symmetry-based constraints. Like the CMA-ES, BBDE's only control parameter is the population size. In short, BBDE appears to be the simplest DE strategy to conform to a set of symmetry-based constraints that are necessary for unbiased, i.e. black box, optimization.