Extremal Optimization for Ground States of the Three-Spin Mean Field Spin Glass Open Access
Lau, Ginger (Spring 2024)
Abstract
While the ground state energy of the p=2 mean field spin glass has been analytically obtained by Parisi, the analogous p=3 spin glass has not yet been solved. Instead, a variety of numerical methods, simulations, and heuristics have been developed to approximate complex combinatorial optimization problems such as spin glasses. This honors thesis project applied the extremal optimization (EO) heuristic to estimate the ground state energy of the three-spin mean field spin glass. In this research, two key modifications were made to the existing version of EO. First, multiple spins are now flipped at each time step in a parallelized update scheme to increase efficiency. Second, an auxiliary matrix is now used to hold intermediate fitness calculations and reduce run duration. The heuristic contains two tuning parameters: t, total number of update steps, and τ, a parameter to determine how many spins to flip once the system reaches a local minimum. Values for these quantities were chosen to be t=(0.3)N^3 and τ=1.4. Applying the modified EO to system sizes up to N≈100, the ground state energy density of the three-spin mean field spin glass in the N→∞ limit was obtained to be ⟨e⟩=−0.4708(1). This value is within a 0.001 error of previous studies in the literature. The finite-N scaling correction was obtained to be ω=4/5 through fitting methods.
Table of Contents
Chapter 1: Introduction 1
Chapter 2: Background 3
2.1 Extremal Optimization 3
2.1.1 Self-Organized Criticality 4
2.2 Spin Glasses 5
Chapter 3: Approach 7
3.1 Three-Spin SK Model 7
3.2 Three-Spin Extremal Optimization 7
3.3 EO Heuristic Initialization 9
3.4 EO Heuristic Update Procedure 11
3.4.1 Code Development: Parallel Spin Updates 12
3.4.2 Parallel Spin Update Scheme 13
3.4.3 Code Development: Auxiliary Matrix 13
3.4.4 Fitness Update Scheme 15
Chapter 4: Experiments 16
4.1 Runtime and τ Test 16
4.1.1 Optimal τ Value 17
4.1.2 Optimal Runtime 18
4.2 Testing Solvable Models: Ferromagnet 19
4.3 Branch-and-bound for Solvable Models 19
Chapter 5: Results and Analysis 22
5.1 Production Runs 22
5.2 Ground State Energy Density and Finite-Size Corrections 22
5.3 General Mean Field Spin Glass Ground States 25
Chapter 6: Conclusion 26
Appendix A 28
Appendix B 29
Bibliography 30
About this Honors Thesis
| School | |
|---|---|
| Department | |
| Degree | |
| Submission | |
| Language |
|
| Research Field | |
| Keyword | |
| Committee Chair / Thesis Advisor | |
| Committee Members |
Primary PDF
| Thumbnail | Title | Date Uploaded | Actions |
|---|---|---|---|
|
|
Extremal Optimization for Ground States of the Three-Spin Mean Field Spin Glass () | 2024-04-11 12:37:17 -0400 |
|
Supplemental Files
| Thumbnail | Title | Date Uploaded | Actions |
|---|