A New Method for Heuristic Evaluation by Means of Finite Size Scaling Público

Abstract

We develop a new method for evaluating the efficacy of NP-hard optimization heuristics as an alternative to testbed heuristic evaluation. The new method evaluates heuristics using finite-size scaling by extrapolating the observed relationship between resource utilization and maximum system size with optimized solutions to larger system sizes. This improves upon testbed heuristic evaluation by providing better evaluation of average-case problems and providing insight into proper resource allocation to efficiently find heuristic solutions. We demonstrate this on the parallel tempering algorithm for the Edwards-Anderson model of a hypercubic spin-glass with periodic boundary conditions and bimodal bond distribution. We run the parallel tempering algorithm with different time resources and observe the system sizes where the algorithm deviates from the accepted ground state energies. We observe deviations between systems sizes with 343 spins and 729 spins for between 125 and 3000 time steps of the parallel tempering algorithm. This information is extrapolated to evaluate the efficacy of the parallel tempering algorithm at finding ground states of larger spin-glasses. 

Table of Contents

Introduction 1

NP-Hard Problems and Heuristics 1

Heuristic Evaluation Methods 2

The Edwards-Anderson Spin Glass 3

The Parallel Tempering Algorithm 6

Methods 7

Language and Methods for Algorithm Development 7

Distribution of Temperatures 8

Multithreaded Programming 9

Finding Ground States 9

Results 10

Conclusions 12

References 13

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
Palabra Clave	Heuristic Spin Glass Statistical Physics Parallel Tempering NP-Hard Finite Size Scaling
Committee Chair / Thesis Advisor	Boettcher, Stefan, Emory University
Committee Members	Grigni, Michelangelo, Emory University Seitaridou, Effrosyni, Emory University Burton, Justin C., Emory University

Última modificación

Primary PDF

Thumbnail	Title	Date Uploaded	Actions
	A New Method for Heuristic Evaluation by Means of Finite Size Scaling ()	2021-04-29 00:41:02 -0400	Press to Select an action Download

Supplemental Files

Thumbnail	Title	Date Uploaded	Actions