Database Reference
In-Depth Information
Finding the optimal partition size with
simulated annealing
In the previous recipe,
Partitioning Monte Carlo simulations for better pmap performance
,
we more or less guessed what will make a good partition size. We tried a few different values
and saw what gives us the best results. However, it's still largely guesswork since just making
the partitions larger or smaller doesn't give consistently better or worse results.
This is the type of task that computers are good at. Namely, searching a complex space to
ind the function parameters that result in an optimal output value. For this recipe, we'll use a
fairly simple optimization algorithm called simulated annealing. Similar to many optimization
algorithms, this is based on a natural process: the way molecules settle into low-energy
conigurations as the temperature drops to freezing. This is what allows water to form
eficient crystal lattices as it freezes.
In simulated annealing, we feed a state to a cost function. At each point, we evaluate
a random neighboring state and possibly move to it. As the energy in the system (the
temperature) goes down, we are less likely to jump to a new state, especially if that state
is worse than the current one according to the cost function. Finally, after either reaching
a target output or iterating through a set number of steps, we take the best match found.
Similar to many optimization algorithms, this doesn't guarantee that the result will be the
absolute best match, but it should be a good one.
For this recipe, we'll use the Monte Carlo pi approximation function that we did in the
Partitioning Monte Carlo simulations for better pmap performance
recipe, and we'll use
simulated annealing to ind a better partition size.
Getting ready
We need to use the same dependencies, uses, imports, and functions as we did in the
Partitioning Monte Carlo simulations for better pmap performance
recipe. In addition,
we'll also need the
mc-pi-part
function from that recipe.
How to do it…
1. For this recipe, we'll irst deine a generic simulated annealing system. Then, we'll
deine some functions to pass them as parameters. Everything will be driven by the
simulated
annealing
function that takes all of the function parameters for the
process as arguments (we'll discuss them in more detail in a minute):
(defn annealing
[initial max-iter max-cost
neighbor-fn cost-fn p-fn temp-fn]
(let [get-cost (memoize cost-fn)
