The Moving Peaks Benchmark

The Moving Peaks Benchmark is a fitness function changing over time. It consists of a number of peaks, changing in height, width and location. A simple visualization has been included below, a more formal description can be found here. Two similar versions of this benchmark have been proposed independently at the Congress of Evoluationary Computation held at Washington D.C. in July 1999 by Jürgen Branke resp. Ron Morrison and Ken DeJong. The version compiled here tries to cover many (but not all) of the features available at either of the original versions, and adds some more. Also, it is programmed to be easily expandable. Eventually, I still hope that we can come up with a unified version, but since this took too long, we decided it would be a good idea to release the current version. I will try to ensure that future versions remain compatible with this one.

Parameters

The benchmark allows to set the following parameters:

• the random seed of the benchmark problem. Different random seeds lead to a different initialization and different changes. Using a fixed random seed allows to reproduce the exact benchmark over and over.
• number of peaks
• number of dimensions resp. real-valued genes
• minimum and maximum height of each peak
• minimum and maximum slope of each peak
• minimum and maximum coordinate in each dimension
• vlength, the distance a single peak moves when change_peaks() is called. This distance may also be changed during the run by calling change_stepsize()
• height_severity and width_severity, the standard deviation of the changes made to the height resp. width parameters
• inclusion of a stationary (not moving) basis function. This might e.g. be useful to study a single moving peak in an otherwise fixed landscape, or to introduce a lower bound to the fitness values.
• arbitrary peak functions, but the only changing features are the location of the center, the height and the slope
• the correlation between consecutive movements of a single peak. For lambda = 0.0, the movements are completely uncorrelated, for lambda = 1.0, the peak always moves in the same direction (except at boundaries where it bounces off like a billard ball). The file maxpeak.ps shows a number of example paths of a single peak for different settings of lambda.
• change frequency. The fitness landscape changes whenever the "change_peaks()" function is called. The frequency of making these calls is up to the user.

Functions Provided

The module can be easily incorporated into any C program. Simply include the movpeaks.h file which allows you to call the functions

• init_peaks: creates a pseudo-random initial landscape. Since movpeak uses its own random number generator, the landscape only depends on the random number seed "movrandseed" as defined in movpeaks.c
• change_peaks: changes all peaks
• eval_movpeaks: takes as input an array of double-values (an individual) and returns the function value at that point
• dummy eval: allows function calls to the evaluation function that are not included in the performance measures (see below).
• free_peaks: frees the memory space at the end of the program
• change_stepsize allows to change the stepsize (vlength)

Performance Evaluation

• get_number_of_eval: returns the number of evaluations so far
• get_avg_error: returns the average deviation from the optimum of all evaluations so far
• get_offline_performance: returns the offline performance so far. Offline performance for dynamic optimization functions is defined as the average of all evaluations e*(t), where e*(t) is the best evaluation since the last change of the environment and time t.
• get_current_error: returns the deviation of the best individual evaluated since the last change from the optimum
• get_offline_error: returns the offline error so far. Offline error for dynamic optimization functions is defined as the average of all current errors, i.e. the average deviation of the currently best individual from the optimum.

Source Code

All other variables can be influenced from the main program by declaring them extern, an example is given  in movmain.c.

To download the source code,click here.

There is also a graphic version available that requires the QT library and a C++ compiler. It allows to view a 2-dimensional moving peaks landscape in motion. On the right you can see an example ouput of this version. When you click on the image, you will see 15 consecutive changes of the landscape, then starting again from the beginning. The source code of the graphical version is also available for download. Allways keep in mind that this can only show 2-dimensional versions of the benchmark.

Direct any questions or suggestions to Jürgen Branke, Institute AIFB, University of Germany, Karlsruhe. I will try to maintain the module, adding additional features, more standard settings, and increase usability.

If you experience any problems, find any bugs, or would like to have another feature added, please drop me a note. I will give my best efforts to respond timely.

Standard Settings

No matter how many features a benchmark provides, it is only useful when it is possible to reproduce it.
In the following, I will try to maintain a set of standard settings, with references and results. If you use other settings, or obtain better results with the settings below, let me know.

Scenario	1	2	3
movrand	1	1-5	1
no of peaks	5	10-200	50
no of dimensions	5	5	5
minheight	30	30	30
maxheight	70	70	70
stdheight	50	50	0
minwidth	0.0001	1.0	1.0
maxwidth	0.2	12.0	12.0
stdwidth	0.1	0.0	0.0
mincoordinate	0	0	0
maxcoordinate	100	100	100
vlength	0.0-2.0	0.0-3.0	1.0
height_severity	7.0	7.0	1.0
width_severity	0.01	1.0	0.5
use_basis_function	FALSE	FALSE	TRUE
correlation lambda	0.0	0.0-1.0	0.5
change every x evaluations	5000	1000-5000	1000
peak_function	function1	cone	cone
change_stepsize	constant	constant	constant

Remarks concerning the different scenarios:

1.  The settings I used in my CEC paper [2] are no longer exactly reproducable with this benchmark. The settings from scenario 1 would probably come closest.

2. For a recent paper [4], I have run a number of experiments with scenario2. It uses more peaks, a different peak shape, and different correlation values. To give an idea for performance, using scenario 2 with a change every 5000 evaluations, no of peaks 50, vlength 1.0 and correlation lambda 0.0 I achieve an offline error of 4.605 (average over 50 runs with different random seeds for the GA and movrandseed=1 all the time).

A recent survey on papers using the Moving Peaks Benchmark has been compiled by Irene Moser from Swinburne University of Technology and is courteously provided for download here.

References:

[1] J. Branke: "Evolutionary Algorithms for Dynamic Optimization Problems - A Survey -", Technical Report No. 387, Insitute AIFB, University of Karlsruhe, 76128 Karlsruh e, Germany, February 1999

[2] J. Branke: "Memory-Enhanced Evolutionary Algorithms", Congress on Evolutionary Computation (CEC'99), IEEE, 1999, vol.3 pp. 1875-1882

[3] J. Branke: "Evolutionary Approaches to Dynamic Optimization Problems - A Survey", GECCO Workshop on Evolutionary Algorithms for Dynamic Optimization Problems, A. Wu (ed.), 1999, pp. 134-137

[4] J. Branke, H. Schmeck: "Designing Evolutionary Algorithms for Dynamic Optimization Problems", In S. Tsutsui and A. Ghosh, editors, Theory and Application of Evolutionary Computation: Recent Trends, pages 239-262. Springer, 2002