On the Evolvability of Monotone Conjunctions with an Evolutionary Mutation Mechanism

Abstract

A Bernoulli(p)n distribution Bn, p over 0, 1n is a product distribution where each variable is satisfied with the same constant probability p. Diochnos (2016) showed that Valiant's swapping algorithm for monotone conjunctions converges efficiently under Bn, p distributions over 0, 1n for any 0 < p < 1. We continue the study of monotone conjunctions in Valiant's framework of evolvability. In particular, we prove that given a Bn, p distribution characterized by some p ∈ (0, 1/3] ∪ 1/2, then an evolutionary mechanism that relies on the basic mutation mechanism of a (1+1) evolutionary algorithm converges efficiently, with high probability, to an ε-optimal hypothesis. Furthermore, for 0 < α ≤ 3/13, a slight modification of the algorithm, with a uniform setup this time, evolves with high probability an ε-optimal hypothesis, for every Bn, p distribution such that p ∈ [α, 1/3 - 4α/9] ∪ 1/3 ∪ 1/2.