〈⟨

# A hybrid estimation of distribution algorithm for
joint stratification and
sample allocation

Mervyn O’Luing  1 Steven Prestwich  1 S. Armagan Tarim2

Abstract

In this study we propose a hybrid estimation of distribution algorithm (HEDA)
to solve the joint stratification and sample allocation problem. This is a
complex problem in which each the quality of each stratification from the set
of all possible stratifications is measured its optimal sample allocation.
EDAs are stochastic black-box optimization algorithms which can be used to
estimate, build and sample probability models in the search for an optimal
stratification. In this paper we enhance the exploitation properties of the
EDA by adding a simulated annealing algorithm to make it a hybrid EDA. Results
of empirical comparisons for atomic and continuous strata show that the HEDA
attains the bests results found so far when compared to benchmark tests on the
same data using a grouping genetic algorithm, simulated annealing algorithm or
hill-climbing algorithm. However, the execution times and total execution are,
in general, higher for the HEDA.

Keywords: Hybrid estimation of distribution algorithm; Optimal stratification;
Sample allocation; R software.

††footnotetext: 1 Insight Centre for Data Analytics, Department of Computer
Science, University College Cork, Ireland. Email: mervyn.oluing@insight-
centre.org<EMAIL_ADDRESS>††footnotetext: 2 Cork
University Business School, University College Cork, Ireland. Email:
<EMAIL_ADDRESS>
###  1 Introduction

The joint determination of stratification and sample allocation designs is a
complex problem in which each solution is a stratification of basic strata
(either atomic or continuous). The quality of each solution is measured by the
optimal sample size that can be allocated to this stratification and still
meet the precision constraints set by the survey designer. This quality is
evaluated by the Bethel-Chromy algorithm (Bethel, 1985; Chromy, 1987; Bethel,
1989) which is expensive (in computational terms). Previous contributions in
this area includes work carried out by (Kozak et al., 2007; Keskintürk and Er,
2007; Benedetti et al., 2008; Baillargeon and Rivest, 2009, 2011; Ballin and
Barcaroli, 2013; O’Luing et al., 2019; Ballin and Barcaroli, 2020; O’Luing et
al., 2020, 2021).

In this paper, we propose a hybrid estimation of distribution algorithm (HEDA)
to solve this problem. EDAs are stochastic black-box optimization algorithms
which can be used to estimate, build and sample probability models in the
search for an optimal solution. We, therefore, describe the search for the
lowest cost stratification as that of black-box optimization, in order to tie
the problem in with existing EDA literature.

Rather than other methodologies where the strata have already been determined
(e.g. administrative strata or the cumulative root frequency method) before
evaluating the optimal sample allocation - the basic premise of this problem
is that the optimal solution is unknown. It is a non linear problem with a
rugged search space for which there are many near-optimal sample allocations
(or local minima) and also perhaps more than one (i.e. attainable through
multiple stratifications) optimal sample allocation (global minimum).

However, we cannot see the sample allocation for each stratification in
advance, and thus cannot say _a priori_ which stratification provides the
optimal allocation. We could say that we are dealing with a black box. The
only sure way of determining the optimal stratification is to evaluate each
solution. This is known as grid-search and is intractable for large problems.
Indeed, for representative surveys, especially in official statistics, for any
practical sized sampling frame the number of basic strata to be stratified
(given that they may be derived from multiple auxiliary variables) can be
quite large.

A black-box optimization procedure explores the search space by generating
solutions, evaluating them, and processing the results of this evaluation in
order to generate new promising solutions (Gonzalez-Fernandez and Soto, 2012).
Such procedures tend to find local minima of varying proximity to a global
minimum. However they tend to be faster alternatives to grid-search. Some are
deterministic, e.g. the direct search approach of (Hooke and Jeeves, 1961) or
the simplex method of (Nelder and Mead, 1965) and some stochastic, e.g.
k-means (Hartigan and Wong, 1979), grouping genetic algorithm (John, 1975),
simulated annealing (Kirkpatrick et al., 1983; Černỳ, 1985) and hill-climbing
(Lin, 1965; Lin and Kernighan, 1973) . The latter set of procedures provide a
means of attaining a solution that is "good enough" in a computing time that
is "small enough" (Sörensen and Glover, 2013).

That has been our focus in earlier papers in which we presented evolutionary
(a grouping genetic algorithm -(O’Luing et al., 2019)) and local search
(simulated annealing algorithm - (O’Luing et al., 2020) algorithms and
explored multi-stage combinations of clustering algorithms with a hill-
climbing algorithm ((O’Luing et al., 2021)). We have evaluated the performance
of these algorithms by the solution quality and computation time taken to find
a local minimum. In (O’Luing et al., 2020) and (O’Luing et al., 2021) we also
considered training times. The performance has varied according to each data
stratification problem.

To expand on the details mentioned above, we explore a new paradigm of
evolutionary algorithms named estimation of distribution algorithms (EDAs)
(Baluja, 1994; Mühlenbein and Paaß, 1996; Larrañaga and Lozano, 2001; Pelikan
et al., 2003) in the context of this problem. In particular, we consider the
application of a hybridised version of an EDA and compare it against the best
results achieved so far with the algorithms discussed in (O’Luing et al.,
2019), (O’Luing et al., 2020) and (O’Luing et al., 2021). Section 2 provides
some background details on EDAs. Section 3 motivates the use of a HEDA for
this problem. Section 4 summarises the objective function.

paper. Section 6 discusses the evaluation approach. Section 7 demonstrates how
the EDA component of the HEDA works. Sections 8 and 9 give results of
empirical comparisons of the HEDA for atomic and continuous strata. Sections
10 and 11 describe our conclusions and suggestions for further work.

###  2 Estimation of distribution algorithms (EDAs)

EDAs, which are also known as probabilistic model-building genetic algorithms
(PMBGAs), belong to a family of evolutionary algorithms. They are, in effect,
stochastic black-box optimization algorithms which are characterized by
iteratively estimating, building and sampling probability models in the search
for optimal solutions.

To put it another way, EDAs work by selecting promising solutions from a
population (similar to elitism in evolutionary algorithms) and building
probabilistic models of those solutions. They then sample from the
corresponding probability distributions to obtain new solutions (Lima et al.,
2011). It is these characteristics of probabilistic model building and
sampling from that model that most differentiates the EDA from other
evolutionary algorithms such as the genetic algorithm.

If the model built in each generation captures the important features of
selected solutions and generates new solutions with these features, then the
EDA should be able to quickly converge to the optimum (Mühlenbein and Mahnig,
1999). Indeed, assuming that the population size is large enough to ensure
reliable convergence (Harik et al., 1999; Goldberg, 2002), the EDA based on
the probability model provides an efficient and reliable approach to solving
many optimization problems (Hauschild and Pelikan, 2011).

Furthermore, as EDAs iteratively refine the probabilistic model using elite
solutions, thereby increasing the probability of generating the global
optimum, after a reasonable number of iterations, the procedure should locate
the global optimum or its accurate approximation (Hauschild and Pelikan,
2011). Empirically, EDAs have been shown to outperform other optimisation
techniques in problems such as the multi-objective knapsack problem (Shah and
Reed, 2011), multi-objective monitoring network design (Kollat et al., 2008)
or optimising cancer chemotherapy (Petrovski et al., 2006).

Basic EDAs use a simple probability model that has a fixed structure and
learns the parameters for that model, e.g. the univariate marginal
distribution algorithm (UMDA) (Mühlenbein and Paaß, 1996), population-based
incremental learning (PBIL) (Baluja, 1994) and compact genetic algorithm (cGA)
(Harik et al., 1999). Such EDAS are suitable for univariate problems.

On the other hand, for more complex problems there are EDAs with adaptive
multivariate models such as Bayesian networks (BNs) (Pearl, 1988), which can
model complex multivariate interactions. Examples of Bayesian EDAs include the
Bayesian optimization algorithm (BOA) (Pelikan et al., 1999; Pelikan et al.,
2003), the estimation of Bayesian networks algorithm (EBNA) Etxeberria (1999),
and the learning factorized distribution algorithm (LFDA)(Mühlenbein and
Mahnig, 1999).

For this problem, as we are dealing with mutually exclusive basic strata, we
assume that the probability distribution of any basic stratum belonging to a
particular stratum is independent of that for another basic stratum, and for
this reason we will implement a univariate EDA based closely on the UMDA.

###  3 A hybrid estimation of distribution algorithm (HEDA)

Even though we pointed out in section 2 that EDAs should locate the global
optimum or its near approximation in a reasonable amount of iterations, they
have two main computational bottlenecks: $(1)$ fitness evaluation and $(2)$
model building. These must be addressed by efficiency enhancement techniques
suitable for EDAs (Hauschild and Pelikan, 2011).

The latter bottleneck we have addressed by using the simple model building
approach of the UMDA - thus avoiding the computational overhead of more
complex model building. The former bottleneck, clearly, is not only an issue
for the EDA as it relates not only to the size of the search space but also
the complexity of the problem. However, we can address this using
hybridisation (Hauschild and Pelikan, 2011). This is an efficiency technique
the purpose of which is to speed up the performance of the EDA.

In many real-world applications, evolutionary algorithms are combined with
other search optimization algorithms such as local search, tabu search,
simulated annealing or hill-climbing algorithms. Such metaheuristic hybrids
combine the advantages of population based exploration methods (which search
regions of the search space) with trajectory methods (which optimise locally
and are often very successful). Simulated annealing is one example of a
trajectory method which we focus on in this paper.

Simulated annealing resembles hill-climbing in that it makes small adjustments
to a candidate solution - keeping those which lead to an improvement in
solution quality and gradually morphing the solution towards the closest local
optimum. Hill-climbing algorithms generally attain good results especially
when combined with population based search procedures (Lima et al., 2009).

As an example, to solve the minimal switching graph problem (Tang and Lau,
2005) combined the exploration properties of the UMDA and the exploitation
properties of the hill-climbing algorithm into a hybrid EDA to find an optimal
or near-optimal solution efficiently and effectively. They compared the hybrid
algorithm with the UMDA and the hill-climbing algorithm separately, and found
that the performance of the hybrid EDA is significantly better than both the
UMDA and the hill-climbing algorithm.

Although, the literature on hybridisation of EDAs does not appear to have
considered simulated annealing, we expect a hybrid EDA using simulated
annealing to perform well. This is because hill-climbing solutions gravitate
towards the nearest local minima, where they become trapped until the
algorithm reaches a pre-defined end-point. On the other hand, simulated
annealing allows for a probabilistic acceptance of inferior quality solutions,
enabling escape from local minima and thus attaining better quality solutions
than hill-climbing. As it relates to our problem, for the reasons outlined in
this section and in section 2, combining an EDA with simulated annealing
should generate less solutions and thus translate into calling the Bethel-
Chromy evaluation algorithm less often to attain optimal or near-optimal
solutions.

###  4 Objective function

A detailed consideration of the objective function is provided in (O’Luing et
al., 2019). We provide an outline below:

$\begin{array}[]{l}\min n=\sum_{h=1}^{H}n_{h}\\\
s.t.\;\;CV\left(\hat{T}_{g}\right)\leq\varepsilon_{g}\;\;\;(g=1,\ldots,G)\\\
2\leq n_{h}\leq N_{h}\end{array}$

where $n$ is the sample size, $n_{h}$ is the sample size for stratum $h$,
$N_{h}$ is the number of units in stratum $h$ and $H$ is the number of strata.
$\hat{T}_{g}$ is the estimator of the population total for each one of $G$
target variable columns. The upper limit of precision $\varepsilon_{g}$ is
expressed as a coefficient of variation $CV$ for each $\hat{T}_{g}$. We use
the Bethel-Chromy algorithm (Bethel, 1985, 1989; Chromy, 1987) to solve the
allocation problem for a particular stratification.

###  5 Outline of the HEDA

We base our description of the hyrbid estimation of distribution aglorithm on
that found in (Gonzalez-Fernandez and Soto, 2012). We start with a population
of $N_{p}$ solutions either generated at random, or generated with random
permutations of a starting solution (accompanying that solution). The
population is evaluated and the best solutions are selected. Any selection
method can be used (e.g. roulette wheel, tournament selection, Boltzmann
selection, etc.) however for our algorithm we use elitism. We construct a
probability model of the best solutions. We then use that model to generate
new solutions to replace those not selected at the elitism stage. After a
tunable number of iterations a simulated annealing algorithm is applied to a
tunable number of solutions from the population (for the experiments in
sections 8 and 9 we apply simulated annealing to the top ranked solution).
This process continues until a stopping rule has been reached.

Algorithm 1 Hybrid EDA

1:Set $i\leftarrow 1$ and generate initial population $P_{1}$ of $N_{p}$
solutions

2:Apply simulated annealing algorithm $\triangleright$ tunable conditions

3:Select $N_{Elite}$ promising solutions $S_{i}$ from $P_{i}$

4:Construct a probability model $M_{i}$ of the best solution from $S_{i}$.

5:Create a new population $P_{i+1}$ by sampling a set of $N_{p}-N_{Elite}$ new
solutions according to the distribution encoded by $M_{i}$

6:set $i\leftarrow i+1$

7:If stopping criteria (number of iterations, $I$) not met repeat steps $2$ to
$6$

###  6 Evaluation approach

Each of the $N_{p}$ solutions in the population are evaluated in a two step-
approach using the _aggrStrata_ function (Ballin and Barcaroli, 2020) and
_Bethel_ algorithm (Ballin and Barcaroli, 2020; De Meo and De Meo, 2009). The
_aggrStrata_ function obtains summary statistics (including point estimates)
for the basic strata. The _Bethel_ function uses those statistics to compute
the optimal sample allocation for that stratification. We have coded these
functions in _C++_ and integrated them, along with the remainder of the HEDA,
into the _R_ software language (R Core Team, 2021) using the _Rcpp_ package
(Eddelbuettel, 2013) in order to speed up computation times. Accordingly, the
traditional _set.seed()_ function in _R_ which was useful for reproducbility
of experiments is not easily applied in _Rcpp_ \- meaning that some further
work is required before we can reproduce results exactly.

Nonetheless, we found this two-step approach to be a more useful evaluation
metric for the HEDA than the Bayesian Information Criterion (BIC) or total
within sums of squares (TWSS) which are more suited to clustering problems and
faster than the evaluation algorithm. We initially considered these as
"surrogate" functions. However, solutions which attain better BIC or TWSS
scores might not attain better sample allocations. This is because minimising
TWSS eventually leads towards one cluster per atomic stratum whereas
maximising BIC scores is useful for selecting the optimal number of clusters,
but not necessarily the optimal arrangement of items within clusters.

###  7 Example of EDA component of the HEDA on the iris data set

To demonstrate how an estimation of distribution algorithm works we use the
iris data set (Anderson, 1935; Fisher, 1936; R Core Team, 2021) and atomic
strata. We select Petal Length and Petal Width as the target variables. We use
Sepal Length and Species as auxiliary variables. We convert Sepal Length to a
categorical variable with 3 bins using the k-means algorithm (Hartigan and
Wong, 1979) and a seed of $1234$. We use an upper coefficient of variation
level of $0.05$ for the target variables. The cross product of the categorical
version of Sepal Length with Species results in 8 atomic strata. We group
these 8 atomic strata into $H$ strata, in this example $H=3$ or $H=4$, i.e.
some of the solutions have three strata and some have four.

Table 7.1: Summary statistics for the $L$ atomic strata Atomic Stratum, $l$ | N | M1 | M2 | S1 | S2
---|---|---|---|---|---
a | 40 | 1.46 | 0.24 | 0.17 | 0.10
b | 5 | 3.40 | 1.10 | 0.30 | 0.15
c | 1 | 4.50 | 1.70 | 0.00 | 0.00
d | 10 | 1.48 | 0.29 | 0.17 | 0.09
e | 31 | 4.23 | 1.31 | 0.36 | 0.19
f | 12 | 5.07 | 1.88 | 0.22 | 0.27
g | 14 | 4.64 | 1.45 | 0.21 | 0.11
h | 37 | 5.74 | 2.08 | 0.50 | 0.25

We initialise a population size of $N_{p}$ solutions (in this case $N_{p}=5$)
each of size $L$, i.e. the number of atomic strata, where $l=1,2,\dots,L$. As
can be seen in table 7.1 we initially use letters of the alphabet to
differentiate between atomic strata, however in subsequent tables an integer
denotes to which one of the $H$ strata each atomic stratum belongs. Each
solution is evaluated and ranked.

Table 7.2: Population of size $N_{p}$ with solution quality and rank Initial Population | Quality | Rank
---|---|---
3 | 2 | 2 | 3 | 2 | 1 | 2 | 2 | 19.19 | 3
3 | 2 | 4 | 3 | 2 | 1 | 2 | 3 | 46.77 | 5
3 | 2 | 4 | 1 | 2 | 1 | 2 | 4 | 14.48 | 2
3 | 2 | 4 | 3 | 2 | 1 | 1 | 4 | 10.65 | 1
3 | 3 | 2 | 3 | 2 | 1 | 2 | 2 | 30.30 | 4

We create a new selected population of the best solutions (in this example we
select 2 solutions) in a process that is analgous with elitism in evolutionary
algorithms.

Table 7.3: Selected population of best elite solutions Selected Population
---
3 | 2 | 4 | 3 | 2 | 1 | 1 | 4
3 | 2 | 4 | 1 | 2 | 1 | 2 | 4

We then construct a probabilistic model of the solutions in the selected
population with the aim of estimating the probability distribution for each of
the $H$ strata for each atomic stratum. The probability of a candidate
solution (or vector, $V$) where ($V=V_{1},V_{2},...,V_{L}$) is the product of
probabilities of individual strata for each atomic stratum:

$p(V_{1},V_{2},...,V_{L})=p(V_{1})\times p(V_{2}),...,\times p(V_{L})$ (7.1)

where $p(V_{l})$ is the probability of variable $(V_{l}=v_{l})$, $v_{l}$ is an
integer between $1$ and $H$ and $p(V_{1},V_{2},...,V_{L})$ is the probability
of the candidate solution $(V_{1},V_{2},...,V_{L})$ and $H$ represents the
number of strata which are labelled individually by an integer between $1$ and
$H$. The univariate model for the $L$ variables consists of $L$ vectors
containing probabilities of an atomic stratum belonging to the different
strata. The probabilities different strata sum to 1.

The joint probability distribution is factorized as a product of independent
univariate marginal distributions, which are estimated from marginal
frequencies (Paul and Iba, 2002):

$p(V_{l})=\frac{\sum_{j=1}^{N_{Elite}}\delta_{j}(V_{l}=v_{l}|N_{Elite}^{iter-1})}{N_{Elite}^{iter-1}}$
(7.2)

where $N_{Elite}^{iter-1}$is the number of elite solutions from the previous
iteration, $\delta_{j}(V_{l}=v_{l}|N_{Elite}^{iter-1})=1$ if $V_{l}=v_{l}$ in
the $j^{th}$case of $N_{Elite}^{iter-1}$, and $0$ otherwise.

Table 7.4: Model estimating the probability of each atomic stratum $l$ belonging to each stratum $h$ Stratum, $h$ | Probability Model
---|---
1 | 0 | 0 | 0 | 0.5 | 0 | 1 | 0.5 | 0
2 | 0 | 1 | 0 | 0 | 1 | 0 | 0.5 | 0
3 | 1 | 0 | 0 | 0.5 | 0 | 0 | 0 | 0
4 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1
Total | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1

We generate new solutions from this model to replace the non-elite solutions
by sampling from that distribution. We evaluate the new solutions and rank all
solutions by their quality. This offspring population returns a solution
quality of $9.34$ which is the global minimum (to find the global minimum we
evaluated each of the 4,140 possible partitions of the 8 atomic strata).

Table 7.5: Offspring population with solution quality and rank Offspring Population | Quality | Rank
---|---|---
3 | 2 | 4 | 3 | 2 | 1 | 1 | 4 | 10.65 | 2
3 | 2 | 4 | 1 | 2 | 1 | 2 | 4 | 14.48 | 3
3 | 2 | 4 | 3 | 2 | 1 | 1 | 4 | 10.65 | 2
3 | 2 | 4 | 3 | 2 | 1 | 2 | 4 | 9.34 | 1
3 | 2 | 4 | 1 | 2 | 1 | 2 | 4 | 14.48 | 3

Normally the algorithm repeats the above process until a stopping criterion
has been met.

The extreme probabilities — $0$ and $1$ — mean that unless some mitigating
measure is introduced the atomic stratum $l$ would remain fixed forever to
stratum $h$ at a probability of either $0$ or $1$, obstructing some regions of
the search space (Dang et al., 2019). However, at advanced stages of the
search, e.g. when using a starting solution, the stratifications are of good
quality and atomic stratum may already be in the correct stratum (i.e. the
stratum it would be allocated to in the optimal solution).

In the above experiment it is clear that for all solutions in the population
there are a number of cases where there is only one stratum choice available
for an atomic stratum (i.e. it is assigned to that stratum with a probability
of $1$). Here we are very close to a global minimum and we get there on the
second step - without adjusting the probability of strata assignments. On a
more general level however, the hybrid EDA uses mutation and add strata
components (see (O’Luing et al., 2019)), as well as simulated annealing (see
(O’Luing et al., 2020) which enable escape from this occurrence. The UMDA also
has alternative approaches of avoiding $1,0$ probabilities (such as capping
the probability interval to between $\frac{1}{L}$ and $(1-\frac{1}{L})$) e.g.
(Doerr and Krejca, 2020), however, for our purposes they are not required.

###  8 Empirical comparisons for atomic strata

####  8.1 Background details

We compare the performance of the HEDA with the best solution qualities from
the experiments we carried out on the same data sets, with the grouping
genetic algorithm, simulated annealing algorithm and combinations of
clustering algorithms with hill-climbing. We use the results from these
experiments as a benchmark for comparing the HEDA. More details on these
experiments are provided in O’Luing et al. (2019); O’Luing et al. (2020,
2021).

The data sets including target and auxiliary variables are summarised in table
8.1. We explain the meaning of each variable in table 1 in section 1.

Table 8.1: Summary by data set of the variables, number of records and atomic strata Data set |  | Target
---
Variables
| Auxiliary Variables
---
| Number of
---
Records
| Number of
---
Atomic
Strata
Swiss Municipalities | Surfacesbois, Airbat | POPTOT , HApoly | 2,896 | 579
| American Community
---
Survey, 2015
| HINCP, VALP,
---
SMOCP, INSP
| BLD, TEN, WKEXREL,
---
WORKSTAT, HFL, YBL
619,747 | 123,007
Kiva Loans |  | terminmonths,
---
lendercount,
loanamount
| sector, currency, activity,
---
region, partnerid
614,361 | 84,897

Table 8.2 provides details of the best sample sizes and the corresponding
algorithms from the aforementioned which they were attained with.

Table 8.2: Summary by data set of the sample size and evaluation time for the final stage in multi stage combinations of clustering algorithms with the simulated annealing algorithm and hill-climbing algorithm Dataset |  | Initial
---
Stage(s)
| Final
---
Stage
| Sample
---
Size
| Execution
---
Time
| Total
---
Execution
Time
Swiss Municipalities | Kmeans | SAA | 125.17 | 248.91 | 8,808.63
| American Community
---
Survey, 2015
SOM, FC | HC | 9,065.45 | 6,298.81 | 6,298.81
Kiva Loans | FC | HC | 6,326.35 | 6,018.61 | 6,018.61

However, as we have sought to develop algorithms that provide solutions that
are good enough in a computing time that is small enough we also report
evaluation (execution) and training (total execution) times to provide context
to the results. In table 8.2, _SAA_ refers to simulated annealing algorithm,
_SOM_ applies to self-organising map, _FC_ relates to Fuzzy Clustering and
_HC_ indicates hill-climbing.

For comparison purposes execution time and total execution time relates to the
final stage algorithms only. Note: there was no fine-tuning required for the
hill-climbing algorithm. Details of the fine-tuning time for the initial stage
solutions are available in (O’Luing et al., 2020) and (O’Luing et al., 2021).

####  8.2 Hyperparameters

The hyperparameters used in the experiments for the HEDA are provided in Table
8.3.

Table 8.3: Hyperparameters for the hybrid estimation of distribution algorithm (HEDA) Dataset | Iterations, I |  | SAA
---
Frequency
| Mutation
---
Chance
| Elitism
---
Rate
| Add
---
Strata
Factor
| Temperature,
---
T
Swiss Municipalities | 3,000 | 100 | 0.000185221 | 0.20 | 0.000000146 | 0.000000027
American Community Survey, 2015 | 200 | 10 | 0.000000016 | 0.30 | 0.000000054 | 0.000655857
Kiva Loans | 600 | 100 | 0.000038838 | 0.30 | 0.000000739 | 0.001400962
Dataset |  | Decrement
---
Constant,DC
| Max
---
number of
sequences,
maxit
| Length
---
of
sequence,
J
| % of L
---
for maximum
q value,
Lmax%
| Probability
---
of New
Stratum,
P(H + 1)
| Population Size,
---
$N_{p}$
Swiss Municipalities | 0.941411680 | 2 | 20,000 | 0.10 | 0.009183601 | 20
American Community Survey, 2015 | 0.815042754 | 20 | 5,000 | 0.01 | 0.000000609 | 20
Kiva Loans | 0.954218273 | 2 | 10,000 | 0.02 | 0.000052373 | 20

The hyperparameters operate in this way, _Iterations, $I$_ indicates the
number of iterations the algorithm runs for. The algorithm stops at the last
iteration. The HEDA builds and samples from a _probability model, $M_{i}$_
once every iteration. The simulated annealing algorithm also runs after a
tunable number of iterations, i.e. for the Swiss Municipalities and Kiva Loans
experiments it runs once every $100$ iterations whereas for the American
Community Survey experiment it runs once every $10$ iterations. The simulated
annealing algorithm runs each time for a maximum number of sequences with the
length of each sequence varying for each experiment. See (O’Luing et al.,
2020) for more details on the hyperparameters for the simulated annealing
algorithm.

The following hyperparameters are described in more detail in (O’Luing et al.,
2019). However in brief, _Elitism rate_ indicates the proportion of the ranked
population that is carried over to the next iteration, _Mutation chance_
indicates the probability of each atomic stratum being moved to another
stratum every iteration. Similarly, _Add Strata Factor_ is the probability of
an atomic stratum moving to a new stratum. _Population size, $N_{p}$_ is the
number of solutions used for exploration and evolution each iteration.

The hyperparameters often need to be fine-tuned to suit the characteristics of
a particular data set. We fine-tuned the hyperparameters for these experiments
using the methodology on as described by (Bischla et al., 2017) in the R
software language (R Core Team, 2021). Finally, although we have stated the
hyperparameters, the solution quality attained with them in the HEDA may not
be reproduced exactly on their first application. See table
LABEL:HEDAhyper_atomic for details of the hyperaparameters, execution and
total execution times in the training process.

####  8.3 Results

The results of these experiments are provided in Table 8.4.

Table 8.4: Summary by data set of the benchmark sample size and evaluation time for the multi stage combinations of clustering algorithms with the HEDA Data set | Initial Stage(s) | Final Stage | Sample Size | Execution Time | Total Execution Time
---|---|---|---|---|---
Swiss Municipalities | Kmeans | HEDA | 122.39 | 1,316.11 | 47,045.87
American Community Survey, 2015 | SOM and FC | HEDA | 8,800.53 | 28,857.52 | 550,676.58
Kiva Loans | Kmeans | HEDA | 6,246.74 | 3,292.97 | 53,006.37

We compare the sample sizes attained in table 8.2 and table 8.4 and present
the results below in table 8.5.

Table 8.5: Ratio comparison of the sample sizes for the benchmark results and the HEDA results Data set | Benchmark results | HEDA Results | Ratio comparisons
---|---|---|---
Swiss Municipalities | 125.17 | 122.39 | 0.98
American Community Survey, 2015 | 9,065.45 | 8,800.53 | 0.97
Kiva Loans | 6,326.35 | 6,246.74 | 0.99

The ratio of the HEDA results to the benchmark results indicate that, although
they are similar, the HEDA results are of better quality in all cases.
However, as our focus has been on obtaining results that are good enough in a
time that is small enough these results should be considered in the context of
execution and total execution times.

Table 8.6 compares the execution times for the HEDA and those for the final
stage algorithm in the benchmark results.

Table 8.6: Ratio comparison of the execution times and total execution times for the benchmark results and the HEDA results |  | Benchmark
---
Results
| HEDA
---
Results
|  | Benchmark
---
Results
| HEDA
---
Results
Data set |  | Execution
---
Time
| Execution
---
Time
| Ratio
---
Comparisons
| Total
---
Execution
Time
| Total
---
Execution
Time
| Ratio
---
Comparisons
Swiss Municipalities | 248.91 | 1,316.11 | 5.29 | 8,808.63 | 47,045.87 | 5.34
American Community Survey, 2015 | 6,298.81 | 28,857.52 | 4.58 | 6,298.81 | 550,676.58 | 87.43
Kiva Loans | 6,018.61 | 3,292.97 | 0.55 | 6,018.61 | 53,006.37 | 8.81

In brief the results indicate that overall, for these experiments, the HEDA
takes longer to execute and fine-tune than the SAA for the Swiss
Municipalities,or the combination of clustering algorithms with hill-climbing
for the American Community Survey, 2015 and Kiva Loans experiments.

###  9 Empirical comparisons for continuous strata

Using the same methodology applied in section 8 we ran experiments using the
same data sets comparing the performance of the HEDA on the stratification of
continuous strata with the benchmark results from experiments we described in
(O’Luing et al., 2019), (O’Luing et al., 2020) and (O’Luing et al., 2021). As
before we first provide a summary of the target and auxiliary variables in
table 9.1.

Table 9.1: Target and auxiliary variables for the Continuous method Data set |  | Target variables
---
Auxiliary variables
Swiss Municipalities | Airbat | Surfacesbois |  |
| American Community
---
Survey, 2015
HINCP | VALP | SMOCP | INSP
US Census, 2000 | HHINCOME |  |  |
Kiva Loans | term_in_months | lender_count | loan_amount |
| UN Commodity Trade
---
Statistics data
trade_usd |  |  |

Likewise table 9.2 provides details of the best sample sizes and the
corresponding algorithms from the aforementioned which they were attained
with.

Table 9.2: Summary by data set of the sample size and evaluation time for the final stage of multi stage combinations of clustering algorithms with the hill-climbing algorithm Dataset | Initial Stage(s) | Final Stage | Sample Size | Execution Time | Total Execution Time
---|---|---|---|---|---
Swiss Municipalities | NG and EM | HC | 110 | 38.61 | 38.61
| American Community
---
Survey, 2015
NG and FC | HC | 2,753.55 | 28,632.09 | 28,632.09
Kiva Loans | EM | HC | 1,752.82 | 7,370.53 | 7,370.53

####  9.1 Hyperparameters

The hyperparameters used in the HEDA are provided below in Table 9.3.

Table 9.3: Hyperparameters for the hybrid estimation of distribution algorithm (HEDA) Dataset |  | Iterations,
---
I
| SAA
---
Frequency
| Mutation
---
Chance
| Elitism
---
Rate
| Add
---
Strata
Factor
| Temperature,
---
T
Swiss Municipalities | 1,000 | 100 | 0.0000008 | 0.2 | 0.0000000 | 0.0000058
American Community Survey, 2015 | 30 | 10 | 0.0000003 | 0.3 | 0.0000010 | 0.0000010
Kiva Loans | 90 | 10 | 0.0000004 | 0.3 | 0.0000001 | 0.0000001
Dataset |  | Decrement
---
Constant,
DC
| Max
---
number
of
sequences,
maxit
| Length
---
of
sequence,
J
| % of L
---
for
maximum
q value,
Lmax%
| Probability
---
of
New
Stratum,
P(H + 1)
| Population
---
Size,
N_p
Swiss Municipalities | 0.6266293 | 10 | 3,000 | 0.0195154 | 0.0000377 | 20
American Community Survey, 2015 | 0.9849021 | 2 | 50,000 | 0.0113557 | 0.0000001 | 20
Kiva Loans | 0.9844605 | 2 | 20,000 | 0.0156086 | 0.0000008 | 20

Table LABEL:HEDAhyper_cont outlines the hyperaparameters used, along with the
execution and total execution times resulting from the training process.

####  9.2 Results

The results of the HEDA experiments on continuous strata are provided in Table
9.4.

Table 9.4: Summary by data set of the sample size and evaluation time for the final stage in multi stage combinations of clustering algorithms with the HEDA Data set | Initial Stage(s) | Final Stage | Sample Size | Execution Time | Total Execution Time
---|---|---|---|---|---
Swiss Municipalities | Kmeans | HEDA | 104.93 | 207.11 | 6,792.40
American Community Survey, 2015 | NG and FC | HEDA | 2,619.06 | 22,663.52 | 247,314.63
Kiva Loans | NG and Kmeans | HEDA | 1,576.80 | 8,791.12 | 88,951.97

As before, we compare the sample sizes attained in table 9.2 and table 9.4 and
present the results below in table 9.5.

Table 9.5: Ratio comparison of the sample sizes for the benchmark results and the HEDA results Data set | Benchmark Results | HEDA Results | Ratio Comparisons
---|---|---|---
Swiss Municipalities | 110 | 104.930419822273 | 0.95
American Community Survey, 2015 | 2,753.55 | 2619.06326917666 | 0.95
Kiva Loans | 1,752.82 | 1,576.80 | 0.90

The ratio of the HEDA results to the benchmark results indicate that, the HEDA
results are of better quality in all three experiments.

Table 9.6 indicates that the execution times and total execution times are,
overall, significantly greater for the HEDA.

Table 9.6: Ratio comparison of the execution times and total execution times for the benchmark results and the HEDA results  |  | Benchmark
---
Results
| HEDA
---
Results
|  | Benchmark
---
Results
| HEDA
---
Results
Data set |  | Execution
---
Time
| Execution
---
Time
| Ratio
---
Comparisons
| Total
---
Execution
Time
| Total
---
Execution
Time
| Ratio
---
Comparisons
Swiss Municipalities | 38.61 | 207.11 | 5.36 | 95.33 | 6,792.40 | 71.25
American Community Survey, 2015 | 28,632.09 | 22,663.52 | 0.79 | 41,740.96 | 247,314.63 | 5.92
Kiva Loans | 7,370.53 | 8,791.12 | 1.19 | 7,428.64 | 88,951.97 | 11.97

###  10 Conclusions

Although these experiments are intended to be demonstrative rather than
exhaustive, the multi-stage combination of an initial solution with the HEDA
generally attains better sample sizes than the combinations of initial
solutions with either the SAA or HC algorithm which had attained the best
results in earlier experiments (that also included the GGA).

The execution times and total execution are, generally, significantly higher
for the HEDA than some of the best alternative performing algorithms
(especially the clustering algorithms considered in (O’Luing et al., 2021)).
However, it is worth recalling that the HC algorithm in the above experiments
had converged on a solution and would not have attained better results without
adjusting the stopping conditions for algorithm or adjusting the solution. We
should also bear in mind that the HEDA has found the best results so far for
these experiments, and the execution and total times for the benchmark
algorithms to find solutions of that quality (or better), using either the
same or alternative starting solution, have not been evaluated.

That said, the HEDA is useful for a survey designer with expert knowledge of
the sampling frame and the stratification of basic strata (atomic and
continuous)- for whom the requirement to fine-tune hyperparameters is
mitigated by prior knowledge. It is also useful for survey designers for whom
the fine-tuning times can be included in their computation budget.

Nonetheless, because of the combination of probability models, explorative and
exploitative search we feel the HEDA is well placed to generally outperform
when it comes to attaining results which are good enough in a time that is
small enough.

###  11 Further Work

in the case of the HEDA adjustments can be made in order to use a seed
function for reproducibility of results. Optimised versions of the GGA, SAA
and basic EDA can also be implemented in _Rcpp_. It might be useful to extend
the functionality of the HEDA to the stratification approach used for spatial
sampling by Ballin and Barcaroli (2020). Furthermore, as we kept the
population size, and the number of solutions to which we applied simulated
annealing to every iteration, the same for all experiments, there is scope to
fine those hyperparameters. Lastly, we could investigate more complex
techniques such as the Bayesian optimisation algorithm, the estimation of
Bayesian networks algorithm, the learning factorized distribution algorithm or
mutual information maximising input clustering (MIMIC) (De Bonet et al., 1997)
on this problem.

###  12 Acknowledgements

We acknowledge the useful discussions with Dr. Thierry Vallée of the Central
Statistics Office in general with respect to the progress of the PhD, but also
with respect to tweaking the _Rcpp_ code outlined above.

This material is based upon work supported by the Insight Centre for Data
Analytics and Science Foundation Ireland under Grant No. 12/RC/2289-P2 which
is co-funded under the European Regional Development Fund. Also, this
publication has emanated from research supported in part by a grant from
Science Foundation Ireland under Grant number 16/RC/3918 which is co-funded
under the European Regional Development Fund.

## References

  * Anderson (1935) Anderson, E. (1935).  The irises of the gaspe peninsula.  Bulletin of the American Iris society 59, 2–5.
  * Baillargeon and Rivest (2009) Baillargeon, S. and L.-P. Rivest (2009).  A general algorithm for univariate stratification.  International Statistical Review 77(3), 331–344.
  * Baillargeon and Rivest (2011) Baillargeon, S. and L.-P. Rivest (2011).  The construction of stratified designs in r with the package stratification.  Survey Methodology 37(1), 53–65.
  * Ballin and Barcaroli (2013) Ballin, M. and G. Barcaroli (2013).  Joint determination of optimal stratification and sample allocation using genetic algorithm.  Survey Methodology 39(2), 369–393.
  * Ballin and Barcaroli (2020) Ballin, M. and G. Barcaroli (2020).  Optimization of sampling strata with the SamplingStrata package.  Accessed 3 May 2021.  https://barcaroli.github.io/SamplingStrata/articles/SamplingStrata.html
  * Baluja (1994) Baluja, S. (1994).  Population-based incremental learning. a method for integrating genetic search based function optimization and competitive learning.  Technical report, Carnegie-Mellon Univ Pittsburgh Pa Dept Of Computer Science.
  * Benedetti et al. (2008) Benedetti, R., G. Espa, and G. Lafratta (2008).  A tree-based approach to forming strata in multipurpose business surveys.  Survey Methodology 34(2), 195–203.
  * Bethel (1985) Bethel, J. W. (1985).  An optimum allocation algorithm for multivariate surveys.  American Statistical Proceedings of the Survey Research Methods, Section, 209-212.
  * Bethel (1989) Bethel, J. (1989).  Sample allocation in multivariate surveys.  Survey methodology 15(1), 47-57.
  * Bischla et al. (2017) Bischla, B., J. Richterb, J. Bossekc, D. Hornb, J. Thomasa, and M. Langb (2017).  mlrmbo: A modular framework for model-based optimization of expensive black-box functions.  Gradient Boosting in Automatic Machine Learning: Feature Selection and Hyperparameter Optimization, 36.
  * Černỳ (1985) Černỳ, V. (1985).  Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm.  Journal of optimization theory and applications 45(1), 41–51.
  * Chromy (1987) Chromy, J. R. (1987).  Design optimization with multiple objectives.  Proceedings of the Survey Research Methods Section.
  * De Bonet et al. (1997) De Bonet, J. S., C. L. Isbell, P. Viola, et al. (1997).  Mimic: Finding optima by estimating probability densities.  Advances in neural information processing systems, 424–430.
  * De Meo and De Meo (2009) De Meo, M. and M. M. De Meo (2009).  Package ‘bethel’.
  * Dang et al. (2019) Dang, D.-C., P. K. Lehre, and P. T. H. Nguyen (2019).  Level-based analysis of the univariate marginal distribution algorithm.  Algorithmica 81(2), 668–702.
  * Doerr and Krejca (2020) Doerr, B. and M. S. Krejca (2020).  The univariate marginal distribution algorithm copes well with deception and epistasis.  In Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion, pp. 17–18.
  * Eddelbuettel (2013) Eddelbuettel, E. (2013).  Seamless R and C++ Integration with Rcpp  ISBN 978-1-4614-6867-7 10.1007/978-1-4614-6868-4
  * Etxeberria (1999) Etxeberria, R. (1999).  Global optimization using bayesian networks.  In Proc. 2nd Symposium on Artificial Intelligence (CIMAF-99).
  * Fisher (1936) Fisher, R. A. (1936).  The use of multiple measurements in taxonomic problems.  Annals of Eugenics 7(2), 179–188.
  * Goldberg (2002) Goldberg, D. E. (2002).  The design of innovation: Lessons from and for competent genetic algorithms, Volume 1.  Springer.
  * Gonzalez-Fernandez and Soto (2012) Gonzalez-Fernandez, Y. and M. Soto (2012).  copulaedas: An r package for estimation of distribution algorithms based on copulas.  arXiv preprint arXiv:1209.5429.
  * Harik et al. (1999) Harik, G. R., F. G. Lobo, and D. E. Goldberg (1999).  The compact genetic algorithm.  IEEE transactions on evolutionary computation 3(4), 287–297.
  * Harik et al. (1999) Harik, G., E. Cantú-Paz, D. E. Goldberg, and B. L. Miller (1999).  The gambler’s ruin problem, genetic algorithms, and the sizing of populations.  Evolutionary computation 7(3), 231–253.
  * Hartigan and Wong (1979) Hartigan, J. A. and M. A. Wong (1979). Hybrid Evolutionary Algorithms for Graph Coloring.Algorithm as 136: A k-means clustering algorithm Journal of the Royal Statistical Society. Series C (Applied Statistics) 28(1), 100–108.
  * Hauschild and Pelikan (2011) Hauschild, M. and M. Pelikan (2011).  An introduction and survey of estimation of distribution algorithms.  Swarm and evolutionary computation 1(3), 111–128.
  * Hooke and Jeeves (1961) Hooke, R. and T. A. Jeeves (1961).  “direct search”solution of numerical and statistical problems.  Journal of the ACM (JACM) 8(2), 212–229.
  * John (1975) Holland, J. (1975).  Adaptation in natural and artificial systems, 1992.  Ann Arbor, MI: University of Michigan Press.
  * Keskintürk and Er (2007) Keskintürk, T. and Ş. Er (2007).  A genetic algorithm approach to determine stratum boundaries and sample sizes of each stratum in stratified sampling.  Computational Statistics & Data Analysis 52(1), 53–67.
  * Kirkpatrick et al. (1983) Kirkpatrick, S., C. D. Gelatt, and M. P. Vecchi (1983).  Optimization by simulated annealing.  science 220(4598), 671–680.
  * Kollat et al. (2008) Kollat, J. B., P. M. Reed, and J. R. Kasprzyk (2008).  A new epsilon-dominance hierarchical bayesian optimization algorithm for large multiobjective monitoring network design problems.  Advances in Water Resources 31(5), 828–845.
  * Kozak et al. (2007) Kozak, M., M. R. Verma, and A. Zielinski (2007).  Modern approach to optimum stratification: Review and perspectives.  Statistics in Transition-new series 8(2), 223–250.
  * Larrañaga and Lozano (2001) Larrañaga, P. and J. A. Lozano (2001).  Estimation of distribution algorithms: A new tool for evolutionary computation, Volume 2.  Springer Science & Business Media.
  * Lima et al. (2009) Lima, C. F., M. Pelikan, F. G. Lobo, and D. E. Goldberg (2009).  Loopy substructural local search for the bayesian optimization algorithm.  In International Workshop on Engineering Stochastic Local Search Algorithms, pp. 61–75. Springer.
  * Lima et al. (2011) Lima, C. F., F. G. Lobo, M. Pelikan, and D. E. Goldberg (2011).  Model accuracy in the bayesian optimization algorithm.  Soft Computing 15(7), 1351–1371.
  * Lin (1965) Lin, S. (1965).  Computer solutions of the traveling salesman problem.  Bell System Technical Journal 44(10), 2245–2269.
  * Lin and Kernighan (1973) Lin, S. and B. W. Kernighan (1973).  An effective heuristic algorithm for the traveling-salesman problem.  Operations research 21(2), 498–516.
  * Mühlenbein and Paaß (1996) Mühlenbein, H. and G. Paaß (1996).  From recombination of genes to the estimation of distributions i. binary parameters.  In International conference on parallel problem solving from nature, pp. 178–187. Springer.
  * Mühlenbein and Mahnig (1999) Mühlenbein, H. and T. Mahnig (1999).  Fda-a scalable evolutionary algorithm for the optimization of additively decomposed functions.  Evolutionary computation 7(4), 353–376.
  * Mühlenbein and Mahnig (2001) Mühlenbein, H. and T. Mahnig (2001).  Evolutionary algorithms: From recombination to search distributions.  In Theoretical Aspects of Evolutionary Computing, pp. 135–173. Springer.
  * Nelder and Mead (1965) Nelder, J. A. and R. Mead (1965).  A simplex method for function minimization.  The computer journal 7(4), 308–313.
  * O’Luing et al. (2019) O’Luing, M., S. Prestwich, and S. Armagan Tarim (2019).  A grouping genetic algorithm for joint stratification and sample allocation designs.  Survey Methodology 45(3), 513–531.
  * O’Luing et al. (2020) O’Luing, M., S. Prestwich, and S. A. Tarim (2020).  A simulated annealing algorithm for joint stratification and sample allocation designs.  arXiv preprint arXiv:2011.13006.
  * O’Luing et al. (2021) O’Luing, M., S. Prestwich, and S. A. Tarim (2021).  Combining k-means type algorithms with hill climbing for joint stratification and sample allocation designs.  arXiv preprint arXiv:2108.08038.
  * Paul and Iba (2002) Paul, T. K. and H. Iba (2002).  Linear and combinatorial optimizations by estimation of distribution algorithms.  In 9th MPS symposium on Evolutionary Computation, IPSJ, Japan, Volume 12.
  * Pearl (1988) Pearl, J. (1988).  Probabilistic reasoning in intelligent systems: networks of plausible inference.  San Mateo, CA: Morgan Kaufmann.
  * Pelikan et al. (1999) Pelikan, M., D. E. Goldberg, E. Cantú-Paz, et al. (1999).  Boa: The bayesian optimization algorithm.  In Proceedings of the genetic and evolutionary computation conference GECCO-99, Volume 1, pp. 525–532. Citeseer.
  * Pelikan et al. (2003) Pelikan, M., D. E. Goldberg, and S. Tsutsui (2003).  Hierarchical bayesian optimization algorithm: toward a new generation of evolutionary algorithms.  In SICE 2003 Annual Conference (IEEE Cat. No. 03TH8734), Volume 3, pp. 2738–2743. IEEE.
  * Petrovski et al. (2006) Petrovski, A., S. Shakya, and J. McCall (2006).  Optimising cancer chemotherapy using an estimation of distribution algorithm and genetic algorithms.  In Proceedings of the 8th annual conference on Genetic and evolutionary computation, pp. 413–418.
  * R Core Team (2021) R Core Team (2021).  R: A Language and Environment for Statistical Computing.  Vienna, Austria: R Foundation for Statistical Computing.
  * Robles et al. (2006) Robles, V., J. M. Peña, P. Larrañaga, M. S. Pérez, and V. Herves (2006).  Ga-eda: A new hybrid cooperative search evolutionary algorithm.  In Towards a New Evolutionary Computation, pp. 187–219. Springer.
  * Shah and Reed (2011) Shah, R. and P. Reed (2011).  Comparative analysis of multiobjective evolutionary algorithms for random and correlated instances of multiobjective d-dimensional knapsack problems.  European Journal of Operational Research 211(3), 466–479.
  * Sörensen and Glover (2013) Sörensen, K. and F. Glover (2013).  Metaheuristics.  Encyclopedia of operations research and management science 62, 960–970.
  * Tang and Lau (2005) Tang, M. and R. Lau (2005).  A hybrid estimation of distribution algorithm for the minimal switching graph problem.  In International Conference on Computational Intelligence for Modelling, Control and Automation and International Conference on Intelligent Agents, Web Technologies and Internet Commerce (CIMCA-IAWTIC’06), Volume 1, pp. 708–713.

##  Chapter 0 Appendix

###  1 Descriptions of target and auxiliary variables for the HEDA experiment
data sets

Table 1: Breakdown by data set of descriptions for target and auxiliary variables Data set | Variable | Description
---|---|---
SwissMunicipalities | Surfacebois | wood area.
SwissMunicipalities | Airbat | area with buildings.
SwissMunicipalities | POPTOT | total population
SwissMunicipalities | Hapoly | municipality area.
American Community Survey, 2015 | HINCP | Household income (past 12 months)
American Community Survey, 2015 | VALP | Property value
American Community Survey, 2015 | SMOCP | Selected monthly owner costs
American Community Survey, 2015 | INSP | Fire/hazard/flood insurance (yearly amount)
American Community Survey, 2015 | BLD | Units in structure
American Community Survey, 2015 | TEN | TEN
American Community Survey, 2015 | WKEXREL | Work experience of householder and spouse
American Community Survey, 2015 | WORKSTAT | Work status of householder or spouse in family households
American Community Survey, 2015 | HFL | House heating fuel
American Community Survey, 2015 | YBL | When structure first built
Kiva Loans | term_in_months | The duration for which the loan was disbursed in months
Kiva Loans | lender_count | The total number of lenders that contributed to this loan
Kiva Loans | loan_amount | The amount disbursed by the field agent to the borrower (USD)
Kiva Loans | sector | High level category, e.g. Food
Kiva Loans | currency | The currency in which the loan was disbursed
Kiva Loans | activity | More granular category, e.g. Fruits & Vegetables
Kiva Loans | region | Full region name within the country
Kiva Loans | partner_id | ID of partner organization

###  2 Fine-tuning the hyperparameters for the hybrid Estimation of
Distribution Algorithm - Atomic Strata

Table 1: Hyperparameters for the HEDA in the case of Atomic Strata Swiss
Municipalities
---
| Fine-tuning
---
iteration
No.
Iterations, I |  | SAA
---
Frequency
| Mutation
---
Chance
| Elitism
---
Rate
| Add
---
Strata
Factor
| Temperature,
---
T
| Decrement Constant,
---
DC
1 | 5,000 | 100 | 0.0004011 | 0.15 | 0.0000008 | 0.00000002 | 0.6933468
2 | 3,000 | 100 | 0.0009943 | 0.15 | 0.0000002 | 0.00000005 | 0.5736595
3 | 5,000 | 100 | 0.0002985 | 0.2 | 0.0000005 | 0.00000009 | 0.9229554
4 | 5,000 | 50 | 0.0004681 | 0.1 | 0.0000008 | 0.00000003 | 0.7242638
5 | 3,000 | 100 | 0.0001686 | 0.1 | 0.0000005 | 0.00000007 | 0.8150428
6 | 3,000 | 50 | 0.0000172 | 0.1 | 0.0000000 | 0.00000006 | 0.6266293
7 | 4,000 | 50 | 0.0006155 | 0.1 | 0.0000004 | 0.00000004 | 0.8724350
8 | 4,000 | 50 | 0.0005785 | 0.15 | 0.0000002 | 0.00000003 | 0.9842787
9 | 5,000 | 100 | 0.0008674 | 0.2 | 0.0000006 | 0.00000008 | 0.7707891
10 | 4,000 | 50 | 0.0007308 | 0.2 | 0.0000010 | 0.00000010 | 0.5456765
11 | 3,000 | 100 | 0.0007510 | 0.1 | 0.0000006 | 0.00000007 | 0.8459806
12 | 4,000 | 50 | 0.0007705 | 0.1 | 0.0000004 | 0.00000006 | 0.8436530
13 | 3,000 | 100 | 0.0001289 | 0.15 | 0.0000006 | 0.00000007 | 0.8117457
14 | 3,000 | 100 | 0.0001827 | 0.2 | 0.0000003 | 0.00000007 | 0.8184057
15 | 3,000 | 100 | 0.0001847 | 0.2 | 0.0000003 | 0.00000003 | 0.8292686
16 | 3,000 | 50 | 0.0001903 | 0.2 | 0.0000003 | 0.00000004 | 0.8295554
17 | 3,000 | 100 | 0.0001852 | 0.2 | 0.0000001 | 0.00000003 | 0.9414117
18 | 4,000 | 100 | 0.0001856 | 0.2 | 0.0000001 | 0.00000001 | 0.8659521
19 | 3,000 | 100 | 0.0001844 | 0.2 | 0.0000008 | 0.00000002 | 0.8288662
20 | 3,000 | 100 | 0.0001343 | 0.2 | 0.0000002 | 0.00000003 | 0.9526036
| Fine-tuning
---
iteration
No.
| Max
---
number
of sequences,
maxit
| Length
---
of
sequence,
J
| % of
---
L
for
maximum
q value,
Lmax%
| Probability
---
of
New
Stratum,
P(H + 1)
| Population
---
Size,
N_p
| Sample
---
Size
| Execution
---
Time
1 | 1 | 10,000 | 0.0801744 | 0.0007444 | 20 | 128.98 | 840.66
2 | 2 | 30,000 | 0.0546600 | 0.0096341 | 20 | 131.21 | 3,752.61
3 | 1 | 20,000 | 0.0458527 | 0.0073244 | 20 | 128.19 | 1,314.53
4 | 1 | 30,000 | 0.0287394 | 0.0048503 | 20 | 129.06 | 5,527.23
5 | 2 | 20,000 | 0.0120236 | 0.0060850 | 20 | 133.58 | 1,353.60
6 | 2 | 10,000 | 0.0670922 | 0.0037592 | 20 | 126.99 | 886.40
7 | 2 | 20,000 | 0.0821999 | 0.0028418 | 20 | 125.84 | 3,697.88
8 | 2 | 30,000 | 0.0625123 | 0.0057328 | 20 | 127.06 | 7,791.48
9 | 1 | 20,000 | 0.0946376 | 0.0082044 | 20 | 126.42 | 1,367.88
10 | 1 | 10,000 | 0.0233130 | 0.0018504 | 20 | 130.34 | 659.67
11 | 2 | 20,000 | 0.0954986 | 0.0064802 | 20 | 125.10 | 1,304.16
12 | 2 | 20,000 | 0.0135087 | 0.0033416 | 20 | 130.00 | 3,382.07
13 | 2 | 20,000 | 0.0880779 | 0.0050088 | 20 | 126.38 | 1,379.07
14 | 2 | 20,000 | 0.0958774 | 0.0076491 | 20 | 122.92 | 1,316.11
15 | 2 | 20,000 | 0.0101602 | 0.0088849 | 20 | 138.17 | 1,240.32
16 | 2 | 30,000 | 0.0988187 | 0.0085451 | 20 | 125.56 | 5,776.53
17 | 2 | 20,000 | 0.0990880 | 0.0091836 | 20 | 122.39 | 1,337.31
18 | 2 | 20,000 | 0.0105801 | 0.0090396 | 20 | 133.49 | 1,587.33
19 | 2 | 20,000 | 0.0992476 | 0.0093288 | 20 | 128.43 | 1,319.65
20 | 2 | 20,000 | 0.0102580 | 0.0082125 | 20 | 133.65 | 1,211.38
|  |  |  |  | Minimum | 122.39 |
|  |  |  |  |  | Total | 47,045.87
American Community Survey, 2015
| Fine-tuning
---
iteration
No.
Iterations, I |  | SAA
---
Frequency
| Mutation
---
Chance
| Elitism
---
Rate
| Add
---
Strata
Factor
| Temperature,
---
T
| Decrement Constant,
---
DC
1 | 300 | 10 | 0.0000000 | 0.4 | 0.0000001 | 0.00009222 | 0.6933468
2 | 200 | 10 | 0.0000001 | 0.4 | 0.0000000 | 0.00042573 | 0.5736595
3 | 300 | 10 | 0.0000000 | 0.5 | 0.0000000 | 0.00085991 | 0.9229554
4 | 300 | 5 | 0.0000000 | 0.3 | 0.0000001 | 0.00019888 | 0.7242638
5 | 200 | 10 | 0.0000000 | 0.3 | 0.0000001 | 0.00065586 | 0.8150428
6 | 200 | 5 | 0.0000000 | 0.3 | 0.0000000 | 0.00057615 | 0.6266293
7 | 200 | 5 | 0.0000001 | 0.3 | 0.0000000 | 0.00033515 | 0.8724350
8 | 300 | 5 | 0.0000001 | 0.4 | 0.0000000 | 0.00021361 | 0.9842787
9 | 300 | 10 | 0.0000001 | 0.5 | 0.0000001 | 0.00077701 | 0.7707891
10 | 200 | 5 | 0.0000001 | 0.5 | 0.0000001 | 0.00095672 | 0.5456765
11 | 200 | 10 | 0.0000000 | 0.3 | 0.0000001 | 0.00013141 | 0.8217492
12 | 300 | 10 | 0.0000000 | 0.5 | 0.0000001 | 0.00004408 | 0.7949279
13 | 300 | 10 | 0.0000001 | 0.3 | 0.0000001 | 0.00011081 | 0.7006825
14 | 300 | 10 | 0.0000000 | 0.4 | 0.0000001 | 0.00001201 | 0.8424332
15 | 300 | 10 | 0.0000000 | 0.5 | 0.0000001 | 0.00015274 | 0.8056020
16 | 300 | 10 | 0.0000001 | 0.3 | 0.0000001 | 0.00009295 | 0.6690758
17 | 200 | 10 | 0.0000000 | 0.4 | 0.0000001 | 0.00007020 | 0.7462928
18 | 300 | 10 | 0.0000000 | 0.3 | 0.0000001 | 0.00076447 | 0.8238593
19 | 300 | 10 | 0.0000001 | 0.5 | 0.0000001 | 0.00009108 | 0.6111786
20 | 200 | 10 | 0.0000001 | 0.4 | 0.0000001 | 0.00043680 | 0.7087167
| Fine-tuning
---
iteration
No.
| Max
---
number
of sequences,
maxit
| Length
---
of
sequence,
J
| % of
---
L
for
maximum
q value,
Lmax%
| Probability
---
of
New
Stratum,
P(H + 1)
| Population
---
Size,
N_p
| Sample
---
Size
| Execution
---
Time
1 | 10 | 2,500 | 0.0216957 | 0.0000001 | 20 | 8,849.13 | 8,542.77
2 | 20 | 5,000 | 0.0174433 | 0.0000010 | 20 | 8,829.25 | 28,978.64
3 | 10 | 2,500 | 0.0159755 | 0.0000007 | 20 | 8,834.01 | 6,984.81
4 | 10 | 5,000 | 0.0131232 | 0.0000005 | 20 | 8,805.62 | 36,489.00
5 | 20 | 5,000 | 0.0103373 | 0.0000006 | 20 | 8,800.53 | 28,857.52
6 | 20 | 2,500 | 0.0195154 | 0.0000004 | 20 | 8,824.74 | 20,805.10
7 | 20 | 2,500 | 0.0220333 | 0.0000003 | 20 | 8,816.72 | 20,756.65
8 | 20 | 5,000 | 0.0187521 | 0.0000006 | 20 | 8,811.21 | 89,838.25
9 | 10 | 5,000 | 0.0241063 | 0.0000008 | 20 | 8,838.34 | 17,576.73
10 | 10 | 2,500 | 0.0122188 | 0.0000002 | 20 | 8,809.30 | 9,145.87
11 | 20 | 5,000 | 0.0110847 | 0.0000001 | 20 | 8,801.18 | 28,832.86
12 | 20 | 5,000 | 0.0100309 | 0.0000001 | 20 | 8,810.14 | 44,465.19
13 | 20 | 5,000 | 0.0143632 | 0.0000001 | 20 | 8,807.34 | 44,395.63
14 | 10 | 2,500 | 0.0109556 | 0.0000001 | 20 | 8,822.30 | 7,088.03
15 | 20 | 5,000 | 0.0217767 | 0.0000000 | 20 | 8,819.96 | 44,605.16
16 | 10 | 5,000 | 0.0154209 | 0.0000006 | 20 | 8,824.89 | 17,641.07
17 | 20 | 5,000 | 0.0153991 | 0.0000007 | 20 | 8,815.61 | 28,870.49
18 | 10 | 5,000 | 0.0111377 | 0.0000007 | 20 | 8,811.88 | 17,556.67
19 | 20 | 5,000 | 0.0105166 | 0.0000000 | 20 | 8,804.58 | 44,660.20
20 | 10 | 2,500 | 0.0103235 | 0.0000004 | 20 | 8,850.46 | 4,585.94
|  |  |  |  | Minimum | 8,800.53 |
|  |  |  |  |  | Total | 550,676.58
Kiva Loans
| Fine-tuning
---
iteration
No.
Iterations, I |  | SAA
---
Frequency
| Mutation
---
Chance
| Elitism
---
Rate
| Add
---
Strata
Factor
| Temperature,
---
T
| Decrement Constant,
---
DC
1 | 600 | 300 | 0.0000396 | 0.2 | 0.0000008 | 0.00100396 | 0.6933468
2 | 400 | 300 | 0.0000994 | 0.3 | 0.0000002 | 0.00430903 | 0.5736595
3 | 600 | 300 | 0.0000292 | 0.3 | 0.0000005 | 0.00861177 | 0.9229554
4 | 600 | 100 | 0.0000463 | 0.2 | 0.0000008 | 0.00206098 | 0.7242638
5 | 400 | 300 | 0.0000161 | 0.2 | 0.0000005 | 0.00658958 | 0.8150428
6 | 400 | 200 | 0.0000008 | 0.2 | 0.0000000 | 0.00579972 | 0.6266293
7 | 500 | 100 | 0.0000612 | 0.2 | 0.0000003 | 0.00341138 | 0.8724350
8 | 500 | 100 | 0.0000575 | 0.3 | 0.0000002 | 0.00220699 | 0.9842787
9 | 600 | 200 | 0.0000866 | 0.3 | 0.0000006 | 0.00779018 | 0.7707891
10 | 500 | 200 | 0.0000728 | 0.3 | 0.0000010 | 0.00957111 | 0.5456765
11 | 600 | 100 | 0.0000388 | 0.3 | 0.0000007 | 0.00140096 | 0.9542183
12 | 600 | 100 | 0.0000058 | 0.3 | 0.0000007 | 0.00025835 | 0.9846227
13 | 600 | 100 | 0.0000402 | 0.3 | 0.0000008 | 0.00950009 | 0.9444742
14 | 600 | 300 | 0.0000919 | 0.3 | 0.0000005 | 0.00164402 | 0.9690933
15 | 600 | 100 | 0.0000229 | 0.2 | 0.0000010 | 0.00040293 | 0.6803285
16 | 600 | 300 | 0.0000342 | 0.3 | 0.0000009 | 0.00065333 | 0.9685014
17 | 600 | 100 | 0.0000345 | 0.3 | 0.0000008 | 0.00030204 | 0.9093287
18 | 500 | 100 | 0.0000228 | 0.3 | 0.0000004 | 0.00848591 | 0.9809824
19 | 600 | 100 | 0.0000375 | 0.3 | 0.0000009 | 0.00109957 | 0.6936422
20 | 600 | 100 | 0.0000281 | 0.3 | 0.0000009 | 0.00166877 | 0.6873736
| Fine-tuning
---
iteration
No.
| Max
---
number
of sequences,
maxit
| Length
---
of
sequence,
J
| % of
---
L
for
maximum
q value,
Lmax%
| Probability
---
of
New
Stratum,
P(H + 1)
| Population
---
Size,
N_p
| Sample
---
Size
| Execution
---
Time
1 | 1 | 5,000 | 0.0216957 | 0.0000075 | 20 | 6,536.39 | 7,325.52
2 | 3 | 10,000 | 0.0174433 | 0.0000963 | 20 | 6,338.61 | 6,190.59
3 | 2 | 5,000 | 0.0159755 | 0.0000733 | 20 | 6,559.13 | 3,720.53
4 | 1 | 10,000 | 0.0131232 | 0.0000486 | 20 | 6,285.78 | 2,837.05
5 | 3 | 10,000 | 0.0103373 | 0.0000609 | 20 | 6,374.74 | 1,422.56
6 | 3 | 5,000 | 0.0195154 | 0.0000377 | 20 | 6,441.66 | 1,111.02
7 | 2 | 5,000 | 0.0220333 | 0.0000285 | 20 | 6,321.22 | 1,768.59
8 | 3 | 10,000 | 0.0187521 | 0.0000574 | 20 | 6,265.44 | 3,174.16
9 | 2 | 10,000 | 0.0241063 | 0.0000821 | 20 | 6,349.25 | 2,045.19
10 | 1 | 5,000 | 0.0122188 | 0.0000186 | 20 | 6,447.99 | 1,280.92
11 | 2 | 10,000 | 0.0151998 | 0.0000524 | 20 | 6,246.74 | 3,292.97
12 | 2 | 5,000 | 0.0162442 | 0.0000388 | 20 | 6,287.11 | 2,154.07
13 | 2 | 5,000 | 0.0152621 | 0.0000566 | 20 | 6,439.26 | 2,109.17
14 | 2 | 5,000 | 0.0150536 | 0.0000973 | 20 | 6,466.34 | 1,400.07
15 | 1 | 10,000 | 0.0187736 | 0.0000071 | 20 | 6,250.33 | 2,703.06
16 | 2 | 10,000 | 0.0195352 | 0.0000050 | 20 | 6,365.74 | 1,649.00
17 | 1 | 5,000 | 0.0162050 | 0.0000009 | 20 | 6,313.38 | 1,888.96
18 | 1 | 10,000 | 0.0141372 | 0.0000678 | 20 | 6,428.67 | 2,138.39
19 | 1 | 10,000 | 0.0159892 | 0.0000338 | 20 | 6,250.00 | 2,677.30
20 | 2 | 5,000 | 0.0160194 | 0.0000343 | 20 | 6,274.33 | 2,117.25
|  |  |  |  | Minimum | 6,246.74 |
|  |  |  |  |  | Total | 53,006.37

###  3 Fine-tuning the hyperparameters for the hybrid Estimation of
Distribution Algorithm - Continuous Strata

Table 1: Hyperparameters for the HEDA in the case of Continuous Strata Swiss
Municipalities
---
| Fine-tuning
---
iteration
No.
Iterations, I |  | SAA
---
Frequency
| Mutation
---
Chance
| Elitism
---
Rate
| Add
---
Strata
Factor
| Temperature,
---
T
| Decrement Constant,
---
DC
1 | 3,000 | 200 | 0.0000396 | 0.2 | 0.00000082 | 0.0000010 | 0.6933468
2 | 1,000 | 200 | 0.0000994 | 0.3 | 0.00000023 | 0.0000043 | 0.5736595
3 | 3,000 | 200 | 0.0000292 | 0.3 | 0.00000049 | 0.0000086 | 0.9229554
4 | 3,000 | 100 | 0.0000463 | 0.2 | 0.00000076 | 0.0000021 | 0.7242638
5 | 1,000 | 200 | 0.0000161 | 0.2 | 0.00000054 | 0.0000066 | 0.8150428
6 | 1,000 | 100 | 0.0000008 | 0.2 | 0.00000003 | 0.0000058 | 0.6266293
7 | 2,000 | 100 | 0.0000612 | 0.2 | 0.00000035 | 0.0000034 | 0.8724350
8 | 2,000 | 100 | 0.0000575 | 0.3 | 0.00000020 | 0.0000022 | 0.9842787
9 | 3,000 | 200 | 0.0000866 | 0.3 | 0.00000063 | 0.0000078 | 0.7707891
10 | 2,000 | 100 | 0.0000728 | 0.3 | 0.00000098 | 0.0000096 | 0.5456765
11 | 2,000 | 100 | 0.0000041 | 0.3 | 0.00000006 | 0.0000098 | 0.6376087
12 | 3,000 | 200 | 0.0000018 | 0.3 | 0.00000002 | 0.0000082 | 0.5233369
13 | 3,000 | 100 | 0.0000002 | 0.3 | 0.00000004 | 0.0000069 | 0.8926658
14 | 1,000 | 100 | 0.0000011 | 0.2 | 0.00000003 | 0.0000076 | 0.8248724
15 | 2,000 | 200 | 0.0000008 | 0.3 | 0.00000002 | 0.0000013 | 0.6029297
16 | 1,000 | 100 | 0.0000007 | 0.2 | 0.00000003 | 0.0000056 | 0.5545023
17 | 1,000 | 200 | 0.0000002 | 0.3 | 0.00000003 | 0.0000088 | 0.6750674
18 | 1,000 | 100 | 0.0000008 | 0.2 | 0.00000040 | 0.0000008 | 0.5495252
19 | 1,000 | 100 | 0.0000677 | 0.2 | 0.00000002 | 0.0000057 | 0.5490809
20 | 1,000 | 200 | 0.0000008 | 0.2 | 0.00000008 | 0.0000085 | 0.6441513
| Fine-tuning
---
iteration
No.
| Max
---
number
of sequences,
maxit
| Length
---
of
sequence,
J
| % of
---
L
for
maximum
q value,
Lmax%
| Probability
---
of
New
Stratum,
P(H + 1)
| Population
---
Size,
N_p
| Sample
---
Size
| Execution
---
Time
1 | 5 | 3,000 | 0.0216957 | 0.0000075 | 20 | 107.80 | 458.67
2 | 10 | 5,000 | 0.0174433 | 0.0000963 | 20 | 107.94 | 218.91
3 | 5 | 4,000 | 0.0159755 | 0.0000733 | 20 | 108.06 | 364.22
4 | 5 | 5,000 | 0.0131232 | 0.0000486 | 20 | 107.91 | 629.75
5 | 10 | 4,000 | 0.0103373 | 0.0000609 | 20 | 107.82 | 161.03
6 | 10 | 3,000 | 0.0195154 | 0.0000377 | 20 | 104.93 | 207.11
7 | 10 | 4,000 | 0.0220333 | 0.0000285 | 20 | 107.74 | 571.95
8 | 10 | 5,000 | 0.0187521 | 0.0000574 | 20 | 107.48 | 728.80
9 | 5 | 4,000 | 0.0241063 | 0.0000821 | 20 | 108.03 | 359.16
10 | 5 | 3,000 | 0.0122188 | 0.0000186 | 20 | 108.32 | 296.15
11 | 5 | 3,000 | 0.0156453 | 0.0000395 | 20 | 107.76 | 296.91
12 | 5 | 4,000 | 0.0179254 | 0.0000770 | 20 | 107.89 | 371.97
13 | 10 | 3,000 | 0.0155686 | 0.0000116 | 20 | 106.97 | 674.13
14 | 5 | 3,000 | 0.0213493 | 0.0000442 | 20 | 106.65 | 139.98
15 | 10 | 3,000 | 0.0191401 | 0.0000816 | 20 | 107.40 | 280.55
16 | 10 | 4,000 | 0.0119913 | 0.0000363 | 20 | 107.00 | 277.91
17 | 10 | 5,000 | 0.0195217 | 0.0000438 | 20 | 106.90 | 201.23
18 | 10 | 3,000 | 0.0188604 | 0.0000191 | 20 | 107.65 | 213.88
19 | 5 | 4,000 | 0.0235152 | 0.0000413 | 20 | 107.03 | 174.75
20 | 10 | 4,000 | 0.0218042 | 0.0000257 | 20 | 105.95 | 165.34
|  |  |  |  | Minimum | 104.93 |
|  |  |  |  |  | Total | 6,792.40
American Community Survey, 2015
| Fine-tuning
---
iteration
No.
Iterations, I |  | SAA
---
Frequency
| Mutation
---
Chance
| Elitism
---
Rate
| Add
---
Strata
Factor
| Temperature,
---
T
| Decrement Constant,
---
DC
1 | 30 | 15 | 0.0000004 | 0.2 | 0.0000008 | 0.0000001 | 0.6933468
2 | 20 | 15 | 0.0000010 | 0.3 | 0.0000002 | 0.0000004 | 0.5736595
3 | 30 | 15 | 0.0000003 | 0.3 | 0.0000005 | 0.0000009 | 0.9229554
4 | 30 | 10 | 0.0000005 | 0.2 | 0.0000008 | 0.0000002 | 0.7242638
5 | 20 | 15 | 0.0000002 | 0.2 | 0.0000005 | 0.0000007 | 0.8150428
6 | 20 | 10 | 0.0000000 | 0.2 | 0.0000000 | 0.0000006 | 0.6266293
7 | 20 | 10 | 0.0000006 | 0.2 | 0.0000003 | 0.0000003 | 0.8724350
8 | 30 | 10 | 0.0000006 | 0.3 | 0.0000002 | 0.0000002 | 0.9842787
9 | 30 | 15 | 0.0000009 | 0.3 | 0.0000006 | 0.0000008 | 0.7707891
10 | 20 | 10 | 0.0000007 | 0.3 | 0.0000010 | 0.0000010 | 0.5456765
11 | 30 | 10 | 0.0000003 | 0.3 | 0.0000002 | 0.0000009 | 0.9659689
12 | 30 | 10 | 0.0000005 | 0.3 | 0.0000002 | 0.0000009 | 0.9542911
13 | 30 | 15 | 0.0000002 | 0.3 | 0.0000002 | 0.0000009 | 0.9813440
14 | 30 | 10 | 0.0000002 | 0.3 | 0.0000001 | 0.0000001 | 0.9533995
15 | 30 | 10 | 0.0000003 | 0.3 | 0.0000002 | 0.0000009 | 0.9863629
16 | 30 | 10 | 0.0000003 | 0.3 | 0.0000002 | 0.0000010 | 0.9702858
17 | 30 | 10 | 0.0000003 | 0.3 | 0.0000010 | 0.0000010 | 0.9849021
18 | 20 | 15 | 0.0000004 | 0.3 | 0.0000010 | 0.0000008 | 0.9729872
19 | 30 | 10 | 0.0000000 | 0.3 | 0.0000002 | 0.0000010 | 0.5353839
20 | 30 | 10 | 0.0000003 | 0.3 | 0.0000008 | 0.0000010 | 0.5662247
| Fine-tuning
---
iteration
No.
| Max
---
number
of sequences,
maxit
| Length
---
of
sequence,
J
| % of
---
L
for
maximum
q value,
Lmax%
| Probability
---
of
New
Stratum,
P(H + 1)
| Population
---
Size,
N_p
| Sample
---
Size
| Execution
---
Time
1 | 1 | 25,000 | 0.0216957 | 0.00000008 | 20 | 3,026.35 | 4,003.11
2 | 2 | 50,000 | 0.0174433 | 0.00000096 | 20 | 2,762.46 | 11,470.11
3 | 1 | 25,000 | 0.0159755 | 0.00000073 | 20 | 3,029.18 | 3,987.64
4 | 1 | 50,000 | 0.0131232 | 0.00000049 | 20 | 2,703.32 | 15,910.83
5 | 2 | 50,000 | 0.0103373 | 0.00000061 | 20 | 2,766.39 | 11,459.90
6 | 2 | 25,000 | 0.0195154 | 0.00000038 | 20 | 2,932.12 | 5,156.96
7 | 2 | 25,000 | 0.0220333 | 0.00000028 | 20 | 2,928.78 | 5,177.00
8 | 2 | 50,000 | 0.0187521 | 0.00000057 | 20 | 2,620.40 | 22,859.85
9 | 1 | 50,000 | 0.0241063 | 0.00000082 | 20 | 2,861.24 | 8,281.68
10 | 1 | 25,000 | 0.0122188 | 0.00000019 | 20 | 3,027.27 | 3,872.97
11 | 2 | 50,000 | 0.0157505 | 0.00000043 | 20 | 2,621.62 | 22,758.15
12 | 1 | 50,000 | 0.0165162 | 0.00000033 | 20 | 2,704.42 | 15,941.84
13 | 1 | 25,000 | 0.0155316 | 0.00000041 | 20 | 3,015.87 | 4,023.10
14 | 2 | 25,000 | 0.0145631 | 0.00000047 | 20 | 2,759.56 | 10,261.55
15 | 1 | 25,000 | 0.0177011 | 0.00000055 | 20 | 2,856.91 | 7,632.94
16 | 2 | 50,000 | 0.0158378 | 0.00000001 | 20 | 2,623.53 | 22,497.67
17 | 2 | 50,000 | 0.0113557 | 0.00000013 | 20 | 2,619.06 | 22,663.52
18 | 2 | 50,000 | 0.0166339 | 0.00000014 | 20 | 2,763.13 | 11,136.54
19 | 2 | 50,000 | 0.0126639 | 0.00000001 | 20 | 2,619.99 | 22,400.28
20 | 1 | 50,000 | 0.0121512 | 0.00000007 | 20 | 2,701.10 | 15,818.99
|  |  |  |  | Minimum | 2,619.06 |
|  |  |  |  |  | Total | 247,314.63
Kiva Loans
| Fine-tuning
---
iteration
No.
Iterations, I |  | SAA
---
Frequency
| Mutation
---
Chance
| Elitism
---
Rate
| Add
---
Strata
Factor
| Temperature,
---
T
| Decrement Constant,
---
DC
1 | 90 | 20 | 0.0000004 | 0.2 | 0.0000008 | 0.0000001 | 0.6933468
2 | 50 | 20 | 0.0000010 | 0.3 | 0.0000002 | 0.0000004 | 0.5736595
3 | 90 | 20 | 0.0000003 | 0.3 | 0.0000005 | 0.0000009 | 0.9229554
4 | 100 | 10 | 0.0000005 | 0.2 | 0.0000008 | 0.0000002 | 0.7242638
5 | 60 | 20 | 0.0000002 | 0.2 | 0.0000005 | 0.0000007 | 0.8150428
6 | 50 | 10 | 0.0000000 | 0.2 | 0.0000000 | 0.0000006 | 0.6266293
7 | 70 | 10 | 0.0000006 | 0.2 | 0.0000003 | 0.0000003 | 0.8724350
8 | 80 | 10 | 0.0000006 | 0.3 | 0.0000002 | 0.0000002 | 0.9842787
9 | 100 | 20 | 0.0000009 | 0.3 | 0.0000006 | 0.0000008 | 0.7707891
10 | 70 | 10 | 0.0000007 | 0.3 | 0.0000010 | 0.0000010 | 0.5456765
11 | 80 | 10 | 0.0000004 | 0.3 | 0.0000008 | 0.0000001 | 0.9727142
12 | 80 | 20 | 0.0000003 | 0.3 | 0.0000008 | 0.0000000 | 0.9796571
13 | 90 | 10 | 0.0000004 | 0.3 | 0.0000008 | 0.0000002 | 0.9820326
14 | 90 | 20 | 0.0000004 | 0.3 | 0.0000004 | 0.0000002 | 0.9887106
15 | 90 | 10 | 0.0000004 | 0.3 | 0.0000001 | 0.0000001 | 0.9844605
16 | 90 | 20 | 0.0000003 | 0.3 | 0.0000000 | 0.0000001 | 0.9838737
17 | 90 | 10 | 0.0000004 | 0.3 | 0.0000007 | 0.0000001 | 0.9778088
18 | 90 | 10 | 0.0000001 | 0.3 | 0.0000005 | 0.0000001 | 0.9318817
19 | 90 | 10 | 0.0000004 | 0.3 | 0.0000004 | 0.0000001 | 0.9233493
20 | 90 | 10 | 0.0000004 | 0.3 | 0.0000008 | 0.0000002 | 0.7065010
| Fine-tuning
---
iteration
No.
| Max
---
number
of sequences,
maxit
| Length
---
of
sequence,
J
| % of
---
L
for
maximum
q value,
Lmax%
| Probability
---
of
New
Stratum,
P(H + 1)
| Population
---
Size,
N_p
| Sample
---
Size
| Execution
---
Time
1 | 1 | 10,000 | 0.0216957 | 0.0000001 | 20 | 1,806.82 | 1,150.00
2 | 2 | 20,000 | 0.0174433 | 0.0000010 | 20 | 1,747.71 | 2,157.59
3 | 1 | 10,000 | 0.0159755 | 0.0000007 | 20 | 1,797.86 | 1,120.60
4 | 1 | 20,000 | 0.0131232 | 0.0000005 | 20 | 1,613.25 | 6,316.39
5 | 2 | 20,000 | 0.0103373 | 0.0000006 | 20 | 1,719.17 | 2,172.81
6 | 2 | 10,000 | 0.0195154 | 0.0000004 | 20 | 1,753.86 | 1,463.30
7 | 2 | 10,000 | 0.0220333 | 0.0000003 | 20 | 1,681.44 | 2,239.25
8 | 2 | 20,000 | 0.0187521 | 0.0000006 | 20 | 1,597.02 | 7,702.03
9 | 1 | 20,000 | 0.0241063 | 0.0000008 | 20 | 1,647.24 | 2,869.39
10 | 1 | 10,000 | 0.0122188 | 0.0000002 | 20 | 1,683.68 | 1,517.16
11 | 1 | 20,000 | 0.0183654 | 0.0000007 | 20 | 1,606.42 | 4,810.26
12 | 1 | 20,000 | 0.0187089 | 0.0000006 | 20 | 1,739.74 | 2,112.80
13 | 2 | 20,000 | 0.0137673 | 0.0000001 | 20 | 1,592.34 | 8,885.01
14 | 2 | 20,000 | 0.0138855 | 0.0000001 | 20 | 1,629.67 | 4,429.31
15 | 2 | 20,000 | 0.0156086 | 0.0000008 | 20 | 1,576.80 | 8,791.12
16 | 2 | 20,000 | 0.0152018 | 0.0000008 | 20 | 1,622.36 | 4,377.68
17 | 1 | 20,000 | 0.0197092 | 0.0000001 | 20 | 1,600.29 | 5,549.41
18 | 2 | 20,000 | 0.0156407 | 0.0000009 | 20 | 1,607.65 | 9,208.90
19 | 2 | 10,000 | 0.0166562 | 0.0000008 | 20 | 1,651.75 | 3,107.61
20 | 2 | 20,000 | 0.0150126 | 0.0000001 | 20 | 1,590.36 | 8,971.35
|  |  |  |  | Minimum | 1,576.80 |
|  |  |  |  |  | Total | 88,951.97