Summary (pdf)

Simultaneous Generalized Hill Climbing Algorithms

for Addressing Sets of

Discrete Optimization Problems

http://scholar.lib.vt.edu/thesis/available/etd-08042000-1459---3/unrestricted/dianeetd.pdf

Dr. Diane Elizabeth Vaughan

The objective of this dissertation is to introduce and study a general mathematical framework, termed simultaneous generalized hill climbing (SGHC) algorithms, for simultaneously addressing a set of related discrete optimization problems using local search algorithms. It is common to encounter several discrete optimization problems where a relationship exists between the solution spaces of the individual problems. In general, these problems are approached individually. However, because of their similarities, the same computational tools can be effectively used to address them simultaneously. For example, the Material Process Design Branch of the Air Force Research Laboratory, Wright Patterson Air Force Base (Dayton, Ohio, USA) has several similar discrete manufacturing process design optimization problems under study. These problems are difficult to solve due to the large number of feasible design sequences and associated input parameter setting combinations. Local search algorithms embedded in the generalized hill climbing (GHC) algorithm framework were introduced to address such manufacturing design problems (Jacobson et al. 1998). Initial results with GHC algorithms required the manufacturing process design sequence to be fixed, with the GHC algorithm used to identify optimal input parameter settings for each feasible design sequence (each path in Figure 1 from Initial Shape to Finish Machining represents a design sequence hence a discrete optimization problem).

Figure 1: Manufacturing Designs

The SGHC algorithm framework is motivated by a study reported in Vaughan et al. (2000) which develops a new neighborhood function that allows a local search algorithm to be used to also identify the optimal discrete manufacturing process design sequence from among a set of valid design sequences. This neighborhood function allows local search algorithms to simultaneously optimize over both the design sequences and the input parameters, hence eliminating the need to approach each design sequence (i.e., each discrete optimization problem) individually. Therefore, all design sequences (i.e., the paths in Figure 1) can be considered in a single algorithm application. The computational results in Vaughan et al. (2000) suggest that such an approach is optimal and yields impressive results. However, the neighborhood function developed for this purpose was problem specific.

This dissertation generalizes the results reported in Vaughan et al. (2000) by formally defining a class of sets of discrete optimization problems where a relationship exists, similar to the one described for the manufacturing problem. A set of discrete optimization problems contained in this class is defined as a set of fundamentally related discrete optimization problems. The SGHC algorithm framework is used to simultaneously approach such sets of discrete optimization problems using local search algorithms (see Figure 2a). A metric (distance) between elements in a set of fundamentally related discrete optimization problems is introduced to evaluate if and when it is advantageous to address a particular set of discrete optimization problems with a SGHC algorithm (Vaughan and Jacobson 2001a).

The SGHC algorithm consists of two iteration counters k=1, 2, …, K and n=1, 2, …, N(k), corresponding to inner and outer loops, respectively. During the inner loop iterations, the SGHC algorithm is optimizing over the current discrete optimization problem D_y using a local search algorithm. At each outer loop iteration, the SGHC algorithm may move between discrete optimization problems according to a problem generation probability function. When the algorithm moves between discrete optimization problems, information gained while optimizing over the current discrete optimization problem is used to define the initial solution for the subsequent discrete optimization problem. This information is determined by the practitioner for the particular set of problems under study. However, effective strategies are often apparent based on the problem description. For example, in the manufacturing design problem, the optimal parameter values for the current design sequence were used to generate the initial solution in the subsequent design sequence (for the common processes across the two design sequences). An effective strategy for a set of traveling salesman problems is provided in this dissertation. Moreover, an effective strategy for a set of permutation flow shop problems can be found in Vaughan and Jacobson (2001a).

This dissertation shows that for a fixed outer loop iteration k=1, 2, …, K, the stochastic process {}, k=1, 2, …, K, n=1, 2, …, N(k), ÎW with solution space W={w₁, w₂, …, w_|W|} corresponding to the current solution of the SGHC algorithm during inner loop iterations n=1, 2, …, N(k) satisfies the Markov property for every n and all states w₁, w₂, …, w_n (i.e., {} is a Markov chain). Moreover, it is shown that for outer loop iterations k=1, 2, …, K, the possible movement between discrete optimization problems is a stochastic process {Y(k)}, Y(k)ÎS, k=1, 2, … that also satisfies the Markov property (see Figure 2b). Therefore, for a SGHC algorithm, movement between discrete optimization problems can be modeled as a Markov chain (Vaughan and Jacobson 2001a). This Markov chain is used to determine the number of iterations that the SGHC algorithm will spend in each discrete optimization problem for given problem generation probability functions (Vaughan and Jacobson 2001a). Moreover, sufficient conditions that guarantee that this Markov chain has a uniform stationary probability distribution are provided (Vaughan and Jacobson 2001b).

Figures 2 a, b: Markov Chain Theory

Therefore, the SGHC algorithm can be applied such that it optimizes over every discrete optimization problem in a fundamentally related set uniformly (i.e., every problem considered is optimized over the same number of iterations). Additionally, this dissertation provides sufficient convergence conditions that guarantee that a SGHC algorithm will visit the globally optimal solution for each of the problems in a set of discrete optimization problems (Vaughan and Jacobson 2001b). Therefore, the SGHC algorithm can be applied such that it is guaranteed to identify the globally optimal solution in each of the discrete optimization problems in the set.

This dissertation reports computational results with SGHC algorithms for a set of randomly generated traveling salesman problems. For comparison purposes, local search algorithms are also applied individually to each traveling salesman problem (TSP). The computational results for the set of TSPs suggest that the SGHC algorithms overwhelmingly outperform local search algorithms applied to the TSPs individually, as measured by the average optimal tour distances across multiple replications. Moreover, computational results are presented in Vaughan et al. (2001a) for a randomly generated set of permutation flow shop problems. The computational results for the set of permutation flow shop problems suggest that the SGHC algorithms outperform local search algorithms applied to the permutation flow shop problems individually. These computational results for randomly generated problem instances are further supported by applications of the SGHC algorithm to real-world problem instances. For example, Henderson et al. (2001) reports results where the SGHC algorithm is applied to a military search and rescue problem. Optimal strategies for conducting searches with limited assets are of interest to military decision makers. Different platforms with varying degrees of effectiveness are used for surveillance or search and rescue operations (e.g., helicopters versus fixed wing or satellite). Due to the timeliness required in these operations, efficient use of available assets is critical to success. The SGHC algorithm is used in Henderson et al. (2001) to determine which fleet platforms can best search a given area (see Figure 3). Computational results and experimentation demonstrate that the approach of applying the SGHC algorithm to this problem provides excellent solutions a reasonable amount of computing time.

Figure 3: Optimal Search Strategies

The SGHC algorithm is a new approach for addressing a set of fundamentally related discrete optimization problems that is more efficient than the traditional approach of addressing each discrete optimization problem in the set individually with a local search algorithm. For example, SGHC algorithms allow practitioners to make a single algorithm run over a set of fundamentally related discrete optimization problems. Moreover, real-world examples (e.g., see Vaughan et al. 2000, Henderson et al. 2001) as well as theoretical examples (e.g., see Vaughan et al. 2001a,b) suggest that SGHC algorithms significantly outperform sequential applications of local search algorithms. The development of the SGHC algorithm and the mathematical results in the dissertation make it possible for the SGHC algorithm to be adapted and used to approach a wide variety of real-world problems that were previously unsolvable.

References

Henderson, D., Vaughan, D.E., Jacobson, S.H., Wakefield, R., 2001, “Optimal Search Strategies Using Local Search Strategies,” Invited Paper, Military Operations Research. Submitted.

Jacobson, S.H., Sullivan, K.A., Johnson, A.W., 1998, “Discrete Manufacturing Process Design Optimization Using Computer Simulation and Generalized Hill Climbing Algorithms”, Engineering Optimization, 31, 247-260.

Vaughan, D.E., Jacobson, S.H., Armstrong, D., 2000, “A New Neighborhood Function for Discrete Manufacturing Process Design Optimization using Generalized Hill Climbing Algorithms,” ASME Journal of Mechanical Design, 122 (2), 164-171.

Vaughan, D.E., Jacobson, S.H., 2001a, “Simultaneous Generalized Hill Climbing Algorithms for Addressing Sets of Discrete Optimization Problems,” In preparation to be Submitted.

Vaughan, D.E., Jacobson, S.H., 2001b, “Nonstationary Markov Chain Analysis of Simultaneous Generalized Hill Climbing Algorithms,” In preparation to be Submitted.