University of Kent

An explanation of the outputs produced by MARXAN (section 1)

Simulated annealing is the process at the heart of the MARXAN conservation planning software and its results can be displayed and manipulated using CLUZ. Sections 2 and 3 of this explanation describe how MARXAN uses this technique but this page explains how simulated annealing works by using an analogy based on robot exploration.

Imagine that the UK Government funded a project to look for life on Mars based on advice that it was most likely to be found in low-lying areas. The problem of finding the lowest-lying area on Mars is similar to the problem of finding the most efficient planning portfolio, in that there are a huge number of alternatives to choose between. This is why the Chief Scientist decided to develop robots that used a searching process based on simulated annealing. An example of the robot is shown on the left and it has four arms spaced equally around its diameter.

The first element of the simulated annealing process is based on iterative improvement. This means that the robot repeatedly follows the same set of rules to gradually locate low-lying areas. In this case the set of rules that the robots follows are:

1. Measure the elevation of the ground directly beneath the robot body.



2. Randomly choose an arm and measure the elevation of the ground beneath the arm.



3. If the ground beneath the arm is lower than the robot base then move to the point that was measured by the arm.

So if the robot was dropped by parachute onto the surface of Mars then it would move step-by-step downhill until it reached the valley bottom.

However, this strategy has a flaw, because it results in a process where the robot will never go uphill, and so won't locate lower areas on the other side of the valley in which it lands.

The result of the problem is illustrated here. The robot has moved to the bottom of the valley but there are deeper valleys elsewhere on the Mars surface.

The same problem occurs when choosing low-cost portfolios. By only accepting short term improvements, it is likely that more effective portfolios will be missed.

One way to reduce this problem is to add a random element to the iterative process, so that the robot occasionally moves up a slope in the hope that it might move into neighbouring, lower-lying valleys. These backward steps are generally more effective just after the robot has landed, before it has moved far down the original valley slope, so the simulated annealing process ensures that they tend to occur at the beginning of the iterative improvement process.

The value of this process is illustrated here. The left figure shows the robot landing and, at random, moving uphill.

The right figure shows the iterative improvement process that follows, which allows the robot to find the bottom of the new valley that it has entered.

The final way to increase the chances of finding the lowest-lying area is to repeat the process a number of times. This is illustrated below, where a number of robots are shown dropping to the surface of Mars.

This combination of 1) iterative improvement, 2) random backward steps towards the beginning of the process and 3) repetition, help ensure that the low-lying areas will be found. Increasing the number of iterations and increasing the number of repeats will also increase the likelihood of finding low-lying areas. However, increasing the number of iterations beyond a certain point will not increase the likelihood of finding low-lying areas. For example, it would be ineffective to increase the number of iterations so that the robot continued to search even when it was likely to have reached the valley bottom.

Click on the red arrow to go the next section, which describes how MARXAN uses similar principles to the ones described above to identify efficient portfolios.