Second online lecture 03-11

The second lecture takes place on the 3rd of November 2021 at 4:30 PM (CET), virtually.

The zoom link to register and attend the lecture is:

The lecture will be given by professor Darrell Whitley, here’s the info:

Next Generation Genetic Algorithms

New developments in Gray Box Optimization makes it possible to construct new Genetic Algorithms that do not use random mutation or random recombination. Instead, for certain classes of NP Hard problems, it is possible to exactly compute the location of improving moves in constant time, and to use highly efficient forms of greedy deterministic recombination. In some domains, this makes random mutation and random recombination obsolete. Deterministic “Partition Crossover” can be applied to k-bounded pseudo-Boolean optimization problems such as MAXSAT and NK Landscapes as well as problems such as the Traveling Salesman Problem. Partition Crossover locally decomposes a recombination graph into q subgraphs in O(n) time. It can then identify the best of 2^q possible offspring. For example, for q=40, partition crossover returns the best of one trillion possible offspring. If the parents are local optima, all offspring are also guaranteed to be locally optimal in the largest hyperplane subspace containing both parents. This allows partition crossover to directly “tunnel” between local optima, moving directly from local optimum to local optimum. On adjacent NK-Landscapes, this approach find the global optimum on problems with 1 million variables. New work has shown how certain large industrial and “crafted” MAX-kSAT problems can be optimized using these methods: the results are competitive with or improve on the current state of the art Iterative Local Search Methods.

Download the slides

Darrell Whitley is a Professor of Computer Science at Colorado State University. He served as the Chair of the International Society of Genetic Algorithm from 1993 to 1997, and as the Editor-in-Chief of the journal Evolutionary Computation from 1997 to 2003. He was Chair of the Governing Board of ACM SIGEVO from 2007 to 2011. He was named an ACM Fellow in 2019 for his contributions to the field of genetic and evolutionary computation. He has also received the 2022 IEEE Pioneer Award in Evolutionary Computation.