Crossover for cardinality constrained optimization
Tobias Friedrich, Timo Kötzing, Aishwarya Radhakrishnan, Leon Schiller, Martin Schirneck, Georg Tennigkeit, Simon Wietheger · Proceedings of the Genetic and Evolutionary Computation Conference · 2022
In order to understand better how and why crossover can benefit optimization, we consider pseudo-Boolean functions with an upper bound B on the number of 1s allowed in the bit string (cardinality constraint). We consider the natural translation of the OneMax test function, a linear function where B bits have a weight of 1 + ε and the remaining bits have a weight of 1. The literature gives a bound of Θ(n2) for the (1+1) EA on this function.