Papers with
Abstracts
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.
Paper Abstract
Discrete manufacturing
process design optimization can be difficult, due to the large number of
manufacturing process design sequences and associated input parameter setting
combinations that exist. Generalized
hill climbing algorithms have been introduced to address such manufacturing
design problems. Initial results with
generalized hill climbing algorithms required the manufacturing process design
sequence to be fixed, with the generalized hill climbing algorithm used to
identify optimal input parameter settings.
This paper introduces a new neighborhood function that allows generalized
hill climbing algorithms to be used to also identify the optimal discrete
manufacturing process design sequence among a set of valid design
sequences. The neighborhood function
uses a switch function for all the input parameters, hence allows the generalized
hill climbing algorithm to simultaneously optimize over both the design
sequences and the inputs parameters.
Computational results are reported with an integrated blade rotor
discrete manufacturing process design problem under study at the Materials
Process Design Branch of the Air Force Research Laboratory, Wright Patterson
Air Force Base (Dayton, Ohio, USA).
Henderson, D., Vaughan,
D.E., Jacobson, S.H., Wakefield, R., 2001a, “Optimal Search Strategies Using
Local Search Strategies,” Invited Paper, Nominated for Barchi Prize, Submitted
to Military Operations Research.
Paper Abstract
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.
This paper presents a strategy for developing an
optimal route for surveillance, search and rescue platforms. A route is sought that maximizes coverage
and minimizes the total distance traveled.
The problem is formulated as a discrete optimization problem (which is
NP-hard) and solved using three local search algorithms (deterministic local
search, Monte Carlo search and simulated annealing). These local search algorithms are formulated and computationally
compared using the generalized hill climbing algorithm framework.
The optimal routes developed for individual platforms
with local search strategies can be extended to optimizing a fleet of search
platforms. A simultaneous generalized
hill climbing algorithm is presented which optimizes a fleet of platforms based
on overlapping information. The same
ideas can be extended to optimizing surveillance assets to maximize coverage of
a given area. Computational results and
experimentation show that local search algorithms can provide solutions to the problem
in a reasonable amount of computing time.
Henderson, D., Wakefield,
R.R., Vaughan, D.E., Jacobson, S.H., 2001b, “Optimal Earthmoving Vehicle Routes
Using Local Search Algorithms,” Invited Paper, Accepted by the First
International Conference on Innovation in Architecture, Engineering and
Construction.
Paper Abstract
This paper introduces the
Shortest Route Cut and Fill Problem (SRCFP) for finding a vehicle route that
minimizes the total distance traveled by a vehicle between cut and fill locations
while leveling a construction project site.
An optimal vehicle route is a route that minimizes the total haul
distance that an individual earth-moving vehicle travels. The SRCFP is formulated as a discrete
optimization search problem, proven to be NP-hard, and addressed with a greedy
algorithm, Monte Carlo search, and simulated annealing. A comparison of the results using these
algorithms is presented, based on the number of visits to the globally optimal
solution (i.e., the globally optimal vehicle route).
Vaughan, D.E., Jacobson,
S.H., 2001a, “Formulating the Meta-Heuristic Tabu Search in the Generalized
Hill Climbing Algorithm Framework,” Submitted.
Paper Abstract
This paper formulates tabu search
strategies as meta-heuristics that guide generalized hill climbing (GHC)
algorithms for addressing discrete optimization problems. The resulting
framework is termed tabu guided generalized hill climbing (TG2HC)
algorithms. Tabu search strategies are
often applied in conjunction with local search algorithms. Exploration into the utility and performance
of tabu search strategies as meta-heuristics that guide local search algorithms
is difficult and generally handled on a case-by-case basis. This is due, in
part, to the variety of tabu search strategies and the wide range of local
search algorithms. The TG2HC
framework allows for concurrent exploration into the performance of a range of
tabu search strategies as meta-heuristics that guide local search algorithms.
The TG2HC
algorithm framework includes a tabu release parameter that allows the algorithm
to accept moves currently on the list of forbidden moves according to an
iteration dependent probability function.
The tabu release parameter allows practitioners to control the
probability that solutions on the tabu list will be visited. Numerous tabu search strategies can be
modeled within the TG2HC algorithm framework.
This paper shows that an application of a TG2HC
algorithm can be modeled as a nonstationary Markov chain. Therefore, at every iteration, the
probabilities of moving between solutions can be represented by the elements of
a transition matrix. It is shown that
this transition matrix can be written in terms of the transition matrix that
corresponds an application of the GHC algorithm without the tabu search
strategy. Therefore, the ability to
model an application of the TG2HC algorithm as a Markov chain allows
properties that are known for given local search algorithms to be extended to
TG2HC algorithms. Moreover, the TG2HC
algorithm framework can provide practitioners with guidelines for developing
tabu search strategies to use in conjunction with a local search algorithm that
do not destroy such algorithm’s known performance properties.
Henderson, D., Vaughan,
D.E., Jacobson, S.H., Wakefield, R., Sewell, E.C., 2001, “Optimal Cut and Fill
Strategies Using Local Search Algorithms,” Submitted.
Paper Abstract
This paper discusses the
Shortest Route Cut and Fill Problem (SRCFP).
The SRCFP is a NP-hard discrete optimization problem for leveling a
construction project site, where the objective is to find a vehicle route that
minimizes the total distance traveled by a single earthmoving vehicle between
cut and fill locations. An optimal
vehicle route is a route that minimizes the total haul distance that a single
earthmoving vehicle travels. Simulated
annealing algorithms are formulated to address the SRCFP. To assess the effectiveness of simulated
annealing on the SRCFP, a greedy algorithm is constructed to compute an upper
bound and the Held-Karp 1-tree lower bound is used to compute a lower
bound. Extensive computational results
are presented using several randomly generated instances of the SRCFP.
Vaughan, D.E., Jacobson,
S.H., 2001c, “Nonstationary Markov Chain Analysis of Simultaneous Generalized
Hill Climbing Algorithms,” Submitted.
Paper Abstract
This paper uses
nonstationary Markov chain theory to analyze simultaneous generalized hill
climbing (SGHC) algorithms. Simultaneous
generalized hill climbing (SGHC) algorithms provide a framework for using
heuristics to simultaneously address sets of intractable discrete optimization
problems. Many well-known heuristics
have been embedded within the SGHC algorithm framework, including simulated
annealing, threshold accepting, t-extremal optimization and
pure local search (among others).
Moreover, SGHC algorithms can be applied to a wide variety of sets of
related manufacturing, military, and service industry discrete optimization
problems. For example, SGHC algorithms
have been used to efficiently approach a set of traveling salesman problems, a
set of permutation flow-shop problems and a set of MAX Satisfiability problems.
A SGHC algorithm
probabilistically moves between discrete optimization problems during its
execution according to a problem generation probability function. When a SGHC algorithm moves between discrete
optimization problems, information gained while optimizing over the current
discrete optimization problem is used to set the initial solution in the
subsequent discrete optimization problem, where 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.
This paper establishes that the problem generation probability function is a stochastic process that satisfies the Markov property and that a SGHC algorithm can be modeled by a set of Markov chains. This Markov chain theory aids in the development of suitable problem generation probability functions for particular sets of problems based on the long-term behavior of the algorithm. For example, the theory is used to determine the proportion of iterations that a SGHC algorithm will spend optimizing over each discrete optimization problem. Sufficient conditions guaranteeing that the algorithm spends an equal number of iterations in each discrete optimization problem are provided. It is shown that a SGHC algorithm can be formulated such that the overall performance of the algorithm is independent of the initial discrete optimization problem chosen. Moreover, sufficient convergence conditions guaranteeing that a SGHC algorithm will visit the globally optimal solution for each discrete optimization problem are obtained.
Papers in
preparation to be submitted
Vaughan, D.E., Jacobson,
S.H., 2001b, “Simultaneous Generalized Hill Climbing Algorithms for Addressing
Sets of Discrete Optimization Problems,” Technical Paper, University of
Illinois at Urbana-Champaign.
Paper Abstract
This paper introduces
simultaneous generalized hill climbing (SGHC) algorithms as a mathematical
framework for simultaneously addressing a set of related discrete optimization
problems using local search algorithms.
Many well-known local search algorithms can be embedded within the SGHC
algorithm framework, including simulated annealing, threshold accepting, and
pure local search (among others) as well as more sophisticated heuristics such
as tabu search and t-extremal optimization.
SGHC algorithms
probabilistically move between a set of related discrete optimization problems
during their execution according to a problem generation probability
function. When an SGHC algorithm moves
between discrete optimization problems, information gained while optimizing
over the current discrete optimization problem is used to set the initial
solution in the subsequent discrete optimization problem. This paper establishes that the problem
generation probability function is a stochastic process that satisfies the
Markov property. Therefore, given a
SGHC algorithm, movement between these discrete optimization problems can be
modeled as a Markov chain. This Markov
chain is used to determine the number of iterations that the SGHC algorithm
will spend in each discrete optimization problem for a given problem generation
probability function.
This paper was motivated by
a discrete manufacturing process design optimization problem (that is used
throughout the paper to illustrate the development of the SGHC algorithm). However, the SGHC algorithm is developed
such that it can be applied to a wide variety of sets of related manufacturing,
military and service industry discrete optimization problems. To illustrate this, three additional sets of
related (well-known) discrete optimization problems that can be addressed with
local search algorithms are discussed in this paper: a set of traveling
salesman problems, a set of permutation flow-shop problems and a set of MAX
Satisfiability problems. These illustrative examples suggest how other sets of
discrete optimization problems can be modeled such that the SGHC algorithm can
be implemented. Computational results
using the SGHC algorithm (embedding the heuristics simulated annealing, local
search and t-extremal optimization,
respectively) for randomly generated instances of these three examples are
presented. For comparison purposes, the
same heuristics are also applied to all of the individual discrete optimization
problems in the sets. These
computational results suggest that optimal/near-optimal solutions can be
reached more effectively and efficiently using SGHC algorithms.
Vaughan, D.E., Kobza, J.,
Jacobson, S.H., 2001, “The Urn Problem with Random Sample Sizes,” Technical
Paper, University of Illinois at Urbana-Champaign.
Paper Abstract
Consider an urn containing m red balls. Define K1, K2, … to be independently and identically distributed random variables with probability mass function bj=P{Ki=j}, j=0, 1, 2, … , m, for every i=1, 2, … . Suppose that a sample of size K1 balls is drawn from the urn. The balls drawn in the sample are painted white and returned to the urn. This iterative process can be continued indefinitely (i.e., Ki balls being drawn and painted white on the ith iteration). Assume, at every iteration, each ball in the urn has an equal probability of being contained in a drawn sample. Define the random variable N to be the minimum number iterations required for the urn to contain m white balls. This paper presents approximations and exact expressions for E[N], examines their complexity and compares them with an approximation from the literature.
Vaughan, D.E., Henderson,
D., Jacobson, S.H., 2001, “Investigating Neighborhood Functions for the Optimal
Search Strategy Problem,” Technical Paper, University of Illinois at
Urbana-Champaign.
Paper Abstract
Optimal search strategies
with limited assets are of interest to military decision makers.
Different search 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 of these operations, efficient
use of available assets is critical to the success of such missions.
The problem of developing
optimal search strategies for a given search area using a single search
platform can be modeled as a traveling salesman problem (TSP). Therefore,
this optimal search strategy problem is a NP-hard discrete optimization problem
that can be addressed by a wide variety of local search algorithms (e.g.,
iterative improvement, simulated annealing, threshold accepting). A critical component impacting the
performance of local search algorithms is the neighborhood function. Neighborhood functions allow the solution
space to be traversed, hence provide connections between solutions in the
solution space.
This paper formulates the simultaneous generalized hill climbing (SGHC) algorithm framework to develop neighborhood function hybrids for addressing the NP-hard TSP. In particular, the SGHC algorithm framework is used to merge two well-known neighborhood functions for the TSP. The resulting hybrid neighborhood function is introduced as a method which contains potential for good finite-time performance as well as good asymptotic performance.