Keywords: global optimization, Nelder-Mead, composite laminate design.

Complex engineering optimization problems are characterized by calculation intensive system simulations, difficulties in estimating sensitivities (when they exist) and a multiplicity of local solutions. Acknowledging the last point, much research has been devoted to global optimization (e.g., [1,2]). The high numerical cost of global optimizers has been at the origin of subsequent efforts to speed up the search either by adding problem specific knowledge to the search, or by mixing efficient, local algorithms with global algorithms. There are many ways in which local and global searches can cooperate. The simplest strategy is to link the searches in series, meaning that, firstly, a global optimization of limited cost is executed, the solution of which is refined by a local search. An example of the serial hybrid is given in [3] where simulated annealing, the global optimizer, is coupled with a sequential quadratic programming and a Nelder-Mead algorithm. A large number of parallel local-global searches have been proposed [1,4] and analyzed [5,6]. In these cases, iterations of global and local algorithms are intertwined. One can further classify parallel hybrids into those where the local searches converge, and those where local searches may be prematurely stopped. Memetic genetic algorithms [7] and multistart methods are examples of the former.

When considering a real engineering optimization problem, a common situation is that the affordable total number of analyses is limited, that the presence of spurious local minima is unknown, and that it is uncertain if it will be possible to complete as few as two local searches. Nevertheless, achieving global results remains an objective of the optimizer. This typically occurs when dealing with an unknown function of less than 20 variables, for which one is willing to wait for about 1000 evaluations of the objective function. In such a case, a local-global method based on restart is the safest strategy because it can terminate in a short time (the length of a single local search).

In the current work a fixed cost local search, which sequentially becomes global is developed. Globalization is achieved by probabilistic restart. The restart procedure uses an adaptive spacial probability density keeping a memory of past local searches. Also, the number of restarts is unknown beforehand because a maximum number of analyses is imposed and the cost of each local search is unknown.

An improved Nelder-Mead algorithm [8] makes the local optimizer, so the method can be applied to discontinuous (no gradient information needed) and nonconvex functions. Improvements to the Nelder-Mead algorithm consist of simplex degeneracy detection and handling through reinitialization. Limits on variables are taken into account through projection. Once the algorithm terminates, the list of possible local (eventually global) optima makes the results of the search. In practice, the calculation of many local or global optima is a benefit of the method in comparison with global optimizers that provide a single solution (e.g., standard evolutionary algorithms).

The resulting method, called Globalized Bounded Nelder-Mead (GBNM) algorithm, is particularly adapted to tackle multimodal, discontinuous optimization problems, for which it is uncertain that a global optimization can be afforded. The GBNM method is simple in its principles, and the aforementionned features make it particularly useful in an engineering design context. Numerical experiments are performed to compare different restart strategies. The GBNM method compares favorably to an evolutionary algorithm, both in terms of numerical cost and accuracy.

1

A.A. Törn and A. Zilinskas, "Global Optimization", Springer-Verlag, Berlin, 1989.

2

T. Bäck, "Evolutionary Algorithms in Theory and Practice", Oxford Univ. Press, 1996.

3

Y. Shang, Y. Wan, M.P.J. Fromherz and L. Crawford, "Toward Adaptive Cooperation between Global and Local Solvers for Continuous Constraint Problems", CP'01 Workshop on cooperative Solvers in Constraints Programming, (held in Pahos, Cyprus, Decembre (2001)).

4

M. Okamoto, T. Nonaka, S. Ochiai and D. Tominaga, "Nonlinear numerical optimization with use of a hybrid Genetic Algorithm incorporating the Modified Powell method", Applied Mathematics and Computation, 91, 63-72, 1998. doi:10.1016/S0096-3003(97)10007-8

5

A. A. Törn, "A Search-Clustering Approach to Global Optimization", Towards Global Optimization 2, 49-62, 1978.

6

D.E. Goldberg and S. Voessner, "Optimizing Global-Local Search Hybrids", GECCO 99 - Genetic and Evolutionary Computation Conference, (held in Orlando, Florida, USA), 220-228, 1999.

7

P. Moscato, "On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts: Towards Memetic Algorithms", Caltech Concurrent Computation Program, C3P Report 826, 1989.

8

J.A. Nelder and R. Mead, "A simplex for function minimization", Computer J., 7, 308-313, 1965.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £85 +P&P)