Title page for ETD etd-08042000-14590003


Type of Document Dissertation
Author Vaughan, Diane Elizabeth
URN etd-08042000-14590003
Title Simultaneous Generalized Hill Climbing Algorithms for Addressing Sets of Discrete Optimization Problems
Degree PhD
Department Industrial and Systems Engineering
Advisory Committee
Advisor Name Title
Jacobson, Sheldon H. Committee Co-Chair
Koelling, Charles Patrick Committee Co-Chair
Bish, Ebru K. Committee Member
Nachlas, Joel A. Committee Member
Rogers, Robert C. Committee Member
Keywords
  • Traveling Salesman Problem
  • Ergodicity
  • Local Search
  • Markov Chains
  • Simulated Annealing
  • Generalized Hill Climbing Algorithms
  • Manufacturing Applications
Date of Defense 2000-07-31
Availability unrestricted
Abstract
Generalized hill climbing (GHC) algorithms provide a framework for using local search algorithms to address intractable discrete optimization problems. Many well-known local search algorithms can be formulated as GHC algorithms, including simulated annealing, threshold accepting, Monte Carlo search, and pure local search (among others).

This dissertation develops a mathematical framework for simultaneously addressing a set of related discrete optimization problems using GHC algorithms. The resulting algorithms, termed simultaneous generalized hill climbing (SGHC) algorithms, can be applied to a wide variety of sets of related discrete optimization problems. The SGHC algorithm probabilistically moves between these discrete optimization problems according to a problem generation probability function. This dissertation establishes that the problem generation probability function is a stochastic process that satisfies the Markov property. Therefore, given a SGHC algorithm, movement between these discrete optimization problems can be modeled as a Markov chain. Sufficient conditions that guarantee that this Markov chain has a uniform stationary probability distribution are presented. Moreover, sufficient conditions are obtained that guarantee that a SGHC algorithm will visit the globally optimal solution over all the problems in a set of related discrete optimization problems.

Computational results are presented with SGHC algorithms for a set of traveling salesman problems. For comparison purposes, GHC algorithms are also applied individually to each traveling salesman problem. These computational results suggest that optimal/near optimal solutions can often be reached more quickly using a SGHC algorithm.

Files
  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  dianeetd.pdf 887.90 Kb 00:04:06 00:02:06 00:01:50 00:00:55 00:00:04
  vita.pdf 3.30 Kb < 00:00:01 < 00:00:01 < 00:00:01 < 00:00:01 < 00:00:01

Browse All Available ETDs by ( Author | Department )

dla home
etds imagebase journals news ereserve special collections
virgnia tech home contact dla university libraries

If you have questions or technical problems, please Contact DLA.