Populationsbasierte Optimierung durch das Lernen von Interaktionen mit Bayes'schen Netzen

Ziel dieser Arbeit ist es, populationsbasierte Optimierungsmethoden für diskrete Probleme zu analysieren. Indem man Populationen, also Mengen von Suchpunkten, durch Verteilungen beschreibt, lassen sich genetische Algorithmen als Operatoren im Raum dieser Verteilungen auffassen. Es zeigt sich dabei, dass die zu genetischen Algorithmen passende Verteilung die einfache Produktverteilung der univariaten Randverteilungen ist. Das Verhalten der Algorithmen lässt sich analysieren, in dem man die durchschnittliche Fitness betrachtet. Parametrisiert über die univariaten Randverteilungen transformiert sie das diskrete Optimierungsproblem in ein kontinuierliches. Dabei führt der genetische Algorithmus näherungsweise Gradientenaufstieg in diesem Raum durch. Dieses Verhalten wird im ersten Teil der Arbeit näher untersucht. Da die Produktverteilung Interaktionen zwischen Parametern nicht darstellen kann, wird im zweiten Teil der Arbeit die Optimierung durch eine andere Suchverteilung dargestellt, die Boltzmann-Verteilung. Um die Parameter dieser Verteilung mit polynomiellem Aufwand schätzen zu können, wird eine Faktorisierung benötigt. Die Theorie der Bayes'schen Netzwerke liefert eine theoretische Grundlage, um diese aus den Datenpunkten zu lernen. Der resultierende Algorithmus ist in der Lage, Abhängigkeiten zwischen Variablen zu lernen und dieses Wissen für die Optimierung zu benutzen. Um in der Population in der Boltzmann-Verteilung zu halten, muss Boltzmann-Selektion angewandt werden. Dies wurde bisher nicht gemacht, weil dafür ein Parameter pro Zeitschritt benötigt wird, der dem Abkühlungsplan bei Simulated Annealing entspricht. Die Talyorentwicklung der durchschnittlichen Fitness erlaubte es, einen solchen Plan zu entwicklen, der Buncation Selection imitiert und daher ähnlich robust ist und auf einen Algorithmus führt, der invariant unter positiven linearen Transformationen der zu optimierenden Funktion ist. Im letzten Teil der Arbeit werden die vorgestellten Algorithmen auf schwierige Probleminstanzen der Graph-Bipartitionierung angewandt.

This thesis analyzes population based optimization methods for discrete problems. By describing populations with probability distributions, genetic algorithms can be seen as operators in the space of these distributions. It turns out that the corresponding distribution is the product of the univariate marginal distributions. The behaviour of the algorithm can furthermore be explained by examining the average fitness of the population. Parameterised by the univariate marginal distributions, the average fitness transforms the discrete optimization problem into a continuous one. Genetic algorithms perform an approximate gradient ascent in this space. This behaviour is analysed in the first part of this thesis. As the product distribution cannot represent interactions between parameters, a different search distribution is used in the second part, the Boltzmann distribution. In order to be able to estimate the parameters of this distribution in polynomial time, a factorization is needed. Learning the factorization from the data points can be done using the theory of Bayesian networks. The resulting algorithm is able to learn dependencies between parameters and use this knowledge for the optimization. To keep the population in the Boltzmann distribution, we have t o use Boltzmann selection. This was not done as a parameter per time step is needed. This parameter corresponds to an annealing schedule in simulated annealing. The Taylor expansion of the average fitness made it possible to develop such a schedule. It imitates truncation selection and is similarly robust, and the resulting algorithm is invariant under positive linear transformations of the function to optimize. Finally, in the last part of this work, the algorithms are applied to difficult instances of the graph bipartitioning problem.