Extremal Optimization for Ground States of the Three-Spin Mean Field Spin Glass Public

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

Rights statement

• Permission granted by the author to include this thesis or dissertation in this repository. All rights reserved by the author. Please contact the author for information regarding the reproduction and use of this thesis or dissertation.

School	Emory College
Department	Physics
Degree	B.S.
Submission	Honors Thesis
Language	English
Research Field	Physics, General
Mot-clé	extremal optimization spin glass
Committee Chair / Thesis Advisor	Boettcher, Stefan, Emory University
Committee Members	Brody, Jed, Emory University Sussman, Daniel, Emory University

Dernière modification

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	Press to Select an action Download

Supplemental Files

Thumbnail	Title	Date Uploaded	Actions