Multiple Local Optima

In this post I’ll present one of the examples I used in my lecture at the Design Modelling Symposium in Berlin in October/2011. This particular example shows how the Simulated Annealing solver handles fitness landscapes with multiple local optima. I’ll also talk briefly about how to set up the test-case in Grasshopper+Galapagos.

Most problems have multiple local optima, sometimes these optima represent very similar fitnesses and sometimes they represent very different fitnesses. A good solver should not allow itself to get stuck in a low-quality optimum.

Let’s consider the problem of fitting a circle to a collection of points in the 2D plane so that the distance between the circle and the points is minimized. There are good algorithms available for finding such a circle so we don’t have to rely on a generic solver such as Simulated Annealing, but it is a good example because it’s both easy to set up and see whether or not the answer we’re given is correct.

Our problem is three-dimensional while we’re limited to the 2D plane because the least amount of variables we need to define any circle equals three; x, y and radius. Every unique combination of {x,y,R} results in a unique circle, and every possible circle can be represented by picking the appropriate {x,y,R}. So the question basically becomes; “which values for x, y and R result in the best fitting circle?”

The Grasshopper file that represents both this problem and the fitness function looks as follows:

We have a collection of target points stored in the red point parameter. Our three variables are represented by the three sliders. The green group contains the two components that create a circle from the three variables and the blue group contains the components that measure the distance (i.e. fitness) from the points to the circle. As you can see I’m actually measuring the square of the distance rather than distance itself. Most fitting operations minimize the square of the distances as that’s a more useful mathematical concept. I explain why this is needed in the Define Fitness and Fitness Pressure blog posts.

The title of this post is “Multiple Local Optima” and it might surprise you to learn that the fitness landscape associated with this problem does indeed have multiple optima. There’s the obvious fitness peak at the {x,y,R} state which represents the best fit, but there’s an additional peak hiding along the edges of the landscape. To see why this is so have a look at the following two cases:

The green curve represents a circle which is obviously far too large to be a good fit. We’d expect a somewhat smaller circle to have a higher fitness, but unfortunately it doesn’t. Or rather, it doesn’t up to a certain size. The much larger red circle is actually more “fit” by our definition than the green one because even though it is farther away from the points in the upper left, it is closer to the points in the lower right. And due to the square root in our fitness definition, a somewhat smaller large distance is to be preferred over a somewhat larger small distance. When we actually plot the real fitness landscape this double peak characteristic becomes visible:

I had to collapse the x and y variables into a single axis called ‘Position’ because it’s difficult to display a four-dimensional landscape on a two-dimensional computer screen, but otherwise this graphic is synonymous with the real fitness landscape. In the lower left hand corner you can see a high peak that corresponds with the ideal circle. However towards the upper right corner there is a gradual slope. This slope never gets anywhere near as high as the green peak, but it does continue to get higher and higher the further you go (in a fashion similar to the ArcTangent function).

When we plot the path of steepest ascent for every point in this landscape and assign a colour to the point based on which peak we found, we end up with two regions; green and red. One leads to the ideal solution, the other leads to the wrong solution. These two regions are called ‘Basins of Attraction’ and every peak has a basin around it by definition*. The larger the basin of attraction the easier it becomes to ‘find’ a peak. Ideally we’d like our solvers to be able to find peaks according to their height, not by the size of their respective basins. So when we ask the Simulated Annealing solver to tackle this problem, we expect to end up at the green peak more often than the red one.

Download the file and find out!

* Actually this is not true for some Fractal landscapes, but then fractal fitness landscapes are near impossible to solve anyway.