Abstract

Stochastic methods, including simulated annealing, genetic algorithms and evolutionary programs are being used for many types of practical global optimization problems. These problems include discrete and continuous variables, and the functions have many local optima. Yet the performance of these adaptive stochastic search methods is difficult to analyze. This tutorial will present theoretical results on a family of stochastic search methods, including pure random search, pure adaptive search, hesitant adaptive search, adaptive search, and most recently backtracking adaptive search to gain understanding of the convergence of adaptive random search techniques.

Click **here** for the full tutorial
(.pdf file)

References:

Berbee, H.C.P., Boender, C.G.E., Rinnooy Kan, A.H.G., Scheffer, C.L.,
Smith, R.L., and Telgen, J., "Hit-and-Run Algorithms for the Identification
of Nonredundant Linear Inequalities," __Mathematical Programming__,
Vol. 37, pages 184-207,1987.

Bulger, D.W., Alexander, D., Baritompa, W.P., Wood, G.R., Zabinsky, Z.B., "Expected Hitting Times for Backtracking Adaptive Search," submitted 2001.

Bulger, D.W. and Wood, G.R., "Hesitant Adaptive Search for Global Optimization,"
__Mathematical
Programming__, Vol. 81, pages 89-102, 1998.

Graesser, D.L., Zabinsky, Z.B., Tuttle, M.E., Kim, G.I., "Designing
Laminated Composites Using Random Search Techniques," __Composite Structures__,
Vol. 18, pages 311-325, 1991.

Kaufman, D.E. and Smith, R.L., "Direction Choice for Accelerated Convergence
in Hit-and-Run Sampling," __Operations Research__, Vol. 46, No. 1, pages
84-95, 1998.

Kristinsdottir, B.P., "Complexity Analysis of Random Search Algorithms," Ph.D. Dissertation, University of Washington, 1997.

Kristinsdottir, B.P., Zabinsky, Z.B., Tuttle, M.E., Csendes, T., "Incorporating
Manufacturing Tolerances in Near-Optimal Design of Composite Structures,"
__Engineering
Optimization__, Vol. 26, pages 1-23, 1996.

Kristinsdottir, B.P., Zabinsky, Z.B. and Wood, G.R., "Discrete Backtracking
Adaptive Search for Global Optimization," A book chapter in __Stochastic
and Global Optimisation__ dedicated to the 70th anniversary of Professor
J. Mockus, Kluwer Academic Publishers, edited by G.Dzemyde, V. Saltenis,
A.Zilinskas. To appear.

Mabson, G.E., Flynn, B.W., Ilcewicz, L.B., and Graesser, D.L., "The
Use of COSTADE in Developing Composite Commercial Aircraft Fuselage Structures,"
__Proceedings
of the 35th AIAA / ASME / ASCE / AHS / ASC Structure, Structural Dynamics,
and Materials Conference__, April 1994.

Metschan, S., Mabson, G.E., Graesser, D.L., "Designing a Window Belt,"
__Proceedings
of the 5th NASA Advanced Composite Technology Conference__, August 1994.

Neogi, S., "Design of Large Composite Structures using Global Optimization and Finite Element analysis," Ph.D. dissertation, University of Washington, 1997.

Romeijn, H.E. and Smith, R.L., "Simulated Annealing and Adaptive Search
in Global Optimization," __Probability in the Engineering and Informational
Sciences__, Vol. 8, pages 571-590, 1994.

Romeijn, H.E. and Smith, R.L., "Simulated Annealing for Constrained
Global Optimization," __Journal of Global Optimization__, Vol. 5, pages
101-126, 1994.

Romeijn, H.E., Zabinsky, Z.B., Graesser, D.L., Neogi, S., "New Reflection
Generator for Simulated Annealing in Mixed integer/Continuous Global Optimization,"
__Journal
of Optimization Theory and Applications__, Vol. 101, No. 2, pages 403-427,
1999.

Savic, V., Tuttle, M.E., Zabinsky, Z.B., "Optimization of Composite
I-Sections Using Fiber Angles as Design Variables," __Composite Structures__,
Vol. 53, pages 265-277, 2001.

Smith, R.L., "Efficient Monte Carlo Procedures for Generating Points
Uniformly Distributed over Bounded Regions," __Operations Reserach__,
Vol.32, pages 1296-1308, 1984.

Swanson, G.D., Ilcewicz, L.B., Walker, T., Graesser, D.L., Tuttle, M.E.,
and Zabinsky, Z.B., "Local Design Optimization for Transport Fuselage Crown
Panels," __Proceedings of the 9th DoD / NASA / FAA Conference on Fibrous
Composites in Structural Design__, Lake Tahoe, Nevada, November 1991.

Wood, G.R., Zabinsky, Z.B., and Kristinsdottir, B.P., "Hesitant Adaptive
Search: the distribution of the number of iterations to convergence," __Mathematical
Programming__, Vol. 89, No. 3, pages 479-486, 2001.

Zabinsky, Z.B. and Kristinsdottir, B.P., "Complexity Analysis Integrating
Pure Adaptive Search (PAS) and Pure Random Search (PRS)," __Developments
in Global Optimization__, ed.s: Bomze, Csendes, Horst, and Pardalos,
Kluwer Adcademic Publishers, Pages 171-182, 1997.

Zabinsky, Z.B. and Smith, R.L., "Pure Adaptive Search in Global Optimization,"
__Mathematical
Programming__, Vol. 53, pages 323-338, 1992.

Zabinsky, Z.B., Wood, G.R., Steel, M.A. and Baritompa, W.P., "Pure Adaptive
Search for Finite Global Optimization," __Mathematical Programming__,
Vol. 69, pages 443-448, 1995.

Zabinsky, Z.B., Smith, R.L., McDonald, J.F., Romeijn, H.E., Kaufman,
D.E., "Improving Hit and Run for Global Optimization," __Journal of Global
Optimization__, Vol. 3, pages 171-192, 1993.