.. include:: headings.inc .. role:: boldred .. role:: boldgreen .. role:: backred .. role:: backyellow .. role:: backgreen .. role:: red .. role:: green .. _LGMVG: |infinity| LGMVG ================ | .. table:: =================== =================== ==================== F\ :sub:`opt` Known X\ :sub:`opt` Known Difficulty =================== =================== ==================== :green:`Yes` :red:`No` :backgreen:`Easy` =================== =================== ==================== | The LGMVG test suite is a Gaussian landscape generator and it is intended to be a general-purpose tool for generating unconstrained single-objective continuous test problems within box-bounded search spaces. The implementation follows the "Max-Set of Gaussians Landscape Generator" described in http://boyuan.global-optimization.com/LGMVG/index.htm . The major motivation for this problem generator was to increase the research value of experimental studies on Evolutionary Algorithms and other optimization algorithms by giving experimenters access to a set of purposefully built test problems with controllable internal structure. The major advantages of using a landscape generator compared to using classical benchmark test problems are listed as below: 1. The structure of test problems can be conveniently controlled by a small number of parameters. 2. A large number of test problems with similar structure can be generated to increase the reliability of experimental results. 3. Deep insights into the behaviour of algorithms can be achieved by relating their performance to the specific structural properties of test problems. | |methodology| Methodology ------------------------- The basic components or building-blocks of this landscape generator are a set of multivariate Gaussian functions: .. math:: g(X) = \frac{1}{\left ( 2\pi \right )^{\pi/2}\left | \Sigma \right |^{1/2}}e^{-\frac{1}{2} (X - \mu)^T \Sigma^{-1}(X - \mu)} Where :math:`\mu` is an :math:`n`-dimenional vector of means and :math:`\Sigma` is a :math:`n \times n` covariance matrix. The fitness value of a vector :math:`X` is determined by the weighted component that gives it the largest value: .. math:: F(X) = \underset{i}{max} \: \omega_i\cdot g_i(X) Since the normalizing factor of each Gaussian function is a constant, it can be combined with its weight :math:`\omega`. Also, the :math:`n`-th root of the Gaussian function (i.e., :math:`n` is the dimensionality) is used to avoid some issues in high-dimensional spaces. The actual fitness function has the following form: .. math:: F(X) = \underset{i}{max} \: \omega_i\cdot e^{-\frac{1}{2n} (X - \mu_i)^T \Sigma_i^{-1}(X - \mu_i)} Generally speaking, the number of components serves as a rough indicator of the multimodality of the generated landscapes. However, the actual number of optima is likely to be less than the number of components as the peaks of weak components could be dominated by others. That said, my approach to generate test functions for this benchmark has been the following: 1. The dimensionality of the problem varies between :math:`N = 2` and :math:`N = 5` 2. The number of Gaussian components varies from 10 to 100 in steps of 5 3. The vectors of means :math:`\mu` is generated either from a uniform distribution or from a normal distribution 4. :math:`\omega` is either a random number between 0 and 1 or a specific array used to explicitly control the height of each component With all these variable settings, I generated 76 valid test function per dimension, thus the current LGMVG test suite contains 304 benchmark functions. A few examples of 2D benchmark functions created with the LGMVG generator can be seen in `Figure 7.1`_. .. _Figure 7.1: +------------------------------------------------------------------------------+------------------------------------------------------------------------------+---------------------------------------------------------------------+ | .. figure:: ../benchmarks/LGMVG/figures/docs/LGMVG_1.png | .. figure:: ../benchmarks/LGMVG/figures/docs/LGMVG_2.png | .. figure:: ../benchmarks/LGMVG/figures/docs/LGMVG_3.png | | :align: center | :align: center | :align: center | | | | | | **LGMVG Function 5** | **LGMVG Function 24** | **LGMVG Function 29** | +------------------------------------------------------------------------------+------------------------------------------------------------------------------+---------------------------------------------------------------------+ | .. figure:: ../benchmarks/LGMVG/figures/docs/LGMVG_4.png | .. figure:: ../benchmarks/LGMVG/figures/docs/LGMVG_5.png | .. figure:: ../benchmarks/LGMVG/figures/docs/LGMVG_6.png | | :align: center | :align: center | :align: center | | | | | | **LGMVG Function 53** | **LGMVG Function 63** | **LGMVG Function 72** | +------------------------------------------------------------------------------+------------------------------------------------------------------------------+---------------------------------------------------------------------+ | |test_functions| General Solvers Performances --------------------------------------------- `Table 7.1`_ below shows the overall success of all Global Optimization algorithms, considering every benchmark function, for a maximum allowable budget of :math:`NF = 2,000`. The LGMVG benchmark suite is a relatively easy test suite: the best solver for :math:`NF = 2,000` is **SHGO**, with a success rate of 77.6%, closely followed by **DualAnnealing** and :ref:`MCS`. .. note:: The reported number of functions evaluations refers to **successful optimizations only**. | .. _Table 7.1: .. cssclass:: pretty-table benchmark_dimensionality_table .. table:: **Table 7.1**: Solvers performances on the LGMVG benchmark suite at NF = 2,000 +---------------------+---------------------+-----------------------+ | Optimization Method | Overall Success (%) | Functions Evaluations | +=====================+=====================+=======================+ | AMPGO | 46.38% | 570 | +---------------------+---------------------+-----------------------+ | BasinHopping | 13.16% | 339 | +---------------------+---------------------+-----------------------+ | BiteOpt | 43.75% | 486 | +---------------------+---------------------+-----------------------+ | CMA-ES | 28.29% | 623 | +---------------------+---------------------+-----------------------+ | CRS2 | 50.66% | 1,002 | +---------------------+---------------------+-----------------------+ | DE | 42.11% | 1,198 | +---------------------+---------------------+-----------------------+ | DIRECT | 65.79% | 375 | +---------------------+---------------------+-----------------------+ | DualAnnealing | 75.33% | 322 | +---------------------+---------------------+-----------------------+ | LeapFrog | 32.57% | 246 | +---------------------+---------------------+-----------------------+ | MCS | 70.07% | 488 | +---------------------+---------------------+-----------------------+ | PSWARM | 20.39% | 1,686 | +---------------------+---------------------+-----------------------+ | SCE | 48.36% | 604 | +---------------------+---------------------+-----------------------+ | SHGO | 77.63% | 427 | +---------------------+---------------------+-----------------------+ These results are also depicted in `Figure 7.2`_, which shows that **SHGO** is the better-performing optimization algorithm, followed by **DualAnnealing** and :ref:`MCS`. .. _Figure 7.2: .. figure:: figures/LGMVG/performances_LGMVG_2000.png :alt: Optimization algorithms performances on the LGMVG test suite at :math:`NF = 2,000` :align: center **Figure 7.2**: Optimization algorithms performances on the LGMVG test suite at :math:`NF = 2,000` | Pushing the available budget to a very generous :math:`NF = 10,000`, the results show **SHGO** basically solving the vast majority of problems (more than 95%), followed at a distance by :ref:`MCS` and **DualAnnealing**. The results are also shown visually in `Figure 7.3`_. .. _Table 7.2: .. cssclass:: pretty-table benchmark_dimensionality_table .. table:: **Table 7.2**: Solvers performances on the LGMVG benchmark suite at NF = 10,000 +---------------------+---------------------+-----------------------+ | Optimization Method | Overall Success (%) | Functions Evaluations | +=====================+=====================+=======================+ | AMPGO | 73.03% | 2,304 | +---------------------+---------------------+-----------------------+ | BasinHopping | 11.84% | 412 | +---------------------+---------------------+-----------------------+ | BiteOpt | 49.67% | 1,072 | +---------------------+---------------------+-----------------------+ | CMA-ES | 33.22% | 1,390 | +---------------------+---------------------+-----------------------+ | CRS2 | 57.57% | 1,194 | +---------------------+---------------------+-----------------------+ | DE | 69.08% | 2,113 | +---------------------+---------------------+-----------------------+ | DIRECT | 73.68% | 791 | +---------------------+---------------------+-----------------------+ | DualAnnealing | 79.61% | 492 | +---------------------+---------------------+-----------------------+ | LeapFrog | 32.57% | 246 | +---------------------+---------------------+-----------------------+ | MCS | 86.18% | 1,214 | +---------------------+---------------------+-----------------------+ | PSWARM | 57.89% | 2,138 | +---------------------+---------------------+-----------------------+ | SCE | 53.62% | 896 | +---------------------+---------------------+-----------------------+ | SHGO | 95.07% | 1,357 | +---------------------+---------------------+-----------------------+ .. _Figure 7.3: .. figure:: figures/LGMVG/performances_LGMVG_10000.png :alt: Optimization algorithms performances on the LGMVG test suite at :math:`NF = 10,000` :align: center **Figure 7.3**: Optimization algorithms performances on the LGMVG test suite at :math:`NF = 10,000` | |results| Sensitivities on Functions Evaluations Budget ------------------------------------------------------- It is also interesting to analyze the success of an optimization algorithm based on the fraction (or percentage) of problems solved given a fixed number of allowed function evaluations, let’s say 100, 200, 300,... 2000, 5000, 10000. In order to do that, we can present the results using two different types of visualizations. The first one is some sort of "small multiples" in which each solver gets an individual subplot showing the improvement in the number of solved problems as a function of the available number of function evaluations - on top of a background set of grey, semi-transparent lines showing all the other solvers performances. This visual gives an indication of how good/bad is a solver compared to all the others as function of the budget available. Results are shown in `Figure 7.4`_. .. _Figure 7.4: .. figure:: figures/LGMVG/sm_maxfun_LGMVG.png :alt: Percentage of problems solved given a fixed number of function evaluations on the LGMVG test suite :align: center **Figure 7.4**: Percentage of problems solved given a fixed number of function evaluations on the LGMVG test suite | The second type of visualization is sometimes referred as "Slopegraph" and there are many variants on the plot layout and appearance that we can implement. The version shown in `Figure 7.5`_ aggregates all the solvers together, so it is easier to spot when a solver overtakes another or the overall performance of an algorithm while the available budget of function evaluations changes. .. _Figure 7.5: .. figure:: figures/LGMVG/sg_maxfun_LGMVG.png :alt: Percentage of problems solved given a fixed number of function evaluations on the LGMVG test suite :align: center **Figure 7.5**: Percentage of problems solved given a fixed number of function evaluations on the LGMVG test suite | A few obvious conclusions we can draw from these pictures are: 1. For this specific benchmark test suite, if you have a very limited budget in terms of function evaluations, then the best choices are **DualAnnealing**, **SHGO** and **DIRECT**. 2. There is a distinct improvements of performances for solvers like **AMPGO** and **DE** when the maximum number of function evaluations is relaxed (to very high limits though). In general though, if you have a large budget then **SHGO**, **DualAnnealing** and :ref:`MCS` are far superior compared to other algorithms. |size| Dimensionality Effects ----------------------------- Since I used the LGMVG test suite to generate test functions with dimensionality ranging from 2 to 5, it is interesting to take a look at the solvers performances as a function of the problem dimensionality. Of course, in general it is to be expected that for larger dimensions less problems are going to be solved - although it is not always necessarily so as it also depends on the function being generated. Results are shown in `Table 7.3`_ . .. _Table 7.3: .. cssclass:: pretty-table benchmark_dimensionality_table .. table:: **Table 7.3**: Dimensionality effects on the LGMVG benchmark suite at NF = 2,000 +-------------------+--------------------+-------------------+-------------------+-------------------+-------------------+ | **Solver** | **N = 2** | **N = 3** | **N = 4** | **N = 5** | **Overall** | +===================+====================+===================+===================+===================+===================+ | AMPGO | 82.9 | 53.9 | 32.9 | 15.8 | 46.4 | +-------------------+--------------------+-------------------+-------------------+-------------------+-------------------+ | BasinHopping | :boldred:`19.7` | 18.4 | 9.2 | 5.3 | 13.2 | +-------------------+--------------------+-------------------+-------------------+-------------------+-------------------+ | BiteOpt | 85.5 | 47.4 | 30.3 | 11.8 | 43.8 | +-------------------+--------------------+-------------------+-------------------+-------------------+-------------------+ | CMA-ES | 48.7 | 25.0 | 21.1 | 18.4 | 28.3 | +-------------------+--------------------+-------------------+-------------------+-------------------+-------------------+ | CRS2 | 85.5 | 59.2 | 44.7 | 13.2 | 50.7 | +-------------------+--------------------+-------------------+-------------------+-------------------+-------------------+ | DE | 92.1 | 71.1 | 5.3 | :boldred:`0.0` | 42.1 | +-------------------+--------------------+-------------------+-------------------+-------------------+-------------------+ | DIRECT | 98.7 | 80.3 | 60.5 | 23.7 | 65.8 | +-------------------+--------------------+-------------------+-------------------+-------------------+-------------------+ | DualAnnealing | :boldgreen:`100.0` | 77.6 | 67.1 | :boldgreen:`56.6` | 75.3 | +-------------------+--------------------+-------------------+-------------------+-------------------+-------------------+ | LeapFrog | 59.2 | 30.3 | 17.1 | 23.7 | 32.6 | +-------------------+--------------------+-------------------+-------------------+-------------------+-------------------+ | MCS | 98.7 | 89.5 | 56.6 | 35.5 | 70.1 | +-------------------+--------------------+-------------------+-------------------+-------------------+-------------------+ | PSWARM | 80.3 | :boldred:`1.3` | :boldred:`0.0` | :boldred:`0.0` | 20.4 | +-------------------+--------------------+-------------------+-------------------+-------------------+-------------------+ | SCE | 82.9 | 48.7 | 27.6 | 34.2 | 48.4 | +-------------------+--------------------+-------------------+-------------------+-------------------+-------------------+ | :boldgreen:`SHGO` | :boldgreen:`100.0` | :boldgreen:`98.7` | :boldgreen:`77.6` | 34.2 | :boldgreen:`77.6` | +-------------------+--------------------+-------------------+-------------------+-------------------+-------------------+ | `Figure 7.6`_ shows the same results in a visual way. .. _Figure 7.6: .. figure:: figures/LGMVG/LGMVG_high_level_dimens_2000.png :alt: Percentage of problems solved as a function of problem dimension at :math:`NF = 2,000` :align: center **Figure 7.6**: Percentage of problems solved as a function of problem dimension for the LGMVG test suite at :math:`NF = 2,000` | What we can infer from the table and the figure is that, for lower dimensionality problems (:math:`NF < 5`), the **SHGO** algorithm has a significant advantage over all other algorithms, although the SciPy optimizer **DualAnnealing** is not too far behind. For higher dimensionality problems (:math:`N \geq 5`), **DualAnnealing** appears to be better than any other solver. Pushing the available budget to a very generous :math:`NF = 10,000`, the results show that **SHGO** is always the best solver no matter what dimensionality we are considering. It has 100% success rate for low dimensional problems (:math:`N \leq 3`) and very good convergence results for higher dimensions. The results for the benchmarks at :math:`NF = 10,000` are displayed in `Table 7.4`_ and `Figure 7.7`_. .. _Table 7.4: .. cssclass:: pretty-table benchmark_dimensionality_table .. table:: **Table 7.4**: Dimensionality effects on the LGMVG benchmark suite at NF = 10,000 +-------------------+--------------------+--------------------+-------------------+-------------------+-------------------+ | **Solver** | **N = 2** | **N = 3** | **N = 4** | **N = 5** | **Overall** | +===================+====================+====================+===================+===================+===================+ | AMPGO | :boldgreen:`100.0` | 86.8 | 63.2 | 42.1 | 73.0 | +-------------------+--------------------+--------------------+-------------------+-------------------+-------------------+ | BasinHopping | :boldred:`21.1` | :boldred:`14.5` | :boldred:`6.6` | :boldred:`5.3` | 11.8 | +-------------------+--------------------+--------------------+-------------------+-------------------+-------------------+ | BiteOpt | 90.8 | 57.9 | 34.2 | 15.8 | 49.7 | +-------------------+--------------------+--------------------+-------------------+-------------------+-------------------+ | CMA-ES | 61.8 | 27.6 | 23.7 | 19.7 | 33.2 | +-------------------+--------------------+--------------------+-------------------+-------------------+-------------------+ | CRS2 | 85.5 | 61.8 | 47.4 | 35.5 | 57.6 | +-------------------+--------------------+--------------------+-------------------+-------------------+-------------------+ | DE | 92.1 | 75.0 | 57.9 | 51.3 | 69.1 | +-------------------+--------------------+--------------------+-------------------+-------------------+-------------------+ | DIRECT | :boldgreen:`100.0` | 84.2 | 68.4 | 42.1 | 73.7 | +-------------------+--------------------+--------------------+-------------------+-------------------+-------------------+ | DualAnnealing | :boldgreen:`100.0` | 81.6 | 73.7 | 63.2 | 79.6 | +-------------------+--------------------+--------------------+-------------------+-------------------+-------------------+ | LeapFrog | 59.2 | 30.3 | 17.1 | 23.7 | 32.6 | +-------------------+--------------------+--------------------+-------------------+-------------------+-------------------+ | MCS | 98.7 | 97.4 | 88.2 | 60.5 | 86.2 | +-------------------+--------------------+--------------------+-------------------+-------------------+-------------------+ | PSWARM | 97.4 | 61.8 | 42.1 | 30.3 | 57.9 | +-------------------+--------------------+--------------------+-------------------+-------------------+-------------------+ | SCE | 84.2 | 59.2 | 40.8 | 30.3 | 53.6 | +-------------------+--------------------+--------------------+-------------------+-------------------+-------------------+ | :boldgreen:`SHGO` | :boldgreen:`100.0` | :boldgreen:`100.0` | :boldgreen:`90.8` | :boldgreen:`89.5` | :boldgreen:`95.1` | +-------------------+--------------------+--------------------+-------------------+-------------------+-------------------+ | .. _Figure 7.7: .. figure:: figures/LGMVG/LGMVG_high_level_dimens_10000.png :alt: Percentage of problems solved as a function of problem dimension at :math:`NF = 10,000` :align: center **Figure 7.7**: Percentage of problems solved as a function of problem dimension for the LGMVG test suite at :math:`NF = 10,000`