Technical Report: DCC-2007-06

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

João Pedro Pedroso

DCC-FC, Universidade do Porto
R. do Campo Alegre 1021/1055 , 4169-007 Porto, Portugal
Phone: +351 220402919 , Fax: 351 22 402 950
E-mail: {jpp}

June 2007


In this paper we present an extension of the Nelder and Mead simplex algorithm for non-linear programming, which makes it 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 effective 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 filter, 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 difficult problems.