Genetic algorithms have unique properties which are useful when applied to black-box optimization. Using selection, crossover, and mutation operators, candidate solutions may be obtained without... Show moreGenetic algorithms have unique properties which are useful when applied to black-box optimization. Using selection, crossover, and mutation operators, candidate solutions may be obtained without the need to calculate a gradient. In this work, we study results obtained from using quantum-enhanced operators within the selection mechanism of a genetic algorithm. Our approach frames the selection process as a minimization of a binary quadratic model with which we encode fitness and distance between members of a population, and we leverage a quantum annealing system to sample low-energy solutions for the selection mechanism. We benchmark these quantum-enhanced algorithms against classical algorithms over various black-box objective functions, including the OneMax function, and functions from the IOHProfiler library for black-box optimization. We observe a performance gain in the average number of generations to convergence for the quantum-enhanced elitist selection operator in comparison to classical on the OneMax function. We also find that the quantum-enhanced selection operator with ∗Corresponding author email: David.VonDollen@vw.com non-elitist selection outperforms benchmarks on functions with fitness perturbation from the IOHProfiler library. Additionally, we find that in the case of elitist selection, the quantum-enhanced operators outperform classical benchmarks on functions with varying degrees of dummy variables and neutrality Show less
This thesis involves three topics: benchmarking discrete optimization algorithms, empirical analyses of evolutionary computation, and automatic algorithm configuration. The objective is... Show moreThis thesis involves three topics: benchmarking discrete optimization algorithms, empirical analyses of evolutionary computation, and automatic algorithm configuration. The objective is benchmarking EAs on discrete optimization for the selection and design of better optimizers.In practice, we start with building the IOHprofiler benchmark software, which supports us in testing algorithms on a wide range of problems and allows us to perform and visualize the statistical analysis on algorithms' performance.While performing numerous benchmark studies, we study the impact of mutation rate and population size on the EAs and investigate how crossover and mutation interplay with each other and the impact of population size on the GAs. Moreover, we analyze a smooth way of interpolating between local and non-local search by proposing a new normalized bit mutation.We apply Irace, MIP-EGO, and MIES to configure the GA for ERT and AUC, respectively. Our results suggest that even when interested in ERT, it might be preferable to tune for AUC for the configuration task. We also observe that tuning for ERT is much more sensitive with respect to the budget that is allocated to the target algorithms.At last, we leverage our benchmark data of static algorithms to study dynamic algorithm selection. Show less
This study presents an agent-based simulation model exploring the patterns of presence and absence of Late Pleistocene Neanderthals in western Europe. HomininSpace implements a parameterized... Show moreThis study presents an agent-based simulation model exploring the patterns of presence and absence of Late Pleistocene Neanderthals in western Europe. HomininSpace implements a parameterized generic demographic and social model of hominin dispersal while avoiding parameter value biases and explicitly modelled handicaps. Models are simulated through time within a high-resolution environment where reconstructed temperatures and precipitation levels influence the carrying capacity of the landscape. Model parameter values are assigned and varied automatically while optimizing the match with Neanderthal archaeology using a Genetic Algorithm (GA) inspired by the processes of natural selection. The system is able to traverse the huge parameter space that is created by the complete set of all possible parameter value combinations to find those values that will result in a simulation that matches well with archaeological data in the form of radiometrically obtained presence data. Show less