Models, code, and papers for "Frank Neumann":

Computational Complexity Analysis of Multi-Objective Genetic Programming

Mar 22, 2012
Frank Neumann

The computational complexity analysis of genetic programming (GP) has been started recently by analyzing simple (1+1) GP algorithms for the problems ORDER and MAJORITY. In this paper, we study how taking the complexity as an additional criteria influences the runtime behavior. We consider generalizations of ORDER and MAJORITY and present a computational complexity analysis of (1+1) GP using multi-criteria fitness functions that take into account the original objective and the complexity of a syntax tree as a secondary measure. Furthermore, we study the expected time until population-based multi-objective genetic programming algorithms have computed the Pareto front when taking the complexity of a syntax tree as an equally important objective.

* A conference version has been accepted for GECCO 2012 

  Click for Model/Code and Paper
A Feature-Based Prediction Model of Algorithm Selection for Constrained Continuous Optimisation

Feb 09, 2016
Shayan Poursoltan, Frank Neumann

With this paper, we contribute to the growing research area of feature-based analysis of bio-inspired computing. In this research area, problem instances are classified according to different features of the underlying problem in terms of their difficulty of being solved by a particular algorithm. We investigate the impact of different sets of evolved instances for building prediction models in the area of algorithm selection. Building on the work of Poursoltan and Neumann [11,10], we consider how evolved instances can be used to predict the best performing algorithm for constrained continuous optimisation from a set of bio-inspired computing methods, namely high performing variants of differential evolution, particle swarm optimization, and evolution strategies. Our experimental results show that instances evolved with a multi-objective approach in combination with random instances of the underlying problem allow to build a model that accurately predicts the best performing algorithm for a wide range of problem instances.


  Click for Model/Code and Paper
Parameterized Analysis of Multi-objective Evolutionary Algorithms and the Weighted Vertex Cover Problem

Apr 06, 2016
Mojgan Pourhassan, Feng Shi, Frank Neumann

A rigorous runtime analysis of evolutionary multi-objective optimization for the classical vertex cover problem in the context of parameterized complexity analysis has been presented by Kratsch and Neumann (2013). In this paper, we extend the analysis to the weighted vertex cover problem and provide a fixed parameter evolutionary algorithm with respect to OPT, the cost of the the optimal solution for the problem. Moreover, using a diversity mechanisms, we present a multi-objective evolutionary algorithm that finds a 2-approximation in expected polynomial time and introduce a population-based evolutionary algorithm which finds a $(1+\varepsilon)$-approximation in expected time $O(n\cdot 2^{\min \{n,2(1- \varepsilon)OPT \}} + n^3)$.


  Click for Model/Code and Paper
A Feature-Based Comparison of Evolutionary Computing Techniques for Constrained Continuous Optimisation

Sep 23, 2015
Shayan Poursoltan, Frank Neumann

Evolutionary algorithms have been frequently applied to constrained continuous optimisation problems. We carry out feature based comparisons of different types of evolutionary algorithms such as evolution strategies, differential evolution and particle swarm optimisation for constrained continuous optimisation. In our study, we examine how sets of constraints influence the difficulty of obtaining close to optimal solutions. Using a multi-objective approach, we evolve constrained continuous problems having a set of linear and/or quadratic constraints where the different evolutionary approaches show a significant difference in performance. Afterwards, we discuss the features of the constraints that exhibit a difference in performance of the different evolutionary approaches under consideration.

* 16 Pagesm 2 Figures 

  Click for Model/Code and Paper
A Feature-Based Analysis on the Impact of Set of Constraints for e-Constrained Differential Evolution

Jun 23, 2015
Shayan Poursoltan, FranK Neumann

Different types of evolutionary algorithms have been developed for constrained continuous optimization. We carry out a feature-based analysis of evolved constrained continuous optimization instances to understand the characteristics of constraints that make problems hard for evolutionary algorithm. In our study, we examine how various sets of constraints can influence the behaviour of e-Constrained Differential Evolution. Investigating the evolved instances, we obtain knowledge of what type of constraints and their features make a problem difficult for the examined algorithm.

* 17 Pages 

  Click for Model/Code and Paper
On the Runtime of Randomized Local Search and Simple Evolutionary Algorithms for Dynamic Makespan Scheduling

Apr 23, 2015
Frank Neumann, Carsten Witt

Evolutionary algorithms have been frequently used for dynamic optimization problems. With this paper, we contribute to the theoretical understanding of this research area. We present the first computational complexity analysis of evolutionary algorithms for a dynamic variant of a classical combinatorial optimization problem, namely makespan scheduling. We study the model of a strong adversary which is allowed to change one job at regular intervals. Furthermore, we investigate the setting of random changes. Our results show that randomized local search and a simple evolutionary algorithm are very effective in dynamically tracking changes made to the problem instance.

* Conference version appears at IJCAI 2015 

  Click for Model/Code and Paper
Computational Complexity Results for Genetic Programming and the Sorting Problem

May 06, 2011
Markus Wagner, Frank Neumann

Genetic Programming (GP) has found various applications. Understanding this type of algorithm from a theoretical point of view is a challenging task. The first results on the computational complexity of GP have been obtained for problems with isolated program semantics. With this paper, we push forward the computational complexity analysis of GP on a problem with dependent program semantics. We study the well-known sorting problem in this context and analyze rigorously how GP can deal with different measures of sortedness.

* 12 pages 

  Click for Model/Code and Paper
Fast Re-Optimization via Structural Diversity

Apr 16, 2019
Benjamin Doerr, Carola Doerr, Frank Neumann

When a problem instance is perturbed by a small modification, one would hope to find a good solution for the new instance by building on a known good solution for the previous one. Via a rigorous mathematical analysis, we show that evolutionary algorithms, despite usually being robust problem solvers, can have unexpected difficulties to solve such re-optimization problems. When started with a random Hamming neighbor of the optimum, the (1+1) evolutionary algorithm takes $\Omega(n^2)$ time to optimize the LeadingOnes benchmark function, which is the same asymptotic optimization time when started in a randomly chosen solution. There is hence no significant advantage from re-optimizing a structurally good solution. We then propose a way to overcome such difficulties. As our mathematical analysis reveals, the reason for this undesired behavior is that during the optimization structurally good solutions can easily be replaced by structurally worse solutions of equal or better fitness. We propose a simple diversity mechanism that prevents this behavior, thereby reducing the re-optimization time for LeadingOnes to $O(\gamma\delta n)$, where $\gamma$ is the population size used by the diversity mechanism and $\delta \le \gamma$ the Hamming distance of the new optimum from the previous solution. We show similarly fast re-optimization times for the optimization of linear functions with changing constraints and for the minimum spanning tree problem.

* To appear at Genetic and Evolutionary Computation Conference (GECCO '19) 

  Click for Model/Code and Paper
The Evolutionary Process of Image Transition in Conjunction with Box and Strip Mutation

Aug 05, 2016
Aneta Neumann, Bradley Alexander, Frank Neumann

Evolutionary algorithms have been used in many ways to generate digital art. We study how evolutionary processes are used for evolutionary art and present a new approach to the transition of images. Our main idea is to define evolutionary processes for digital image transition, combining different variants of mutation and evolutionary mechanisms. We introduce box and strip mutation operators which are specifically designed for image transition. Our experimental results show that the process of an evolutionary algorithm in combination with these mutation operators can be used as a valuable way to produce unique generative art.

* Conference version appears at ICONIP 2016 

  Click for Model/Code and Paper
Evolutionary Image Transition Based on Theoretical Insights of Random Processes

Apr 21, 2016
Aneta Neumann, Bradley Alexander, Frank Neumann

Evolutionary algorithms have been widely studied from a theoretical perspective. In particular, the area of runtime analysis has contributed significantly to a theoretical understanding and provided insights into the working behaviour of these algorithms. We study how these insights into evolutionary processes can be used for evolutionary art. We introduce the notion of evolutionary image transition which transfers a given starting image into a target image through an evolutionary process. Combining standard mutation effects known from the optimization of the classical benchmark function OneMax and different variants of random walks, we present ways of performing evolutionary image transition with different artistic effects.


  Click for Model/Code and Paper
Parameterized Runtime Analyses of Evolutionary Algorithms for the Euclidean Traveling Salesperson Problem

Oct 09, 2012
Andrew M. Sutton, Frank Neumann

Parameterized runtime analysis seeks to understand the influence of problem structure on algorithmic runtime. In this paper, we contribute to the theoretical understanding of evolutionary algorithms and carry out a parameterized analysis of evolutionary algorithms for the Euclidean traveling salesperson problem (Euclidean TSP). We investigate the structural properties in TSP instances that influence the optimization process of evolutionary algorithms and use this information to bound the runtime of simple evolutionary algorithms. Our analysis studies the runtime in dependence of the number of inner points $k$ and shows that $(\mu + \lambda)$ evolutionary algorithms solve the Euclidean TSP in expected time $O((\mu/\lambda) \cdot n^3\gamma(\epsilon) + n\gamma(\epsilon) + (\mu/\lambda) \cdot n^{4k}(2k-1)!)$ where $\gamma$ is a function of the minimum angle $\epsilon$ between any three points. Finally, our analysis provides insights into designing a mutation operator that improves the upper bound on expected runtime. We show that a mixed mutation strategy that incorporates both 2-opt moves and permutation jumps results in an upper bound of $O((\mu/\lambda) \cdot n^3\gamma(\epsilon) + n\gamma(\epsilon) + (\mu/\lambda) \cdot n^{2k}(k-1)!)$ for the $(\mu+\lambda)$ EA.

* A conference version has been accepted for AAAI 2012 

  Click for Model/Code and Paper
Runtime Analysis of RLS and (1+1) EA for the Dynamic Weighted Vertex Cover Problem

Mar 06, 2019
Mojgan Pourhassan, Vahid Roostapour, Frank Neumann

In this paper, we perform theoretical analyses on the behaviour of an evolutionary algorithm and a randomised search algorithm for the dynamic vertex cover problem based on its dual formulation. The dynamic vertex cover problem has already been theoretically investigated to some extent and it has been shown that using its dual formulation to represent possible solutions can lead to a better approximation behaviour. We improve some of the existing results, i.e. we find a linear expected re-optimization time for a (1+1) EA to re-discover a 2-approximation when edges are dynamically deleted from the graph. Furthermore, we investigate a different setting for applying the dynamism to the problem, in which a dynamic change happens at each step with a probability $P_D$. We also expand these analyses to the weighted vertex cover problem, in which weights are assigned to vertices and the goal is to find a cover set with minimum total weight. Similar to the classical case, the dynamic changes that we consider on the weighted vertex cover problem are adding and removing edges to and from the graph. We aim at finding a maximal solution for the dual problem, which gives a 2-approximate solution for the vertex cover problem. This is equivalent to the maximal matching problem for the classical vertex cover problem.

* The paper has been accepted for Theoretical Computer Science journal 

  Click for Model/Code and Paper
Analysis of Baseline Evolutionary Algorithms for the Packing While Travelling Problem

Feb 13, 2019
Vahid Roostapour, Mojgan Pourhassan, Frank Neumann

Although the performance of base-line Evolutionary Algorithms (EAs) on linear functions has been studied rigorously, the same theoretical analyses on non-linear objectives are still far behind. In this paper, variations of the Packing While Travelling (PWT), also known as a non-linear knapsack problem, is considered to address this gap. We investigate PWT for two cities with correlated weights and profits using single-objective and multi-objective algorithms. Our results show that RLS finds the optimal solution in $O(n^3)$ expected time while the GSEMO enhanced with a specific selection operator to deal with exponential population size, calculates all the Pareto front solutions in the same expected time. In the case of uniform weights, (1+1)~EA is able to find the optimal solution in expected time $O(n^2\log{(\max\{n,p_{max}\})})$, where $p_{max}$ is the largest profit of the given items. We also validate the theoretical results using practical experiments and present estimation for expected running time according to the experiments.


  Click for Model/Code and Paper
Analysis of Evolutionary Algorithms in Dynamic and Stochastic Environments

Jun 22, 2018
Vahid Roostapour, Mojgan Pourhassan, Frank Neumann

Many real-world optimization problems occur in environments that change dynamically or involve stochastic components. Evolutionary algorithms and other bio-inspired algorithms have been widely applied to dynamic and stochastic problems. This survey gives an overview of major theoretical developments in the area of runtime analysis for these problems. We review recent theoretical studies of evolutionary algorithms and ant colony optimization for problems where the objective functions or the constraints change over time. Furthermore, we consider stochastic problems under various noise models and point out some directions for future research.

* This book chapter is to appear in the book "Theory of Randomized Search Heuristics in Discrete Search Spaces", which is edited by Benjamin Doerr and Frank Neumann and is scheduled to be published by Springer in 2018 

  Click for Model/Code and Paper
Feature-Based Diversity Optimization for Problem Instance Classification

Apr 08, 2016
Wanru Gao, Samadhi Nallaperuma, Frank Neumann

Understanding the behaviour of heuristic search methods is a challenge. This even holds for simple local search methods such as 2-OPT for the Traveling Salesperson problem. In this paper, we present a general framework that is able to construct a diverse set of instances that are hard or easy for a given search heuristic. Such a diverse set is obtained by using an evolutionary algorithm for constructing hard or easy instances that are diverse with respect to different features of the underlying problem. Examining the constructed instance sets, we show that many combinations of two or three features give a good classification of the TSP instances in terms of whether they are hard to be solved by 2-OPT.

* 20 pages, 18 figures 

  Click for Model/Code and Paper
Multiplicative Approximations, Optimal Hypervolume Distributions, and the Choice of the Reference Point

Sep 16, 2013
Tobias Friedrich, Frank Neumann, Christian Thyssen

Many optimization problems arising in applications have to consider several objective functions at the same time. Evolutionary algorithms seem to be a very natural choice for dealing with multi-objective problems as the population of such an algorithm can be used to represent the trade-offs with respect to the given objective functions. In this paper, we contribute to the theoretical understanding of evolutionary algorithms for multi-objective problems. We consider indicator-based algorithms whose goal is to maximize the hypervolume for a given problem by distributing {\mu} points on the Pareto front. To gain new theoretical insights into the behavior of hypervolume-based algorithms we compare their optimization goal to the goal of achieving an optimal multiplicative approximation ratio. Our studies are carried out for different Pareto front shapes of bi-objective problems. For the class of linear fronts and a class of convex fronts, we prove that maximizing the hypervolume gives the best possible approximation ratio when assuming that the extreme points have to be included in both distributions of the points on the Pareto front. Furthermore, we investigate the choice of the reference point on the approximation behavior of hypervolume-based approaches and examine Pareto fronts of different shapes by numerical calculations.


  Click for Model/Code and Paper
A Fast and Effective Local Search Algorithm for Optimizing the Placement of Wind Turbines

Apr 20, 2012
Markus Wagner, Jareth Day, Frank Neumann

The placement of wind turbines on a given area of land such that the wind farm produces a maximum amount of energy is a challenging optimization problem. In this article, we tackle this problem, taking into account wake effects that are produced by the different turbines on the wind farm. We significantly improve upon existing results for the minimization of wake effects by developing a new problem-specific local search algorithm. One key step in the speed-up of our algorithm is the reduction in computation time needed to assess a given wind farm layout compared to previous approaches. Our new method allows the optimization of large real-world scenarios within a single night on a standard computer, whereas weeks on specialized computing servers were required for previous approaches.

* 16 pages, 2 algorithms, 4 figures, 1 table 

  Click for Model/Code and Paper
Evolutionary Diversity Optimization Using Multi-Objective Indicators

Nov 16, 2018
Aneta Neumann, Wanru Gao, Markus Wagner, Frank Neumann

Evolutionary diversity optimization aims to compute a diverse set of solutions where all solutions meet a given quality criterion. With this paper, we bridge the areas of evolutionary diversity optimization and evolutionary multi-objective optimization. We show how popular indicators frequently used in the area of multi-objective optimization can be used for evolutionary diversity optimization. Our experimental investigations for evolving diverse sets of TSP instances and images according to various features show that two of the most prominent multi-objective indicators, namely the hypervolume indicator and the inverted generational distance, provide excellent results in terms of visualization and various diversity indicators.


  Click for Model/Code and Paper
Pareto Optimization for Subset Selection with Dynamic Cost Constraints

Nov 14, 2018
Vahid Roostapour, Aneta Neumann, Frank Neumann, Tobias Friedrich

In this paper, we consider the subset selection problem for function $f$ with constraint bound $B$ which changes over time. We point out that adaptive variants of greedy approaches commonly used in the area of submodular optimization are not able to maintain their approximation quality. Investigating the recently introduced POMC Pareto optimization approach, we show that this algorithm efficiently computes a $\phi= (\alpha_f/2)(1-\frac{1}{e^{\alpha_f}})$-approximation, where $\alpha_f$ is the submodularity ratio of $f$, for each possible constraint bound $b \leq B$. Furthermore, we show that POMC is able to adapt its set of solutions quickly in the case that $B$ increases. Our experimental investigations for the influence maximization in social networks show the advantage of POMC over generalized greedy algorithms.


  Click for Model/Code and Paper