# An Iterated Local Search Algorithm for Estimating the Parameters of the Gamma/Gompertz Distribution

Authors: Behrouz Afshar-Nadjafi
Journal: Modelling and Simulation in Engineering
 (2014)

---

## Abstract

Extensive research has been devoted to the estimation of the parameters of frequently used distributions. However, little attention has been paid to estimation of parameters of Gamma/Gompertz distribution, which is often encountered in customer lifetime and mortality risks distribution literature. This distribution has three parameters. In this paper, we proposed an algorithm for estimating the parameters of Gamma/Gompertz distribution based on maximum likelihood estimation method. Iterated local search (ILS) is proposed to maximize likelihood function. Finally, the proposed approach is computationally tested using some numerical examples and results are analyzed.


---

## Body

## 1. Introduction

In probability and statistics, the Gompertz distribution is a continuous probability distribution. The Gompertz distribution was first introduced by Gompertz [1] to describe human mortality and establish actuarial tables. Since then, many investigators have used the Gompertz distribution or some related forms of it in a variety of studies. There are many forms of the Gompertz distribution in the literature. The Gompertz distribution is often applied to describe the distribution of adult lifespans by demographers [2, 3] and actuaries [4, 5]. Related fields of science such as biology [6] and gerontology [7] also considered the Gompertz distribution for the analysis of survival. More recently, computer scientists have also started to model the failure rates of computer codes by the Gompertz distribution [8]. In marketing science, it has been used as an individual-level model of customer lifetime [9]. Also, the Gompertz distribution is applied in reliability, life testing, epidemiological, and biomedical studies. Several such situations have been discussed by Ananda et al. [10], Walker and Adham [11], Jaheen [12], and many others. The probability density function of the Gompertz distribution is
(1)
f
(
x
)
=
b
η
e
b
x
e
η
exp
⁡
(
-
η
e
b
x
)
;
0
≤
x
<
∞
,
b
>
0
,
η
>
0
,
where b is the scale parameter and η is the shape parameter of the Gompertz distribution. In the actuarial and biological sciences and in demography, the Gompertz distribution is parameterized slightly and differently The Gompertz distribution is a flexible distribution that can be skewed to the right and to the left. The Gompertz density function can take on different shapes depending on the values of the shape parameter  η. The nth moment of a Gompertz distributed random variable X is
(2)
E
(
X
n
)
=
n
!
b
n
e
n
E
1
n
-
1
(
η
)
,
where E
s
n
(
z
)
=
(
1
/
n
!
)
∫
1
∞
(
ln
⁡
x
)
n
x
-
s
e
-
z
x
d
z  is the generalized integroexponential function [13]. When the shape parameter  η of a Gompertz distribution varies according to a Gamma distribution with shape parameter  α  and scale parameter β (mean
=
α
/
β), the distribution of x is Gamma/Gompertz [9]. The Gamma/Gompertz distribution has been used as an aggregate-level model of customer lifetime and a model of mortality risks. Missov studied life expectancy resulting from a gamma-Gompertz force of mortality [14].The probability density function of the Gamma/Gompertz distribution is(3)
f
(
x
)
=
b
s
e
b
x
β
s
(
β
-
1
+
e
b
x
)
s
+
1
;
0
≤
x
<
∞
,
b
>
0
,
β
>
0
,
s
>
0
,
where b is the scale parameter and β  and s are the shape parameters of the Gamma/Gompertz distribution (Figure 1). The cumulative distribution function of the Gamma/Gompertz distribution is
(4)
F
(
x
)

=

1
-
β
s
(
β
-
1
+
e
b
x
)
s
;
0
≤
x
<
∞
,
b
>
0
,
β
>
0
,
s
>
0
.
When β
=
1, this reduces to an exponential distribution with parameter s
b:
(5)
F
(
x
)
=
1
-
e
-
b
s
x
;
0
≤
x
<
∞
,
b
>
0
,
s
>
0
.
The expected value of random variable X of a Gamma/Gompertz distribution depends on the values of b, β , and s; that is, we have E
(
x
)
=
(
1
/
β
)
[
β
/
(
β
-
1
)
]
ln
⁡
β  for b
,
s
>
0,  β
≠
1 and E
(
x
)
=
1
/
b
s  for  b
,
s
>
0,  β
=
1. Also, the median of this distribution is (
1
/
b
)
ln
⁡
{
β
[
(
1
/
2
)
-
1
/
s
-
1
]
+
1
}.Figure 1
Three parameters Gamma/Gompertz distribution density function.Successful application of Gamma/Gompertz distribution depends on having acceptable statistical estimates of the distribution parameters. One of the best methods of obtaining a point estimator of a parameter is the method of maximum likelihood. As the name implies, the estimator will be the value of the parameter that maximizes the likelihood function. While the method of maximum likelihood is an excellent technique, sometimes complications arise in its use. For example, it may not always be possible to use calculus methods directly to determine the maximum of likelihood function. This difficulty is obvious in estimating the parameters of the Gamma/Gompertz distribution.In this paper, we use iterated local search (ILS) to estimate Gamma/Gompertz parameters. The paper is organized as follows. Section2 describes the notion of maximum likelihood estimation. Section 3 explains the basics of iterated local search (ILS). In Section 4, we explain the steps of ILS algorithm to solve the problem. Some numerical examples and their computational results are represented in Section 5. Finally, Section 6 contains the conclusions.


## 2. Maximum Likelihood Estimation

Maximum-likelihood estimation (MLE) is a method of estimating the parameters of a statistical model. In general, for a fixed set of data and underlying statistical model, the method of maximum likelihood selects values of the model parameters that produce a distribution that gives the observed data the greatest probability (i.e., parameters that maximize the likelihood function). In essence the method selects a set of model parameters that predicts that events that occur often in the data are very likely to occur and events that occur seldom in the data are predicted to occur with small probability. Maximum-likelihood estimation gives a unified approach to estimation, which is well-defined in the case of the normal distribution and many other problems.Suppose thatx is a random variable with probability distribution  f
(
x
,
θ
→
)  where θ
→
=
(
θ
1
,
θ
2
,
θ
3
,
…
,
θ
k
) is unknown parameters vector. Let x
1
,
x
2
,
…
,
x
n be the observed values in a random sample of size n. Then, the likelihood function of the sample is
(6)
L
(
θ
→
)
=
f
(
x
1
;
θ
→
)
=
f
(
x
2
;
θ
→
)
f
(
x
3
;
θ
→
)
⋯
f
(
x
n
;
θ
→
)
=
∏
i
=
1
n
f
(
x
i
;
θ
→
)
.
Note that the likelihood function is now a function of only the unknown parameters  θ
→
=
(
θ
1
,
θ
2
,
θ
3
,
…
,
θ
k
). The maximum likelihood estimators of θ
→ are the values that maximize the likelihood function  L
(
θ
→
). In practice, it is often more convenient to work with the logarithm of the likelihood function:
(7)
Ln
L
(
θ
→
)
=
Ln
∏
i
=
1
n
f
(
x
i
;
θ
→
)
.
The maximum likelihood estimators would be found by equating the k partial derivatives to zero and solving the resulting system of equations:
(8)
∂
∂
θ
→
L
(
θ
→
)
=
0
→
or
∂
∂
θ
→
Ln
L
(
θ
→
)
=
0
→
.
While the method of maximum likelihood is an excellent technique for many models and a maximum likelihood estimator can be found as an explicit function of the observed data x
1
,
…
,
x
n, sometimes complications arise in its use. For example, it is not always easy to maximize the likelihood function because the equation(s) obtained from partial derivatives may be difficult to solve or no closed-form solution to the maximization problem is known or available. Therefore, an MLE has to be found numerically using optimization methods.


## 3. General Iterated Local Search

Iterated local search is a simple but powerful metaheuristic algorithm [15]. It applies local search to an initial solution until it finds a local optimum; then it perturbs the solution and restarts local search. The importance of the perturbation is obvious: a too small perturbation might not enable the system to escape from the basin of attraction of the local optimum just found. On the other side, a too strong perturbation would make the algorithm similar to a random restart local search.A local search is effective if it is able to find good local optima, that is, if it can find the basin of attraction of those states. When the search space is wide and/or when the basin of attraction of good local optima is small, a simple multistart algorithm is almost useless. An effective search could be designed as a trajectory only in the set of local optimas
*, instead of in the set s of all the states.The requirement on the perturbation ofs is to produce a starting point for local search such that a local optimum different from s is reached. However, this new local optimum should be closer to s than a local optimum produced by a random restart. Theacceptance criterion acts as a counter balance, as it filters and gives feedback to the perturbation action, depending on the characteristics of the new local optimum. A high level description of ILS steps is presented in Algorithm 1.Algorithm 1:Iterated local search (ILS) algorithm.
s
0
← Generate Initial Solution (s)
s
*
← Apply Local Search (s
0)
While termination condition not met do
s
′              ←  Apply perturbation (s
*)
s
′
*  ←  Apply Local Search (s
′)
s
*         ←  Apply acceptance criterion (s
*
,
s
′
*)
Memorize Best Found Solution
End WhileThe design of ILS algorithms has several degrees of freedom in the choice of the initial solution, perturbation, and acceptance criteria.The construction of initial solutions should be fast, and initial solutions should be a good starting point for local search. The fastest way of producing an initial solution is to generate it at random; however, this is the easiest way for problems that are unconstrained, whilst in other cases the construction of a feasible solution requires also constraint checking.The perturbation is usually nondeterministic in order to avoid cycling. Its most important characteristic is the strength, roughly defined as the amount of changes made on the current solution. The strength parameter,λ, can be either fixed or variable. In the first case, the distance between perturbation and local search is kept constant, independently of the problem size. However, a variable strength is in general more effective, since it has been experimentally found that, in most of the problems, the bigger the problem size is, the larger should be the strength.A second choice is the mechanism to perform perturbations. This may be a random mechanism, or the perturbation may be produced by a deterministic or semideterministic method.The third important component is the acceptance criterion. Two extreme examples consist in (1) accepting the new local optimum only in case of improvement and (2) in always accepting the new solution. In-between, there are several possibilities. In this paper, we consider an annealing scheme for acceptance criterion. Simulated annealing is one of the most novel algorithms initially presented by Kirkpatrick et al. [16]. The algorithm is based upon that of Metropolis et al. which was originally proposed as a means of finding the equilibrium configuration of a collection of atoms at a given temperature [17]. Similar to other metaheuristic algorithms, it attempts to solve hard combinatorial optimization problems through controlled randomization. Sometimes simulated annealing was applied to parameters estimation [18].The performance of ILS algorithm depends on the definition of the several control parameters. The choice of an appropriateλ is crucial for the performance of the algorithm. The value of parameter λ decrease during the search process; thus, at the beginning of the search, diversification is high and as it gradually goes on its search path, intensification becomes intense. Hereby, with the choice of appropriate  λ, a dynamic balance is given between diversification and intensification.


## 4. Applying Hybrid ILS for Estimating Gamma/Gompertz Parameters

To estimate the three parameters of Gamma/Gompertz distribution, letx
1
,
…
,
x
n be a random sample from the Gamma/Gompertz distribution. The log of the likelihood function is
(9)
Ln
L
(
b
,
β
,
s
)
=
n
Ln
(
b
)
+
n
Ln
(
s
)
+
n
s
Ln
(
β
)
+
b
∑
i
=
1
n
x
i
-
(
s
+
1
)
Ln
∏
i
=
1
n
(
β
-
1
+
e
b
x
i
)
.
When the derivatives are equated to zero, we obtain the following equations that must be solved to find the maximum likelihood estimators of b,  β, ands:
(10)
∂
∂
b
Ln
L
(
b
,
β
,
s
)
=
0
,
∂
∂
β
Ln
L
(
b
,
β
,
s
)
=
0
,
(11)
∂
∂
s
Ln
L
(
b
,
β
,
s
)
=
0
.
There is no closed form solution to these equations and it is very difficult to solve these equations using ordinary optimization techniques. To estimate the parameters  b,  β, and  s  we are to maximize  L
(
b
,
β
,
s
) (or  Ln
L
(
b
,
β
,
s
)), using hybrid iterated local search.For a given values ofb  and  β, (11) gives an expression of  Ln
L
(
b
,
β
,
s
)  as a function of only s which is calledreduced  Ln
L
(
b
,
β
,
s
). Although Ln
L
(
b
,
β
,
s
)  is a nonconcave function, it is obvious from expression (11) thatreduced
Ln
L
(
b
,
β
,
s
) is a concave function because second partial derivative ofreduced
Ln
L
(
b
,
β
,
s
) with respect to s is nonpositive. Therefore, taking the first derivative ofreduced
Ln
L
(
b
,
β
,
s
)  with respect to s and setting (
∂
/
∂
s
)
r
e
d
u
c
e
d
Ln
L
(
b
,
β
,
s
)
=
0 yield
(12)
s
=
n
Ln
(
∏
i
=
1
n
(
β
-
1
+
e
b
x
i
)
/
β
)
.
Therefore, problem reduces to obtain parameters  b  and  β; s is computable from relation (12). Of course, only positive values for s are acceptable. To challenge this very difficult problem, we propose a hybrid iterated local search approach. In this regard, the steps of this algorithm are briefly presented in Algorithm 2, where the following notation is used:θ
0
→: Initial solution
θ
→: Current solution
θ
′
→: Perturbed solution
θ
′
*
→: Local optimum solution
θ
*
→: Best solution
Ln
L
(
θ
→
): Value of the objective function at solution θ
→
ε: Neighborhood step-length parameter
λ: Perturbation step-length parameter
C: Geometric cooling factor
τ
0: Initial temperature.The algorithm starts with an initial random solution for the problem (positive values for b and β), and by initializing the so-called perturbation step-length parameter  λ, the neighborhood step-length parameter  ε, cooling factor C and initial temperature  τ
0. At each solution, parameter s is calculated by relation (12) and only solutions are considered feasible for which s is positive. Two-neighborhood solution is generated by right shift and left shift of current solution by an amount of ε, for b  or  β, at random. Feasible improving direction is detected. The generated feasible solution in improving direction replaces the current one. Generating feasible neighborhood solution at same direction continues until a local optimum solution θ
′
*
→ is reached. This first local optimum solution sets as best solution  θ
*
→. The cycle of algorithm repeats while the acceptance criterion is satisfied. At each repetition of the algorithm, a perturbed solution of the current local optimum solution   θ
′
*
→ is generated as follows: with generating two binary random numbers z
1 and z
2, we select a direction for perturbation (right or left) for each of the parameters  b  and  β. Perturbed solution is obtained by adding to or subtracting from current local optimum solution,  θ
′
*
→, a dynamic amount, depending on the perturbation directions and  λ, where  λ  is the perturbation step-length parameter playing an important role in our algorithm. The generated feasible solution replaces the current one. Local search procedure is applied to the newly chosen solution. We suppose that after the local optimum is reached, it is always acceptable (with checking positivity of s). After generating newly local optimum solution,  θ
′
*
→, a kind of annealing schedule is considered as acceptance criterion: accept all the improving new local optima and accept also the nonimproving ones with a probability that is a function of the temperature  τ  and the difference of objective values, in formulas:
(13)
P
(Acceptance)
=
{
1
WWWWWWWWWIW
if
Ln
L
(
θ
′
*
→
)
>
Ln
L
(
θ
*
→
)
exp
⁡
(
-
Ln
L
(
θ
*
→
)
-
Ln
L
(
θ
′
*
→
)
τ
)
W
W
W
W
W
w
a
a
a
a
W
w
W
W
otherwise.
It is obvious that control parameter, τ, is chosen with respect to the specific problem at hand. When adapting this general algorithm to a specific problem, the procedure to generate both initial and perturbed solutions is very important in addition to the control parameter. Hereby, the most important feature of this algorithm, as a metaheuristic, is the possibility of accepting a worst solution, which can allow it to prevent falling into local optimum trap. Obviously, the probability of accepting a worse solution decreases as the temperature decreases in each outer cycle. The initial temperature (τ
0) should be high enough that, in the first iteration of the algorithm, the probability of accepting a worse solution is, at least, of 80% [16]. The most commonly used temperature reducing function is geometric; that is, τ
i
=
C
τ
i
-
1 in which C
<
1 is constant. The termination condition happens when the system has reached to a desired energy level.Algorithm 2:Proposed hybrid iterated local search.
Obtain a random sample from the distribution the size of which should be big enough.
Initialize the ILS control parameter (λ, ε, C, τ
0)
select an initial solutionθ
0
⟶
=
(
b
,
β
);
Setθ
⟶
=
θ
0
⟶
θ
*
⟶
← Apply Local Search (θ
→)
While termination condition not met do
θ
′
⟶   ← Apply perturbation (θ
*
⟶)
θ
′
*
⟶
← Apply Local Search (θ
′
⟶)
θ
*
⟶      ← Apply acceptance criterion (θ
*
⟶
,
θ
′
*
⟶)
Memorize Best Found Solution
End While


## 5. Numerical Examples

In this section, we solve two problem instances for illustrative and comparative purposes. In addition, to know the effects of the sample size, different sample sizes have been chosen and used to solve estimate parameters. We consider two Gamma/Gompertz distributions with parametersb
=
2, β
=
4, and s
=
3 (Example 1) and  b
=
3,  β
=
3 , and  s
=
3 (Example 2), respectively. Let x
1
,
x
2
,
…
,
x
n be the observed values from each distribution in a random sample of size n
=
100, 200, and 300. The coding has been done using MatLab 7.12 and run on an Intel Core i5 CPU processor with 4 GB of RAM.The performance of metaheuristic algorithms depends excessively on the value of their parameters. To know the effects of the perturbation rule and acceptance criterion, different approaches have been chosen and used to estimate parameters. We obtained best results with perturbation rule according toλ
=
(
101
-
i
)
*
ε (in which i is iteration counter) and acceptance criterion based on  τ
>
τ
0.In this paper, the proposed algorithm parameter values are selected through the computational experiments. The experiments indicated that the best values for the parameters of the algorithms in our examples are as follows:C
=
0.975 and τ
0
=
100. ε
=
0.01 is selected for the examples.Tables1 and 2 show the results. Figures 2 and 3 show the likelihood function for all the values evaluated during the process of maximization. The experimental results demonstrate that calibration provides high quality solutions. It is quite clear that as the sample size increases the estimation will be better. It is straightforward from the primary estimation theory that the bigger the sample size the better the estimation. With comparing the CPU time requirements, it is clear that as the sample size increases more run time is needed. It is because as the sample size increases the more complicated will be the likelihood function to maximize.Table 1
Experimental result for Example 1.
Example 1
(
b
,
β
,
s
)
=
(
2,4
,
3
)
N
100
200
300
(
b
^
,
β
^
,
s
^
)
(2.02, 4.12, 3.0728)
(1.98, 4.06, 2.944)
(1.98, 3.93, 2.9506)
Ln
L
(
b
^
,
β
^
,
s
^
)
−318.6441
−645.8559
−948.7620
Run time (sec)
2.19
12.38
19.06Table 2
Experimental result for Example 2.
Example 1
(
b
,
β
,
s
)
=
(
3,3
,
3
)
n
100
200
300
(
b
^
,
β
^
,
s
^
)
(2.87, 3.06, 2.8466)
(2.85, 2.91, 3.0412)
(3.09, 2.93, 3.029)
Ln
L
(
b
^
,
β
^
,
s
^
)
−233.1599
−458.5367
−651.2425
Run time (sec)
1.84
9.76
23.05Ln
L
(
b
,
β
,
s
)  versus iteration counter for Example 1: (a) n
=
100, (b) n
=
200, and (c) n
=
300.
(a)
(b)
(c)Ln
L
(
b
,
β
,
s
)  versus iteration counter for Example 2: (a) n
=
100, (b) n
=
200, and (c) n
=
300.
(a)
(b)
(c)


## 6. Conclusions

We considered the Gamma/Gompertz distribution, which is often encountered in customer lifetime and mortality risks distribution literature. We developed hybrid iterated local search to estimation of Gamma/Gompertz parameters. To improve the efficiency of the proposed algorithm, its parameters were selected through the computational experiments. The results of the computational experiment showed that calibration provides high quality solutions. The large size samples perform better than the small size ones, measured by the solution accuracy index but with more CPU time.



---

*Source: 629693-2014-06-05.xml*