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

Burton, Justin Y. J. (Spring 2021)

Permanent URL: https://etd.library.emory.edu/concern/etds/s4655h84c?locale=es
Published

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
Department
Degree
Submission
Language
  • English
Research Field
Palabra Clave
Committee Chair / Thesis Advisor
Committee Members
Última modificación

Primary PDF

Supplemental Files