A convergence analysis of generalized hill climbing algorithms

Kelly A. Sullivan; Sheldon H. Jacobson

doi:10.1109/9.940936

A convergence analysis of generalized hill climbing algorithms

Research output: Contribution to journal › Article › peer-review

Abstract

Generalized hill climbing (GHC) algorithms provide a well-defined framework for describing the performance of local search algorithms for discrete optimization problems. Necessary and sufficient convergence conditions for GHC algorithms are presented. These convergence conditions are derived using a new iteration classification scheme for GHC algorithms. The implications of the necessary and the sufficient convergence conditions for GHC algorithms with respect to existing convergence theory for simulated annealing are also discussed.

Original language	English (US)
Pages (from-to)	1288-1293
Number of pages	6
Journal	IEEE Transactions on Automatic Control
Volume	46
Issue number	8
DOIs	https://doi.org/10.1109/9.940936
State	Published - Aug 2001

Keywords

Convergence
Discrete optimization
Hill climbing algorithms
Local search
Markov chain
Metaheuristics
Simulated annealing

ASJC Scopus subject areas

Control and Systems Engineering
Computer Science Applications
Electrical and Electronic Engineering

Online availability

10.1109/9.940936

Library availability

Discover UIUC Full Text

Cite this

@article{e194f97ba6144994b8326afa2076a7eb,

title = "A convergence analysis of generalized hill climbing algorithms",

abstract = "Generalized hill climbing (GHC) algorithms provide a well-defined framework for describing the performance of local search algorithms for discrete optimization problems. Necessary and sufficient convergence conditions for GHC algorithms are presented. These convergence conditions are derived using a new iteration classification scheme for GHC algorithms. The implications of the necessary and the sufficient convergence conditions for GHC algorithms with respect to existing convergence theory for simulated annealing are also discussed.",

keywords = "Convergence, Discrete optimization, Hill climbing algorithms, Local search, Markov chain, Metaheuristics, Simulated annealing",

author = "Sullivan, {Kelly A.} and Jacobson, {Sheldon H.}",

note = "Funding Information: Manuscript received February 11, 2000; revised November 2, 2000 and March 9, 2001. Recommended by Associate Editor L. Dai. This work was supported in part by the Air Force Office of Scientific Research under Grants F49620-95-1-0124, F49620-98-1-0111, F49620-98-1-0432, and F49620-01-1-0007, and in part by the National Science Foundation under Grant DMI-9907980.",

year = "2001",

month = aug,

doi = "10.1109/9.940936",

language = "English (US)",

volume = "46",

pages = "1288--1293",

journal = "IRE Transactions on Automatic Control",

issn = "0018-9286",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "8",

}

TY - JOUR

T1 - A convergence analysis of generalized hill climbing algorithms

AU - Sullivan, Kelly A.

AU - Jacobson, Sheldon H.

N1 - Funding Information: Manuscript received February 11, 2000; revised November 2, 2000 and March 9, 2001. Recommended by Associate Editor L. Dai. This work was supported in part by the Air Force Office of Scientific Research under Grants F49620-95-1-0124, F49620-98-1-0111, F49620-98-1-0432, and F49620-01-1-0007, and in part by the National Science Foundation under Grant DMI-9907980.

PY - 2001/8

Y1 - 2001/8

N2 - Generalized hill climbing (GHC) algorithms provide a well-defined framework for describing the performance of local search algorithms for discrete optimization problems. Necessary and sufficient convergence conditions for GHC algorithms are presented. These convergence conditions are derived using a new iteration classification scheme for GHC algorithms. The implications of the necessary and the sufficient convergence conditions for GHC algorithms with respect to existing convergence theory for simulated annealing are also discussed.

AB - Generalized hill climbing (GHC) algorithms provide a well-defined framework for describing the performance of local search algorithms for discrete optimization problems. Necessary and sufficient convergence conditions for GHC algorithms are presented. These convergence conditions are derived using a new iteration classification scheme for GHC algorithms. The implications of the necessary and the sufficient convergence conditions for GHC algorithms with respect to existing convergence theory for simulated annealing are also discussed.

KW - Convergence

KW - Discrete optimization

KW - Hill climbing algorithms

KW - Local search

KW - Markov chain

KW - Metaheuristics

KW - Simulated annealing

UR - http://www.scopus.com/inward/record.url?scp=0035418539&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0035418539&partnerID=8YFLogxK

U2 - 10.1109/9.940936

DO - 10.1109/9.940936

M3 - Article

AN - SCOPUS:0035418539

SN - 0018-9286

VL - 46

SP - 1288

EP - 1293

JO - IRE Transactions on Automatic Control

JF - IRE Transactions on Automatic Control

IS - 8

ER -

A convergence analysis of generalized hill climbing algorithms

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this