Rastrigin function explained

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 Rastrigin[1] as a 2-dimensional function and has been generalized by Rudolph.[2] The generalized version was popularized by Hoffmeister & Bäck[3] and Mühlenbein et al.[4] 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(x)=An+

n
\sum
i=1
2
\left[x
i

-A\cos(2\pixi)\right]

where

A=10

and

xi\in[-5.12,5.12]

. There are many extrema:

x=0

where

f(x)=0

.

xi\in[-5.12,5.12]

is located around

xi\in[\pm4.52299366...,...,\pm4.52299366...]

:
Number of dimensionsMaximum value at

\pm4.52299366


140.35329019
280.70658039
3121.0598706
4161.4131608
5201.7664509
6242.1197412
7282.4730314
8322.8263216
9363.1796117

Here are all the values at 0.5 interval listed for the 2D Rastrigin function with

xi\in[-5.12,5.12]

:

f(x)

x1

0

\pm0.5

\pm1

\pm1.5

\pm2

\pm2.5

\pm3

\pm3.5

\pm4

\pm4.5

\pm5

\pm5.12

x2

0

020.25122.25426.25932.251640.252528.92

\pm0.5

20.2540.521.2542.524.2546.529.2552.536.2560.545.2549.17

\pm1

121.25223.25527.251033.251741.252629.92

\pm1.5

22.2542.523.2544.526.2548.531.2554.538.2562.547.2551.17

\pm2

424.25526.25830.251336.252044.252932.92

\pm2.5

26.2546.527.2548.530.2552.535.2558.542.2566.551.2555.17

\pm3

929.251031.251335.251841.252549.253437.92

\pm3.5

32.2552.533.2554.536.2558.541.2564.548.2572.557.2561.17

\pm4

1636.251738.252042.252548.253256.254144.92

\pm4.5

40.2560.541.2562.544.2566.549.2572.556.2580.565.2569.17

\pm5

2545.252647.252951.253457.254165.255053.92

\pm5.12

28.9249.1729.9251.1732.9255.1737.9261.1744.9269.1753.9257.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

Notes

  1. Rastrigin, L. A. "Systems of extremal control." Mir, Moscow (1974).
  2. G. Rudolph. "Globale Optimierung mit parallelen Evolutionsstrategien". Diplomarbeit. Department of Computer Science, University of Dortmund, July 1990.
  3. F. 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.
  4. H. Mühlenbein, D. Schomisch and J. Born. "The Parallel Genetic Algorithm as Function Optimizer ". Parallel Computing, 17, pages 619 - 632, 1991.