Optimization in discrete and mixed domains is a fundamental challenge across various disciplines, such as computer science, engineering, and the natural sciences. Evolutionary algorithms (EAs), as randomized search heuristics, have become a powerful approach to these problems due to their ability to cope with noisy and poorly understood landscapes. Given the widespread empirical success of EAs, establishing a rigorous theoretical understanding of their performance, and in particular identifying the conditions under which they perform well, has become a significant research direction. Run time analysis addresses this by formally studying the expected number of fitness evaluations required to obtain high-quality solutions and explains the influence of algorithmic design choices and problem structures. This thesis presents a run time analysis of EAs on four distinct problems, each capturing a different challenge in discrete or mixed optimization. First, in constrained problems, we analyze variants of the classical LeadingOnes with both deterministic and stochastic constraints. For the (1+1) EA under uniform constraint, we show tight bound of Θ (nB + n (n-B) log B) on the expected run time. We further show that reformulating the task as a bi-objective problem reduces the run time to O (n²), and that population-based EAs can help stabilize algorithmic performance under stochastic constraints. Second, we analyze the run time of the integer-valued OneMax problem. We prove that single-step mutation requires Θ (n (|a|∞ + log |a|H) evaluations, where a is the optimum. Heavy-tailed operators reduce the dependence on the distance to a poly-logarithmic term, O (n log² |a|₁ (loglog |a|₁) {1+ε), while self-adjusting strategies achieve Θ (n |a|₁), where a|₁ denotes the ℓ₁-distance to the optimum. We further show that ℓ₁-symmetric operators are provably inefficient, requiring at least linear time in |a|₁. Third, we study the role of parent selection in evolutionary multi-objective algorithms. We show that a simple multi-objective EA optimizes pairs of generalized OneMax functions in O (dnlog n) expected time, where d is the distance between the two optima, and prove that curiosity-driven selection reduces the run time on OneMinMax to O (n²), improving upon the classical O (n²log n) bound. Finally, in mixed-binary problems, we consider optimization tasks with binary and continuous variables. We introduce and empirically analyze a hybrid of covariance matrix adaptation and population-based incremental learning (CMA-ES-PBIL), showing that it outperforms established CMA-ES variants on some benchmark functions and that the discrete part is solved much faster than the continuous part. Overall, this work contributes to a better understanding of which evolutionary algorithms could be more suitable for complex real-world optimization problems.
Aishwarya Radhakrishnan (Thu,) studied this question.