TY - JOUR A1 - Doerr, Benjamin A1 - Kötzing, Timo A1 - Lagodzinski, Gregor J. A. A1 - Lengler, Johannes T1 - The impact of lexicographic parsimony pressure for ORDER/MAJORITY on the run time JF - Theoretical computer science : the journal of the EATCS N2 - While many optimization problems work with a fixed number of decision variables and thus a fixed-length representation of possible solutions, genetic programming (GP) works on variable-length representations. A naturally occurring problem is that of bloat, that is, the unnecessary growth of solution lengths, which may slow down the optimization process. So far, the mathematical runtime analysis could not deal well with bloat and required explicit assumptions limiting bloat. In this paper, we provide the first mathematical runtime analysis of a GP algorithm that does not require any assumptions on the bloat. Previous performance guarantees were only proven conditionally for runs in which no strong bloat occurs. Together with improved analyses for the case with bloat restrictions our results show that such assumptions on the bloat are not necessary and that the algorithm is efficient without explicit bloat control mechanism. More specifically, we analyzed the performance of the (1 + 1) GP on the two benchmark functions ORDER and MAJORITY. When using lexicographic parsimony pressure as bloat control, we show a tight runtime estimate of O(T-init + nlogn) iterations both for ORDER and MAJORITY. For the case without bloat control, the bounds O(T-init logT(i)(nit) + n(logn)(3)) and Omega(T-init + nlogn) (and Omega(T-init log T-init) for n = 1) hold for MAJORITY(1). KW - genetic programming KW - bloat control KW - theory KW - runtime analysis Y1 - 2020 U6 - https://doi.org/10.1016/j.tcs.2020.01.011 SN - 0304-3975 SN - 1879-2294 VL - 816 SP - 144 EP - 168 PB - Elsevier CY - Amsterdam [u.a.] ER - TY - JOUR A1 - Kötzing, Timo A1 - Lagodzinski, Gregor J. A. A1 - Lengler, Johannes A1 - Melnichenko, Anna T1 - Destructiveness of lexicographic parsimony pressure and alleviation by a concatenation crossover in genetic programming JF - Theoretical computer science N2 - For theoretical analyses there are two specifics distinguishing GP from many other areas of evolutionary computation: the variable size representations, in particular yielding a possible bloat (i.e. the growth of individuals with redundant parts); and also the role and the realization of crossover, which is particularly central in GP due to the tree-based representation. Whereas some theoretical work on GP has studied the effects of bloat, crossover had surprisingly little share in this work.
We analyze a simple crossover operator in combination with randomized local search, where a preference for small solutions minimizes bloat (lexicographic parsimony pressure); we denote the resulting algorithm Concatenation Crossover GP. We consider three variants of the well-studied MAJORITY test function, adding large plateaus in different ways to the fitness landscape and thus giving a test bed for analyzing the interplay of variation operators and bloat control mechanisms in a setting with local optima. We show that the Concatenation Crossover GP can efficiently optimize these test functions, while local search cannot be efficient for all three variants independent of employing bloat control. (C) 2019 Elsevier B.V. All rights reserved. KW - genetic programming KW - mutation KW - theory KW - run time analysis Y1 - 2020 U6 - https://doi.org/10.1016/j.tcs.2019.11.036 SN - 0304-3975 VL - 816 SP - 96 EP - 113 PB - Elsevier CY - Amsterdam ER - TY - THES A1 - Quade, Markus T1 - Symbolic regression for identification, prediction, and control of dynamical systems T1 - Symbolische Regression zur Identifikation, Vorhersage und Regelung dynamischer Systeme N2 - In the present work, we use symbolic regression for automated modeling of dynamical systems. Symbolic regression is a powerful and general method suitable for data-driven identification of mathematical expressions. In particular, the structure and parameters of those expressions are identified simultaneously. We consider two main variants of symbolic regression: sparse regression-based and genetic programming-based symbolic regression. Both are applied to identification, prediction and control of dynamical systems. We introduce a new methodology for the data-driven identification of nonlinear dynamics for systems undergoing abrupt changes. Building on a sparse regression algorithm derived earlier, the model after the change is defined as a minimum update with respect to a reference model of the system identified prior to the change. The technique is successfully exemplified on the chaotic Lorenz system and the van der Pol oscillator. Issues such as computational complexity, robustness against noise and requirements with respect to data volume are investigated. We show how symbolic regression can be used for time series prediction. Again, issues such as robustness against noise and convergence rate are investigated us- ing the harmonic oscillator as a toy problem. In combination with embedding, we demonstrate the prediction of a propagating front in coupled FitzHugh-Nagumo oscillators. Additionally, we show how we can enhance numerical weather predictions to commercially forecast power production of green energy power plants. We employ symbolic regression for synchronization control in coupled van der Pol oscillators. Different coupling topologies are investigated. We address issues such as plausibility and stability of the control laws found. The toolkit has been made open source and is used in turbulence control applications. Genetic programming based symbolic regression is very versatile and can be adapted to many optimization problems. The heuristic-based algorithm allows for cost efficient optimization of complex tasks. We emphasize the ability of symbolic regression to yield white-box models. In contrast to black-box models, such models are accessible and interpretable which allows the usage of established tool chains. N2 - In der vorliegenden Arbeit nutzen wird symbolische Regression zur automatisierten Modellierung dynamischer Systeme. Symbolische Regression ist eine mächtige und vielseitige Methode, welche zur Daten-getriebenen Identifikation von mathematischen Ausdrücken geeignet ist. Insbesondere werden dabei Struktur und Parameter des gesuchten Ausdrucks parallel ermittelt. Zwei Varianten der symbolischen Regression werden im Rahmen dieser Arbeit in Betracht gezogen: sparse regression und symbolischer Regression basierend auf genetischem Programmieren. Beide Verfahren werden für die Identifikation, Vor- hersage und Regelung dynamischer Systeme angewandt. Wir führen eine neue Methodik zur Identifikation von dynamischen Systemen, welche eine spontane Änderung erfahren, ein. Die Änderung eines Modells, wel- ches mit Hilfe von sparse regression gefunden wurde, ist definiert als sparsamste Aktualisierung im Hinblick auf das Modell vor der Änderung. Diese Technik ist beispielhaft am chaotischem Lorenz System und dem van der Pol Oszillator demonstriert. Aspekte wie numerische Komplexität, Robustheit gegenüber Rauschen sowie Anforderungen an Anzahl von Datenpunkten werden untersucht. Wir zeigen wie symbolische Regression zur Zeitreihenvorhersage genutzt wer- den kann. Wir nutzen dem harmonischen Oszillator als Beispielmodell, um Aspekte wie Robustheit gegenüber Rauschen sowie die Konvergenzrate der Optimierung zu untersuchen. Mit Hilfe von Einbettungsverfahren demonstrieren wir die Vorhersage propagierenden Fronten in gekoppelten FitzHugh-Nagumo Oszillatoren. Außerdem betrachten wir die kommerzielle Stromproduktionsvorhersage von erneuerbaren Energien. Wir zeigen wie man diesbezügliche die numerische Wettervorhersage mittels symbolischer Regression verfeinern und zur Stromproduktionsvorhersage anwenden kann. Wir setzen symbolische Regression zur Regelung von Synchronisation in gekoppelten van der Pol Oszillatoren ein. Dabei untersuchen wir verschiedene Topologien und Kopplungen. Wir betrachten Aspekte wie Plausibilität und Stabilität der gefundenen Regelungsgesetze. Die Software wurde veröffentlicht und wird u. a. zur Turbulenzregelung eingesetzt. Symbolische Regression basierend auf genetischem Programmieren ist sehr vielseitig und kann auf viele Optimierungsprobleme übertragen werden. Der auf Heuristik basierenden Algorithmus erlaubt die effiziente Optimierung von komplexen Fragestellungen. Wir betonen die Fähigkeit von symbolischer Regression, sogenannte white-box Modelle zu produzieren. Diese Modelle sind – im Gegensatz zu black-box Modellen – zugänglich und interpretierbar. Dies ermöglicht das weitere Nutzen von etablierten Methodiken. KW - dynamical systems KW - symbolic regression KW - genetic programming KW - identification KW - prediction KW - control KW - Dynamische Systeme KW - Symbolische Regression KW - Genetisches Programmieren KW - Identifikation KW - Vorhersage KW - Regelung Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-419790 ER -