Parallel competing algorithms in global optimization

Abstract

Specialized techniques are needed to solve global optimization problems, due to the existence of multiple local optima or numerical noise in the objective function. The complexity of the problem is aggravated when discontinuities and constraints are present, or when evaluation of the objective function is computationally expensive. The global (minimization) programming problem is defined as finding the variable set for which the objective function obtains not only a local minimum, but also the smallest value, the global minimum. From a mathematical point of view, the global programming problem is essentially unsolvable, due to a lack of mathematical conditions characterizing the global optimum. In this study, the unconstrained global programming problem is addressed using a number of novel heuristic approaches. Firstly, a probabilistic global stopping criterion is presented for multi-start algorithms. This rule, denoted the unified Bayesian stopping criterion, is based on the single mild assumption that the probability of convergence to the global minimum is comparable to the probability of convergence to any other local minimum. This rule was previously presented for use in combination with a specific global optimization algorithm, and is now shown to be effective when used in a general multi-start approach. The suitability of the unified Bayesian stopping criterion is demonstrated for a number of algorithms using standard test functions. Secondly, multi-start global optimization algorithms based on multiple local searches, com¬bined with the unified Bayesian stopping criterion, are presented. Numerical results reveal that these simple multi-start algorithms outperform a number of leading contenders. Thirdly, parallelization of the sequential multi-start algorithms is shown to effectively re¬duce the apparent computational time associated with solving expensive global programming problems. Fourthly, two algorithms simulating natural phenomena are implemented, namely the rel¬atively new particle swarm optimization method and the well known genetic algorithm. For the current implementations, numerical results indicate that the computational effort associated with these methods is comparable. Fifthly, the observation that no single global optimization algorithm can consistently out¬perform any other algorithm when a large set of problems is considered, leads to the de¬velopment of a parallel competing algorithm infrastructure. In this infrastructure different algorithms, ranging from deterministic to stochastic, compete simultaneously for a contri¬bution to the unified Bayesian global stopping criterion. This is an important step towards facilitating an infrastructure that is suitable for a range of problems in different classes. In the sixth place, the constrained global programming problems is addressed using con¬strained algorithms in the parallel competing algorithm infrastructure. The developed methods are extensively tested using standard test functions, for both serial and parallel implementations. An optimization procedure is also presented to solve the slope stability problem faced in civil engineering. This new procedure determines the factor of safety of slopes using a global optimization approach.