Differential evolution vs. Simulated annealing

The differential evolution (DE) algorithm is somewhat popular in quantitative finance, for example to calibrate stochastic volatility models such as Heston. There are a few parameters to setup properly but in general, it is not too difficult to find those, and the algorithm works well on many different problems.

An older technique, much more popular in physics is simulated annealing (SA). There are few papers on its use for stochastic volatility calibration, most don’t find the technique competitive (the ASA algorithm appear very slow in this paper from Ricardo Crisostomo, more standard SA is worse than a random search according to ManWo Ng) or even usable (see Jorg Kienitz book).

There are many different algorithm for SA and it’s not really easy to find out which one would be appropriate. I stumbled upon the Fortran code from Alan Miller for the algorithm of Corana et al.. I liked that it looked relatively simple (less than 200 lines of code) and yet it still includes practicle improvements over the most basic algorithm. I did not like the ASA algorithm as much, even if tends to be more frequently quoted on forums and finance papers, as the C code is quite large and it looks too much like a black box whose magic is difficult to grasp.

My first trial with SA was not very successful. There are many parameters (a few more than for differential evolution), and I just picked the official recommendation, that is $$T_0=1.0, R_T = 0.85, N_S = 20, N_T = 100, N_{\epsilon}=4$$ with a tolerance \(\epsilon=10^{-4}\) and a maximum of 2000 function evaluations.

I obtained an RMSE of 2.41E-2 along with a completely unrealistic \( \kappa \) value: \( v_0 = 0.0014926198, \kappa = 11.6967708372, \theta=0.0243195875, \sigma=2.0133153096, \rho=-0.6130317709\).

It turns out that the recommendation is valid on specific problems: most papers work with fast to evaluate objective functions (typically some analytical function), and are ok with more than 100 000 function evaluations.

I tried to change the temperature, as it was supposedly key. On some calibration problems the resulting RMSE became lower, on this one, it did not. With \(T_0=0.001\), I obtained an RMSE of 4.94E-2 for the parameters \( v_0 = 0.0514607073, \kappa = 15.9510297320, \theta=0.0162640037, \sigma=1.7068530314, \rho=-0.9950165035\).

Using a small temperature makes the algorithm effectively work as a local minimizer as the Metropolis step is then always bypassed.

The typical settings for SA are not really appropriate for Heston, as computing the RMSE of a full options surface is costly. I aim for around 1000 function evaluations, which takes around 2s. With this in mind and the need for the temperature to decrease, it appears that one should use a small \(R_T=0.2\), a smaller number of cycles \(N_S = 5\), and a smaller number of iterations before temperature reduction \(N_T=5\). With those settings, the RMSE becomes 1.22E-2 and the parameters are much more moderate \( v_0 =0.0123858333, \kappa = 2.9627864991, \theta=0.0237545288, \sigma= 0.5081900883, \rho=-0.6414988464\).

It is then competitive to differential evolution with a population NP = 10, a frequency F = 0.9 and a crossover rate CR = 0.5.

At the end of the day, simulated annealing can work well for Heston calibration. On some better behaved calibration problems, it is often faster and more accurate than DE (although I am sure one could tune the DE or SA parameters a bit better). The settings have a drastic impact, and tuning the settings is only possible with an understanding the algorithm (i.e. by using a simple algorithm).

In reality, the Heston calibration is most of the time well behaved if one is careful with the accuracy of the numerical option prices. For this example, I used on purpose a somewhat bad basic Simpson quadrature with 100 points, which is going to add noise for out-of-the-money options.