View article

Surrogate models are crucial tools for many real-world optimization problems. An optimization algorithm can evaluate a data-driven surrogate model instead of an expensive objective function. While surrogate models are well-established in the continuous optimization domain, they are less frequently applied to more complex search spaces with discrete or combinatorial solution representations. The main goal of this thesis is to fill this gap. We develop and improve methods for data-driven surrogate modeling in discrete search spaces. After an initial review of existing approaches, this work focuses on a similarity-based, or kernel-based, model: Kriging. The intuitive idea is to change the underlying kernel, thus adapting Kriging to arbitrary data types. However, the model is sensitive to the employed kernel. Hence, methods for combining or selecting kernels are required. To that end, this thesis discusses various methods based on concepts like correlation, likelihood, and cross-validation. Our experiments show that choosing or constructing the right kernel determines the success of the optimization algorithm. Another challenge is that kernels are often desired to be positive semi-definite (e.g., correlation functions) or conditionally negative semi-definite (distances). Analytical proofs of a kernel's definiteness are possible, yet not always feasible in practice. At the same time, these properties can have a significant effect on model accuracy. Hence, we propose a randomized, empirical search procedure to determine whether a kernel is definite. Once a kernel is determined to be indefinite, appropriate counter-measures have to be taken to avoid …