Modern Gray Box Optimization makes it possible to construct new forms of Genetic Algorithms that do not use random mutation or random recombination. For certain classes of NP Hard problems (ranging from MAXSAT to QUBO to Machine Scheduling to the Traveling Salesman Problem), it is possible to exactly compute the location of improving moves, sometimes in constant time.

New results show that there are additional decompositions that can be exploited by intelligent recombination operators such as “Partition Crossover” (PX). New methods are able to “break” critical nonlinear interactions such that the nonlinear interactions cancel, or otherwise have no effect during crossover. PX can identify the best of 2q. New results also show how PX can be applied to new problems, such as single machine scheduling as well as a subset of QAP problems. Under PX, if the parents are local optima, the offspring are guaranteed to be locally optimal in smallest hyperplane subspace containing both parents. New theoretical results also show why offspring are more likely than not to also be local optima in the full space. This allows partition crossover to directly “tunnel” between local optima, moving directly from local optimum to local optimum. Recent theoretical results also show that the local optima for combinatorial problems are largely arranged in a hierarchically organized lattice structure. New mathematics has also been developed that uses linear equations to evaluate local minima that are organized into lattices. Finally, these methods can also make it possible to construct new and more efficient local search operators as well.

The tutorial will also show how “transforms” can be used to convert any pseudo-Boolean function (with a polynomial description) into k-bounded pseudo-Boolean functions, including the QUBO functions frequently used in quantum computing . This makes it possible to use more powerful evolutionary algorithms which can exploit k-bounded nonlinearity.