Optimization Heuristics for Cost Function Minimization: Extremal and Hysteretic Optimization

Event Sponsor: 
Mathematics and Computer Science Division Seminar
Start Date: 
Feb 29 2008 (All day)
Building/Room: 
Building 221 Conference Room A216
Location: 
Argonne National Laboratory
Speaker(s): 
Bruno Goncalves
Speaker(s) Title: 
Emory University
Host: 
Mihai Anitescu

A wide range of problems can be formulated in terms of determining the minimal value of a cost function defined in terms of discrete two valued variables. Examples from Physics, Mathematics and Computer Science include the Constraint Satisfaction Problem, the Voter Model, and finding the ground state of magnetic systems. We present two
distinct algorithms that can be applied to this class of problems, and analyze their performance. Extremal Optimization performs a search of solution space, not by preserving the best adjusted variables, but by eliminating the worst. This approach preserves enough variability to
keep the algorithm from becoming stuck in poor local minima.
Hysteretic Optimization, on the other hand, uses a global field to drive the system through barriers and force it to explore solution space in search of the global minimum. The dynamics of each method are analyzed and advantages and disadvantages are presented.

Miscellaneous Information: