Research project "Bridging the Gap between Theory and Practice in Nature-inspired Algorithms"

Funding agency and no.: Danish Council for Independent Research (DFF), 4002-00542

Abstract

Nature-inspired algorithms such as evolutionary algorithms and ant colony optimization form a class of "off-the-shelf" heuristics for optimization applied in practice when no problem-specific algorithm is available. Despite huge empirical knowledge about nature-inspired algorithms, there is only little theoretically guided advice on the design and application of such algorithms. In particular, existing theory gives little advice on the choice of the abundant parameters that nature-inspired algorithms come with. The aim of this research project is to bridge the gap between theory in practice in nature-inspired algorithms by developing a practically applicable theory of complexity and parameter choice. Results are envisaged which analyze the efficiency on classes of problems for realistic problem sizes and determine the influence of common parameters such as search operators and population size. Such results are expected to improve the design of nature-inspired algorithms and their applicability when optimization problems have to be solved in our society.

Staff

Carsten Witt - principal investigator
Christian Gießen - PhD student

News

August 20, 2014: Recruitment process finished
October 1, 2014: Project starts; PhD student Christian Gießen starts
March 2015: Research article "Population Size vs. Mutation Strength for the (1+λ) EA on OneMax" by Christian Gießen and Carsten Witt accepted as full paper in the Theory Track at the Genetic and Evolutionary Computation Conference (GECCO 2015), Madrid, July 11-15, 2015
July 2015: Christian attended GECCO 2015 conference in Madrid
September 2015: Carsten and Christian attended 9th Workshop on Theory of Randomized Search Heuristics (ThRaSH 2015) in Sheffield, UK
March 2016: Carsten and Christian organized the 10th ThRaSH Workshop at DTU.
April 2016: Research article "Optimal Mutation Rates for the (1+λ) EA on OneMax" by Christian Gießen and Carsten Witt accepted as full paper in the Theory Track at the Genetic and Evolutionary Computation Conference (GECCO 2016), Denver, July 20-24, 2016
September 2016: Research article "The Interplay of Population Size and Mutation Probability in the (1+λ) EA on OneMax" by Christian Gießen and Carsten Witt published as journal article in Algorithmica journal
January 2017: Carsten co-organized FOGA 2017
March 2017: Research article "The (1+λ) Evolutionary Algorithm with Self-Adjusting Mutation Rate" by Benjamin Doerr, Christian Gießen, Carsten Witt and Jing Yang accepted as full paper in the Theory Track at the Genetic and Evolutionary Computation Conference (GECCO 2017), July 15-19, 2017
March 2017: Research article "Upper Bounds on the Runtime of the Univariate Marginal Distribution Algorithm on OneMax" by Carsten Witt accepted as full paper in the Theory Track at the Genetic and Evolutionary Computation Conference (GECCO 2017), July 15-19, 2017
December 2017: Christian Gießen successfully defended his PhD thesis, which includes several research results obtained in the project.