Algorithms For Dummies

  Performing Local Search 

     341

3. 

Determine which solution to use in place of the current solution based on the 

output of a heuristic that accepts the candidates’ list as input.

4. 

Continue performing Steps 2 and 3 until you see no further improvement on 

the solution, which means that you have the best solution available.

Although easy to design, local search solutions may not find a solution in a rea-

sonable time (you can stop the process and use the current solution) or produce a 

minimum quality solution. You can employ some tricks of the trade to ensure that 

you get the most out of this approach.

At the start of the local search, you pick an initial solution. If you decide on a ran-

dom solution, it’s helpful to wrap the search in repeated iterations in which you 

generate  different  random  start  solutions.  Sometimes,  arriving  at  a  good  final 

solution depends on the starting point. If you start from an existing solution to be 

refined,  plugging  the  solution  into  a  greedy  algorithm  may  prove  to  be  a  good 

compromise in fitting a solution that doesn’t take too long to produce.

After choosing a starting point, define the neighborhood and determine its size. 

Defining a neighborhood requires figuring the smallest change you can impose on 

your solution. If a solution is a set of elements, all the neighboring solutions are 

the sets in which one of the elements mutates. For instance, in the traveling sales-

man  problem  (TSP),  neighboring  solutions  could  involve  changing  the  ending 

 cities of two (or more) trips, as shown in Figure 18-1.

Based on how you create the neighborhood, you may have a smaller or a larger 

candidates’ list. Larger lists require more time and computations but, contrary to 

short lists, may offer more opportunities for the process to end earlier and better. 

FIGURE 18-1: 

Switching ending 

trips in a TSP 

problem may 

bring better 

results.

---

342