The Ising Model: Simple Evolutionary Algorithms as Adaptation Schemes (2008)
Patrick Briest, Dimo Brockhoff, Bastian Degener, Matthias Englert, Christian Gunia, Oliver Heering, ...
Abstract. The investigation of evolutionary algorithms as adaptation schemes has a long history starting with Holland (1975). The Ising model from physics leads to a variety of different problem...
(Universität Dortmund, Deutschland) (2008)
Andrea Schweer, Prof Dr, Ingo Wegener, Dr. Annika Hinze
ii
Tight bounds for blind search on the integers (2008)
Dietzfelbinger, Martin, Rowe, Jonathan E., Wegener, Ingo, Woelfel, Philipp
We analyze a simple random process in which a token is moved in the interval $A={0,dots,n$: Fix a probability distribution $mu$ over ${1,dots,n$. Initially, the token is placed in a random position...
It is well known that the hardest bit of integer multiplication is the middle bit, i.e. MULn−1,n. This paper contains several new results on its complexity. First, the size s of randomized read-k...
Mohamed Hussein, Dekan Prof, Dr. Bernhard Steffen, Gutachter Prof, ...
In the classical scheduling problems, it has been assumed that complete knowledge of the problem was available when it was to be solved. However, scheduling problems in the real world face the...
Teaching Nondeterminism as a Special Case of Randomization (2008)
Nondeterminism is a central concept in computer science. Every student of computer science is faced with this concept, since it is the basis of the ¢¡-completeness theory and is applied in automata...
Robin Nunkesser, Thorsten Bernholt, Holger Schwender, Katja Ickstadt, Ingo Wegener
Motivation: Not individual single nucleotide polymorphisms (SNPs), but high-order interactions of SNPs are assumed to be responsible for complex diseases such as can-cer. Therefore, one of the major...
Binary Decision Diagrams (2008)
Beate Bollig, Martin Sauerhoff, Detlef Sieling, Ingo Wegener
Decision diagrams are a natural representation of finite functions. The obvious complexity measures are length and size which correspond to time and space of computations. Decision diagrams are the...
Many people working with computers know much about the software. However, their knowledge on the basic hardware components is restricted. Most people are convinced that computers do arithmetics as...
How to analyze evolutionary algorithms (2008)
Hans-Georg Beyer, Ingo Wegener, Hans-Paul Schwefel
Many variants of evolutionary algorithms have been designed and applied. The experimental knowledge is immense. The rigorous analysis of evolutionary algorithms is difficult, but such a theory can...
Tight Bounds for Blind Search on the Integers (2008)
Dietzfelbinger, Martin, Rowe, Jonathan E., Wegener, Ingo, Woelfel, Philipp
We analyze a simple random process in which a token is moved in the interval $A=\{0,...,n\$: Fix a probability distribution $\mu$ over $\{1,...,n\$. Initially, the token is placed in a random...
Combinational circuits or shortly circuits are a model of the lowest level of computer hardware which is of interest from the point of view of computer science. Circuit complexity has a longer...
Printed and bound in Great Britain (2008)
Ingo Wegener, Wegener Ingo, Wegener Ingo, Ii. Teubner, Wegener Ingo
This version of the book is for your personal use only. The material is copyrighted and may not be redistributed.
Abstract The One-Dimensional Ising Model: Mutation versus Recombination (2008)
The investigation of genetic and evolutionary algorithms on Ising model problems gives much insight into how these algorithms work as adaptation schemes. The onedimensional Ising model with periodic...
Printed and bound in Great Britain (2008)
Ingo Wegener, Wegener Ingo, Wegener Ingo, Ii. Teubner, Wegener Ingo
This version of the book is for your personal use only. The material is copyrighted and may not be redistributed.
Combinational circuits or shortly circuits are a model of the lowest level of computer hardware which is of interest from the point of view of computer science. Circuit complexity has a longer...
Tight bounds for blind search on the integers (2008)
Dietzfelbinger, Martin, Rowe, Jonathan E., Wegener, Ingo, Woelfel, Philipp
We analyze a simple random process in which a token is moved in the interval A = [0,n]: Fix a probability distribution µ over [1,n]. Initially, the token is placed in a random position in A. In...
Tight Bounds for Blind Search on the Integers (2008)
Dietzfelbinger, Martin, Rowe, Jonathan, Wegener, Ingo, Woelfel, Philipp
We analyze a simple random process in which a token is moved in the interval $A=\{0,\dots,n\$: Fix a probability distribution $\mu$ over $\{1,\dots,n\$. Initially, the token is placed in a random...
Tight Bounds for Blind Search on the Integers (2008)
Dietzfelbinger, Martin, Rowe, Jonathan, Wegener, Ingo, Woelfel, Philipp
We analyze a simple random process in which a token is moved in the interval $A=\{0,\dots,n\$: Fix a probability distribution $\mu$ over $\{1,\dots,n\$. Initially, the token is placed in a random...
Genetic and Evolutionary Computation Conference 2008 : GECCO 2008 (2008)
Keijzer, Maarten, Antoniol., Giuliano, Congdon, Clare Bates, Deb, Kalyanmoy, Doerr, Benjamin, Hansen, Nikolaus, ...
22. Tight Bounds for Blind Search on the Integers (2008)
Dietzfelbinger, Martin, Rowe, Jonathan E., Wegener, Ingo, Woelfel, Philipp
We analyze a simple random process in which a token is moved in the interval $A={0,dots,n$: Fix a probability distribution $mu$ over ${1,dots,n$. Initially, the token is placed in a random position...
Un I Vers I Ty Of Dortmund (2007)
Re He Computat, Re I He, Computat I Onal, I Ntell, I Gence, Stefan Droste, ...
Many experimental results are reported on all types of Evolutionary Algorithms but only few results have been proved. A step towards a theory on Evolutionary Algorithms, in particular, the so-called...
Approximability and Non-Approximability by Binary Decision Diagrams (Extended Abstract) (2007)
Beate Bollig, Martin Sauerhoff, Ingo Wegener
The usual applications of BDDs (binary decision diagrams), e. g., in verification and for CAD problems, require an exact representation of the considered boolean functions. However, if BDDs are used...
Optimal Depth, Very Small Size Circuits For Symmetric Functions In AC^0 (2007)
Johan Hastad, Ingo Wegener, Norbert Wurm, Sang-Zin Yi
It is well-known which symmetric Boolean functions can be computed by constant depth, polynomial size, unbounded fan-in circuits, i.e. which are contained in the complexity class AC 0 . This result...
The Analysis of a Recombinative Hill-Climber on (2007)
Re I He, Computat I Onal, I Ntell, I Gence, Clarissa Van Hoyweghen, Ingo Wegener, ...
Abstract--- Many experiments have proved that crossover is an essential search operator in evolutionary algorithms, at least for certain functions. However, the rigorous analysis of such algorithms...
Evolutionary Algorithms and the Maximum Matching Problem (2007)
Re I He, Computat I Onal, I Ntell, I Gence, Ingo Wegener, Oliver Giel, ...
Abstract. Randomized search heuristics like evolutionary algorithms are mostly applied to problems whose structure is not completely known but also to combinatorial optimization problems....
Fitness Landscapes Based on Sorting and Shortest Paths Problems (2007)
Reihe Computational Intelligence, Ingo Wegener, Jens Scharnow, Jens Scharnow, Karsten Tinnefeld, Karsten Tinnefeld
This work is a product of the Collaborative Research Center 531, "Computational
How to analyse evolutionary algorithms (2007)
Re I He, Computat I Onal, I Ntell, I Gence, Hans-georg Beyer, Hans-paul Schwefel, ...
a,1
by Simple Randomized Search Heuristics (2007)
Re I He, Computat I Onal, I Ntell, I Gence, Ingo Wegener, Ingo Wegener, ...
This work is a product of the Collaborative Research Center 531, "Computational
A New Framework for the Valuation of Algorithms for Black-Box Optimization (2007)
Re I He, Computat I Onal, I Ntell, I Gence, For Black-box-optimization, Thomas Jansen, ...
Black-box optimization algorithms cannot use the specific parameters of the problem instance, i.e., of the fitness function f. Their run time is measured as the number of f-evaluations. This implies...
On the Performance of WEAK-HEAPSORT 1 (2007)
Abstract. Dutton �1993 � presents a further HEAPSORT variant called WEAK-HEAPSORT, which also contains a new data structure for priority queues. The sorting algorithm and the underlying data...
THEORETICAL ASPECTS OF EVOLUTIONARY ALGORITHMS (2007)
Re I He, Computat I Onal, I Ntell, I Gence, Ingo Wegener, Ingo Wegener
Abstract. Randomized search heuristics like simulated annealing and evolutionary algorithms are applied successfully in many di#erent situations. However, the theory on these algorithms is still in...
Secretary of the SFB 531 (2007)
Re I He, Computat I Onal, I Ntell, I Gence, Thomas Jansen, Thomas Jansen, ...
The most simple evolutionary algorithm, the so-called (1+1)EA accepts a child if its fitness is at least as large (in the case of maximization) as the fitness of its parent. The variant (1 + 1) # EA...
Re I He, Computat I Onal, I Ntell, I Gence, Stefan Droste, Thomas Jansen, ...
Evolutionary algorithms (EAs) are randomized search strategies which have turned out to be e#cient for optimization problems of quite di#erent kind. In order to understand the behavior of EAs, one...
On the design and analysis of evolutionary algorithms # (2007)
Re I He, Computat I Onal, I Ntell, I Gence, Ingo Wegener, Ingo Wegener
Abstract: Evolutionary algorithms are problem-independent randomized search heuristics. It is discussed when it is useful to work with such algorithms and it is argued why these search heuristics...
Dynamic Parameter Control in Simple Evolutionary Algorithms (2007)
Re I He, Computat I Onal, I Ntell, I Gence, Stefan Droste, Thomas Jansen, ...
Evolutionary algorithms are general, randomized search heuristics that are influenced by many parameters. Though evolutionary algorithms are assumed to be robust, it is well-known that choosing the...
Real Royal Road Functions--- Where Crossover Provably is Essential # (2007)
Re I He, Computat I Onal, I Ntell, I Gence, Ingo Wegener, Ingo Wegener
Mutation and crossover are the main search operators of di#erent variants of evolutionary algorithms. Despite the many discussions on the importance of crossover nobody has proved rigorously for some...
Algorithm on Quadratic Pseudo-Boolean Functions # (2007)
Re I He, Computat I Onal, I Ntell, I Gence, Ingo Wegener, Ingo Wegener, ...
This work is a product of the Collaborative Research Center 531, "Computational
Distributed Hybrid Genetic Programming for Learning Boolean Functions (2007)
Re I He, Computat I Onal, I Ntell, I Gence, Dominic Heutelbeck, Ingo Wegener, ...
This work is a product of the Collaborative Research Center 531, "Computational
PSEUDO-BOOLEAN FUNCTIONS (2007)
Re I He, Computat I Onal, I Ntell, I Gence, Ingo Wegener, Ingo Wegener
This work is a product of the Collaborative Research Center 531, "Computational
Secretary of the SFB 531 (2007)
Re I He, Computat I Onal, I Ntell, I Gence, Thomas Jansen, Thomas Jansen, ...
This work is a product of the Collaborative Research Center 531, "Computational
ON THE EXPECTED RUNTIME AND THE SUCCESS PROBABILITY OF EVOLUTIONARY ALGORITHMS (2007)
Re I He, Computat I Onal, I Ntell, I Gence, Ingo Wegener, Ingo Wegener
This work is a product of the Collaborative Research Center 531, "Computational
Re I He, Computat I Onal, I Ntell, I Gence, Stefan Droste, Thomas Jansen, ...
This work is a product of the Collaborative Research Center 531, "Computational
PERHAPS NOT A FREE LUNCH BUT AT LEAST (2007)
Re I He, Computat I Onal, I Ntell, I Gence, A Free Appetizer, Stefan Droste, ...
It is often claimed that Evolutionary Algorithms are superior to other optimization techniques, in particular, in situations where not much is known about the objective function to be optimized. In...
Beate Bollig, Martin Sauerhoff, Ingo Wegener
Branching programs are considered as a nonuniform model of computation in complexity theory as well as a data structure for boolean functions in several applications. In many applications (e. g.,...
Many people working with computers know much about the software. However, their knowledge on the basic hardware components is restricted. Most people are convinced that computers do arithmetics as...
Teaching Nondeterminism as a Special Case of Randomization (2007)
Nondeterminism is a central concept in computer science. Every student of computer science is faced with this concept, since it is the basis of the NP-completeness theory and is applied in automata...
Binary Decision Diagrams (2007)
Beate Bollig, Martin Sauerhoff, Detlef Sieling, Ingo Wegener
Decision diagrams are a natural representation of finite functions. The obvious complexity measures are length and size which correspond to time and space of computations. Decision diagrams are the...
Evolutionary Algorithms, Randomized Local Search, and the Maximum Matching Problem ∗ (2007)
The design and analysis of problem-specific algorithms for combinatorial optimization problems is a well-studied subject. It is accepted that randomization is a powerful concept for theoretically and...
Nunkesser, Robin, Bernholt, Thorsten, Schwender, Holger, Ickstadt, Katja, Wegener, Ingo
Motivation: Not individual single nucleotide polymorphisms (SNPs), but high-order interactions of SNPs are assumed to be responsible for complex diseases such as can- cer. Therefore, one of the major...
Nunkesser, Robin, Bernholt, Thorsten, Schwender, Holger, Ickstadt, Katja, Wegener, Ingo
Motivation: Not individual single nucleotide polymorphisms (SNPs), but high-order interactions of SNPs are assumed to be responsible for complex diseases such as cancer. Therefore, one of the major...
Minimum spanning trees made easier via multi-objective optimization (2006)
Frank Neumann, Frank Neumann, Ingo Wegener, Ingo Wegener
the Deutsche Forschungsgemeinschaft.
Reliable and Efficient Computational Geometry Via Controlled Perturbation (2006)
Mehlhorn, Kurt, Osbild, Ralf, Sagraloff, Michael, Bugliesi, Michele, Preneel, Bart, Sassone, Vladimir, ...
Most algorithms of computational geometry are designed for the Real-RAM and non-degenerate input. We call such algorithms idealistic. Executing an idealistic algorithm with floating point arithmetic...
A Faster Deterministic Algorithm for Minimum Cycle Bases in Directed Graphs (2006)
Hariharan, Ramesh, Telikepalli, Kavitha, Mehlhorn, Kurt, Bugliesi, Michele, Preneel, Bart, Sassone, Vladimir, ...
We consider the problem of computing a minimum cycle basis in a directed graph. The input to this problem is a directed graph G whose edges have non-negative weights. A cycle in this graph is...
The One-Dimensional Ising Model: Mutation versus Recombination (2005)
The investigation of genetic and evolutionary algorithms on Ising model problems gives much insight into how these algorithms work as adaptation schemes. The onedimensional Ising model with periodic...
Searching randomly for maximum matchings (2005)
Oliver Giel, Oliver Giel, Ingo Wegener, Ingo Wegener
Abstract. Many real-world optimization problems in, e. g., engineering or biology have the property that not much is known about the function to be optimized. This excludes the application of...
The Ising model on the ring: Mutation versus recombination (2004)
Simon Fischer, Simon Fischer, Ingo Wegener, Ingo Wegener
the Deutsche Forschungsgemeinschaft.
Randomized search heuristics as an alternative to exact optimization (2004)
Abstract. There are many alternatives to handle discrete optimization problems in applications. Problem-specific algorithms vs. heuristics, exact optimization vs. approximation vs. heuristic...
Randomized local search, evolutionary algorithms, and the minimum spanning tree problem (2004)
Frank Neumann, Frank Neumann, Ingo Wegener, Ingo Wegener
the Deutsche Forschungsgemeinschaft.
Patrick Briest, Dimo Brockhoff, Bastian Degener, Matthias Englert, Christian Gunia, Oliver Heering, ...
Abstract. It is typical for the EA community that theory follows experiments. Most theoretical approaches use some model of the considered evolutionary algorithm (EA) but there is also some progress...
Bdds – design, analysis, complexity, and applications (2004)
BDDs (binary decision diagrams) and their variants are the most frequently used representation types or data structures for boolean functions. Research on BDD variants has turned out to be one of the...
Modified Repeated Median Filters (2004)
Bernholt, Thorsten, Fried, Roland, Gather, Ursula, Wegener, Ingo
Briest, Patrick, Brockhoff, Dimo, Degener, Bastian, Englert, Matthias, Gunia, Christian, Heering, Oliver, ...
The Ising Model: Simple Evolutionary Algorithms as Adaptation Schemes (2004)
Briest, Patrick, Brockhoff, Dimo, Degener, Bastian, Englert, Matthias, Gunia, Christian, Heering, Oliver, ...
Advances in Computational Intelligence : Theory and Practice (2003)
Schwefel, Hans-Paul (ed.), Wegener, Ingo (ed.), Weinert, Klaus (ed.)
Compilación de artículos escritos después de 1997 centrados en los resultados de la investigación sobre inteligencia computacional, en particular sobre las técnicas de la inteligencia...
Advances in Computational Intelligence : Theory and Practice (2003)
Schwefel, Hans-Paul (ed.), Wegener, Ingo (ed.), Weinert, Klaus (ed.)
3-540-43269-8
Upper and lower bounds for randomized search heuristics in black-box optimization (2003)
Stefan Droste, Stefan Droste, Thomas Jansen, Thomas Jansen, Ingo Wegener, Ingo Wegener
Randomized search heuristics like local search, tabu search, simulated annealing or all kinds of evolutionary algorithms have many applications. However, for most problems the best worst-case...
Real royal road functions for constant population size (2003)
Tobias Storch, Tobias Storch, Ingo Wegener, Ingo Wegener
Abstract. Evolutionary and genetic algorithms (EAs and GAs) are quite successful randomized function optimizers. This success is mainly based on the interaction of different operators like selection,...
Towards a theory of randomized search heuristics (2003)
Abstract. There is a well-developed theory about the algorithmic complexity of optimization problems. Complexity theory provides negative results which typically are based on assumptions like NP�=P...
On converting CNF to DNF (2003)
Peter Bro Miltersen, Jaikumar Radhakrishnan, Ingo Wegener
Abstract. We study how big the blow-up in size can be when one switches between the CNF and DNF representations of boolean functions. For a function f: {0, 1} n → {0, 1}, cnfsize(f) denotes the...
Towards a Theory of Randomized Search Heuristics (2003)
There is a well-developed theory about the algorithmic complexity of optimization problems. Complexity theory provides negative results which typically are based on assumptions like NP#=P or NP#=RP.
Randomized search heuristics like evolutionary algorithms and simulated annealing find many applications, especially in situations where no full information on the problem instance is available. In...
On the Optimization of Monotone Polynomials (2003)
Simple Randomized Search, Ingo Wegener, Carsten Witt
Randomized search heuristics like evolutionary algorithms and simulated annealing find many applications, especially in situations where no full information on the problem instance is available. In...
Methods for the analysis of evolutionary algorithms on pseudo-boolean functions (2002)
Abstract Many experiments have shown that evolutionary algorithms are useful randomized search heuristics for optimization problems. In order to learn more about the reasons for their e#ciency and in...
On the analysis of a simple evolutionary algorithm on quadratic pseudo-boolean functions (2002)
Evolutionary algorithms are randomized search heuristics, which are often used as function optimizers. In this paper the well-known (1+1) Evolutionary Algorithm ((1+1) EA) and its multistart variants...
Evolutionary algorithms are randomized search heuristics, which are often used as function optimizers. In this paper the well-known (1+1) Evolutionary Algorithm ((1+1) EA) and its multistart variants...
On the analysis of the (1+1) evolutionary algorithm (2002)
Stefan Droste, Thomas Jansen, Ingo Wegener
Many experimental results are reported on all types of Evolutionary Algorithms but only few results have been proved. A step towards a theory on Evolutionary Algorithms, in particular, the so-called...
Fitness Landscapes Based on Sorting and Shortest Path Problems (2002)
Scharnow, Jens, Tinnefeld, Karsten, Wegener, Ingo
The analysis of evolutionary algorithms is up to now limited to special classes of functions and fitness landscapes. It is not possible to describe those subproblems of NP-hard optimization problems...
On the Optimization of Monotone Polynomials by Simple Randomized Search Heuristics (2002)
Randomized search heuristics like evolutionary algorithms and simulated annealing find many applications, especially in situations where no full information on the problem instance is available. In...
Evolutionary Algorithms and the Maximum Matching Problem (2002)
Randomized search heuristics like evolutionary algorithms are mostly applied to problems whose structure is not completely known but also to combinatorial optimization problems. Practitioners report...
The analysis of a recombinative hill climber on HIFF (2002)
Dietzfelbinger, Martin, Hoyweghen, Clarissa Van, Naudts, Bart, Wegener, Ingo
Real royal road functions – where crossover provably is essential (2001)
Mutation and crossover are the main search operators of different variants of evolutionary algorithms. Despite the many discussions on the importance of crossover nobody has proved rigorously for...
On the analysis of a dynamic evolutionary algorithm (2001)
Evolutionary algorithms are applied as problem-independent optimization algorithms. They are quite efficient in many situations. However, it is difficult to analyze even the behavior of simple...
On the Utility of Populations in Evolutionary Algorithms (2001)
Evolutionary algorithms (EAs) are population-based search heuristics often used for function optimization. Typically they employ selection, crossover, and mutation as search operators. It is known...
A comparison of free BDDs and transformed BDDs (2001)
Ordered binary decision diagrams (OBDDs) introduced by Bryant (1986) have found a lot of applications in verification and CAD. Their use is limited if the OBDD size of the considered functions is too...
A Comparison Of Free BDDs And Transformed BDDs (2001)
Ordered binary decision diagrams (OBDDs) introduced by Bryant (1986) have found a lot of applications in verification and CAD. Their use is limited if the OBDD size of the considered functions is too...
A Comparison Of Free BDDs And Transformed BDDs (2001)
Ordered binary decision diagrams (OBDDs) introduced by Bryant (1986) have found a lot of applications in verification and CAD. Their use is limited if the OBDD size of the considered functions is too...
Theoretical aspects of evolutionary algorithms (2001)
Abstract. Randomized search heuristics like simulated annealing and evolutionary algorithms are applied successfully in many different situations. However, the theory on these algorithms is still in...
Real Royal Road Functions - Where Crossover Provably is Essential (2001)
Mutation and crossov r are th main s arch op rators of different variants of evolutionary algorithms. Despite the many discussions on the importance of crossover nobody has proved rigorously for some...
Theoretical Aspects of Evolutionary Algorithms (2001)
Randomized search heuristics like simulated annealing and evolutionary algorithms are applied successfully in many different situations. However, the theory on these algorithms is still in its...
On the choice of the mutation probability for the (1+1)EA (2000)
Thomas Jansen, Ingo Wegener, Thomas Jansen, Ingo Wegener
Abstract. When evolutionary algorithms are used for function optimization, they perform a heuristic search that is influenced by many parameters. Here, the choice of the mutation probability is...
On the Analysis of the (1+1) Evolutionary Algorithm (2000)
Stefan Droste, Thomas Jansen, Ingo Wegener
Many experimental results are reported on all types of Evolutionary Algorithms but only few results have been proved. A step towards a theory on Evolutionary Algorithms, in particular, the so-called...
On the Choice of the Mutation Probability for the (1+1) EA (2000)
. When evolutionary algorithms are used for function optimization, they perform a heuristic search that is influenced by many parameters. Here, the choice of the mutation probability is investigated....
On The Expected Runtime And The Success Probability Of Evolutionary Algorithms (2000)
. Evolutionary algorithms are randomized search heuristics whose general variants have been successfully applied in black box optimization. In this scenario the function f to be optimized is not...
A Natural and Simple Function Which is Hard for All Evolutionary Algorithms (2000)
Stefan Droste, Thomas Jansen, Ingo Wegener
Evolutionary algorithms are randomized search strategies which have turned out to be efficient for optimization problems of quite different kind. In order to understand the behavior of evolutionary...
Philipp Kersting, Ingo Wegener
Many people working with computers know much about the software. However, their knowledge on the basic hardware components is restricted. Most people are convinced that computers do arithmetics as...
Asymptotically Optimal Bounds For OBDDs And The Solution Of Some Basic OBDD Problems (2000)
Ingo Wegener, Beate Bollig, Beate Bollig
Ordered binary decision diagrams (OBDDs) are nowadays the most common dynamic data structure or representation type for Boolean functions. Among the many areas of application are verification, model...
Distributed Hybrid Genetic Programming for Learning Boolean Functions (2000)
Stefan Droste, Dominic Heutelbeck, Ingo Wegener
. When genetic programming (GP) is used to find programs with Boolean inputs and outputs, ordered binary decision diagrams (OBDDs) are often used successfully. In all known OBDD-based GP-systems the...
Dynamic Parameter Control in Simple Evolutionary Algorithms (2000)
Stefan Droste, Thomas Jansen, Ingo Wegener
Evolutionary algorithms are general, randomized search heuristics that are influenced by many parameters. Though evolutionary algorithms are assumed to be robust, it is well-known that choosing the...
On the Behavior of the (1+1) Evolutionary Algorithm on Quadratic Pseudo-Boolean Functions (2000)
Evolutionary algorithms are randomized search heuristics, which are often used as function optimizers. In this paper the well-known (1+1) Evolutionary Algorithm ((1+1) EA) and its multistart variants...
On the Performance of WEAK-HEAPSORT (2000)
. Dutton (1993) presents a further HEAPSORT variant called WEAK-HEAPSORT, which also contains a new data structure for priority queues. The sorting algorithm and the underlying data structure are...
On the expected runtime and the success probability of evolutionary algorithms (2000)
Abstract. Evolutionary algorithms are randomized search heuristics whose general variants have been successfully applied in black box optimization. In this scenario the function f to be optimized is...
Distributed hybrid genetic programming for learning boolean functions (2000)
Ingo Wegener, Stefan Droste, Stefan Droste, Dominic Heutelbeck, Dominic Heutelbeck
Abstract. When genetic programming (GP) is used to find programs with Boolean inputs and outputs, ordered binary decision diagrams (OB-DDs) are often used successfully.In all known OBDD-based...
Dynamic Parameter Control in Simple Evolutionary Algorithms (2000)
Droste, Stefan, Jansen, Thomas, Wegener, Ingo
Evolutionary algorithms are general, randomized search heuristics that are influenced by many parameters. Though evolutionary algorithms are assumed to be robust,it is well-known that choosing the...
Distributed Hybrid Genetic Programming for Learning Boolean Functions (2000)
Droste, Stefan, Heutelbeck, Dominic, Wegener, Ingo
When genetic programming (GP)is used to find programs with Boolean inputs and outputs, ordered binary decision diagrams (OBDDs) are often used successfully. In all known OBDD-based GP-systems the...
Droste, Stefan, Jansen, Thomas, Wegener, Ingo
The No Free Lunch (NFL)theorem due to Wolpert and Macready (1997)has led to controversial discussions on the usefulness of randomized search heuristics, in particular, evolutionary algorithms. Here a...
On the Choice of the Mutation Probability for the (1+1) EA (2000)
When evolutionary algorithms are used for function optimization, they perform a heuristic search that is in fluenced by many parameters. Here,the choice of the mutation probability is investigated....
A Natural and Simple Function Which is Hard For All Evolutionary Algorithms (2000)
Droste, Stefan, Jansen, Thomas, Wegener, Ingo
Evolutionary algorit ms (EAs)are randomized search strategies which have turned out to be efficient for optimization problems of quite different kind. In order to understand the behavior of EAs, one...
The most simple evolutionary algorithm,the so-called (1+1)EA accepts a child if its fitness is at least as large (in the case of maximization) as the fittness of its parent. The variant (1 +1)*EA...
On the Behavior of the (1+1) Evolutionary Algorithm on Quadratic Pseudo-Boolean Functions (2000)
Evolutionary algorithms are randomized search heuristics, which are often used as function optimizers. In this paper the well-known (1+1)Evolutionary Algorithm ((1+1)EA)and its multistart variants...
On the Expected Runtime and the Success Probability of Evolutionary Algorithms (2000)
Evolutionary algorithms are randomized search heuristics whose general variants have been successfully applied in black box optimization. In this scenario the function f to be optimized is not known...
Methods for the Analysis of Evolutionary Algorithms on Pseudo-Boolean Functions (2000)
Many experiments ave shown that evolutionary algorithms are useful randomized search heuristics for optimization problems. In order to learn more about the reasons for their efficiency and in order...
Relating branching program size and formula size over the full binary basis (1999)
Martin Sauerhoff, Ingo Wegener, Ralph Werchner
Abstract. Circuit size, branching program size, and formula size of Boolean functions, denoted by C(f), BP(f), and L(f), are the most important complexity measures for Boolean functions. Often also...
Relating branching program size and formula size over the full binary basis (1999)
Martin Sauerhoff, Ingo Wegener, Ralph Werchner
Circuit size, branching program size, and formula size of Boolean functions, denoted by C(f), BP (f), and L(f), are the most important complexity measures for Boolean functions. Often also the...
The most simple evolutionary algorithm, the so-called (1+1)EA accepts a child if its fitness is at least as large (in the case of maximization) as the fitness of its parent. The variant (1 + 1) # EA...
Approximations by OBDDs and the Variable Ordering Problem (1999)
Matthias Krause, Petr Savicky, Ingo Wegener
. Ordered binary decision diagrams (OBDDs) and their variants are motivated by the need to represent Boolean functions in applications. Research concerning these applications leads also to problems...
Approximations by OBDDs and the Variable Ordering Problem (1999)
Re I He, Petr Savicky, Computat I Onal, I Ntell, I Gence, Matthias Krause, ...
Ordered binary decision diagrams (OBDDs) and their variants are motivated by the need to represent Boolean functions in applications. Research concerning these applications leads also to problems and...
Complexity Theoretical Results for Randomized Branching Programs (1999)
Doktors Der Naturwissenschaften, Martin Sauerhoff, Gutachter Prof, Dr. Ingo Wegener, Prof Dr, ...
This work is settled in the area of complexity theory for restricted variants of branching programs. Today, branching programs can be considered one of the standard nonuniform models of computation....
Optimal Ordered Binary Decision Diagrams for Read-Once Formulas (1999)
Martin Sauerhoff, Ingo Wegener, Ralph Werchner
In many applications like verification or combinatorial optimization, OBDDs (ordered binary decision diagrams) are used as a representation or data structure for Boolean functions. Efficient...
Identification of Partial Disjunction, Parity, and Threshold Functions (1999)
Ryuhei Uehara, Kensei Tsuchida, Ingo Wegener
Let F be a class of functions obtained by replacing some inputs of a Boolean function of a fixed type with some constants. The problem considered in this paper, which is called attribute efficient...
Approximations by OBDDs and the Variable Ordering Problem (1999)
Krause, Matthias, Savicky, Petr, Wegener, Ingo
Ordered binary decision diagrams (OBDDs) and their variants are motivated by the need to represent Boolean functions in applications. Research concerning these applications leads also to problems and...
Droste, Stefan, Jansen, Thomas, Wegener, Ingo
Evolutionary algorithms (EAs) are heuristic randomized algorithms which, by many impressive experiments, have been proven to behave quite well for optimization problems of various kinds. In order to...
On The Complexity Of The Hidden Weighted Bit Function For Various BDD Models (1998)
Beate Bollig, Martin Löbbing, Martin Sauerhoff, Ingo Wegener
Ordered binary decision diagrams (OBDDs) and several more general BDD models have turned out to be representations of Boolean functions which are useful in applications like verication, timing...
On the Analysis of the (1+1) Evolutionary Algorithm (1998)
Re I He, Computat I Onal, I Ntell, I Gence, Stefan Droste, Stefan Droste, ...
Many experimental results are reported on all types of Evolutionary Algorithms but only few results have been proved. A step towards a theory on Evolutionary Algorithms, in particular, the so-called...
Stefan Droste, Thomas Jansen, Ingo Wegener
Evolutionary algorithms (EAs) are heuristic randomized algorithms which, by many impressive experiments, have been proven to behave quite well for optimization problems of various kinds. In order to...
Hierarchy Theorems For kOBDDs AND kIBDDs (1998)
Beate Bollig, Martin Sauerhoff, Detlef Sieling, Ingo Wegener
Almost the same types of restricted branching programs (or binary decision diagrams BDDs) are considered in complexity theory and in applications like hardware verification. These models are...
On the analysis of evolutionary algorithms - A proof that crossover really can help (1998)
Re I He, Computat I Onal, I Ntell, I Gence, Thomas Jansen, Thomas Jansen, ...
There is a lot of experimental evidence that crossover is, for some functions, an essential operator of evolutionary algorithms. Nevertheless, it was an open problem to prove for some function that...
Perhaps Not a Free Lunch But At Least a Free Appetizer (1998)
Droste, Stefan, Jansen, Thomas, Wegener, Ingo
It is often claimed that Evolutionary Algorithms are superior to other optimization techniques, in particular, in situations where not much is known about the objective function to be optimized. In...
On the Analysis of the (1 + 1) Evolutionary Algorithm (1998)
Droste, Stefan, Jansen, Thomas, Wegener, Ingo
Many experimental results are reported on all types of Evolutionary Algorithms but only few results have been proved. A step towards a theory on Evolutionary Algorithms, in particular, the socalled...
On the Analysis of Evolutionary Algorithms (1998)
There is a lot of experimental evidence that crossover is, for some functions, an essential operator of evolutionary algorithms. Nevertheless, it was an open problem to prove for some function that...
Stefan Droste, Thomas Jansen, Ingo Wegener
The No Free Lunch (NFL) theorem due to Wolpert and Macready (1997) has led to controversial discussions on the usefulness of randomized search heuristics, in particular, evolutionary algorithms. Here...
Optimal Attribute-Efficient Learning Of Disjunction, Parity, And Threshold Functions (1997)
Ryuhei Uehara, Kensei Tsuchida, Ingo Wegener
Decision trees are a very general computation model. Here the problem is to identify a Boolean function f out of a given set of Boolean functions F by asking for the value of f at adaptively chosen...
The number of knight's tours, i. e. Hamiltonian circuits, on an 8x8 chessboard is computed with decision diagrams which turn out to be a useful tool for counting problems. 1 Introduction Binary...
Optimal Ordered Binary Decision Diagrams for Fanout-Free Circuits (1996)
Martin Sauerhoff, Ingo Wegener, Ralph Werchner
In this paper, the OBDD variable ordering problem for functions representable by general fanout-free circuits which may contain EXOR-gates is investigated. It is proved that some depth first...
Optimal Ordered Binary Decision Diagrams for Tree-like Circuits (1996)
Martin Sauerhoff, Ingo Wegener, Ralph Werchner
Many Boolean functions have short representations by OBDDs (ordered binary decision diagrams) if appropriate variable orderings are used. For tree-like circuits, which may contain EXOR-gates, it is...
On The Complexity Of Minimizing The OBDD Size For Incompletely Specified Functions (1996)
Martin Sauerhoff, Ingo Wegener
The problem to construct an OBDD cover of minimal size for an incompletely specified Boolean function arises in several applications in the CAD domain, e. g. the verification of sequential machines...
Complexity Theoretical Aspects of OFDDs (1996)
Beate Bollig, Martin Löbbing, Martin Sauerhoff, Ingo Wegener
We extend the list of complexity results for OFDDs on problems arising in practical applications. We show that it is NP-hard to decide whether a function represented by some OFDD can be represented...
Variable Orderings For OBDDs, Simulated Annealing, And The Hidden Weighted Bit Function (1996)
Beate Bollig, Martin Löbbing, Ingo Wegener
Ordered binary decision diagrams (OBDDs) are an efficient graph representation for Boolean functions, if good variable orderings are used. Variable orderings are computed by heuristic algorithms and...
On The Complexity Of Minimizing The OBDD Size For Incompletely Specified Functions (1996)
Martin Sauerhoff, Ingo Wegener
The problem of constructing an OBDD cover of minimal size for an incompletely specified Boolean function arises in several applications in the CAD domain, e. g. the verification of sequential...
Complexity Theoretical Aspects of OFDDs (1996)
Beate Bollig, Martin Löbbing, Martin Sauerhoff, Ingo Wegener
Experimental results have shown that OFDDs (ordered functional decision diagrams) are a representation of Boolean functions which are sometimes superior to OBDDs (orered binary decision diagrams)....
Optimal Ordered Binary Decision Diagrams for Tree-like Circuits (1996)
Martin Sauerhoff, Ingo Wegener, Ralph Werchner
Many Boolean functions have short representations by OBDDs (ordered binary decision diagrams), if appropriate variable orderings are used. For tree-like circuits which may contain EXOR-gates it is...
Simulated annealing to improve variable orderings for OBDDs (1995)
Beate Bollig, Martin Lobbing, Ingo Wegener
The choice of a good variable ordering is crucial in applications of Ordered Binary Decision Diagrams (OBDDs). A simulated annealing approach with a new type of neighborhood is presented and...
Simulated Annealing To Improve Variable Orderings For OBDDs (1995)
Beate Bollig, Martin Löbbing, Ingo Wegener
The choice of a good variable ordering is crucial in applications of Ordered Binary Decision Diagrams (OBDDs). A simulated annealing approach with a new type of neighborhood is presented and...
An increasing number of results in graph theory, combinatorics and theoretical computer science is obtained with the help of computers, e. g. the proof of the Four Colours Theorem or the computation...
Read-once Projections and Formal Circuit Verification with Binary Decision Diagrams (1995)
Computational complexity is concerned with the complexity of solving problems and computing functions and not with the complexity of verifying circuit designs. The importance of formal circuit...
The theory of zero-suppressed BDDs and the number of knights tours (1994)
Abstract Zero--suppressed binary decision diagrams (ZBDDs) have been introduced by Minato ([14]-- [17]) who presents applications for cube set representations, fault simulation, timing analysis and...
On The Power Of Different Types Of Restricted Branching Programs (1994)
Beate Bollig, Martin Sauerhoff, Detlef Sieling, Ingo Wegener
Almost the same types of restricted branching programs (or binary decision diagrams BDDs) are considered in complexity theory and in applications like hardware verification. These models are...
The Theory of Zero-Suppressed BDDs and the Number of Knight's Tours (1994)
Martin Löbbing, Olaf Schröer, Ingo Wegener
Zero-suppressed binary decision diagrams (ZBDDs) have been introduced by Minato in [14]--[17]. Here the structural properties of ZBDDs are worked out and a generic synthesis algorithm is presented...
The Complexity of Boolean Functions (1987)
Ingo Wegener, Ii. Teubner, Wegener Ingo, Wegener Ingo, Wegener Ingo
this memory cell. Bit a k-1 decides whether we should 77 search in the first or in the second half of the memory. Therefore SA n (a k-1 a 0 x 0 x n-1 ) = (5.1) = (a k-1 SA n 2 (a k-2 a 0 x n 2 x n-1...
This document in subdirectoryRS/03/45/ On Converting CNF to DNF
Peter Bro Miltersen, Jaikumar Radhakrishnan, Ingo Wegener, Copyright C, Peter Bro Miltersen, Ingo Wegener, ...
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent BRICS...