Joint Lectures on Evolutionary Algorithms (JoLEA) - Next Generation Genetic Algorithms
- Darrell Whitley
- Wednesday 3 November 2021
Joint Lectures on Evolutionary Algorithms (JoLEA) is a new series of top-quality lectures on EAs that will feature world-renowned speakers, local researchers, and PhD students. It’s a joint initiative by Leiden University, CWI, Utrecht University and VU Amsterdam.
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.
For more info and to stay up to date with the latest news, visit the JoLEA website.
About Darrell Whitley
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.