This dissertation presents an algorithm to solve optimization problems with
"black-box" objective functions, i.e., functions that can only be evaluated by running
a computer program. Such optimization problems often arise in engineering
applications, for example, the design of sensor placement. Due to the complexity in
engineering systems, the objective functions usually have multiple local optima and
depend on a huge number of decision variables. These difficulties make many existing
methods less effective.
The proposed algorithm is called adaptive evolutionary Monte Carlo (AEMC),
and it combines sampling-based and metamodel-based search methods. AEMC incorporates
strengths from both methods and compensates limitations of each individual
method. Specifically, the AEMC algorithm combines a tree-based predictive model
with an evolutionary Monte Carlo sampling procedure for the purpose of heuristic
optimization. AEMC is able to escape local optima due to the random sampling component,
and it improves the quality of solutions quickly by using information learned
from the tree-based model. AEMC is also an adaptive Markov chain Monte Carlo
(MCMC) algorithm, and is in fact the rst adaptive MCMC algorithm that simulates
multiple Markov chains in parallel.
The ergodicity property of the AEMC algorithm is studied. It is proven that the
distribution of samples obtained by AEMC converges asymptotically to the "target"
distribution determined by the objective function. This means that AEMC has a larger probability of collecting samples from regions containing the global optimum
than from other regions, which implies that AEMC will reach the global optimum
given enough run time.
The AEMC algorithm falls into the category of heuristic optimization algorithms,
and is applicable to the problems that can be solved by other heuristic methods,
such as genetic algorithm. Advantages of AEMC are demonstrated by applying it
to a sensor placement problem in a manufacturing process, as well as to a suite of
standard test functions. It is shown that AEMC is able to enhance optimization
effectiveness and efficiency as compared to a few alternative strategies, including
genetic algorithm, Markov chain Monte Carlo algorithms, and meta-model based
methods. The effectiveness of AEMC for sampling purposes is also shown by applying
it to a mixture Gaussian distribution.
| Identifer | oai:union.ndltd.org:tamu.edu/oai:repository.tamu.edu:1969.1/ETD-TAMU-2008-12-84 |
| Date | 14 January 2010 |
| Creators | Ren, Yuan |
| Contributors | Ding, Yu |
| Source Sets | Texas A and M University |
| Language | en_US |
| Detected Language | English |
| Type | Book, Thesis, Electronic Dissertation |
| Format | application/pdf |
Page generated in 0.0022 seconds