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.