Extremal Optimization
for Low-Energy Excitations
of very large Spin-Glasses

Stefan Boettcher

Dept of Physics

Collaborators:

Senior:

Allon Percus (Los Alamos)

Paolo Sibani (Odense-DK)

Michelangelo Grigni (Emory/CS)

(Pre-)Prints: www.physics.emory.edu/faculty/boettcher

Students:

Gabriel Charvat (Emory/Phy)

Susannah Cooke (Emory/Phy)

Martin Frank (Emory/Phy)

Support: NSF-DMR

Summary:

EO for Mean-Field Glasses (SK) (n≤1000)

Spin Glass Ground States with ~106 Spins

EO for Defect Energies of Glasses in d=3,..,7

Comparison with Mean-Field (d→∞) limit

Result: Mean-Field Prediction fails

Poster:

EO vs Metropolis: Energy-Landscape Explorations

EO of MAX-3-Coloring at Phase Transition

EO for the Thomson Problem

Theory of EO

Applications of Extremal Optimization (EO)

Here:

Extremal Optimization (EO)

Motivated by Self-Organized Criticality

Emergent Structure

without tuning any Control Parameters

despite (or because of) Large Fluctuations

How can we use it to optimize?

Extremal Driving:

Select and eliminate the “bad”,

Replace it at random,

Eventually, only the “good” is left!

 Evolutionary Search Heuristic

Spin Glasses (eg. MAX-CUT):

λi = xi ∑j Ji,j xj

Cost ∝ H = -∑i λi

Coloring (eg. Potts Anti-ferro):

λi = - (#-monochrome edges of xi)

xi

Partitioning (eg. MIN-CUT):

λi = - (#-cut edges of xi)

xi

xi

“Fitness” λ for various Problems:

>> “Extremal Optimization” (EO): <<

(1) Provide initial Configuration S=(x1,...,xn),

(3) Rank all i=∏(k) according to

λ∏(1) ≤ λ∏(2) ≤ ... ≤ λ∏(n)

(2) Determine “Fitness” λi for each Variable xi ,

(6) For tmax times, Repeat at (2),

(5) Update xw unconditionally,

(4) Select xw w/ w=∏(1), i.e. xw has worst Fitness!

(7) Return: Best Cost(S) found along the way!

τ-EO - Searching at the “Ergodic Edge”:

For Ranks λ∏(1) ≤ ... ≤ λ∏(n), update i=∏(k) with

scale-free, power-law distribution

<Cost>

τ

P(k) ∝ k-τ

0←τ

random walk,

too ergodic

τ→∞

greedy + frozen,

non-ergodic

τ–1~

“ergodic edge”

τ-EO for Sherrington-Kirkpatrick (SK):

Mean-Field (d→∞) Spin Glasses:

Parisi's RSB

Scaling Correction

ω=2/3

Kondor ('83)

Fluctuation Exponent

θf=3/4

Ground State E0

Ground State E0 E0'

Reverse Bonds (Perturb) on scale L

Lattice Spin Glasses (at T=0):

Defect-Energy:

⇨Low-Energy Excitations (like “small Oscillations”)

Measure Energy Fluctuations ΔE(L)

Reverse Bonds (Perturb) on scale L

Measure “Stiffness”: σ(ΔE)~ Ly

⇨Low-Energy Excitations on bond-diluted Lattices

After:

5 spins

Before:

100 spins

Lattice Spin Glasses (at T=0):

Defect-Energy:

How bond-diluted Lattices?

Measure “Stiffness”: σ(ΔE)~ Ly

Tg

pc

Why bond-diluted Lattices?

Simpler Problem

Larger Sizes L

Better Scaling

T=0

Defect-Energy of diluted Lattices:

“Stiffness”: σ(ΔE)~ Ly

Stiffness Exponent y for Lattice Glasses:

Reduction plus τ-EO for dilute-Lattice ±J Glasses:

d=3

d= 4

d=5

d=6

d=7 (!)

Comparing with Mean-Field Theory:



“Stiffness”: σ(ΔE)~ Ly

yRSB = d(1-θf)

Cinderella Cluster:



18 Boxes w/ AthlonXP (2GHz), 512 Mb, no HD, Video, etc

1 Server w/ P4, 1Gb, RAID5, Tape, etc

Diskless NetBoot over fast Switch

QUANTIAN_4.6.0.9 (Debian) w/

TerminalServer

OPENMOSIX loadbalancer

MPI for parallel processing

Cost: ~$8,000

2004-02-16T02:04:00