Foundations of Bio-Inspired Computing: Previous Projects

Parameterized Analysis of Bio-inspired Computing

We develop, from the present simple state of art, an extensive parameterized analysis of bio-inspired computing and transfer these new insights into better performing algorithms. We do this by examining features of important combinatorial optimization problems and their influence on the performance of bio-inspired computing methods. These theoretical investigations are carried out by feature-based analysis and by using parameterized computational complexity analyses of bio-inspired computing methods. These fundamental investigations allow us to get new insights on how different parameters of combinatorial optimization problems influence the runtime behaviour of bio-inspired computing methods. Our studies will mainly focus on problems related to supply chain management such as vehicle routing, packing, and scheduling and problems motivated by computer vision research such as the multi-cut problem. We will use the theoretical results obtained to develop new and more effective algorithms for the investigated problems. This will be done by developing new bio-inspired computing methods that are particularly target towards the hard instances of a given combinatorial optimization problem. The knowledge gained from our investigations will boost the understanding on how effective bio-inspired computing methods can be design by taking important instance parameters into account.

Approximation Guided Evolution

Most real-world optimization problems are characterized by multiple objectives. As these objectives are often in conflict with each other, the goal of solving a multi-objective optimization (MOO) problem is to find a (not too large) set of compromise solutions. The Pareto front of a MOO problem consists of the function values representing the different trade-offs with respect to the given objective functions. Multi-objective optimization is assumed to be more (or at least as) difficult as single-objective optimization due to the task of computing several solutions. From a computational complexity point of view even simple single-objective problems on weighted graphs like shortest paths or minimum spanning trees become NP-hard when they encounter at least two weight functions. In addition, the size of the Pareto front is often exponential for discrete problems and even infinite for continuous ones.

Evolutionary algorithms are frequently used to solve multi-objective optimization problems. Often, it is very hard to formally define the optimization that current state-of-the-art approaches work with. We have developed a new evolutionary multi-objective algorithm (called AGE) that works with a formal notion of approximation. The framework of our algorithm allows to work with various formal notions of approximations. Our experimental results show that given a fixed time budget it outperforms current state-of-the-art approaches in terms of the desired additive approximation on standard benchmark functions. Additionally, it also performs better regarding the covered hypervolume. This holds, in particular, for problems with many objectives, which most other algorithms have difficulties dealing with.

Software

The runtime of our algorithm AGE (IJCAI 2011 + GECCO 2013, see below) increases only linearly with the number of objectives. It was implemented for two widely-used libraries of (evolutionary) algorithms, and is available for download.
GECCO 2013 version: Source Code: jMetal implementation (Note, Author: Markus Wagner). The C implementation will come in a few weeks, stay tuned.
Note: the IJCAI 2011 code is available as well. However, it is recommended that you use the GECCO 2013 version due to the significant improvements. IJCAI 2011 version: jMetal implementation (Note, Author: Markus Wagner), Shark implementation.

Additional Resources

• Approximation-Guided Evolutionary Optimization at the Friedrich Schiller University Jena
  

Computational Complexity Analysis of Genetic Programming

One of the challenges of computer science is to get a computer to do what needs to be done, without telling it how this can be accomplished. Genetic Programming addresses this challenge by providing a scheme for automatically building computer programs from a high-level statement of the problem. This is achieved by "breeding" a population of computer programs using the principles of Darwinian natural selection and biologically inspired operations. In the last decade, Genetic Programming algorithms have found various applications in a number of domains, such as symbolic regression, financial trading, and bioinformatics. Because of the complexity of genetic programming variants and the challenging nature of the problems they address, it is arguably impossible in most cases to make formal guarantees about the number of fitness evaluations needed for an algorithm to find an optimal solution.

Recently, the first computational complexity results have been presented for simple genetic programming algorithms. We contribute to the theoretical understanding of genetic programming algorithms, by analyzing the influence of acceptance criteria, mutation behavior, and population sizes on the optimization time needed for different problems.

Software

GPFramework (0.1) is a Java framework for rapid prototyping of mutation-only Genetic Programming systems (mostly, but not exclusively, with the goal to assess their computational complexity). Hosted at: BitBucket (Mercurial), GitHub (Git), and Google Code (Subversion).

Publications

• F. Neumann, C. Witt (2015): On the runtime of randomized local search and simple evolutionary algorithms for dynamic makespan scheduling. In: International Joint Conferences on Artificial Intelligence, IJCAI 2015 (to appear).
• M. Pourhassan, W. Gao, F. Neumann (2015): Maintaining 2-approximations for the dynamic vertex cover Problem using evolutionary algorithms. In: Genetic and Evolutionary Computation Conference, GECCO 2015, ACM Press (to appear).
• M. Pourhassan, F. Neumann (2015): On the impact of local search operators and variable neighbourhood search for the generalized travelling salesperson problem. In: Genetic and Evolutionary Computation Conference, GECCO 2015, ACM Press (to appear).
• Doerr, F. Neumann, A. M. Sutton (2015): Improved runtime bounds for the (1+1) EA on random 3-CNF formulas based on fitness-distance correlation. In: Genetic and Evolutionary Computation Conference, GECCO 2015, ACM Press (to appear).
• A. Nguyen, Markus Wagner, and F. Neumann (2014): Incorporating User Preferences into Approximation-Guided Multi-Objective Evolution. In: 10th Int. Conference on Simulated Evolution and Artificial Life, SEAL 2014.
• M. Wagner and F. Neumann (2014): Single- and Multi-Objective Genetic Programming: New Runtime Results for SORTING. In: IEEE World Congress on Computational Intelligence: Congress on Evolutionary Computation, WCCI/CEC 2014.
• M. Wagner, F. Neumann (2013): A Fast Approximation-Guided Evolutionary Multi-Objective Algorithm. Proceedings, Genetic and Evolutionary Computation Conference (GECCO 2013) PDF
• M. Wagner, T. Friedrich (2013): Efficient Parent Selection for Approximation-Guided Evolutionary Multi-Objective Optimization. Proceedings, IEEE Conference on Evolutionary Computation (CEC 2013) PDF
• S. Nallaperuma, A. M. Sutton, F. Neumann (2013): Parameterized complexity analysis and more effective construction methods for ACO algorithms and the Euclidean traveling salesperson problem. In Proceedings of IEEE Congress on Evolutionary Computation, IEEE CEC 2013, IEEE Press.
• S. Nallaperuma, A. M. Sutton, F. Neumann (2013): Fixed-parameter evolutionary algorithms for the Euclidean traveling salesperson problem. In Proceedings of IEEE Congress on Evolutionary Computation, IEEE CEC 2013, IEEE Press.
• D. Corus, P. K. Lehre, F. Neumann (2013): The generalized minimum spanning tree problem: a parameterized complexity analysis of bi-level optimisation. In Proceedings of Genetic and Evolutionary Computation Conference, GECCO 2013, ACM Press. (Best Paper Award in the track "Evolutionary Combinatorial Optimization and Metaheuristics")
• A. Q. Nguyen, T. Urli and M. Wagner (2013): Improved Computational Complexity Results for Weighted ORDER and MAJORITY. In: Foundations of Genetic Algorithms XII, FOGA 2013.
• A. M. Sutton, F. Neumann (2012): A Parameterized Runtime Analysis of Simple Evolutionary Algorithms for Makespan Scheduling. In Proceedings of the Twelfth International Conference on Parallel Problem Solving from Nature (PPSN XII), Taormina, Italy, September 2012. Published in Lecture Notes in Computer Science Vol. 7491, (2012) pp. 52-61. [link]
• A. M. Sutton, F. Neumann (2012): A Parameterized Runtime Analysis of Evolutionary Algorithms for the Euclidean Traveling Salesperson Problem In Proceedings of the Twenty-Sixth Conference on Artificial Intelligence (AAAI-12), Toronto, ON, Canada, July 2012. [CoRR abs/1207.0578]
• A. M. Sutton, J. Day, F. Neumann (2012): A Parameterized Runtime Analysis of Evolutionary Algorithms for MAX-2-SAT In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-12), Philadelphia, PA, July 2012. [link]
• J. Yuen, S. Gao, M. Wagner, F. Neumann (2012): An Adaptive Data Structure for Evolutionary Multi-Objective Algorithms with Unbounded Archives. Proceedings, IEEE World Congress on Computational Intelligence: Congress on Evolutionary Computation (WCCI/CEC 2012).
• M. Wagner, F. Neumann (2012): Parsimony Pressure versus Multi-Objective Optimization for Variable Length Representations. In: Parallel Problem Solving From Nature, PPSN 2012. Available: [Springer]
• T. Urli, M. Wagner, F. Neumann (2012): Experimental Supplements to the Computational Complexity Analysis of Genetic Programming for Problems Modelling Isolated Program Semantics. In: Parallel Problem Solving From Nature, PPSN 2012. Available: [Springer]
• F. Neumann (2012): Computational complexity analysis of multi-objective genetic programming. In: Genetic and Evolutionary Computation Conference, GECCO 2012. CoRR abs/1203.4881]
• T. Kötzing, A. M. Sutton, F. Neumann, U.-M. O'Reilly (2012): The Max Problem revisited: the importance of mutation in genetic programming. In: Genetic and Evolutionary Computation Conference, GECCO 2012. Available: [ACM Digital Library]
• F. Neumann, U.-M. O’Reilly, M. Wagner (2011): Computational complexity analysis of genetic programming - initial results and future directions. In: R. Riolo, E. Vladislavleva, J. H. Moore (Eds.): Genetic Programming Theory and Practice IX, Springer, pages 113-128. Final Version
• T. Kötzing, F. Neumann, R. Spöhel (2011): PAC learning and genetic programming. In: Genetic and Evolutionary Computation Conference, GECCO 2011. Available: [ACM Digital Library]
• G. Durrett, F. Neumann, U.-M. O'Reilly (2011): Computational complexity analysis of simple genetic programming on two problems modeling isolated program semantics.
  In: Foundations of Genetic Algorithms XI, FOGA 2011. Available: [CoRR abs/1007.4636]
• K. Bringmann, T. Friedrich, F. Neumann, M. Wagner (2011): Approximation-Guided Evolutionary Multi-Objective Optimization [the original AGE paper] Proceedings, 21nd International Joint Conference on Artificial Intelligence (IJCAI 2011) PDF | BibTeX | Abstract | Errata
• C. Horoba, F. Neumann (2008): Benefits and drawbacks for the use of epsilon-dominance in evolutionary multi-objective optimization. Proceedings, Genetic and Evolutionary Computation Conference (GECCO 2008) PDF