Generalized hill climbing algorithms for discrete optimization problems

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.

Name thesis:degree_name

Ph. D.

Level thesis:degree_level

doctoral

Discipline thesis:degree_discipline

Industrial and Systems Engineering

Department dc:contributor.department

Industrial and Systems Engineering

Grantor dc:publisher

Virginia Tech

Year dc:date.issued

1996

Author dc:creator

• Johnson, Alan W.

Chair dc:contributor.committeechair

• Jacobson, Sheldon H.

Committee members dc:contributor.committeemember

• Allison, Donald C. S.
• Blanchard, Benjamin S. Jr.
• Sarin, Subhash C.
• Sherali, Hanif D.

• simulated annealing
• hill climbing algorithms
• discrete optimization
• combinatorial optimization
• convergence
• heuristics

Statement dc:rights

• In Copyright

Licence dc:rights.uri

• http://rightsstatements.org/vocab/InC/1.0/

Language dc:language.iso

en

Dc Identifier Other

etd-06062008-152638

OAI identifier oai:identifier

oai:vtechworks.lib.vt.edu:10919/38064