Studies in Probabilistic Model-Building Evolutionary Algorithms

Abstract

Evolutionary algorithms (EAs) are a family of metaheuristics inspired by Darwin's theory of evolution through natural selection. They maintain and evolve a population of candidate solutions through stochastic variation and selection to find optimal or near-optimal solutions to complex problems. Probabilistic Model-Building Evolutionary Algorithms (PMBEAs) are a more recent class of EAs that replace traditional variation operators with constructing and refining probabilistic models over the search space. Rather than directly evolving a population, PMBEAs iteratively sample new candidates from a probability distribution shaped by prior search experience. This thesis investigates the theory and application of PMBEAs across three main contributions.

The first part of this work addresses the problem of genetic drift, a phenomenon where random noise from sampling a finite population gradually steers the model, especially when strong fitness signals are lacking. Over time, these unintended shifts can accumulate, causing the model parameters to drift toward suboptimal values. To address this, we introduce the Competing Genes Evolutionary Algorithm (cgEA), a univariate PMBEA that updates individual marginals only when there is sufficient justification to do so. We rigorously analyze its runtime on several benchmark functions, showing that this cautious update rule helps prevent premature convergence caused by genetic drift and leads to more stable and reliable performance. We also propose two extensions: one that automatically tunes the population size and another that includes partial restarts to mitigate the impact of suboptimal early decisions. Together, these results offer new ideas for the design of stable, drift-resistant PMBEAs.

In the second part, we tackle the challenge of epistasis, where dependencies between variables distort the search landscape and render univariate models ineffective. We explore the potential of quantum computing to overcome these limitations by proposing a quantum evolutionary algorithm with dynamic mutation rates. This algorithm leverages the fixed-point quantum amplitude amplification subroutine to guide the search more efficiently. We analyze its runtime on standard benchmark problems, demonstrating quantum speedups in specific settings. Additionally, we contribute new upper bounds for the quantum black-box complexity of the OneMax and LeadingOnes problems and present specialized quantum algorithms that achieve or approach these bounds.

The final part transitions from theory to application. Here, we apply the principles of evolutionary search and probabilistic modeling to the Target Set Selection problem, which asks for the smallest initial set of influenced nodes that can trigger a full adoption of an idea in a social network. Despite the problem's NP-hardness and inapproximability, practical heuristics have achieved varying levels of success. Existing approaches tend to fall into two categories: search-based metaheuristics, which are often effective but computationally intensive, and one-shot construction heuristics, which are fast but can yield large target sets. To bridge this divide, we develop a probabilistic model-driven genetic programming algorithm that evolves heuristics capable of producing small target sets efficiently. Among the heuristics discovered, we highlight the Evolved Priority Heuristic (ELPH) and show that it consistently outperforms existing one-shot methods on test networks. In addition, we introduce a fast pruning method based on estimating the Shapley values of nodes, providing an efficient way to reduce large initial target sets with minimal simulation of influence propagation. Combined with ELPH, this yields a fast and effective heuristic pipeline for solving the TSS problem, balancing solution quality with scalability.