A Convergence Analysis of Generalized Hill Climbing Algorithms

Generalized hill climbing (GHC) algorithms provide a unifying framework for describing several discrete optimization problem local search heuristics, including simulated annealing and tabu search. A necessary and a sufficient convergence condition for GHC algorithms are presented. The convergence conditions presented in this dissertation are based upon a new iteration classification scheme for GHC algorithms. The convergence theory for particular formulations of GHC algorithms is presented and the implications discussed. Examples are provided to illustrate the relationship between the new convergence conditions and previously existing convergence conditions in the literature. The contributions of the necessary and the sufficient convergence conditions for GHC algorithms are discussed and future research endeavors are suggested.

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

1999

Author dc:creator

• Sullivan, Kelly Ann

Chair dc:contributor.committeechair

• Jacobson, Sheldon H.

Committee members dc:contributor.committeemember

• Nachlas, Joel A.
• Ye, Keying
• Sherali, Hanif D.
• Kobza, John E.

• heuristics
• discrete optimization
• local search
• simulated annealing
• convergence
• combinatorial optimization
• hill climbing algorithms
• Markov chain

Statement dc:rights

• In Copyright

Licence dc:rights.uri

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

Dc Identifier Other

etd-041999-213806

OAI identifier oai:identifier

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