Designing Optimal Generalized Hill Climbing Algorithms with Applications to Discrete Manufacturing Process Design Optimization

摘要

Generalized hill climbing (GHC) algorithms provide a well-defined framework to model and study the performance of algorithms for intractable discrete optimization problems. For ease of analysis, such algorithms have either been studied empirically (involving extensive trial and error on specific problem instances) or asymptotically (hence leading to convergence results as the number of iterations grows). Unfortunately, such results provide limited insight into the finite-time performance of such algorithms, nor provide guidance for practitioners on how to design and implement such algorithms to optimize their performance given a limited amount of computing time and resources. New algorithms have been developed to address sets of related discrete optimization problems. The primary applications for these algorithms are discrete manufacturing process design optimization problems and construction site-level problems of interest to the Air Force. New performance criteria (both asymptotic and finite-time) have also been developed to analyze these and other related GHC algorithms.