Efficient and robust calibration of the Heston option pricing
model for American options using an improved Cuckoo
Search Algorithm
Stefan Haring

Ronald Hochreiter

arXiv:1507.08937v1 [cs.NE] 31 Jul 2015

August 3, 2015
Abstract
In this paper an improved Cuckoo Search Algorithm is developed to allow for an efficient
and robust calibration of the Heston option pricing model for American options. Calibration
of stochastic volatility models like the Heston is significantly harder than classical option
pricing models as more parameters have to be estimated. The difficult task of calibrating one
of these models to American Put options data is the main objective of this paper. Numerical
results are shown to substantiate the suitability of the chosen method to tackle this problem.
Keywords. Option pricing, Heston model, Cuckoo search, Finance

1

Introduction

The classical textbook example for pricing options is the famous Black-Scholes model, see [1].
Since its creation in 1973, it has caused a dramatic increase in options trading because of its
relatively simple usability. It provides closed-form solutions for European Call and Put options
as well as American Call options. For American Put options, no closed-form solution exists
because an optimal stopping time problem has to be solved.
Over the years, criticism of the Black-Scholes model has arisen since it does not accurately
capture the behaviour of option prices in the market. For example, the well-known volatility
smile, which shows that deep in the money and out the money options have higher prices (and
therefore higher implied volatility), is not taken into account in the Black-Scholes model since
one of its main assumptions is constant volatility.
To accurately reflect market behaviour, option pricing models in which volatility changes over
time, so-called stochastic volatility models, have been created. In these models, the volatility
is itself following a process that changes with time t. Some examples for these models are the
Heston model [2], the CEV model [3] [4] and the Chen model [5].
Calibration of these stochastic volatility models is significantly harder than for the BlackScholes model, since more parameters have to be estimated. The difficult task of calibrating one
of these models to American Put options data is the main objective of this paper. We will focus
on the Heston model as it is widely known and cited. In his seminal paper, Heston specified his
stochastic volatility model for option prices as following:
p
dS(t)
= µdt + V (t)dW1
S(t)

1

(1)

dV (t) = κ(θ − V (t))dt + σ

p

V (t)dW2 ,

(2)

where W1 and W2 are Wiener processes that are correlated by dW1 ∗ dW2 = ρdt. The
parameters used for obtaining the variance process are the long run variance θ, the mean reversion
rate κ (the rate at which the volatility reverts to the long run variance) and the volatility of
variance, σ.
Pricing options under the Heston model is not straight-forward when it comes to American
option prices. The price of an American Call option is the same as for a European Call (because
an early exercise is never optimal), however for American Put options no closed-form solution
exists and therefore one has to use numerical approximations. There are many different methods
in the literature for the approximations of these options such as the GARCH lattice approach
as proposed by Ritchken and Trevor [6], tree-models presented by Beliaeva and Nawalkha [7] or
Monte Carlo Simulation developed by Longstaff and Schwarz [8].
What is more important than choosing one of the many possible ways of how to price American options under the Heston model is an efficient and robust way to calibrate the model to
actual data. After all, using the model in practice for means of forecasting and pricing is the
main objective. The goal of this paper is to fill the gap existing in research carried out on the
Heston model. At the time of writing, no rigorously tested method of calibrating the model for
American Call options has been published.
The main reason is that while pricing options under this model is already a difficult task
in itself, calibrating the model to a set of given option prices is even more challenging. In
the standard model (keeping the interest rate fixed), there are five parameters that have to be
calibrated: the aforementioned κ, θ and σ as well as the starting value for the variance process
V0 and the correlation between the stock price and the variance, ρ.
What has been done, however, is calibrating the Heston model for European and Asian options. Gilli and Schumann show the effectiveness in using Heuristics and Evolutionary Algorithms
when calibrating the Heston Model for European options [9], [10]. Collier gives an overview of
algorithms that can be used for optimising a noisy objective function, in this case an Monte
Carlo simulation, to calibrate the Heston model to Asian options data [11].
In this paper a naturally-inspired algorithm, namely Cuckoo Search, will be used to tackle
the calibration problem. Naturally-inspired algorithms (also known as Evolutionary Algorithms)
have been used on a lot of difficult optimization problems in Finance and have shown great
promise (see for example [12], [13], [14], [15]). See also relevant examples published in this
journal including [16], [17], [18], [19], and [20].
The paper is structured as follows. Section 2 gives a detailed overview over the problem and
section 3 will provide a brief introduction to the Cuckoo Search Algorithm. In section 4, the
chosen implementation for the algorithm will be explained while in Section 5 numerical results
will be presented. Section 6 concludes this paper.

2

Calibrating pricing models

When calibrating a pricing model, the task is to find the parameters that minimize the difference between the model price and the actual observed price. This is reflected in the following
optimization problem:
min

N
X

(Pimodel − Piobs )2 ,

i=1

2

(3)

vol.
o

f.vo
l

objective.fun

mean.reversion

Figure 1: Search space when varying volatility of volatility and rate of mean reversion

vol.
o

f.vo

l

objective.fun

volatility

Figure 2: Search space when varying volatility and volatility of volatility
where N is the total number of observed prices. The optimization problem can also be
specified differently ([15]), however the approach given in Equation (3) is used as the objective
function throughout this paper.
The search space for the optimization problem is bounded continuous and not convex, which
means standard optimization methods (e.g. gradient methods based on derivates) are not applicable. It is also characterized by a very high amount of local minima which complicates the task
at hand even more. Figures 1 and 2 show the results of the objective function given in Equation
(3) when varying certain parameters.
As can be seen from the figures, the optimization method must find the perfect balance
between exploration (traverse the whole search space relatively quickly) and exploitation (search
the near-neighbour regions of the best found solutions so far) to avoid getting trapped in the
many local minima.
In order for the algorithm to be a viable option, it has to fulfill the exploration-exploitation
criteria as well as be numerically stable, meaning the error from the obtained solution and the

3

begin
Objective function f(x), x = (x1 , . . . , xd )T
Initialize population of n host nests xi (i = 1, 2, . . . , n)
while stopping criterion is not met
Get a cuckoo randomly by Lévy flights
Evaluate its fitness Fi
Choose a nest j among n randomly
if (Fi > Fj )
replace j by the new solution
end
A fraction (pa ) of worse nests are abandoned and replaced by new ones
Rank solutions and find the current best
end while
Postprocess results and visualization
end
Table 1: Cuckoo Search pseudo-code
actual one has to be minimal. Another important criterion is computational efficiency. The
algorithm has to converge to the solution as quickly and as stable as possible.
The complexity of this task for the Heston pricing model for American options has so far
prevented an effective and reliable method to arise. To this date, no algorithm has been proposed
to solve this specific problem. In order to fulfill all of the above-mentioned criteria, a heuristic
method called Cuckoo search will be used to calibrate the Heston option pricing model to a set
of sample data.

3

Cuckoo Search

The Cuckoo search algorithm is a naturally-inspired optimization algorithm developed by Yang
and Deb [21]. It is a so-called meta-heuristic algorithm meaning that it makes only few assumptions about the problem at hand and can be used effectively when there is only incomplete
information and limited computational capacity given. This makes it an ideal candidate for the
optimization problem outlined in section 2.
The heuristic used in this paper draws its inspiration from the behaviour of cuckoos that lay
their eggs in nests of other birds that they come across during their flights. This so-called brood
parasitism is translated into a very efficient optimization method. The cuckoo search algorithm
follows three simple rules:
1. Every cuckoo lays one egg in a random nest.
2. The best eggs are carried over to the next generation.
3. Cuckoo eggs are discovered by the host bird with a probability pa ∈ [0, 1].
Here, the nests represent the amount of different solutions at each iteration of the optimization
process. The eggs represent the solutions to the objective function and are obtained from the
flight paths of the cuckoos. At each iteration there is a probability that a new solution gets
discarded and replaced by a random result. The pseudo-code for the standard Cuckoo Search
algorithm is given in Table 1.

4

2.5
2.0
1.5
1.0
0.5
0.0
−0.5
−1.0

0.4

0.6

0.8

1.0

1.2

Figure 3: Lévy flight in 2 dimensions with 1000 steps
To model the flight paths that lead to new solutions, Lévy flights are used (for an introduction
to Lévy flights see [22]) There is a plethora of research available on how the flight behaviour of
insects, animals and even humans show the same characteristics as Lévy Flights (see for example
[23], [24]).
A Lévy flight is essentially a random walk where the step lengths are drawn from a Lévy
distribution, which is heavy-tailed. When the Lévy flight is defined in a dimension greater than
1, the steps are isotropic and random,meaning they are uniform in all orientations.
The distinct feature of a Lévy flight is made visible in Figure 3. Lévy flights are characterized
by large jumps followed by a series of small steps around the end of the jumps. This is exactly
the behaviour needed for our optimization algorithm since it presents the perfect mix between
exploration (the long jumps) and exploitation (the series of small steps). The long jumps also
guarantee that the algorithm won’t get trapped in the many local minima present in the search
space.
A detailed explanation of the implementation of the Cuckoo search algorithm used in this
paper is presented in the next section.

4

Implementation

The implementation of the Heston pricing model itself will not be discussed here since any
method that fulfills the criteria of robustness and numerical stability as well as fast computation
time is suitable. For this to achieve, the pricer should be implemented in C++, Julia, Python
or any similarly fast language.
The Cuckoo Search algorithm used in this paper has been implemented as an R [25] package
by the authors. Runtime tests using the package on standard optimization problems (Schwefel’s
Function, Rastrigins Function, Easoms Function) were solved in sufficient time for the Finance
application.
In its essence, the implemented algorithm follows the steps laid out in the pseudo-code given
in Table 1. It is modified in some parts to increase its effectiveness and convergence.
The implemented method requires a small number of parameters because of its heuristic
nature. The necessary input includes the number of nests (starting points and different solutions
at every iteration), the number of iterations (or the error tolerance in the objective function),

5

√

v0
σ
κ
θ
ρ

0.2
0.1
3
0.04
-0.1

0.5
0.1
3
0.25
-0.5

0.3
0.25
2
0.09
-0.1

0.4
0.25
1
0.16
-0.2

Table 2: Parameter sets for the Heston pricing model

upper and lower bounds for the parameters of the Heston pricing model as well as values pmax ,
pmin and pbase that are needed for the calculation of pα .
The part where the chosen implementation differs from the original algorithm is in the way pa ,
the probability that the host bird discovers the cuckoos egg, is set. In the original paper, this is
a fixed value. However Valian, Tavakoli, Mohanna and Haghi [26] show some modifications that
improve accuracy and convergence of the cuckoo search algorithm. One of these modifications
is that pa is not fixed but a decreasing function between two set values, pmax and pmin . The
function looks as follows:
(pmax − pmin )
× iter,
(4)
N
where N is the total number of iterations and iter is the current iteration. This guarantees
that the algorithm finds many new solutions in the beginning (the exploration is enhanced) and
gradually moves on to find new solutions in the neighbourhood of points with an already good
fitness (the exploitation is enhanced). Here we set the value for pmax to 0.95 to have a lot of
new solutions in the beginning of the optimization to further increase the exploration. The value
for pmin is set to 0.05 so that at the end of the optimization the algorithm searches almost
exclusively around the best found positions.
The fitness function used to evaluate each solution in the search space calculates simply the
sum of squared errors between the prices calculated by the Heston model and the observed (real)
prices. It takes as inputs the parameters given by an egg in the Cuckoo Search algorithm and
calculates the prices for all the asset value/strike price combinations.
pa (iter) = pmax −

5

Numerical Results

To test and calibrate the model, an artificial dataset has been used to validate the solutions. The
parameters used in creating the dataset have been chosen to be similar to the dataset in Natural
Computing Vol 4, Chapter 2 [15]. The model has been tested varying the spot price S0 as well
as the strike price, K. In both occasions, the fixed price is set to 100 and the other price varies
between 80 and 120 in steps of 2.
The risk-free interest rate has been set to 5%, however it is very easy to adapt the model to
1 1 1
allow for a varying interest rate as well. The maturities τ for the options are 12
, 4 , 2 and 1 year.
This results in a total amount of 84 prices that are used to calibrate the model.
The parameter sets of the Heston pricing models are given in Table 5.
Lower and upper bounds for all 5 parameters based on logic and empirical findings have been
introduced to restrict the search space only to plausible solutions. The boundaries are as shown
in Table 3.
For the correlation parameter, ρ, that captures the correlation between volatility and the
stock price, the range has been set to be mostly negative according to several papers focused on

6

√

Lower Bound
Upper Bound

v0
0.01
0.1

σ
0.05
0.3

κ
0.5
4

θ
0.01
0.1

ρ
-0.8
0.1

5e−02

Table 3: Lower and upper bounds for the parameters.

5e−03
2e−03
1e−04

5e−04

objective function

2e−02

20 nests
30 nests
40 nests
50 nests

0

100

200

300

400

iterations

Figure 4: Convergence comparison for different nest sizes.
this topic, e.g. Nandi [27].
For the choice of the number of nests used, multiple values have been tested. The algorithm
has proved itself being very stable to changes in the number of nests, meaning values between
20 and 50 have all shown fast convergence and high accuracy.
From Figure 4 it is visible that for all choices of nests, convergence of the objective function
is given and is relatively fast. This means there is no need to fit this parameter for the model
and its selection can be made entirely to increase computational efficiency. The selection made
for this paper is a nest count of 20.
Furthermore tests on how many prices the algorithm needs as input for calibration have been
conducted. Figure 5 shows the convergence on a log-scale for inputs of 5,13 and 21 prices. It is
clearly visible that the algorithm needs fewer iterations if the number of prices increases. There
is, however, an increase in computation time for more prices.
The graphs shown in Figure 6 show the convergence of the objective function as well as of all
5 parameters calibrated by the Cuckoo Search algorithm. It can be seen, that there is a fast and
stable convergence not only of the objective function but also of the parameters. The values of
the objective function and the parameters after conducting the optimization process for each of
the parameter sets are given in Table 4.

6

Conclusion

In this paper an improved Cuckoo Search Algorithm has been developed to allow for an efficient
and robust calibration of the Heston option pricing model for American options. Calibration of
stochastic volatility models like the Heston is significantly harder than classical option pricing
models as more parameters have to be estimated. The difficult task of calibrating one of these
models to American Put options data has been solved using an implementation with the statisti7

1e−05
1e−07
1e−09

objective function

1e−03

5 prices
13 prices
21 prices

0

100

200

300

400

500

iterations

0.044
V0

0.036

0.040

0.004
0.002
0.000

objective fun

Figure 5: Convergence comparison for different number of prices

0

200

400

600

800

1000

0

200

400

600

800

1000

600

800

1000

600

800

1000

iterations

3.5

kappa

2.5
1.5

0.14
0.10

sigma

0.18

4.5

iterations

0

200

400

600

800

1000

0

200

400
iterations

−0.3
rho

−0.7
0

200

400

600

800

1000

0

iterations

CS
True
CS
True
CS
True
CS
True

−0.5

0.06
0.02

theta

0.10

−0.1

iterations

200

400
iterations

Figure 6: Convergence of objective function and parameters.
√
Objective function
v0
σ
κ
θ
ρ
0.000001
0.2
0.1
2.999
0.04
-0.09998
0.2
0.1
3
0.04
-0.1
0.000001
0.49999 0.09999
3.0012
0.25
-0.5
0.5
0.1
3
0.025
-0.5
0.000001
0.3
0.250098
2
0.089978
-0.1
0.3
0.25
2
0.09
-0.1
0.000001
0.39998
0.25
0.99875
0.16
-0.200125
0.4
0.25
1
0.16
-0.2
Table 4: Objective function and parameter values after optimization.

8

cal programming langauge R. The numerical results are very promising such that future research
will focus on applying the algorithm to real-world Options data.

References
[1] F. Black, M. Scholes, The pricing of options and corporate liabilities, The Journal of
Political Economy 81 (1973) 637–654.
[2] S. Heston, A closed-form solution for options with stochastic volatility with applications to
bond and currency options, Review of Financial Studies 6 (1993) 327–343.
[3] J. Cox, Notes on option pricing I: constant elasticity of diffusions, 1975. Unpublished draft.
[4] D. Emanuel, J. MacBeth, Further results on the constant elasticity of variance call option
pricing model, Journal of Financial and Quantitative Analysis 17 (1982) 533–554.
[5] L. Chen, Stochastic mean and stochastic volatility - a three-factor model of the term
structure of interest rates and its application to the pricing of interest rate derivatives,
Financial Markets, Institutions & Instruments 5 (1996) 1–88.
[6] P. Ritchken, R. Trevor, Pricing options under generalized GARCH and stochastic volatility
processes, The Journal of Finance 54 (1999) 377–402.
[7] N. Beliaeva, K. Nawalkha, A simple approach to pricing American options under the Heston
stochastic volatility model, The Journal of Derivatives 17 (2010) 25–43.
[8] F. Longstaff, E. Schwartz, Valuing American options by simulation: a simple least-squares
approach, Review of Financial Studies 14 (2001) 113–147.
[9] M. Gilli, E. Schumann, Calibrating the Heston model with differential evolution, in: Applications of Evolutionary Computation, volume 6025 of Lecture Notes in Computer Science,
Springer, 2010, pp. 242–250.
[10] M. Gilli, E. Schumann, Calibrating option pricing models with heuristics, in: Natural
Computing in Computational Finance, volume 4, Springer, 2011, pp. 9–37.
[11] A.
Collier,
Optimising
a
noisy
objective
function,
Http://www.exegetic.biz/blog/2013/07/optimising-a-noisy-objective-function/.

2013.

[12] A. Brabazon, M. O’Neill (Eds.), Natural Computing in Computational Finance, volume 1,
Springer, 2008.
[13] A. Brabazon, M. O’Neill (Eds.), Natural Computing in Computational Finance, volume 2,
Springer, 2009.
[14] A. Brabazon, M. O’Neill, D. Maringer (Eds.), Natural Computing in Computational Finance, volume 3, Springer, 2010.
[15] A. Brabazon, M. O’Neill, D. Maringer (Eds.), Natural Computing in Computational Finance, volume 4, Springer, 2011.
[16] R. Dash, P. Dash, R. Bisoi, A self adaptive differential harmony search based optimized
extreme learning machine for financial time series prediction, Swarm and Evolutionary
Computation 19 (2014) 25–42.
9

[17] C.-Y. Dye, A finite horizon deteriorating inventory model with two-phase pricing and timevarying demand and cost under trade credit financing using particle swarm optimization,
Swarm and Evolutionary Computation 5 (2012) 37–53.
[18] S. Mishra, G. Panda, R. Majhi, A comparative performance assessment of a set of multiobjective algorithms for constrained portfolio assets selection, Swarm and Evolutionary
Computation 16 (2014) 38–51.
[19] H.-G. Beyer, S. Finck, T. Breuer, Evolution on trees: On the design of an evolution strategy
for scenario-based multi-period portfolio optimization under transaction costs, Swarm and
Evolutionary Computation 17 (2014) 74–87.
[20] G. Pai, T. Michel, Metaheuristic multi-objective optimization of constrained futures portfolios for effective risk management, Swarm and Evolutionary Computation 19 (2014) 1–14.
[21] X.-S. Yang, S. Deb, Cuckoo search via Lévy flights, in: World Congress on Nature &
Biologically Inspired Computing (NaBIC 2009), IEEE, 2009, pp. 210–214.
[22] A. Chechkin, R. Metzler, J. Klafter, V. Gonchar, Introduction to the theory of Lévy flights,
Anomalous Transport: Foundations and Applications (2008) 129–162.
[23] C. Brown, L. Liebovitch, R. Glendon, Lévy flights in dobe juhoansi foraging patterns,
Human Ecology 35 (2007) 129–138.
[24] A. Reynolds, M. Frye, Free-flight odor tracking in drosophila is consistent with an optimal
intermittent scale-free search, PloS one 2 (2007) e354–e354.
[25] R Core Team, R: A Language and Environment for Statistical Computing, R Foundation
for Statistical Computing, Vienna, Austria, 2014. URL: http://www.R-project.org.
[26] E. Valian, S. Tavakoli, S. Mohanna, A. Haghi, Improved cuckoo search for reliability optimization problems, Computers & Industrial Engineering 64 (2013) 459–468.
[27] S. Nandi, How important is the correlation between returns and volatility in a stochastic
volatility model? empirical evidence from pricing and hedging in the S&P 500 index options
market, Journal of Banking & Finance 22 (1998) 589–610.

10

