Johnson, Alan W.2014-03-142014-03-141996-10-01etd-06062008-152638http://hdl.handle.net/10919/38064Generalized 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.ix, 128 leavesBTDapplication/pdfenIn Copyrightsimulated annealinghill climbing algorithmsdiscrete optimizationcombinatorial optimizationconvergenceheuristicsLD5655.V856 1996.J646Dissertationhttp://scholar.lib.vt.edu/theses/available/etd-06062008-152638/