Database Reference
In-Depth Information
1.
What we did was kind of interesting. Let's take the
annealing
function apart to
see how it works. The process is handled by a
loop
inside the
annealing
function.
Its parameters are a snapshot of the state of the annealing process:
(loop [state initial
cost cost
k 1
best-seq [{:state state, :cost cost}]]
2.
We only continue if we need more iterations or if we haven't bested the maximum cost:
(if (and (< k max-iter)
(or (nil? max-cost)
(> cost max-cost)))
3.
If we continue, we calculate the next energy and get a potential state and cost to
evaluate:
(let [t (temp-fn (/ k max-iter))
next-state (neighbor-fn state)
next-cost (get-cost-cache next-state)
next-place {:state next-state, :cost next-cost}]
4.
If the probability function (in this case,
should-move
) indicates so, we move to the
next state and loop. Otherwise, we stay at the current state and loop:
(if (> (p-fn cost next-cost t) (rand))
(recur next-state next-cost (inc k)
(conj best-seq next-place))
(recur state cost (inc k) best-seq)))
5.
If we're done, we return the sequence of the best states and costs seen:
best-seq)))))
This provides a systematic way to explore the problem area. In this case, it was to ind a better
partition size for this problem.
There's more…
Simulated annealing is one of a class of algorithms known as metaheuristic. This is a class
of algorithms that are widely applicable to search a result space but that do not guarantee a
globally optimal solution. Instead, they often approach the problem stochastically, randomly
searching for the best solution that they can ind within a reasonable amount of time. All of
these take a function (the
cost-fn
function mentioned previously) and try to ind the largest
or smallest value for it.
Other optimization algorithms include genetic algorithms, ant colony optimization, particle
swarm optimization, and many others. This is a broad and interesting ield, and being familiar
with these algorithms can be helpful for anyone who does data analysis.
