Author name cluster

Timo Kötzing

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

20 papers

2 author rows

TCS Journal 2020 Journal Article

Analysis of the (1 + 1) EA on subclasses of linear functions under uniform and linear constraints

Tobias Friedrich
Timo Kötzing
J.A. Gregor Lagodzinski
Frank Neumann
Martin Schirneck

Linear functions have gained great attention in the run time analysis of evolutionary computation methods. The corresponding investigations have provided many effective tools for analyzing more complex problems. So far, the runtime analysis of evolutionary algorithms has mainly focused on unconstrained problems, but problems occurring in applications frequently involve constraints. Therefore, there is a strong need to extend the current analyses and used methods for analyzing unconstrained problems to a setting involving constraints. In this paper, we consider the behavior of the classical ( 1 + 1 ) Evolutionary Algorithm on linear functions under linear constraint. We show tight bounds in the case where the constraint is given by the OneMax function and the objective function is given by either the OneMax or the BinVal function. For the general case we present upper and lower bounds.

TCS Journal 2020 Journal Article

Destructiveness of lexicographic parsimony pressure and alleviation by a concatenation crossover in genetic programming

Timo Kötzing
J.A. Gregor Lagodzinski
Johannes Lengler
Anna Melnichenko

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.

TCS Journal 2020 Journal Article

The impact of lexicographic parsimony pressure for ORDER/MAJORITY on the run time

Benjamin Doerr
Timo Kötzing
J.A. Gregor Lagodzinski
Johannes Lengler

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 + n log ⁡ n ) iterations both for Order and Majority. For the case without bloat control, the bounds O ( T init log ⁡ T init + n ( log ⁡ n ) 3 ) and Ω ( T init + n log ⁡ n ) (and Ω ( T init log ⁡ T init ) for n = 1 ) hold for Majority. 1

TCS Journal 2019 Journal Article

First-hitting times under drift

Timo Kötzing
Martin S. Krejca

For the last ten years, almost every theoretical result concerning the expected run time of a randomized search heuristic used drift theory, making it the arguably most important tool in this domain. Its success is due to its ease of use and its powerful result: drift theory allows the user to derive bounds on the expected first-hitting time of a random process by bounding expected local changes of the process – the drift. This is usually far easier than bounding the expected first-hitting time directly. Due to the widespread use of drift theory, it is of utmost importance to have the best drift theorems possible. We improve the fundamental additive, multiplicative, and variable drift theorems by stating them in a form as general as possible and providing examples of why the restrictions we keep are still necessary. Our additive drift theorem for upper bounds only requires the process to be lower-bounded, that is, we remove unnecessary restrictions like a finite, discrete, or bounded state space. As corollaries, the same is true for our upper bounds in the case of variable and multiplicative drift. By bounding the step size of the process, we derive new lower-bounding multiplicative and variable drift theorems. Last, we also state theorems that are applicable when the process has a drift of 0, by using a drift on the variance of the process.

ICAPS Conference 2019 Conference Paper

Mixed Integer Programming versus Evolutionary Computation for Optimizing a Hard Real-World Staff Assignment Problem

Jannik Peters 0001
Daniel Stephan
Isabel Amon
Hans Gawendowicz
Julius Lischeid
Lennart Salabarria
Jonas Umland
Felix Werner

Assigning staff to engagements according to hard constraints while optimizing several objectives is a task encountered by many companies on a regular basis. Simplified versions of such assignment problems are NP-hard. Despite this, a typical approach to solving them consists of formulating them as mixed integer programming (MIP) problems and using a stateof-the-art solver to get solutions that closely approximate the optimum. In this paper, we consider a complex real-world staff assignment problem encountered by the professional service company KPMG, with the goal of finding an algorithm that solves it faster and with a better solution than a commercial MIP solver. We follow the evolutionary algorithm (EA) metaheuristic and design a search heuristic which iteratively improves a solution using domain-specific mutation operators. Furthermore, we use a flow algorithm to optimally solve a subproblem, which tremendously reduces the search space for the EA. For our real-world instance of the assignment problem, given the same total time budget of 100 hours, a parallel EA approach finds a solution that is only 1. 7% away from an upper bound for the (unknown) optimum within under five hours, while the MIP solver Gurobi still has a gap of 10. 5%.

TCS Journal 2019 Journal Article

Unbiasedness of estimation-of-distribution algorithms

Tobias Friedrich
Timo Kötzing
Martin S. Krejca

In the context of black-box optimization, black-box complexity is used for understanding the inherent difficulty of a given optimization problem. Central to our understanding of nature-inspired search heuristics in this context is the notion of unbiasedness. Specialized black-box complexities have been developed in order to better understand the limitations of these heuristics – especially of (population-based) evolutionary algorithms (EAs). In contrast to this, we focus on a model for algorithms explicitly maintaining a probability distribution over the search space: so-called estimation-of-distribution algorithms (EDAs). We consider the recently introduced n-Bernoulli-λ-EDA framework, which subsumes, for example, the commonly known EDAs PBIL, UMDA, λ -MMAS IB, and cGA. We show that an n-Bernoulli-λ-EDA is unbiased if and only if its probability distribution satisfies a certain invariance property under isometric automorphisms of [ 0, 1 ] n. By restricting how an n-Bernoulli-λ-EDA can perform an update, in a way common to many examples, we derive conciser characterizations, which are easy to verify. We demonstrate this by showing that our examples above are all unbiased.

TCS Journal 2016 Journal Article

A map of update constraints in inductive inference

Timo Kötzing
Raphaela Palenta

We investigate how different learning restrictions reduce learning power and how the different restrictions relate to one another. We give a complete map for nine different restrictions both for the cases of complete information learning and set-driven learning. This completes the picture for these well-studied delayable learning restrictions. A further insight is gained by different characterizations of conservative learning in terms of variants of cautious learning. Our analyses greatly benefit from general theorems we give, for example showing that learners which have to obey only delayable restrictions can always be assumed total.

I&C Journal 2016 Journal Article

Enlarging learnable classes

Sanjay Jain
Timo Kötzing
Frank Stephan

We study which classes of recursive functions satisfy that their union with any other explanatorily learnable class of recursive functions is again explanatorily learnable. We provide sufficient criteria for classes of recursive functions to satisfy this property and also investigate its effective variants. Furthermore, we study the question which learners can be effectively extended to learn a larger class of functions. We solve an open problem by showing that there is no effective procedure which does this task on all learners which do not learn a dense class of recursive functions. However, we show that there are two effective extension procedures such that each learner is extended by one of them.

I&C Journal 2016 Journal Article

On the role of update constraints and text-types in iterative learning

Sanjay Jain
Timo Kötzing
Junqi Ma
Frank Stephan

The present work investigates the relationship of iterative learning with other learning criteria such as decisiveness, caution, reliability, non-U-shapedness, monotonicity, strong monotonicity and conservativeness. Building on the result of Case and Moelius that iterative learners can be made non-U-shaped, we show that they also can be made cautious and decisive. Furthermore, we obtain various special results with respect to one-one texts, fat texts and one-one hypothesis spaces.

I&C Journal 2016 Journal Article

Strongly non-U-shaped language learning results by general techniques

John Case
Timo Kötzing

In learning, a semantic or behavioral U-shape occurs when a learner first learns, then unlearns, and, finally, relearns, some target concept. This paper introduces two general techniques and applies them especially to syntactic U-shapes in learning: one technique to show when they are necessary and one to show when they are unnecessary. The technique for the former is very general and applicable to a much wider range of learning criteria. It employs so-called self-learning classes of languages which are shown to characterize completely one criterion learning more than another. We apply these techniques to show that, for set-driven and rearrangement-independent learning, any kind of U-shapes is unnecessary. Furthermore, we show that U-shapes are necessary in a strong way for iterative learning, contrasting with an earlier result by Case and Moelius that semantic U-shapes are unnecessary for iterative learning.

TCS Journal 2016 Journal Article

Topological separations in inductive inference

John Case
Timo Kötzing

Re learning in the limit from positive data, a major concern is which classes of languages are learnable with respect to a given learning criterion. We are particularly interested herein in the reasons for a class of languages to be unlearnable. We consider two types of reasons. One type is called topological where it does not help if the learners are allowed to be uncomputable (an example of Gold's is that no class containing an infinite language and all its finite sub-languages is learnable — even by an uncomputable learner). Another reason is called computational (where the learners are required to be algorithmic). In particular, two learning criteria might allow for learning different classes of languages from one another — but with dependence on whether the unlearnability is of type topological or computational. In this paper we formalize the idea of two learning criteria separating topologically in learning power. This allows us to study more closely why two learning criteria separate in learning power. For a variety of learning criteria, concerning vacillatory, monotone, (several kinds of) iterative and feedback learning, we show that certain learning criteria separate topologically, and certain others, which are known to separate, are shown not to separate topologically. Showing that learning criteria do not separate topologically implies that any known separation must necessarily exploit algorithmicity of the learner.

TCS Journal 2014 Journal Article

Iterative learning from positive data and counters

Timo Kötzing

We analyze iterative learning in the limit from positive data with the additional information provided by a counter. The simplest type of counter provides the current iteration number (counting up from 0 to infinity), which is known to improve learning power over plain iterative learning. We introduce five other (weaker) counter types, for example only providing some unbounded and non-decreasing sequence of numbers. Analyzing these types allows one to understand which properties of a counter learning can benefit from. For the iterative setting, we completely characterize the relative power of the learning criteria corresponding to the counter types. In particular, for our types, the only properties improving learning power are unboundedness and strict monotonicity. Furthermore, we show that each of our types of counter improves learning power over weaker ones in some settings; to this end, we analyze transductive and non-U-shaped learning. Finally we show that, for iterative learning criteria with one of our types of counter, separations of learning criteria are necessarily witnessed by classes containing only infinite languages.

TCS Journal 2014 Journal Article

The Max problem revisited: The importance of mutation in genetic programming

Timo Kötzing
Andrew M. Sutton
Frank Neumann
Una-May O'Reilly

We study the importance of mutation in genetic programming and contribute to the rigorous understanding of genetic programming algorithms by providing runtime complexity analyses for the well-known Max problem. Several experimental studies have indicated that it is hard to solve the Max problem with crossover-based algorithms. Our analyses show that different variants of the Max problem can provably be solved efficiently using simple mutation-based genetic programming algorithms. Our results advance the body of computational complexity analyses of genetic programming, indicate the importance of mutation in genetic programming, and reveal new insights into the behavior of mutation-based genetic programming algorithms.

AIJ Journal 2014 Journal Article

The unbiased black-box complexity of partition is polynomial

Benjamin Doerr
Carola Doerr
Timo Kötzing

Unbiased black-box complexity was introduced as a refined complexity model for random-ized search heuristics (Lehre and Witt (2012) [24]). For several problems, this notion avoids the unrealistically low complexity results given by the classical model of Droste et al. (2006) [10]. We show that for some problems the unbiased black-box complexity remains artificially small. More precisely, for two different formulations of an NP -hard subclass of the well-known Partition problem, we give mutation-only unbiased black-box algorithms having complexity O ( n log ⁡ n ). This indicates that also the unary unbiased black-box complexity does not give a complete picture of the true difficulty of this problem for randomized search heuristics.

TCS Journal 2013 Journal Article

Black-box complexities of combinatorial problems

Benjamin Doerr
Timo Kötzing
Johannes Lengler
Carola Winzen

Black-box complexity, counting the number of queries needed to find the optimum of a problem without having access to an explicit problem description, was introduced by Droste, Jansen, and Wegener [S. Droste, T. Jansen, I. Wegener, Upper and lower bounds for randomized search heuristics in black-box optimization, Theory of Computing Systems 39 (2006) 525–544] to measure the difficulty of solving an optimization problem via generic search heuristics such as evolutionary algorithms, simulated annealing or ant colony optimization. Since then, a number of similar complexity notions were introduced. However, so far these new notions were only analyzed for artificial test problems. In this paper, we move a step forward and analyze the different black-box complexity notions for two classic combinatorial problems, namely the minimum spanning tree and the single-source shortest path problem. Besides proving bounds for their black-box complexities, our work reveals that the choice of how to model the optimization problem has a significant influence on its black-box complexity. In addition, when regarding the unbiased (symmetry-invariant) black-box complexity of combinatorial problems, it is important to choose a meaningful definition of unbiasedness.

Highlights Conference 2013 Conference Abstract

Fast learning of restricted regular expressions and DTDs

Dominik D. Freydenberger
Timo Kötzing

We study the problem of generalizing from a finite sample to a language taken from a predefined language class. The two language classes we consider are generated by restricted regular expressions (CHAREs and SOREs) that have significance in the specification of XML documents. For each of the two language classes we give an efficient algorithm returning a minimal generalization from the given finite sample to an element of the fixed language class; such generalizations are called descriptive. In this sense, both our algorithms are optimal.

TCS Journal 2013 Journal Article

Memory-limited non-U-shaped learning with solved open problems

John Case
Timo Kötzing

In empirical cognitive science, for human learning, a semantic or behavioral U-shape occurs when a learner first learns, then unlearns, and, finally, relearns, some target concept. Within the formal framework of Inductive Inference, for learning from positive data, previous results have shown, for example, that such U-shapes are unnecessary for explanatory learning, but are necessary for behaviorally correct and non-trivial vacillatory learning. Herein we also distinguish between semantic and syntactic U-shapes. We answer a number of open questions in the prior literature as well as provide new results regarding syntactic U-shapes. Importantly for cognitive science, we see more of a previously noticed pattern that, for parameterized learning criteria, beyond very few initial parameter values, U-shapes are necessary for full learning power. We analyze the necessity of U-shapes in two memory-limited settings. The first setting is Bounded Memory State (BMS) learning, where a learner has an explicitly-bounded state memory, and otherwise only knows its current datum. We show that there are classes learnable with three (or more) memory states that are not learnable non-U-shapedly with any finite number of memory states. This result is surprising, since, for learning with one or two memory states, U-shapes are known to be unnecessary. This solves an open question from the literature. The second setting is that of Memoryless Feedback (MLF) learning, where a learner may ask a bounded number of questions about what data has been seen so far, and otherwise only knows its current datum. We show that there is a class learnable memorylessly with a single feedback query such that this class is not learnable non-U-shapedly memorylessly with any finite number of feedback queries. We employ self-learning classes together with the Operator Recursion Theorem for many of our results, but we also introduce two new techniques for obtaining results. The first is for transferring inclusion results from one setting to another. The main part of the second is the Hybrid Operator Recursion Theorem, which enables us to separate some learning criteria featuring complexity-bounded learners, employing self-learning classes. Both techniques are not specific to U-shaped learning, but applicable for a wide range of settings.

TCS Journal 2013 Journal Article

More effective crossover operators for the all-pairs shortest path problem

Benjamin Doerr
Daniel Johannsen
Timo Kötzing
Frank Neumann
Madeleine Theile

The all-pairs shortest path problem is the first non-artificial problem for which it was shown that adding crossover can significantly speed up a mutation-only evolutionary algorithm. Recently, the analysis of this algorithm was refined and it was shown to have an expected optimization time (w. r. t. the number of fitness evaluations) of Θ ( n 3. 25 ( log n ) 0. 25 ). In contrast to this simple algorithm, evolutionary algorithms used in practice usually employ refined recombination strategies in order to avoid the creation of infeasible offspring. We study extensions of the basic algorithm by two such concepts which are central in recombination, namely repair mechanisms and parent selection. We show that repairing infeasible offspring leads to an improved expected optimization time of O ( n 3. 2 ( log n ) 0. 2 ). As a second part of our study we prove that choosing parents that guarantee feasible offspring results in an optimization time of O ( n 3 log n ). Both results show that already simple adjustments of the recombination operator can asymptotically improve the runtime of evolutionary algorithms.

TCS Journal 2012 Journal Article

Learning in the limit with lattice-structured hypothesis spaces

Jeffrey Heinz
Anna Kasprzik
Timo Kötzing

We define a collection of language classes which are TxtEx-learnable (learnable in the limit from positive data). The learners map any data input to an element of a fixed lattice, and keep the least upper bound of all lattice elements thus obtained as the current hypothesis. Each element of the lattice is a grammar for a language, and the learner climbs the lattice searching for the right element. We call these classes in our collection lattice classes. We provide several characterizations of lattice classes and their learners, which suggests they are very natural. In particular, we show that any class of languages is a lattice class iff it is TxtEx-learnable consistently, conservatively, set-drivenly, and strongly monotonically. We show several language classes previously discussed in the literature to be lattice classes, including the locally k -testable classes, the piecewise k -testable classes, the k -reversible languages and the pattern languages. We also show that lattice classes contain three previously known collections of language classes: string extension language classes, function-distinguishable language classes, and closed-set systems. Finally, the lattice perspective helps analyze the learning of these classes. Illustrations include query-learning results in dependence on the lattice structure, characterizations of closure properties and the VC-dimension of lattice classes in terms of lattice properties.

I&C Journal 2012 Journal Article

Learning secrets interactively. Dynamic modeling in inductive inference

John Case
Timo Kötzing

Introduced is a new inductive inference paradigm, dynamic modeling. Within this learning paradigm, for example, function h learns function g iff, in the i-th iteration, h and g both produce output, h gets the sequence of all outputs from g in prior iterations as input, g gets all the outputs from h in prior iterations as input, and, from some iteration on, the sequence of hʼs outputs will be programs for the output sequence of g. Dynamic modeling provides an idealization of, for example, a social interaction in which h seeks to discover program models of gʼs behavior it sees in interacting with g, and h openly discloses to g its sequence of candidate program models to see what g says back. Sample results: every g can be so learned by some h; there are g that can only be learned by an h if g can also learn that h back; there are extremely secretive h which cannot be learned back by any g they learn, but which, nonetheless, succeed in learning infinitely many g; quadratic time learnability is strictly more powerful than linear time learnability. This latter result, as well as others, follows immediately from general correspondence theorems obtained from a unified approach to the paradigms within inductive inference. Many proofs, some sophisticated, employ machine self-reference, a. k. a. , recursion theorems.