We will get to some more techniques for finding a good solution. Unfortunately, although these techniques are fairly robust, they do not have the generality of random and greedy. There is one more general technique I want to discuss: exchange.
Suppose we have a solution. It is often possible to generate a better solution simply by modifying our solution in some way. For instance, if we have a TSP on a map and we see that our tour crosses itself, we can generally improve the tour by replacing two edges with two others. This method of replacing a limited number of variables with other values is called exchanging. It doesn't change the entire solution; it only changes parts of it.
More formally, for any integer k, we can define a k-exchange to take k variables out of the solution and add k (probably different) variables to the solution. Again, this is an idea, not an algorithm. Let's see how we can apply this to our problem.
Suppose we have a tour through the cities. If we remove two edges from the tour, we generally break the tour into two pieces. We can then add two other edges to create a new tour. We can compare the cost of this tour to the old tour and keep the better of the two. To find a very good solution, we can cycle through all possible exchanges. If an exchange is found that improves the objective, then we adopt the new solution as our current solution. If an exchange is worse, then we keep our current solution. This continues until we have a solution for which no exchange is better. This solution is termed a local optimum, for no solution near it (in the sense that it can be reached in one exchange) is better. Depending on how good the exchange algorithm works, local optima can be very, very good, or very, very bad. For the TSP, k=3 gives wonderful answers, while k=2 gives fairly poor answers.
Of course, we could choose k equal to n for these problems and any
local optimum would be a global optimum (that is, it would be an
optimal solution). Clearly, though, the work per iteration is at
least 
. Generally, in order to keep the work down, k is set
to some small number, perhaps 2 or 3. This keeps most of the
structure of our current solution but allows some change.