Title page for ETD etd-06062008-152638


Type of Document Dissertation
Author Johnson, Alan W.
URN etd-06062008-152638
Title Generalized hill climbing algorithms for discrete optimization problems
Degree PhD
Department Industrial and Systems Engineering
Advisory Committee
Advisor Name Title
Jacobson, Sheldon H. Committee Chair
Allison, Donald C. S. Committee Member
Blanchard, Benjamin S. Jr. Committee Member
Sarin, Subhash C. Committee Member
Sherali, Hanif D. Committee Member
Keywords
  • simulated annealing
  • hill climbing algorithms
  • discrete optimization
  • combinatorial optimization
  • convergence
  • heuristics
Date of Defense 1996-10-01
Availability restricted
Abstract
Generalized hill climbing (GHC) algorithms are introduced, as a tool to address difficult discrete optimization problems. Particular formulations of GHC algorithms include simulated annealing (SA), local search, and threshold accepting (T A), among. others. A proof of convergence of GHC algorithms is presented, that relaxes the sufficient conditions for the most general proof of convergence for stochastic search algorithms in the literature (Anily and Federgruen [1987]).

Proofs of convergence for SA are based on the concept that deteriorating (hill climbing) transitions between neighboring solutions are accepted by comparing a deterministic function of both the solution change cost and a temperature parameter to a uniform (0,1) random variable. GHC algorithms represent a more general model, whereby deteriorating moves are accepted according to a general random variable. Computational results are reported that illustrate relationships that exist between the GHC algorithm's finite-time performance on three problems, and the general random variable formulations used. The dissertation concludes with suggestions for further research.

Files
  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
[VT] LD5655.V856_1996.J646.pdf 4.01 Mb 00:18:33 00:09:32 00:08:21 00:04:10 00:00:21
[BTD] next to an author's name indicates that all files or directories associated with their ETD are accessible from the Virginia Tech campus network only.

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.