WCCI2008 Scale-Invariant Optimisation Competition

"Mountains or Molehills"

The competition that puts the exploration back in real-valued optimisation!

Introduction

Real-valued optimisation getting you down? Feel like your populations or swarms have been on a downhill slide? Well, you're not alone.

Many of the benchmarking functions used to compare algorithms in the research literature can be characterised as "more or less downhill" (or flat), often with a few high frequency components (such as cosines) added to increase the modality and hence the difficulty. As a result, many solution algorithms can be roughly characterised as "jiggle about until you fall down a hole", with a good dose of on-going jiggling in case it was the wrong hole. Thus the biases in the benchmark functions and the biases in the solution algorithms have evolved hand-in-hand.

Of course we're simplifying a bit, and other factors such as high-dimensionality and deceptive functions can make the right "holes" hard to find. Nevertheless, it can be argued that many algorithms are primarily designed around exploitation, with exploration taking a back seat.

This competition is set to change all that, forcing solution algorithms to focus as much on the "ups" as the "downs", and put exploration on an equal footing.

Imagine your spaceship has crash landed on an unknown planet. As you regain consciousness after your shocking ordeal, during which your spaceship lost all communications with the outside galaxy, you notice that you have landed in a barren and rugged mountainous terrain.

Being well trained in emergency procedures, you know that your first task is to locate the lowest point on the planet that you can find, in order to establish a base and start drilling for water. You can see that you are in some kind of valley, but you don't know how high that valley is, and whether there are much better places to drill over the surrounding hills. To make matters worse, however, you have no idea how large the planet is, and how big its mountains are - you don't know the scale of the planet. You literally don't know whether the "hills" that you can see are the mountains or the molehills!

Luckily the health and safety engineers have thought of such predicaments, and have included in your emergency kit one thousand aerial probes that can be used to explore the planet. Each probe can be dispatched in the direction and distance of your choosing, where it will deposit itself in the ground and send back readings including the relative height, or depth, at that point. 

The emergency kit also contains a computer that you can use to help with the task. The computer is able to feed the relative co-ordinates into a probe, dispatch it to that location, and accept the relative height value by return.

Your challenge, therefore, is to write an algorithm that finds the lowest point you can using the 1000 probes.

Technical Goals

This competition is designed to challenge a broad range of algorithms from evolutionary and particle swarm algorithms through to traditional search algorithms and their hybrids, and self-adaptive or learning algorithms. All algorithms are put on an even playing field by allowing a fixed number of fitness function evaluations.