General Techniques in Local Search

Variable depth search seems to show more promise than elementary local search due to the possibility that one need not get stuck at local optima. Continuing along the search path, even though it seems to bring less attractive solutions at times does lead to better solutions.

Some notation is required in order to develop a description of the general algorithm. An instance of a problem contains units which can be manipulated in order to form new solutions.

Here are some examples. For graph partitioning, an instance is the graph, units are vertices, and a solution is a partition. Thus swapping vertices between partitions forms new solutions. In the closed tour problem an instance is the distance matrix, units are cities, and solutions are tours. Here, changing a city's position in the tour forms a new solution.

For a problem of size n, we shall say that there are n possible units that can be manipulated to form new solutions since this should be proportional to the problem size. After a group of units (denoted U) is changed, all of the units in U become unavailable for further change. A neighborhood for a solution S is then:

N(S) = { S_U | the units in U were changed in S to form S_U }.

Each solution has a cost and we denote the gain of changing from solution S to solution S_U as:

g(U) = cost(S_U) - cost(S).

In the algorithm, we construct a sequence of solutions: S₀, ... , S_m after which there are no units remaining which can be changed. The integer m depends upon the neighborhood definition. In the MinCut graph partitioning algorithm this was one less than n/2, and in the 1-change closed city tour algorithm this was n-1. At each stage in the sequence we define G[i] as the total gain of S_i over S₀ or if the units in U were modified in order to form S_i:

G[i] = G[i-1] + g(U).

Figure 1 contains the general algorithm.

Figure 1 - Variable Depth Local Search Algorithm

Examining the algorithm reveals that in order to apply this technique to a problem, we must define:

• an initial feasible solution,
• neighborhoods for feasible solutions, and
• costs of solutions or objective functions.

Initial solutions appear in two flavors: random, and the result of a greedy algorithm. Each has its champions. Possibly the best approach is to try both. That is, add a greedy initial solution to a collection of randomly generated solutions.

Neighborhood definition is an art form. They can be obvious, but many are clever and elegant, and some border upon genius. The key to a good neighborhood definition is primarily ease of manipulation. A good formulation makes all of the manipulation and computation flow quickly and easily. A clumsy neighborhood adds to the algorithm’s complexity.

This brings up the computational methods and data structures, which are part of the local search algorithm. We must also develop:

• representations for feasible solutions,
• search techniques for neighborhoods, and
• evaluation methods for gains in cost.

Most feasible solution representations are straightforward. A sequence of cities can be used for closed tours or two sets represents a partition of graph vertices. But, occasionally clever representations can be found which are easier to manipulate than obvious ones. Thus designing solution representations is also an art form.

Searching neighborhoods can be very time consuming if the neighborhood is large and if evaluating the objective function for solutions in the neighborhood is lengthy. There are two common search strategies. One is a greedy search called first improvement because the first solution found that is better than the original is immediately adopted. The other involves searching the entire neighborhood for the best solution and is called steepest descent. It is not clear that the extra time involved in searching an entire neighborhood is that useful. Consider the two-dimensional optimization problem shown in figure 2.

Figure 2 - First Improvement Search Path

Only in a few cases was the best solution in a neighborhood selected, but the algorithm did find the optimal solution just the same. In fact, it took one more neighborhood examination than if a full search of each neighborhood took place, but this is not bad at all if a full search requires O(n²) steps and a restricted search O(n). This example was of course hypothetical, but it does illustrate the attractiveness of not searching entire neighborhoods.

The variable depth method is a nice compromise between the first improvement and steepest descent methods. It begins by searching the entire neighborhood, but reduces its search area as units become unavailable for manipulation.

Finally, if computing the gain involved by changing to a neighboring solution can be sped up, lots of time can be saved. The min-cut algorithm accomplishes this by updating the gain values in linear time during each iteration rather than recomputing all of them at a cost of quadratic time.

In order to perform proper algorithm analysis, three items must be examined when presenting a local search algorithm,

• correctness,
• complexity, and
• the possibility of achieving an optimal solution.

Correctness is often rather simple to guarantee since all that needs to be shown is that a feasible solution is produced. Of course, if the cost can be bounded as some of the previous examples were, this is better.

Complexity is mainly the size of the neighborhood searched times the number of solutions in a sequence if the outer loop is executed only a few times. Otherwise, the algorithm might run for an exponential amount of time. After all, if solutions get better and better it is possible to examine a large number of feasible solutions before halting. In practice, most algorithms execute the outer loop less than five times for large problem instance sizes.

The last consideration, proving that it is possible to go from any initial feasible solution to an optimal one is a nice touch. It really says that the algorithm has a chance of achieving optimality if one is very lucky. It also in some sense certifies that the neighborhood definition and search procedure are reasonable. It is not as trivial as one might think since there are highly cited algorithms in the literature that can be shown to never produce an optimal solution with certain inputs.