Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] Research Annealing

Expand Messages
  • Lance
    Simulated Annealing is a heuristic technique for optimization problems. Think of an optimization problem as hills and valleys where you want to find the lowest
    Message 1 of 1 , Aug 18, 2005
    • 0 Attachment
      Simulated Annealing is a heuristic technique for optimization problems. Think of an optimization problem as hills and valleys where you want to find the lowest point. First the ball starts "hot" and bounces around randomly. As you start to cool the ball down, it doesn't bounce as much as gravity will cause it to go down more often than up. When it cools completely it falls into a local minima. Hopefully you've reduced the temperature at such a rate that the local minima the ball finds is close to the true minimum. Simulated annealing doesn't solve NP-complete problems quickly in general, but it some cases it does reasonably well in practice.

      I used an analogy of simulated annealing to describe to a student how one chooses a research area. First you bounce around for a while looking at many topics through talks, classes and reading some broad papers finding the right fit for your strengths and interests. Then you start to focus, reading more specific papers until you find the right place to start drilling for results.

      One you start drilling you will hopefully find some oil but eventually the well will just output sludge. At this point you should start bouncing around again, slowly at first, to find a new topic. The trick is to know when to start bouncing again. Leave too early and you might miss a new oil supply right under the old one. Leave too late and you will find yourself knee-deep in sludge, forgotten and unable to escape.

      --
      Posted by Lance to Computational Complexity at 8/18/2005 06:32:00 AM

    Your message has been successfully submitted and would be delivered to recipients shortly.