Module 10: Combinatorial Optimization Problems, State Spaces and Local Search

Background:

• What is annealing?
  • Annealing is a metallurgic process for improving the strength of metals.
  • Key idea: cool metal slowly during the forging process.

• Example: making bar magnets:
  • Wrong way to make a magnet:
    1. Heat metal bar to high temperature in magnetic field.

       

    2. Cool rapidly (quench):

       

  • Right way: cool slowly (anneal)

• Why slow-cooling works:
  • At high heat, magnetic dipoles are agitated and move around:

    

  • The magnetic field tries to force alignment:

    

  • If cooled rapidly, alignments tend to be less than optimal (local alignments):

    

  • With slow-cooling, alignments are closer to optimal (global alignment):

    

• Summary: slow-cooling helps because it gives molecules more time to "settle" into a globally optimal configuration.

• Relation between "energy" and "optimality"
  • The more aligned, the lower the system "energy".
  • If the dipoles are not aligned, some dipoles' fields will conflict with others.
  • If we (loosely) associate this "wasted" conflicting-fields with energy
    ⇒ better alignment is equivalent to lower energy.
  • Global minimum = lowest-energy state.

• The Boltzmann Distribution:
  • Consider a gas-molecule system (chamber with gas molecules):

    

  • The state of the system is the particular snapshot (positions of molecules) at any time.
  • There are high-energy states:

    

    and low-energy states:

    

  • Suppose the states \(s_1,s_2,\ldots\) have energies \(E(s_1), E(s_2),\ldots\)
  • A particular energy value \(E\) occurs with probability $$\eqb{ P[E] & \eql & \mbox{Prob}[\mbox{observe energy E}] \\ & \eql & Z e^{-\frac{E}{kT}} }$$ where \(Z\) and \(k\) are constants.
  • Think of this as $$ P[E] \;\; \propto \;\; e^{-\frac{E}{T}} $$

• Low-energy states are more probable at low temperatures:
  • Consider states \(s_1\) and \(s_2\) with energies \(E(s_1)\) and \(E(s_2)\)
  • Suppose that \(E(s_1) \lt E(s_2)\)
  • The ratio of probabilities for these two states is: $$\eqb{ r & \eql & \frac{P[E(s_2)]}{P[E(s_1)]} \\ & \eql & e^{\frac{-[E(s_2) - E(s_1)]}{kT}} \\ & \eql & \exp ({\frac{-[E(s_2) - E(s_1)]}{kT}}) }$$

In-Class Exercise 10.15: Fill in the steps between the first and second lines above. Then, suppose that \(E(s_1) \lt E(s_2)\) and 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:

• 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') \gt C(s)\).
  • Then, jump to it with probability $$ \exp (\frac{-[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.

In-Class Exercise 10.16: Download this template and implement simulated annealing using the neighborhood function of Exercise 10.13. The main-loop as well as the temperature schedule is already in the template.