FOGA 2021

The FOGA conference series aims at advancing the understanding of the working principles behind Evolutionary Algorithms and related Randomized Search heuristics. It is a premier event to discuss advances in the theoretical foundations of these algorithms, corresponding tools and frameworks suitable to analyze them, and different aspects of comparing algorithm performance.

FOGA2021 will be an virtual event. 
Yet, we will do our best to provide a pleasant and exciting conference experience.

 Brief Guideline to Virtual Conference Implementation

FOGA2021 Proceedings in the ACM Digital Library

Pre-Proceedings download

 Call-for-Papers

 

Keynotes

We are very excited to welcome the following keynote speakers

Tim Roughgarden

Data-Driven Algorithm Design

Abstract

The best algorithm for a computational problem generally depends on the “relevant inputs”, a concept that depends on the application domain and often defies formal articulation. While there is a large literature on empirical approaches to selecting the best algorithm for a given application domain, there has been surprisingly little theoretical analysis of the problem.

We adapt concepts from statistical and online learning theory to reason about application-specific algorithm selection. Our models are straightforward to understand, but also expressive enough to capture several existing approaches in the theoretical computer science and AI communities, ranging from self-improving algorithms to empirical performance models. We present one framework that models algorithm selection as a statistical learning problem, and our work here shows that dimension notions from statistical learning theory, historically used to measure the complexity of classes of binary- and real-valued functions, are relevant in a much broader algorithmic context. We also study the online version of the algorithm selection problem, and give possibility and impossibility results for the existence of no-regret learning algorithms.

Joint work with Rishi Gupta.

Biography 

Tim Roughgarden is a Professor of Computer Science and member of the Data Science Institute at Columbia University. Prior to joining Columbia, he spent 15 years on the computer science faculty at Stanford, following a PhD at Cornell and a postdoc at UC Berkeley. His research interests include the many connections between computer science and economics, as well as the design, analysis, applications, and limitations of algorithms. For his research, he has been awarded the ACM Grace Murray Hopper Award, the Presidential Early Career Award for Scientists and Engineers (PECASE), the Kalai Prize in Computer Science and Game Theory, the Social Choice and Welfare Prize, the Mathematical Programming Society's Tucker Prize, and the EATCS-SIGACT Gödel Prize. He was an invited speaker at the 2006 International Congress of Mathematicians, the Shapley Lecturer at the 2008 World Congress of the Game Theory Society, and a Guggenheim Fellow in 2017. He has written or edited ten books and monographs, including Twenty Lectures on Algorithmic Game Theory (2016), Beyond the Worst-Case Analysis of Algorithms (2020), and the Algorithms Illuminated book series (2017-2020).

Adi Livnat

 

 

Sex, recombination and the fundamental nature of mutation

Abstract

The role of sexual recombination in evolution has been called "the queen of problems" in evolutionary biology. Although multiple hypotheses for it have been proposed during the 20th century, none has been able to account for the prevalence of sex in nature. At the same time, a sea of change is underway regarding our empirical knowledge on the nature of genetic change in biological evolution.

In this talk, I will discuss a new way of thinking about the role of sexual recombination in biological evolution and how it made an interdisciplinary contribution by motivating the development in computer science of a key breakthrough that, together with other breakthroughs, enabled the deep learning revolution. In addition, I will discuss new evidence from my lab on the fundamental nature of mutation and how mutation and recombination may be connected. Sexual recombination and mutation are two of the three most basic elements of evolution, the third being selection. Thus, the implications of a new understanding of them reach beyond biological evolution and could inform new developments in evolutionary computation as well, in addition to holding promise for contributing to the understanding of genetic disease and cancer.   

Joint work (in several papers) with Christos Papadimitriou, Nick Pippenger, Marc Feldman, Jonathan Dushoff, Umesh Vazirani, Erick Chastain and Liudmyla Vasylenko

Biography 

Adi Livnat received his undergraduate degree in Biology from Stanford University, his Ph.D. in Ecology and Evolutionary Biology from Princeton University, and was a Miller Fellow at the Miller Institute for Basic Research in Science at UC Berkeley in the Computer Science Division. He is currently a Associate Professor at the Department of Evolutionary and Environmental Biology and the Institute of Evolution at the University of Haifa in Israel. He studies fundamental questions regarding the process of evolution and how it leads to the complexity of life. He has proposed a new way of looking at the biological evolutionary process – interaction-based evolution – based on a re-examination of biological recombinational and mutational mechanisms. His lab employs a wide range of techniques to study mutation and recombination, from mathematical models to cutting-edge experimental methods, while at the same time working to expand the bridge between evolutionary biology and theoretical computer science and to examine the evolutionary process through the computational lens. Questions of interest include the role of sexual recombination in evolution, the fundamental nature of mutation and the potential connection between these two century-old problems.

Accepted papers

We look forward to the following authors presenting their excellent work at FOGA 2021:

  • Laurent Meunier, Iskander Legheraba, Yann Chevaleyre and Olivier Teytaud. Asymptotic convergence rates for averaging strategies
  • Carsten Witt. On Crossing Fitness Valleys with Majority-Vote Crossover and Estimation-of-Distribution Algorithms*
  • Luke Branson and Andrew Sutton. Focused Jump-and-Repair Constraint Handling for Fixed-Parameter Tractable Graph Problems*
  • Dogan Corus, Pietro S. Oliveto and Donya Yazdani. Automatic Adaptation of Hypermutation Rates for Multimodal Optimisation
  • Mario Alejandro Hevia Fajardo and Dirk Sudholt. Self-Adjusting Offspring Population Sizes Outperform Fixed Parameters on the Cliff Function*
  • Nils Müller and Tobias Glasmachers. Non-Local Optimization: Imposing Structure on Optimization Problems by Relaxation
  • Jonathan Heins, Jakob Bossek, Janina Pohl, Moritz Seiler, Heike Trautmann and Pascal Kerschke. On the Potential of Normalized TSP Features for Automated Algorithm Selection*
  • Jakob Bossek and Dirk Sudholt. Do Additional Optima Speed Up Evolutionary Algorithms?
  • Adel Nikfarjam, Jakob Bossek, Aneta Neumann and Frank Neumann. Computing Diverse Sets of High Quality TSP Tours by EAX-Based Evolutionary Diversity Optimisation
  • Denis Antipov and Naumov Semen. The Effect of Non-symmetric Fitness:The Analysis of Crossover-Based Algorithms on RealJump Functions

The * markers indicate the nomination for the FOGA2021 best paper award. The winner will be determined by online voting during the conference.

Click here to acess the FOGA2021 Proceedings in the ACM Digital Library

Program

The conference program is now available below. 

As a virtual event FOGA2021 is realized using the MS teams platform. The following document provides some useful information on the conference implementation.  Brief Guideline to Virtual Conference Implementation

In case of questions, don't hesitate to contact the organizers.

Time (UTC+2h)Topic / TitleSpeaker
12:00 - 12:30OpeningOrganizers
12:30 - 13:30Non-Local Optimization: Imposing Structure on Optimization Problems by RelaxationNils Müller and Tobias Glasmachers
14:00 - 15:30Keynote: Sex, recombination and the fundamental nature of mutationAdi Livnat
16:00 - 17:00Asymptotic Convergence Rates for Averaging StrategiesLaurent Meunier, Iskander Legheraba,
Yann Chevaleyre and Olivier Teytaud
17:30 - 18:30Do Additional Optima Speed Up Evolutionary Algorithms?Jakob Bossek and Dirk Sudholt

 

Time (UTC+2h)Topic / TitleSpeaker
10:00 - 11:00Computing Diverse Sets of High Quality TSP Tours by EAX-Based Evolutionary Diversity OptimisationAdel Nikfarjam, Jakob Bossek, Aneta Neumann and Frank Neumann
11:30 - 12:30The Effect of Non-symmetric Fitness:The Analysis of Crossover-Based Algorithms on RealJump FunctionsDenis Antipov and Naumov Semen
15:00 - 16:00On the Potential of Normalized TSP Features for Automated Algorithm SelectionJonathan Heins, Jakob Bossek, Janina Pohl, Moritz Seiler, Heike Trautmann and Pascal Kerschke
16:30 - 17:30Focused Jump-and-Repair Constraint Handling for Fixed-Parameter Tractable Graph ProblemLuke Branson and Andrew Sutton 

 

Time (UTC+2h)Topic / TitleSpeaker
10:00 - 11:00On Crossing Fitness Valleys with Majority-Vote Crossover and Estimation-of-Distribution AlgorithmsCarsten Witt
11:30 - 12:30Self-Adjusting Offspring Population Sizes Outperform Fixed Parameters on the Cliff FunctionMario Alejandro Hevia Fajardo and Dirk Sudholt
15:00 - 16:00Automatic Adaptation of Hypermutation Rates for Multimodal OptimisationDogan Corus, Pietro S. Oliveto and Donya Yazdani
16:30 - 18:00Keynote: Data-Driven Algorithm Design Tim Roughgarden 
18:00 - 18:30ClosingOrganizers

 

Return to FOGA 2021 main page