One troublesome aspect of heuristic problem solving is that sometimes the answers they give are absurdly bad. Often, a human can see immediately that a solution is not optimal. This aspect of seeing inefficiencies is very worrisome. People don't trust solutions that they can improve on easily. They are not convinced that the solution is ``good'' when it can be made better so quickly. Furthermore, most heuristics can be fooled very badly in some pathological situations. Therefore, it is always good to have a second line of defense. It is normally quite straightforward to create improving heuristics that will create solutions that no human can quickly improve upon. This means that the solutions will look more reasonable and will be more likely to be implemented. Also, since every solution has gone through two stages, it is far more difficult to create examples where the answer is completely absurd.
For the TSP, 2-exchanging creates good solutions, but humans can do 3-exchanging by eye, so even 2-exchanged tours can look bad to us.
To review, given a method to do exchanges, local optimization is as follows:
0) Let S be our current solution.
1) Let S' be the solution after doing some exchange of S.
2) If S' is a better solution, set S to S', go to 1.
3) Otherwise, determine if there is an unexamined exchange of S. If so, go to step 1. Otherwise, terminate, S is the best solution found.
The resulting solution is called a local optimal solution. The ``local'' part of this phrase comes from the fact that it is not the overall optimal solution (probably), but it is better than any solution you can get by exchanging.
In many cases, with a good start and a good exchange rule, the local optimal solution you get is good enough. Note, however, that there might be many local optimal solutions, and you may be stuck with a bad one. This leads naturally to a search for a good local optimal solution. We look at two methods for generating good local optimal solutions: iterated local search and simulated annealing. algorithms.