Theoretical Foundations of Bio-inspired Computation

Bio-inspired search heuristics often turn out to be highly successful for optimization in practice. The theory of these randomized search heuristics explains the success or the failure of these methods in practical applications. Theoretical analyses lead to the understanding of which problems are optimized (or approximated) efficiently by a given algorithm and which are not.

The benefits of theoretical understanding for practitioners are threefold.

• Aiding the algorithm design,
• guiding the choice of the best algorithm for the problem at hand,
• determining the optimal parameter settings.

Thus, theoretical guidance is essential for success in real-world optimization.

The main objective of this task force is to help bridge the gap between theory and practice in bio-inspired computation.

The main goals of this task force are:

• to get theoretical research more propagated in the IEEE CIS community and to more people in general,
• to promote to non-theoreticians the importance of theoretically understanding the behavior and performance of the optimization algorithms they design,
• to bridge the gap between theory and practice.

The scope of this task force includes (but is not limited to) the following topics:

• Theoretical foundations of bio-inspired heuristics
• Exact and approximation runtime analysis for combinatorial optimization
• Black box complexity
• Theoretical analysis of bio-inspired heuristics for continuous optimization
• Fitness landscape analysis
• Statistical approaches for understanding the behavior of bio-inspired heuristics

 
• • C. Cotta
  • 2013 IEEE Symposium on Foundations of Computational Intelligence (FOCI 2013)
  • 16-19 April 2013, Singapore.
• • P.S. Oliveto, X. Yao
  • A Gentle Introduction to the Time Complexity Analysis of Evolutionary Algorithms (4 hour runtime analysis tutorial) (Download Slides)
  • World Congress on Computational Intelligence (WCCI 2012), Brisbane, Australia (10 June 2012, 13:00-17:00).
• • F. Neumann
  • Bio-inspired Computation in Combinatorial Optimisation - Algorithms and Complexity (2 hour runtime analysis tutorial) (Download Slides)
  • World Congress on Computational Intelligence (WCCI 2012), Brisbane, Australia (10 June 2012, 17:00-19:00).
• • X. Yao
  • Unpacking and Understanding Evolutionary Algorithms (Plenary talk)
  • World Congress on Computational Intelligence (WCCI 2012), Brisbane, Australia (12 June 2012, 08:15-09:15)

• Pietro S. Oliveto (Chair)
• Per Kristian Lehre (Vice-Chair)
• Frank Neumann (Vice-Chair)
• Tianshi Chen
• Carlos Cotta
• Benjamin Doerr
• Tobias Friedrich
• Nikolaus Hansen
• Jun He
• Thomas Jansen
• Alberto Moraglio
• Jonathan Rowe
• Dirk Sudholt
• Andrew M. Sutton
• Carsten Witt
• Xin Yao
• Yang Yu
• Christine Zarges

• Andrea Mambrini (University of Birmingham)
• Samadhi Nallaperuma (University of Adelaide)
• Markus Wagner (University of Adelaide)

Books


 
 
• • T. Jansen
  • Analyzing Evolutionary Algorithms. The Computer Science Perspective,
  • Springer, Natural Computation Series, 2013. (book web-page)
 
 

 
 
• • Theory of Randomized Search Heuristics~Foundations and Recent Developments,
  • B. Doerr and A. Auger editors, World Scientific, February 2011. (World Scientific)
 
 
 
 

 
 
• • F. Neumann, C. Witt
  • Bioinspired Computation in Combinatorial Optimization - Algorithms and Their Computational Complexity,
  • Springer, Natural Computation Series, February 2010. (book web-page)
 
 

Tutorials

• • A Gentle Introduction to the Time Complexity Analysis of Evolutionary Algorithms (4 hour tutorial) (Slides)
  • WCCI 2012 runtime analysis tutorial by P.S. Oliveto and X. Yao. - introductory level-
  • Covers first two chapters of the Doerr/Auger edited book.
• • Bio-inspired Computation in Combinatorial Optimisation - Algorithms and Complexity (2 hour tutorial) (Slides)
  • WCCI 2012 runtime analysis tutorial by F. Neumann. - advanced level-
  • Based on the Neumann/Witt textbook.
 

Survey Articles

• • P.S.Oliveto, J.He, X.Yao.
  • Time Complexity of Evolutionary Algorithms for Combinatorial Optimization: A Decade of Results. (pdf)
  • International Journal of Automation and Computing (IJAC)
  • Vol. 4 (3), 2007.

To join the Task Force or for any questions please email p.s.oliveto@cs.bham.ac.uk