×

A class of convergent generalized hill climbing algorithms. (English) Zbl 1032.90036

Summary: Generalized Hill Climbing (GHC) algorithms have been presented as a modeling framework for local search strategies applied to address intractable discrete optimization (minimization) problems. GHC algorithms include simulated annealing, pure local search, and threshold accepting, among others, as special cases. A particular class of GHC algorithms is designed for discrete optimization problems where the objective function value of a globally optimal solution is known (in this case, the task is to identify an associated optimal solution). This class of GHC algorithms is shown to converge, and six examples are provided that illustrate the diversity of GHC algorithms within this class of convergent algorithms. Implications of these results are discussed.

MSC:

90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[3] Sengupta, P.; Solow, D., A finite descent theory for linear programming, piecewise linear convex minimization, and the linear complementarity problem, Naval Research Logistics Quarterly, 32, 417-431 (1985) · Zbl 0583.90057
[5] Dueck, G.; Scheuer, T., Threshold accepting: a general purpose optimization algorithm appearing superior to simulated annealing, Journal of Computational Physics, 90, 161-175 (1990) · Zbl 0707.65039
[7] Jacobson, S. H.; Sullivan, K. A.; Johnson, A. W., Discrete manufacturing process design optimization using computer simulation and generalized hill climbing algorithms, Engineering Optimization, 31, 247-260 (1998)
[8] Cinlar, E., Introduction to Stochastic Processes (1975), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0341.60019
[9] Ross, S. M., Introduction to Probability Models (1993), Academic Press: Academic Press San Diego, CA · Zbl 0781.60001
[10] Jacobson, S. H.; Solow, D., The effectiveness of finite improvement algorithms for finding global optima, Zeitschrift fur Operations Research (ZOR) - Methods and Models of Operations Research, 37, 3, 257-272 (1993) · Zbl 0788.68061
[11] Cottle, R. W.; Pang, J.-S.; Stone, R. E., The Linear Complementarity Problem (1992), Academic Press: Academic Press Boston, MA · Zbl 0757.90078
[12] van Laarhoven, P. J.M.; Aarts, E. H.L., Simulated Annealing: Theory and Applications (1987), Reidel: Reidel Dordrecht, Holland · Zbl 0643.65028
[13] Schuur, P. C., Classification of acceptance criteria for the simulated annealing algorithm, Mathematics of Operations Research, 22, 2, 266-275 (1997) · Zbl 0883.90104
[15] Law, A. M.; Kelton, W. D., Simulation Modeling and Analysis (1991), McGraw-Hill: McGraw-Hill New York
[16] Yücesan, E.; Jacobson, S. H., Computational issues for accessibility in discrete event simulation, ACM Transactions on Modeling and Computer Simulation, 6, 1, 53-75 (1996) · Zbl 1392.68210
[17] Jacobson, S. H.; Yücesan, E., On the complexity of verifying structural properties of discrete event simulation models, Operations Research, 47, 3, 476-481 (1999) · Zbl 1014.90080
[19] Metropolis, N.; Rosenbluth, A. W.; Rosenbluth, M. N.; Teller, A. H.; Teller, E., Equation of state calculations by fast computing machines, Journal of Chemical Physics, 21, 6, 1087-1092 (1953) · Zbl 1431.65006
[20] Aarts, E. H.L.; Korst, J. H.M., Simulated Annealing and Boltzmann Machines (1989), Wiley: Wiley Tiptree · Zbl 0674.90059
[22] Hammersley, J. M.; Handscomb, D. C., Monte Carlo Methods (1964), Spottiswoode, Ballantyne & Co. Ltd: Spottiswoode, Ballantyne & Co. Ltd London
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.