Purpose of the Project
With this project we want to introduce you to all parts of research in theoretical computer science. We start with a literature search, followed by creative white-board work and verification of ideas with formal proofs, concluded by the actual writing of a paper. As for the content, we want to formally analyze the effect of crossover operations in black-box search. We want to consider functions
\(f: \{0,1\}^n \rightarrow \mathbb{R}, x \mapsto \sum_{i=1}^n w_i x_i\),
where \((w_i)_{i \leq n}\) is a sequence of weights. Such functions \(f\) are called linear pseudo-Boolean functions, and their optimization is a good testbed for black-box search. If we impose a cardinality constraint (i.e., for some \(k < n \), only those bit strings with at most \(k\) many \(1\)s are acceptable solutions), the problem quickly approaches the well-known NP-hard knapsack problem. However, with this simple cardinality constraint good solutions can still be found in time about \(\Theta(n^2)\) by simple local search-like genetic algorithms [2]. We will introduce to you advanced tools from probability theory (including drift theory) which make such optimization processes amenable for formal analysis and which can be used to turn expected progress per expectation into expected optimization times. We believe that with these tools a tremendous speedup to \(O(n \log n)\) can be shown when employing good crossover operations with appropriate diversity mechanisms (see [3]).
