If we know the equation for a response surface, then it is relatively easy to find the optimum response. Unfortunately, we rarely know any useful details about the response surface. Instead, we must determine the response surface’s shape and locate the optimum response by running appropriate experiments. One approach for finding the optimum is a searching algorithm.
Shown below is a portion of the South Dakota Badlands, a landscape that includes many narrow ridges formed through erosion. Suppose you wish to climb to the ridge’s highest point. Because the shortest path to the summit is not obvious, you might adopt the following simple rule—look around you and take a step in the direction that has the greatest change in elevation. The route you follow is the result of a systematic search using a searching algorithm. Of course there are as many possible routes as there are starting points, three examples of which are shown by the white paths. Note that some routes do not reach the highest point—what we call the global optimum. Instead, many routes reach a local optimum from which further movement is impossible.
A searching algorithm is characterized by its effectiveness and its efficiency. To be effective, a searching algorithm must find the response surface’s global optimum, or at least reach a point near the global optimum. A searching algorithm may fail to find the global optimum for several reasons, including a poorly designed algorithm, noise affecting the response, or the presence of local optima.
A poorly designed algorithm may prematurely end the search before it reaches the response surface’s global optimum. As shown in the illustration below, an algorithm for climbing a ridge that slopes to the northeast is likely to fail if it allows you to take steps only to the north, south, east, or west.
All measurements contain uncertainty, or noise, that affects our ability to characterize the underlying signal. When the noise is greater than the local change in the signal, then a searching algorithm is likely to end before it reaches the global optimum. The photo below provides a different view of the photo at the top of this post, showing us that the relatively flat terrain leading up to the ridge is heavily weathered and uneven. Because the variation in local height exceeds the slope, our searching algorithm stops the first time we step up onto a less weathered surface.
Finally, a response surface may contain several local optima, only one of which is the global optimum. If we begin the search near a local optimum, our searching algorithm may not be capable of reaching the global optimum. The ridges in the photo above, for example, has many peaks. Only those searches beginning at the far right will reach the highest point on the ridge. Ideally, a searching algorithm should reach the global optimum regardless of where it starts.