TY - GEN
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
T2 - Parallel Problem Solving from Nature – PPSN XV
N2 - For theoretical analyses there are two specifics distinguishing GP from many other areas of evolutionary computation. First, the variable size representations, in particular yielding a possible bloat (i.e. the growth of individuals with redundant parts). Second, the role and 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 a surprisingly little share in this work. We analyze a simple crossover operator in combination with local search, where a preference for small solutions minimizes bloat (lexicographic parsimony pressure); the resulting algorithm is denoted Concatenation Crossover GP. For this purpose three variants of the wellstudied Majority test function with large plateaus are considered. 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.
Y1 - 2018
SN - 978-3-319-99259-4
SN - 978-3-319-99258-7
U6 - https://doi.org/10.1007/978-3-319-99259-4_4
SN - 0302-9743
SN - 1611-3349
VL - 11102
SP - 42
EP - 54
PB - Springer
CY - Cham
ER -
TY - GEN
A1 - Blaesius, Thomas
A1 - Eube, Jan
A1 - Feldtkeller, Thomas
A1 - Friedrich, Tobias
A1 - Krejca, Martin Stefan
A1 - Lagodzinski, Gregor J. A.
A1 - Rothenberger, Ralf
A1 - Severin, Julius
A1 - Sommer, Fabian
A1 - Trautmann, Justin
T1 - Memory-restricted Routing With Tiled Map Data
T2 - 2018 IEEE International Conference on Systems, Man, and Cybernetics (SMC)
N2 - Modern routing algorithms reduce query time by depending heavily on preprocessed data. The recently developed Navigation Data Standard (NDS) enforces a separation between algorithms and map data, rendering preprocessing inapplicable. Furthermore, map data is partitioned into tiles with respect to their geographic coordinates. With the limited memory found in portable devices, the number of tiles loaded becomes the major factor for run time. We study routing under these restrictions and present new algorithms as well as empirical evaluations. Our results show that, on average, the most efficient algorithm presented uses more than 20 times fewer tile loads than a normal A*.
Y1 - 2018
SN - 978-1-5386-6650-0
U6 - https://doi.org/10.1109/SMC.2018.00567
SN - 1062-922X
SP - 3347
EP - 3354
PB - IEEE
CY - New York
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 - JOUR
A1 - Casel, Katrin
A1 - Fischbeck, Philipp
A1 - Friedrich, Tobias
A1 - Göbel, Andreas
A1 - Lagodzinski, J. A. Gregor
T1 - Zeros and approximations of Holant polynomials on the complex plane
JF - Computational complexity : CC
N2 - We present fully polynomial time approximation schemes for a broad class of Holant problems with complex edge weights, which we call Holant polynomials. We transform these problems into partition functions of abstract combinatorial structures known as polymers in statistical physics. Our method involves establishing zero-free regions for the partition functions of polymer models and using the most significant terms of the cluster expansion to approximate them. Results of our technique include new approximation and sampling algorithms for a diverse class of Holant polynomials in the low-temperature regime (i.e. small external field) and approximation algorithms for general Holant problems with small signature weights. Additionally, we give randomised approximation and sampling algorithms with faster running times for more restrictive classes. Finally, we improve the known zero-free regions for a perfect matching polynomial.
KW - Holant problems
KW - approximate counting
KW - partition functions
KW - graph
KW - polynomials
Y1 - 2022
U6 - https://doi.org/10.1007/s00037-022-00226-5
SN - 1016-3328
SN - 1420-8954
VL - 31
IS - 2
PB - Springer
CY - Basel
ER -
TY - JOUR
A1 - Göbel, Andreas
A1 - Lagodzinski, Gregor J. A.
A1 - Seidel, Karen
T1 - Counting homomorphisms to trees modulo a prime
JF - ACM transactions on computation theory : TOCT / Association for Computing Machinery
N2 - Many important graph-theoretic notions can be encoded as counting graph homomorphism problems, such as partition functions in statistical physics, in particular independent sets and colourings. In this article, we study the complexity of #(p) HOMSTOH, the problem of counting graph homomorphisms from an input graph to a graph H modulo a prime number p. Dyer and Greenhill proved a dichotomy stating that the tractability of non-modular counting graph homomorphisms depends on the structure of the target graph. Many intractable cases in non-modular counting become tractable in modular counting due to the common phenomenon of cancellation. In subsequent studies on counting modulo 2, however, the influence of the structure of H on the tractability was shown to persist, which yields similar dichotomies.
Our main result states that for every tree H and every prime p the problem #pHOMSTOH is either polynomial time computable or #P-p-complete. This relates to the conjecture of Faben and Jerrum stating that this dichotomy holds for every graph H when counting modulo 2. In contrast to previous results on modular counting, the tractable cases of #pHOMSTOH are essentially the same for all values of the modulo when H is a tree. To prove this result, we study the structural properties of a homomorphism. As an important interim result, our study yields a dichotomy for the problem of counting weighted independent sets in a bipartite graph modulo some prime p. These results are the first suggesting that such dichotomies hold not only for the modulo 2 case but also for the modular counting functions of all primes p.
KW - Graph homomorphisms
KW - modular counting
KW - complexity dichotomy
Y1 - 2021
U6 - https://doi.org/10.1145/3460958
SN - 1942-3454
SN - 1942-3462
VL - 13
IS - 3
SP - 1
EP - 33
PB - Association for Computing Machinery
CY - New York
ER -
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 -