A new class of test functions for global optimization (by B. Addis and M. Locatelli)

1.0

Abstract

We propose a new class of test functions for unconstrained global optimization problems for which, however, it is a priori known that the global minimum lies in the interior of a sphere centered at the origin. The class depends on some parameters through which the difficulty of the test problems can be controlled. As a basis for future comparison, we propose a selected set of these functions, with increasing difficulty, and some computational experiments with two simple global optimization algorithms.

For a detailed description of the test functions, the parameters used, and the computational experiments please refer to the paper A new class of test functions for global optimization

Documentation and source

The aim of this documentation is to give a complete description of the class implementing our test function generator.
The basic use, that is generation of the test function, evalutation of function and gradient at a given point, printing of paramenters, is presented through two examples.
shortExample::cpp shows the three standard methods that can be used to generate a test function (from standard input, setting parameter in the source code and from file) and how to to save parameters in a standard format file (in this way also the random parameters can be kept and used for several different tests).
shortExample_dim::cpp shows the two standard methods that can be used to generate a test function (from standard input and setting parameter in the source code) and how to to save parameters in a standard format file (in this way also the random parameters can be kept and used for several different tests).
The difference with respect to shortExample::cpp is that the overall dimension $d$ of the test function is required as a parameter in place of the number of basic variables $n$.
RandomSearch::cpp is a simple Random Search applied to a test function generated from file Input.dat.

The code can be compiled with different versions of gcc. In particular test were made with gcc 3.0 up to 4.0. Any compiler compliant with the current C++ standard can now be used.

Results

As a basis for future comparison seven different test functions have been considered. The parameters defining these functions and the results of the global optimization method MBH (Monotonic Basin Hopping) are reported in the following table (a link to input files is in the first column, and the AMPL data file is in the second one).
On each test function 1000 runs have been performed. For each function we report the number of successes over the 1000 runs and the average number of local searches per run.
Testing has been performed on Pentium IV processors 2.4GHz with 512 MB RAM running Linux.
MBH always solves the cases with $L2=L3=1$. It can be seen that increasing the number of local minima (i.e. increasing parameter $K$ from 10 to 20) only slightly worsens the performance of MBH, while different scaling, due to random selection (within the interval $[10,20]$) of the $K_i$ values, is a more serious source of difficulty.
As the values $L_2$ and $L_3$ are increased, we observe a clear decrease of the performance of MBH (MBH gets trapped at a local minimum at level 2 and is unable to escape from it when this is not the global minimum). Notice that MBH reaches in a relativey fast time a local minimum at level 2 (it has been observed that MBH always stops at a local minimum at level 2 and the number of local searches per run is never very large) but then is unable to escape from it.

AMPL

The AMPL model, and a simple run file is available. The "option substout 1" must be used. The data files for the seven test examples are given in the second column of the table below.
A C++ function is added to produce AMPL data files. ExampleAMPL::cpp shows the method used to generate the data file for a given test function

Function

AMPL

n K_i H L2 L3 succ. av. LS
Test 1

data 1

50 10 10 1 1 1000 1517
Test 2

data 2

50 20 10 1 1 1000 2393
Test 3

data 3

50 Random 10 1 1 1000 5271
Test 4

data 4

30 10 10 10 1 82 1444
Test 5

data 5

30 10 10 25 1 30 1810
Test 6

data 6

30 10 10 25 4 17 1781
Test 7

data 7

30 10 10 100 4 3 1867

Acknowledgments

The authors acknowledge support from Progetto FIRB ``Ottimizzazione Non Lineare su Larga Scala''.

Note

If you have any comment and/or request you can send them at the following addresses

addis at dii.unisi.it
locatell at di.unito.it

The site will be continuously updated.

Generated on Tue Sep 19 15:38:37 2006 for TestFunction by  doxygen 1.4.7