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.