How to Solve It:
Modern Heuristics
Zvigniew Michalewicz and David Fogel
pp. 64 ff -- local search.
Focus on a transformation of the given solution to try to improve it.
Suppose you are doing satisfiability.
Local search says:
loop
make a flip of a variable
if improve then keep and stop if done
else reject
until tired
For travelling salesman, the trick is to do local switches.
Take 2 non-adjacent edges and swap them.
e.g. take
(a,b) and (c,d) and suppose there is a path between b and c and between
a and d so we have
a-b-x1..x2- c-d-x3..x4-a
Now we swap so we get
d-b-x1..x2-c-a-x4..x3-d
If that is an improvement then we take it, else choose another.
The Lin-Kernighan algorithm does a clever search for k-opts and
can get within a few percent of the optimal.
In the basic method, k remains 2.
It uses a construct that is one away from a tour called a delta-path.
A delta-path is a sequence of nodes such that each node appears once
except the last one.
e.g. figure 3.7 on page 67.
a-b-c-d-e-c would be an example.
To repair this to a tour, just replace e-c by e-a.
Alternatively, replace c-d by a-d.
We might also do a "switch" by replacing e-c by e-b say.
Since there are two ways to make a delta-path into a tour,
there is the possibility of moving around the search space.
Figure 3.8 shows what to do but the gotos make it hard to read.
Start with a tour.
If there is a cheaper delta-path, then take it.
Look then for a cheaper switch.
Create a new tour. If that is an improvement, then make that the new tour.
To limit the search space, don't retry a switch that has already
been tried.
lin-kernighan [slightly rewritten from the book]
begin
generate a tour T
best_cost = cost(T)
for each node k of T do
for each edge (i k) of T do
begin
if there is a j != k such that cost(i,j) < cost(i,k)
then create a delta-path p by removing (i k) and adding (i j)
flag:= true
haveimproved:= false
while{flag // plus bookeeping to avoid redoing work
flag:= false
construct a tour T from p (but keep p around)
if cost(T) < best_cost
best_cost:= cost(T)
remember T
haveimproved:= true
end if
if there is a switch of p resulting in a delta-path
whose cost <= cost(T)
then
make the switch to get the new path and call that p
flag:= true
end while
if(haveimproved) then call lin-kernighan on best T so far
end if
end
end
p. 70
non-linear programming:
Linear programming is of the form.
optimize some function f(X) given the following constraints
h1(X), h2(X), etc.
If all the functions and constraints are linear, then there
are solvers that will solve it in polynomial time.
Otherwise, must use heuristics.
74 -- gradient method for finding zeros.
Take two points and find the slope and then estimate where
the zero is.
101 -- branch and bound. The idea is to give an estimate of
what the best solution could be in order to bound the answer.
So you don't go off and look at useless paths.
Because if you have a partial solution and then best possible
continuation is more expensive than a solution you already have,
then there is no reason to look at it.
(go to A* notes).
120-124 -- simulated annealing
Annealing is the process of slowly cooling a molten element
in order to make it form a crystal rather than a higher energy state
glob. At high temperatures, many non-greedy moves get taken.
As the temperature cools, fewer and fewer are taken.
Simulated annealing carries this idea to optimization problems:
Figure 5.3:
take an initial solution s1
initialize temperature T to a high value
loop until temperature is low enough or you have found some answer
take a random change to the solution s2
if s2 is better than s1 then take it
else if s2 is worse than s1 then take it with probability
e^((cost(s1)-cost(s2))/T)
// so the exponent is always negative
// the higher T, the closer the exponent is to 0 so prob is high
// The bigger the cost difference, the more negative the exponent
// and the probability approaches 0.
decrease the temperature
end loop
/ A generic simulated annealing function.
/ This requires an exchange function tryexchange
/ that returns a pair, first element is a delta which
/ will be accepted if positive but will be accepted if negative
/ only with a probability that depends on temperature.
/ The second component is how to change the state if the exchange
/ is accepted.
/ It also requires a changestate function that takes that second
/ argument.
/ Thus, this is totally generic.
simannealing:{[hightemp; stepswithintemp]
currenttemp: hightemp
while[currenttemp > 0
/ prob that you will take a bad move
do[stepswithintemp
pair: tryexchange[]
delta: pair[0]
if[~ delta < 0
x: changestate[pair[1]]
]
if[delta < 0
probbad: 2 ^ ((delta*hightemp%currenttemp))
if[((*1 _draw 0) < probbad) / then take the change
x: changestate[pair[1]]
]
]
]
currenttemp-: 1
]
}
There is a lot of tuning of the parameters.
Initial temperature. How long at each temperature?
Halting condition. Selection of neighbor.
p. 125: tabu searching:
memory forces the search to explore new areas of the search space.
Certain areas of the search space become taboo at least for the moment.
If we are varying a number of variables, e.g. in satisfiability.
At some point we vary variable xj and that worked well.
Then for some time we might say that xj can't be varied again.
Helps with neighbor searching.