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

 
• • P. K. Lehre, A. Neumann, C. Qian
  • Special Issue on Theoretical Foundations of Evolutionary Computation (TCS 2021-2022)
  • Theoretical Computer Science Special Issue, Submission Deadline: December 31, 2021
• • M. Ojeda-Aciego, L. Franco, P. S. Oliveto, C. Qian
  • IEEE Symposium on Foundations of Computational Intelligence (IEEE FOCI 2021)
  • 2021 IEEE Symposium Series on Computational Intelligence (SSCI 2021), Orlando, FL, December 5 - 8, 2021
• • P. K. Lehre, A. Neumann, C. Qian
  • Special Session on Theoretical Foundations of Bio-inspired Computation (Special Session)
  • 2021 IEEE Congress on Evolutionary Computation (CEC 2021), Krakow, Poland, 28 June - 1 July, 2021
• • P. S. Oliveto, C. Qian, M. Ojeda-Aciego, L. Franco
  • IEEE Symposium on Foundations of Computational Intelligence (IEEE FOCI 2020)
  • 2020 IEEE Symposium Series on Computational Intelligence (SSCI 2020), December 1 - 4, 2020, Canberra, Australia.
• • C. Qian, Y. Yu
  • Pareto Optimization for Subset Selection: Theories and Practical Algorithms (Tutorial)
  • 2020 IEEE Congress on Evolutionary Computation (CEC 2020), July 19 - 24, 2020, Glasgow, UK.
• • P. S. Oliveto, A. Lissovoi
  • Computational Complexity Analysis of Genetic Programming (Tutorial)
  • 2020 IEEE Congress on Evolutionary Computation (CEC 2020), July 19 - 24, 2020, Glasgow, UK.
• • P. K. Lehre, A. Neumann, C. Qian
  • Special Session on Theoretical Foundations of Bio-inspired Computation (Theory Special Session)
  • 2020 IEEE Congress on Evolutionary Computation (CEC 2020), July 19 - 24, 2020, Glasgow, UK.
• • M. Ojeda-Aciego, P. S. Oliveto, L. Franco
  • IEEE Symposium on Foundations of Computational Intelligence (IEEE FOCI 2019)
  • 2019 IEEE Symposium Series on Computational Intelligence (SSCI 2019), December 6 - 9, 2019, Xiamen, China.
• • P. S. Oliveto
  • A Gentle Introduction to the Time Complexity Analysis of Evolutionary Algorithms (Tutorial)
  • 2019 IEEE Congress on Evolutionary Computation (CEC 2019), June 10 - 13, 2019, Wellington, New Zealand.
• • C. Qian, Y. Yu
  • Pareto Optimization for Subset Selection: Theories and Practical Algorithms (Tutorial)
  • 2019 IEEE Congress on Evolutionary Computation (CEC 2019), June 10 - 13, 2019, Wellington, New Zealand.
• • M. Pourhassan, F. Neumann, C. Qian
  • Special Session on Theory of Bio-inspired Computing (Theory Special Session)
  • 2019 IEEE Congress on Evolutionary Computation (CEC 2019), June 10 - 13, 2019, Wellington, New Zealand.
• • P. S. Oliveto, A. Auger, F. Chicano, C. M. Fonseca
  • Special Issue on Theoretical Foundations of Evolutionary Computation (IEEE TEVC 2019)
  • IEEE Transactions on Evolutionary Computation Special Issue
• • M. Ojeda-Aciego, L. Franco, P. S. Oliveto
  • IEEE Symposium on Foundations of Computational Intelligence (IEEE FOCI 2018)
  • 2018 IEEE Symposium Series on Computational Intelligence (SSCI 2018), November 18 - 21 2018, Bengaluru, India.
• • P. S. Oliveto
  • A Gentle Introduction to the Time Complexity Analysis of Evolutionary Algorithms (Tutorial)
  • 2018 IEEE World Congress on Computational Intelligence (WCCI 2018), July 8 - 13 2018, Rio de Janeiro, Brazil.
• • Y. Yu, C. Qian
  • Pareto Optimization for Subset Selection: Theory and Applications in Machine Learning (Tutorial)
  • 2018 IEEE World Congress on Computational Intelligence (WCCI 2018), July 8 - 13 2018, Rio de Janeiro, Brazil.
• • D. Corus, A. Lissovoi, P. S. Oliveto
  • Theoretical Foundations of Bio-inspired Computation (Theory Special Session)
  • 2018 IEEE World Congress on Computational Intelligence (WCCI 2018), July 8 - 13 2018, Rio de Janeiro, Brazil.
• • L. Franco, M. Ojeda-Aciego, P. S. Oliveto
  • IEEE Symposium on Foundations of Computational Intelligence (IEEE FOCI 2017)
  • 2017 IEEE Symposium Series on Computational Intelligence (SSCI 2017), November 27 - December 1 2017, Hawaii, HI.
• • B. Doerr, P. S. Oliveto
  • Runtime Analysis of Evolutionary Algorithms (Introductory Tutorial)
  • 2017 IEEE Congress on Evolutionary Computation (CEC 2017), June 5 - 8, 2017, Donostia-San Sebastian, Spain.
• • P. K. Lehre, P. S. Oliveto
  • Runtime Analysis of Evolutionary Algorithms (Advanced Tutorial)
  • 2017 IEEE Congress on Evolutionary Computation (CEC 2017), June 5 - 8, 2017, Donostia-San Sebastian, Spain.
• • A. M. Sutton, P. S. Oliveto
  • Theoretical Foundations of Bio-inspired Computation (Theory Special Session)
  • June 5-8, 2017, Donostia-San Sebastian, Spain.
  • Selected accepted papers of the highest quality were invited for extension in a special issue of the Theoretical Computer Science journal published by Elsevier.
• • L. Franco, M. Ojeda-Aciego, P. S. Oliveto
  • IEEE Symposium on Foundations of Computational Intelligence (IEEE FOCI 2016)
  • 2016 IEEE Symposium Series on Computational Intelligence (SSCI 2016)
• • L. Franco, M. Ojeda-Aciego, P. S. Oliveto
  • IEEE Symposium on Foundations of Computational Intelligence (IEEE FOCI 2015)
  • 2015 IEEE Symposium Series on Computational Intelligence (SSCI 2015)
• • P. K. Lehre
  • Runtime Analysis of Population-Based Evolutionary Algorithms (Tutorial)
  • 2015 IEEE Congress on Evolutionary Computation (CEC 2015), May 25 - 28, 2013, Sendai, Japan.
• • F. Neumann, B. Doerr, P. K. Lehre, P. Haddow. (Guest Editors)
  • Special Issue on Theoretical Foundations of Evolutionary Computation (IEEE TEVC 2013)
  • IEEE Transactions on Evolutionary Computation Special Issue
• • C. Cotta, L. Franco, M. Ojeda-Aciego (Programme Chairs)
  • IEEE Symposium on Foundations of Computational Intelligence (IEEE FOCI 2014)
  • 2014 IEEE Symposium Series on Computational Intelligence (SSCI 2014)
• • P. S. Oliveto, A. M. Sutton
  • Theoretical Foundations of Bio-inspired Computation (Theory Special Session)
  • July 6-11, 2014, Beijing, China.
  • Selected accepted papers of the highest quality were invited for extension in a special issue of the Evolutionary Computation journal published by MIT Press.
• • P. S. Oliveto
  • A Gentle Introduction to the Time Complexity Analysis of Evolutionary Algorithms (Tutorial Description)
  • 2014 World Congress on Computational Intelligence (WCCI 2014), July 6, 2014, Beijing, China.
• • B. Doerr
  • Black Box Complexity: A Complexity Theory for Evolutionary Computation (Tutorial Description)
  • 2014 World Congress on Computational Intelligence (WCCI 2014), July 6, 2014, Beijing, China.
• • D. Sudholt
  • Theory of Swarm Intelligence (Tutorial Description)
  • 2014 World Congress on Computational Intelligence (WCCI 2014), July 6, 2014, Beijing, China.
• • B. Mitavskiy, J. He
  • Applications of Markov Chain Methodology in Evolutionary Computation (Tutorial Description)
  • 2014 World Congress on Computational Intelligence (WCCI 2014), July 6, 2014, Beijing, China.
• • P. S. Oliveto, A. M. Sutton
  • Theoretical Foundations of Bio-inspired Computation (Theory Special Session)
  • 2013 IEEE Congress on Evolutionary Computation (CEC 2013), June 20 - 23, 2013, Cancún, México.
• • P. S. Oliveto
  • A Gentle Introduction to the Time Complexity Analysis of Evolutionary Algorithms (Tutorial Description)
  • 2013 IEEE Congress on Evolutionary Computation (CEC 2013), June 20 - 23, 2013, Cancún, México.
• • A. Moraglio
  • The Geometry of Evolutionary Algorithms: Unification and Theory-Laden Design (Tutorial Description)
  • 2013 IEEE Congress on Evolutionary Computation (CEC 2013), June 20 - 23, 2013, Cancún, México.
• • T. Friedrich
  • Theoretical Foundations of Evolutionary Multi-Objective Optimization (Tutorial Description)
  • 2013 IEEE Congress on Evolutionary Computation (CEC 2013), June 20 - 23, 2013, Cancún, México.
• • P. K. Lehre
  • Drift Analysis of Evolutionary Algorithms (Tutorial Description)
  • 2013 IEEE Congress on Evolutionary Computation (CEC 2013), June 20 - 23, 2013, Cancún, México.
• • 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).

Books


 
 
 
• • Theory of Evolutionary Computation~Recent Developments in Discrete Optimization
  • B. Doerr and F. Neumann editors, Springer, Natural Computing Series, 2020. (book web-page)
 
 

 
 
• • Z.-H. Zhou, Y. Yu, C. Qian
  • Evolutionary Learning: Advances in Theories and Algorithms,
  • Springer, 2019. (book web-page)
 
 

 
 
• • T. Jansen
  • Analyzing Evolutionary Algorithms. The Computer Science Perspective,
  • Springer, Natural Computing 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 Computing 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.

If you want to join the task force or if you have any questions, please contact martin.krejca@polytechnique.edu.