The Traveling Salesman Problem (TSP)

Exercise : Consider the ratio of probabilities above:

• Question: what happens to r as T increases to infinity?
• Question: what happens to r as T decreases to zero?

Key ideas in simulated annealing: [Kirk1983].

• Simulated annealing = a modified local-search.

• Use it to solve a combinatorial optimization problem.

• Associate "energy" with "cost".
  → Goal: find lowest-energy state.

• Recall problem with local-search: gets stuck at local minimum.

• Simulated annealing will allow jumps to higher-cost states.

• If randomly-selected neighbor has lower-cost, jump to it (like local-search does).

• If randomly-selected neighbor is of higher-cost
  → flip a coin to decide whether to jump to higher-cost state
  • Suppose current state is s with cost C(s).
  • Suppose randomly-selected neighbor is s' with cost C(s') > C(s).
  • Then, jump to it with probability

    e ^{-[C(s') - C(s)] / kT}

• Decrease coin-flip probability as time goes on:
  → by decreasing temperature T.

• Probability of jumping to higher-cost state depends on cost-difference:

  

Implementation:

• Pseudocode: (for TSP)

  
  Algorithm: TSPSimulatedAnnealing (points)
  Input: array of points
  
       // Start with any tour, e.g., in input order 
  1.   s = initial tour 0,1,...,n-1
  
       // Record initial tour as best so far. 
  2.   min = cost (s)
  3.   minTour = s
  
       // Pick an initial temperature to allow "mobility" 
  4.   T = selectInitialTemperature()
  
       // Iterate "long enough" 
  5.   for i=1 to large-enough-number
             // Randomly select a neighboring state. 
  6.         s' = randomNextState (s)
             // If it's better, then jump to it. 
  7.         if cost(s') < cost(s)
  8.             s = s'
                 // Record best so far: 
  9.             if cost(s') < min
  10.                min = cost(s')
  11.                minTour = s'
  12.            endif
  13.        else if expCoinFlip (s, s')
                 // Jump to s' even if it's worse. 
  14.            s = s'
  15.        endif       // Else stay in current state. 
             // Decrease temperature. 
  16.        T = newTemperature (T)
  17.  endfor
  
  18.  return minTour
  
  Output: best tour found by algorithm
    

  
  Algorithm: randomNextState (s)
  Input: a tour s, an array of integers
  
      // ... Swap a random pair of points ... 
  
  Output: a tour 
    

  
  Algorithm: expCoinFlip (s, s')
  Input: two states s and s'
  
  1.   p = exp ( -(cost(s') - cost(s)) / T)
  2.   u = uniformRandom (0, 1)
  3.   if u < p
  4.       return true
  5.   else
  6.       return false
  
  Output: true (if coinFlip resulted in heads) or false
    

• Implementation for other problems, e.g., BPP
  • The only thing that needs to change: define a nextState method for each new problem.
  • Also, some experimentation will be need for the temperature schedule.

Temperature issues:

• Initial temperature:
  • Need to pick an initial temperature that will accept large cost increases (initially).
  • One way:
    • Guess what the large cost increase might be.
    • Pick initial T to make the probability 0.95 (close to 1).

• Decreasing the temperature:
  • We need a temperature schedule.
  • Several standard approaches:
    • Multiplicative decrease: Use T = a * T, where a is a constant like 0.99.
      → T_n = aⁿ.
    • Additive decrease: Use T = T - a, where a is a constant like 0.0001.
    • Inverse-log decrease: Use T = a / log(n).
  • In practice: need to experiment with different temperature schedules for a particular problem.

Analysis:

• How long do we run simulated annealing?
  • Typically, if the temperature is becomes very, very small there's no point in further execution
    → because probability of escaping a local minimum is miniscule.

• Unlike previous algorithms, there is no fixed running time.

• What can we say theoretically?
  • If the inverse-log schedule is used
    → Can prove "probabilistic convergence to global minimum"
    → Loosely, as the number of iterations increase, the probability of finding the global minimum tends to 1.

In practice:

• Advantages of simulated annealing:
  • Simple to implement.
  • Does not need much insight into problem structure.
  • Can produce reasonable solutions.
  • If greedy does well, so will annealing.

• Disadvantages:
  • Poor temperature schedule can prevent sufficient exploration of state space.
  • Can require some experimentation before getting it to work well.

• Precautions:
  • Always re-run with several (wildly) different starting solutions.
  • Always experiment with different temperature schedules.
  • Always pick an initial temperature to ensure high probability of accepting a high-cost jump.
  • If possible, try different neighborhood functions.

• Warning:
  • Just because it has an appealing origin, simulated annealing is not guaranteed to work
    → when it works, it's because it explores more of the state space than a greedy-local-search.
  • Simply running greedy-local-search on multiple starting points may be just as effective, and should be experimented with.

Variations:

• Use greedyNextState instead of the nextState function above.
  • Advantage: guaranteed to find local minima.
  • Disadvantage: may be difficult or impossible to climb out of a particular local minimum:
    • Suppose we are stuck at state s, a local minimum.
    • We probabilistically jump to s', a higher-cost state.
    • When in s', we will very likely jump back to s (unless a better state lies on the "other side").
  • Selecting a random next-state is more amenable to exploration.
    → but it may not find local minima easily.

• Hybrid nextState functions:
  • Instead of considering the entire neighborhood of 2-swaps, examine some fraction of the neighborhood.
  • Switch between different neighborhood functions during iteration.

• Maintain "tabu" lists:
  • To avoid jumping to states already seen before, maintain a list of "already-visited" states and exclude these from each neighborhood.

• Thermal cycling:
  • Periodically raise temperature and perform "re-starts".
  • The idea is to force more exploration of the state space.

The Held-Karp lower bound