Get Set...

Next, we need to define our four simulated annealing functions... In the left corner, picnicEnergy tells us the overall happiness of our picnic population... smaller, low energy values mean greater happiness. In the right corner, picnicMotion swaps two neighbors randomly to cause motion. In the front corner, (This is a tag-team match) picnicTemperature gives the current temperature: We want to start hot, then cool things down so that our picnic crystalizes in a controlled manner. And finally, in the back, picnicTransitionProbability takes the current temperature and the energy of two states and calculates the likelihood a transition into the new state will occur. For more info, consult you know what...





  
  let picnicEnergy :: [Link] -> EnergyFunction Placement 
      picnicEnergy l a = sum $ map linkEnergy l
          where linkEnergy :: Link -> Int 
                linkEnergy [p1,p2] = mismatches (findPerson a p1) (findPerson a p2)

  let picnicMotion :: [Link] -> MotionFunction Placement 
      picnicMotion l r a = let (n,r2) = randomR (0,(length l)-1) r 
                               [p1,p2] = l!!n                      
                           in (r2,(p1,findPerson a p2):(p2,findPerson a p1):(filter (not.((flip elem) [p1,p2]).fst) a))

  let picnicTemperature :: TemperatureFunction 
      picnicTemperature m c = 50.0 * (exp (0.0 - (5.0 * ((fromIntegral c) / (fromIntegral m)))))

  let picnicTransitionalProbability :: TransitionProbabilityFunction 
      picnicTransitionalProbability e1 e2 t = exp ((fromIntegral (e1 - e2)) / t)

  let annealing_time = 500

  putStr "starting energy: "
  print $ picnicEnergy sitting starting_placement

  putStr "starting temperature: "
  print $ picnicTemperature annealing_time annealing_time


When we run the program with this new addition, We'll now get some info on the picnic starting positions:


> runHaskell tutorial.hs

Hello World! Let's have a picnic!
Number of people coming:
200
starting energy: 16010
starting temperature: 0.33689734


What's Good About This Code?

When it came to the four simulated annealing functions, it was very easy to take the text from the wikipedia, generically translate the types of these functions into generic haskell types, and then create instances of these functions concretely defined for our picnic-organizing needs. This really shows the power of Haskell's highly refined support for declaring and manipulating types.



What's Bad About this Code?

Well, these four functions are going to be the bread and butter of our this program- Probably, about 99% of CPU time will be spent in this little bit of code... Consequently, every little inefficiency in this code will hurt performance hundredfold... And boy, is this code inefficient: Because we're storing everything in lists, it means that any function doing a search, such as findPerson, will be inefficient to the point of absurdity... Even worse is the fact that picnicEnergy checks the happiness of the entire picnicker population, even though only two people move at any one time and does so in the most tedious way by checking every questionaire question on every person against neighbors over and over and over again, instead of precalculating the compatibility of two people ahead of time.

These things can be fixed relatively easily by ugli-fying the code with extra parameters holding precalculated/memoized info and using GHC Maps, HashMaps, and Arrays instead of POLs (plain old lists, to possible coin a new term- 'pwned', watch your back... a new kid's in town!) in the appropriate places. In fact, the "real" version of this annealer I'm using for my picnicmob calculations does all this, but ain't exactly prime tutorial material. However, it runs well over a thousand times faster than this simplified version :-)

NEXT