CEC 2013 Fiesta Americana Grand Coral Beach Hotel Grand Coral Ballroom Chichen Itza and Tulum Isla Contoy Isla Mujeres Ruinas del Rey Cozumel and Hel-Ha Kayaking and Windsurfing Tres rios and Actun Chen

Tutorial

Fast, Powerful Non-Random Search Operators: Constant Time Improving Moves and Exponentially Powerful Recombination

Darrell Whitley
Professor, Chair of the Department of Computer Science
Colorado State University



Abstract:

The field of Evolutionary Computation has long accepted that changes based on random mutation and random recombination are both necessary and fundamental to Evolutionary Algorithms. However, in a number of different domains it is possible to compute the best or approximate best improving move in constant time. This includes all problems that directly map to k-­‐bounded pseudo Boolean optimization. Such problems include weighted MAXSAT, NK-­‐Landscapes, Spin Glass problems, vertex cover, subset sum, maximum independent set, set covering, maximum cut, signed graph balancing, quadratic optimization, as well as variants of hardware and software verification, model checking, AI planning, and graph coloring.

All of these problems share the hypercube as the neighborhood adjacency graph. It can be shown that all k-­‐bounded pseudo-­‐Boolean optimization problems are a superposition of k Elementary Landscapes. The evaluation function can be decomposed into k subfunctions, each of which is an eigenvector of the Graph Laplacian of the search space. Building on this decomposition, it is possible to 1) evaluate new moves in constant time, 2) identify improving moves in constant time, and 3) compute the average over neighborhoods 2 moves ahead in constant time. It is also possible to compute low order statistical moments (variance and skew) in polynomial time over generalized Hamming Spheres of the search space. It is also possible to exactly compute low order hyperplane averages in constant time, which can be used to characterize global trends in the search space. This has made it possible to construct a new generation of extremely powerful search algorithms that easily scale to very large problems. The resulting methods yield improvements over the best MAXSAT solvers (such as AdaptG^2WSAT, and GSAT) and NK-­‐Landscape solvers, particularly on large real world problems of a million or more variables.

Decomposability can also be exploited by recombination. A new recombination operator for the Traveling Salesman Problem partitions the recombination graph into q partitions; in O(n) time it can then identify the best of 2^q possible offspring. If the parents are local optima, then the majority of offspring are also local optima. This allows search to rapidly surge forward after a small number of local optima are located; the resulting search improves on the best methods in the world, such as the Lin-­‐Kernigham-­‐Helsgaun algorithm.

 

Biography:

Prof. Darrell Whitley has been active in Evolutionary Computation since 1986, and has published more than 200 papers. These papers have garnered more than 13,000 citations. Dr. Whitley’s H-­‐index is 50. He has served as Editor-­‐in-­‐Chief of the journal Evolutionary Computation, and recently served as Chair of the Governing Board of ACM Sigevo from 2007 to 2011. He currently serves as an Associate Editor of Artificial Intelligence.

 

The length of the tutorial:
two hours.

//

Theme by Danetsoft and Danang Probo Sayekti inspired by Maksimer