Simple Meta-heuristics using the simplex algorithm for non-linear programming

Abstract

In this paper we present an extension of the Nelder and Mead simplex algorithm for non-linear programming, which makes is suitable for both unconstrained and constrained optimisation. We then explore several extensions of the method for escaping local optima, and which make it a simple, yet powerful tool for optimisation of nonlinear functions with many local optima. A strategy which proved to be extremely robust was random start local search, with a correct, though unusual, setup. Actually, for some of the benchmarks, this simple meta-heuristic remained as the most e®ective one. The idea is to use a very large simplex at the begin; the initial movements of this simplex are very large, and therefore act as a kind of ¯lter, which naturally drives the search into good areas. We propose two more mechanisms for escaping local optima, which, still being very simple to implement, provide better results for some dif- ¯cult problems.