Title page for ETD etd-06062008-152638
|Type of Document
||Johnson, Alan W.
||Generalized hill climbing algorithms for discrete optimization problems
||Industrial and Systems Engineering
|Jacobson, Sheldon H.
|Allison, Donald C. S.
|Blanchard, Benjamin S. Jr.
|Sarin, Subhash C.
|Sherali, Hanif D.
- simulated annealing
- hill climbing algorithms
- discrete optimization
- combinatorial optimization
|Date of Defense
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 ).
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
|| Approximate Download Time
| 28.8 Modem
|| 56K Modem
|| ISDN (64 Kb)
|| ISDN (128 Kb)
|| Higher-speed Access
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.
If you have questions or technical
problems, please Contact DLA.