The optimization method described in the previous section is well suited for an initial planning and in cases where the level of completeness or accuracy of input data is limited. For a detailed optimization that takes the full set of input data into account, a search approach is proposed. That is, the space of possible configurations denoted as search space is explored to find the point in the search space that is optimal with respect to a certain criterion. This point is denoted as global optimum. Exhaustive search traverses the complete search space in a systematic manner. As all points in the search space are visited, with exhaustive search it is guaranteed to find the global optimum. The search space is very large for typical applications in network planning. For each site there can easily be several hundreds of possible configurations. Furthermore, configurations of different sites cannot be considered independently, so that the amount of possible network configurations grows expotentially with the number of sites. Hence targeting this area, an exhaustive search is too time-consuming and local search algorithms are commonly used for network optimization purposes.
Local search algorithms start at some point in the search space denoted as initial solution and subsequently move from the present to neighboring solutions, if they fulfill some criterion, i.e., appear to be better or more promising. Local search algorithms cannot guarantee to find the global optimum. The objective of the search algorithm—developed or tailored for a particular problem—is to find a solution that is at least close to the global optimum. Local search algorithms are thus often classified as heuristics.
The basic procedure of local search is independent of the actual search algorithm applied. Starting from the initial solution in each search step, first a search neighborhood is generated. The search neighborhood is a subset of points from the search space that are close to the current solution, i.e., that have some attributes in common with the current solution. The point that is most appropriate with respect to some criterion is selected from the search neighborhood and accepted as new initial solution for the next search step. If no appropriate new solution is found (or some other stop criterion is fulfilled) the search is terminated. The comparison of points from the search space is carried out by means of cost values associated with them. The cost values are generated from a cost function, in the literature often also referred to as objective function. The objective function maps a given point in the search space to a cost value. The cost value can be a scalar but could also be represented by a vector. In the latter case, an appropriate function to compare cost values needs to be defined.
Local search algorithms are very much application specific. However, several search paradigms have been developed in the last three decades. The simplest search paradigm is the descent method. This method always selects the solution from the neighborhood that has lowest cost. If this value is lower than the lowest value in the last search step, the solution is accepted as a new solution, otherwise the algorithm is terminated. The algorithm hence explores the search space by always moving in the direction of the greatest improvement, so that it typically gets trapped in a local minimum. A local minimum is a solution that is optimal with respect to the search neighborhood but which generally is worse than the global optimum. To escape from local minima, among several others, one widely applied approach is to carry out restarts, that is, the local search is restarted from a new solution that is selected from a different area of the search space. The new start solutions are often selected randomly. If restarts are applied, the algorithm strictly speaking is not a local search algorithm anymore.
Another option for escaping from local minima is to accept also the cost deteriorating neighbors under certain conditions. The most prominent local search paradigms that apply this strategy are simulated annealing and Tabu search.
Simulated annealing is based on an analogy with the physical annealing process. In simulated annealing improving points from the neighborhood are always selected when exploring the search neighborhood, nonimproving points are accepted as new solutions with a certain probability. The probability of acceptance is a function of the level of deterioration, but also gradually decreases during the algorithm execution. The reduction of the probability of acceptance is determined by the cooling scheme.
In contrast to the simulated annealing which comprises randomness, classical Tabu search is deterministic. The basic operation is equivalent to the descent method with the difference that the best point from the neighborhood is also accepted if it is worse than the current solution. In this way the search is directed away from local minima. To avoid a move back to already visited solutions, a Tabu list is introduced. The Tabu list typically contains sets of attributes of solutions that have already been visited. If a point from the neighborhood exhibits one of the sets of attributes stored in the Tabu list, the point is only accepted as new solution if its quality, i.e., cost, exceeds a certain aspiration level. The Tabu list is updated, keeping the individual entries only for a number of iterations. The size of the Tabu list is a very important design parameter of the Tabu search, it in particular needs to be chosen large enough to prevent cycling, but a too large list might introduce too many restrictions. Several enhancements to the basic operation of the Tabu search have been introduced most of which modify the handling of the Tabu list. These include intensification and diversification schemes
