\begin{slide}{violet}
\violet
\begin{center}
Optimization
\end{center}
{\it simulated annealing}: probabilistic algorithm for optimization;
non-deterministic walk on an energy surface that is ``cooling''

apply: 
{\it energy} of permutation $P$ is average seek distance,
$$
energy[P] =  \sum_{i=1}^N \sum_{j=1}^N |P(i) - P(j)| \hat{\pi_i} \hat{\rho_{ij}}
$$

we seek to minimize energy

\pagebreak[4]

{\small
\baselineskip=12pt
\begin{tabbing}
xxxxx\=yyyyy\=zzzzz\= \kill
\#define EQUILIBRIUM (accepts$\ge$2000 AND rejects$\ge$5000) \\
\#define FROZEN (temperature $<$ 0.5) \\
\quad\\
while(not(FROZEN))\{\\
\>accepts = rejects = 0;\\
\>old\_energy = energy();\\
\>while(not(EQUILIBRIUM))\{ \\
\>\>cylinder1 = choose\_random\_cylinder();\\
\>\>cylinder2 = choose\_random\_cylinder();\\
\>\>swap\_cylinders(cylinder1,cylinder2);\\
\>\>new\_energy = energy();\\
\>\>$\Delta E$ = new\_energy - old\_energy;\\
\>\>if(rand(0,1) $< e^{min\{0.0,-\Delta E/\mbox{temperature}\}}$)\{ \\
\>\>\>accepts++;\\
\>\>\>old\_energy = new\_energy;\\
\>\>\>\} \\
\>\>else \{\\  
\>\>\>/* put them back */\\
\>\>\>swap\_cylinders(cylinder1,cylinder2); \\
\>\>\>rejects++; \\
\>\>\>\}  \\
\>\>\}\\
\>temperature = temperature*0.8;\\
\>\}\\ 
\end{tabbing}
}

starting energy: 390.647935 

ending energy: 32.3543347 
\end{slide}
