Rastrigin function

{{short description|Function used as a performance test problem for optimization algorithms}}

{{multiple image

| direction = vertical

| width = 300

| header = Rastrigin function of two variables

| image1 = Rastrigin_function.png

| caption1 = In 3D

| image2 = Rastrigin-smooth-contour.svg

| caption2 = Contour

}}

In mathematical optimization, the Rastrigin function is a non-convex function used as a performance test problem for optimization algorithms. It is a typical example of non-linear multimodal function. It was first proposed in 1974 by RastriginRastrigin, L. A. "Systems of extremal control." Mir, Moscow (1974). as a 2-dimensional function and has been generalized by Rudolph.G. Rudolph. "Globale Optimierung mit parallelen Evolutionsstrategien". Diplomarbeit. Department of Computer Science, University of Dortmund, July 1990. The generalized version was popularized by Hoffmeister & BäckF. Hoffmeister and T. Bäck. "Genetic Algorithms and Evolution Strategies: Similarities and Differences", pages 455–469 in: H.-P. Schwefel and R. Männer (eds.): Parallel Problem Solving from Nature, PPSN I, Proceedings, Springer, 1991. and Mühlenbein et al.H. Mühlenbein, D. Schomisch and J. Born. "The Parallel Genetic Algorithm as Function Optimizer ". Parallel Computing, 17, pages 619–632, 1991. Finding the minimum of this function is a fairly difficult problem due to its large search space and its large number of local minima.

On an $n$ -dimensional domain it is defined by:

: $f(\mathbf{x}) = A n + \sum_{i=1}^n \left[x_i^2 - A\cos(2 \pi x_i)\right]$

where $A=10$ and $x_i\in[-5.12,5.12]$ . There are many extrema:

The global minimum is at $\mathbf{x} = \mathbf{0}$ where $f(\mathbf{x})=0$ .
The maximum function value for $x_i\in[-5.12,5.12]$ is located at $\mathbf{x} = (\pm4.52299366..., ..., \pm4.52299366...)$ :

class="wikitable"

Number of dimensions

! Maximum value at $\pm4.52299366$

style="vertical-align:bottom;"

| 1

| 40.35329019

style="vertical-align:bottom;"

| 2

| 80.70658039

style="vertical-align:bottom;"

| 3

| 121.0598706

style="vertical-align:bottom;"

| 4

| 161.4131608

style="vertical-align:bottom;"

| 5

| 201.7664509

style="vertical-align:bottom;"

| 6

| 242.1197412

style="vertical-align:bottom;"

| 7

| 282.4730314

style="vertical-align:bottom;"

| 8

| 322.8263216

style="vertical-align:bottom;"

| 9

| 363.1796117

Here are all the values at 0.5 interval listed for the 2D Rastrigin function with $x_i\in[-5.12,5.12]$ :

class="wikitable" style="font-weight:bold; vertical-align:bottom;"

style="text-align:center; vertical-align:middle;"

! rowspan="2" colspan="2" | $f(x)$

! colspan="12" | $x_1$

0

| $\pm0.5$

| $\pm1$

| $\pm1.5$

| $\pm2$

| $\pm2.5$

| $\pm3$

| $\pm3.5$

| $\pm4$

| $\pm4.5$

| $\pm5$

| $\pm5.12$

rowspan="12" style="text-align:center; vertical-align:middle;" |

x_2

| $0$

| style="background-color:#548235; color:#FFF;" | 0

| style="background-color:#FFE699; font-weight:normal;" | 20.25

| style="background-color:#B4C6E7;" | 1

| style="background-color:#FFE699; font-weight:normal;" | 22.25

| style="background-color:#B4C6E7;" | 4

| style="background-color:#FFE699; font-weight:normal;" | 26.25

| style="background-color:#B4C6E7;" | 9

| style="background-color:#FFE699; font-weight:normal;" | 32.25

| style="background-color:#B4C6E7;" | 16

| style="background-color:#FFE699; font-weight:normal;" | 40.25

| style="background-color:#B4C6E7;" | 25

| style="background-color:#FFE699; font-weight:normal;" | 28.92

style="font-weight:normal;"

| style="font-weight:bold;" | $\pm0.5$

| style="background-color:#FFE699;" | 20.25

| style="background-color:#FFBDD8;" | 40.5

| style="background-color:#FFE699;" | 21.25

| style="background-color:#FFBDD8;" | 42.5

| style="background-color:#FFE699;" | 24.25

| style="background-color:#FFBDD8;" | 46.5

| style="background-color:#FFE699;" | 29.25

| style="background-color:#FFBDD8;" | 52.5

| style="background-color:#FFE699;" | 36.25

| style="background-color:#FFBDD8;" | 60.5

| style="background-color:#FFE699;" | 45.25

| style="background-color:#FFBDD8;" | 49.17

\pm1

| style="background-color:#B4C6E7;" | 1

| style="background-color:#FFE699; font-weight:normal;" | 21.25

| style="background-color:#B4C6E7;" | 2

| style="background-color:#FFE699; font-weight:normal;" | 23.25

| style="background-color:#B4C6E7;" | 5

| style="background-color:#FFE699; font-weight:normal;" | 27.25

| style="background-color:#B4C6E7;" | 10

| style="background-color:#FFE699; font-weight:normal;" | 33.25

| style="background-color:#B4C6E7;" | 17

| style="background-color:#FFE699; font-weight:normal;" | 41.25

| style="background-color:#B4C6E7;" | 26

| style="background-color:#FFE699; font-weight:normal;" | 29.92

style="font-weight:normal;"

| style="font-weight:bold;" | $\pm1.5$

| style="background-color:#FFE699;" | 22.25

| style="background-color:#FFBDD8;" | 42.5

| style="background-color:#FFE699;" | 23.25

| style="background-color:#FFBDD8;" | 44.5

| style="background-color:#FFE699;" | 26.25

| style="background-color:#FFBDD8;" | 48.5

| style="background-color:#FFE699;" | 31.25

| style="background-color:#FFBDD8;" | 54.5

| style="background-color:#FFE699;" | 38.25

| style="background-color:#FFBDD8;" | 62.5

| style="background-color:#FFE699;" | 47.25

| style="background-color:#FFBDD8;" | 51.17

\pm2

| style="background-color:#B4C6E7;" | 4

| style="background-color:#FFE699; font-weight:normal;" | 24.25

| style="background-color:#B4C6E7;" | 5

| style="background-color:#FFE699; font-weight:normal;" | 26.25

| style="background-color:#B4C6E7;" | 8

| style="background-color:#FFE699; font-weight:normal;" | 30.25

| style="background-color:#B4C6E7;" | 13

| style="background-color:#FFE699; font-weight:normal;" | 36.25

| style="background-color:#B4C6E7;" | 20

| style="background-color:#FFE699; font-weight:normal;" | 44.25

| style="background-color:#B4C6E7;" | 29

| style="background-color:#FFE699; font-weight:normal;" | 32.92

style="font-weight:normal;"

| style="font-weight:bold;" | $\pm2.5$

| style="background-color:#FFE699;" | 26.25

| style="background-color:#FFBDD8;" | 46.5

| style="background-color:#FFE699;" | 27.25

| style="background-color:#FFBDD8;" | 48.5

| style="background-color:#FFE699;" | 30.25

| style="background-color:#FFBDD8;" | 52.5

| style="background-color:#FFE699;" | 35.25

| style="background-color:#FFBDD8;" | 58.5

| style="background-color:#FFE699;" | 42.25

| style="background-color:#FFBDD8;" | 66.5

| style="background-color:#FFE699;" | 51.25

| style="background-color:#FFBDD8;" | 55.17

\pm3

| style="background-color:#B4C6E7;" | 9

| style="background-color:#FFE699; font-weight:normal;" | 29.25

| style="background-color:#B4C6E7;" | 10

| style="background-color:#FFE699; font-weight:normal;" | 31.25

| style="background-color:#B4C6E7;" | 13

| style="background-color:#FFE699; font-weight:normal;" | 35.25

| style="background-color:#B4C6E7;" | 18

| style="background-color:#FFE699; font-weight:normal;" | 41.25

| style="background-color:#B4C6E7;" | 25

| style="background-color:#FFE699; font-weight:normal;" | 49.25

| style="background-color:#B4C6E7;" | 34

| style="background-color:#FFE699; font-weight:normal;" | 37.92

style="font-weight:normal;"

| style="font-weight:bold;" | $\pm3.5$

| style="background-color:#FFE699;" | 32.25

| style="background-color:#FFBDD8;" | 52.5

| style="background-color:#FFE699;" | 33.25

| style="background-color:#FFBDD8;" | 54.5

| style="background-color:#FFE699;" | 36.25

| style="background-color:#FFBDD8;" | 58.5

| style="background-color:#FFE699;" | 41.25

| style="background-color:#FFBDD8;" | 64.5

| style="background-color:#FFE699;" | 48.25

| style="background-color:#FFBDD8;" | 72.5

| style="background-color:#FFE699;" | 57.25

| style="background-color:#FFBDD8;" | 61.17

\pm4

| style="background-color:#B4C6E7;" | 16

| style="background-color:#FFE699; font-weight:normal;" | 36.25

| style="background-color:#B4C6E7;" | 17

| style="background-color:#FFE699; font-weight:normal;" | 38.25

| style="background-color:#B4C6E7;" | 20

| style="background-color:#FFE699; font-weight:normal;" | 42.25

| style="background-color:#B4C6E7;" | 25

| style="background-color:#FFE699; font-weight:normal;" | 48.25

| style="background-color:#B4C6E7;" | 32

| style="background-color:#FFE699; font-weight:normal;" | 56.25

| style="background-color:#B4C6E7;" | 41

| style="background-color:#FFE699; font-weight:normal;" | 44.92

style="font-weight:normal;"

| style="font-weight:bold;" | $\pm4.5$

| style="background-color:#FFE699;" | 40.25

| style="background-color:#FFBDD8;" | 60.5

| style="background-color:#FFE699;" | 41.25

| style="background-color:#FFBDD8;" | 62.5

| style="background-color:#FFE699;" | 44.25

| style="background-color:#FFBDD8;" | 66.5

| style="background-color:#FFE699;" | 49.25

| style="background-color:#FFBDD8;" | 72.5

| style="background-color:#FFE699;" | 56.25

| style="background-color:#C00000; color:#FFF;" | 80.5

| style="background-color:#FFE699;" | 65.25

| style="background-color:#FFBDD8;" | 69.17

\pm5

| style="background-color:#B4C6E7;" | 25

| style="background-color:#FFE699; font-weight:normal;" | 45.25

| style="background-color:#B4C6E7;" | 26

| style="background-color:#FFE699; font-weight:normal;" | 47.25

| style="background-color:#B4C6E7;" | 29

| style="background-color:#FFE699; font-weight:normal;" | 51.25

| style="background-color:#B4C6E7;" | 34

| style="background-color:#FFE699; font-weight:normal;" | 57.25

| style="background-color:#B4C6E7;" | 41

| style="background-color:#FFE699; font-weight:normal;" | 65.25

| style="background-color:#B4C6E7;" | 50

| style="background-color:#FFE699; font-weight:normal;" | 53.92

style="font-weight:normal;"

| style="font-weight:bold;" | $\pm5.12$

| style="background-color:#FFE699;" | 28.92

| style="background-color:#FFBDD8;" | 49.17

| style="background-color:#FFE699;" | 29.92

| style="background-color:#FFBDD8;" | 51.17

| style="background-color:#FFE699;" | 32.92

| style="background-color:#FFBDD8;" | 55.17

| style="background-color:#FFE699;" | 37.92

| style="background-color:#FFBDD8;" | 61.17

| style="background-color:#FFE699;" | 44.92

| style="background-color:#FFBDD8;" | 69.17

| style="background-color:#FFE699;" | 53.92

| style="background-color:#FFBDD8;" | 57.85

The abundance of local minima underlines the necessity of a global optimization algorithm when needing to find the global minimum. Local optimization algorithms are likely to get stuck in a local minimum.

See also

Test functions for optimization

Notes

Category:Test functions for optimization