Analysis of Black-Box Algorithms
Tuesday, March 14, 2017
4-5 p.m., Avery 115
3:30 p.m., Avery 348
Andrew Sutton, Ph.D.Postdoctoral Researcher, University of Potsdam, Germany
Black-box algorithms are general-purpose techniques for solving search and optimization problems under conditions in which little or no problem-specific information is available. Very often, these techniques are inspired by natural processes such as biological evolution. Recently there has also been a renewed interest in applying methods from computer science to problems in evolutionary biology by viewing evolution as a computational process. These processes can then be examined by standard tools from the analysis of algorithms. In this talk I will present some exciting recent work coming out of a three year interdisciplinary project between theoretical population genetics and the theory of evolutionary algorithms. I will sketch a few results to demonstrate how clues from biological models can help to understand the time complexity of some black-box algorithms on certain problems. Finally, I will discuss ways to build bridges between theory and practice by studying instance distributions that are closer to real-world problems.
Andrew M. Sutton is currently a postdoctoral researcher in the Algorithm Engineering group at the Hasso Plattner Institute of the University of Potsdam, Germany. He leads the Evolutionary Computation group at the institute, where his work was sponsored by the interdisciplinary SAGE project funded by the EU Seventh Framework Programme for Research and Technological Development. He received his Ph.D. in computer science from Colorado State University in 2011 under the supervision of Darrell Whitley and Adele Howe. He previously held a postdoctoral fellowship at the University of Adelaide in Australia with Frank Neumann. His research takes an algorithmic approach to studying randomized search heuristics for combinatorial optimization, and he maintains a particular interest in the analysis of interdisciplinary problems and work that bridges theory and practice.