Case Study 02 – Analysis of Algorithm Parameters
Experiment Design for Computer Sciences
Introduction
Many algorithms in computer science have parameters that influence their behavior. The effect of these parameters on the algorithms can be estimated using the experiment design and analysis techniques studied in this course.
In this final case study, you are tasked to perform an experiment to find the effect of changing the parameters of an actual algorithm (Differential Evolution – implemented using the ExpDE R package). You must submit a report where you perform all the steps of the experiment: initial analysis, experiment design, data collection, analysis and conclusion.
Background
Population-based meta-heuristic algorithms are a common alternative for solving engineering optimization problems. Such algorithms are usually composed of an interactive cycle in which a set of candidate solutions to the optimization problems are repeteadly evaluated, modified and selected. The result is that the solution space of the problem is sampled and an optimal solution (maximum or minimum) is found for the given objective function.
Among population-based meta-heuristics, a popular one is known as differential evolution (DE). Put simply, this method is composed by the following steps:
0. Input: N, niter, recpars, mutpars
1. t ← 0
2. Xt ← {⃗x1, ⃗x2, . . . , ⃗xN } (initial population)
3. f⃗ ← f(X ) tt
4. While (t < niter)
1. Vt ← mutation(Xt, mutpars)
2. Ut ← recombination(Xt, Vt, recpars)
3. ⃗jt ← f(Ut)
4. (X , f⃗ )←selection(X, U, f⃗,⃗j)
t+1 t+1 5. t←t+1
t t t t
5. Output: (X , f⃗ ) tt
Suppose that a researcher is interested in investigating the effect of using different recombination operators (step 4.2 above) on the performance of DE for a certain class of problems. To reach this objective, the researcher implements the algorithm and each operator in a standard fashion, using the ExpDE package.
The development version is available on available no Github.
Experimental Task
Given a small number of recombination operators for the DE algorithm, and a single test problem, your goal in this study is to answer the following question:
Is there a difference in the mean performance of the algorithm when using these different recombination operators, for the given test problem? In case there is, which is the best operator in terms of average performance (the lower the value returned, the better), and what is the magnitude of the differences found? Is there an operator that should be recommended in comparison to the others?
1
The following experimental parameters are given for this study:
• Minimal difference of practical significance between any pair of algorithm (padronized as Cohen’s d coefficient): (d∗ = δ∗/σ) = 0.25
• Desired significance: α = 0.05
• Minimum power desired (for the case d = d∗): π = 1−β = 0.85
Technical Information about the ExpDE package:
To install and load the package in your computer, you can sue the following command:
The fixed parameters for the algorithm (along the entire experiment) are given by:
The recombination operators that should be compared are given by:
install.packages("ExpDE") # from the internet library(ExpDE) # loads the package
selpars <- list(name = "selection_standard")
stopcrit <- list(names = "stop_maxeval", maxevals = 60000, maxiter = 1000)
probpars <- list(name = "sphere", xmin = -seq(1,20), xmax = 20 + 5 * seq(5, 24))
## Operator 1 -- Arithmetic recombination
recpars1 <- list(name = "recombination_arith") mutpars1 <- list(name = "mutation_rand", f = 4) popsize1 <- 300
## Operator 2 -- Binomial recombination
recpars2 <- list(name = "recombination_bin", cr = 0.7) mutpars2 <- list(name = "mutation_best", f = 3) popsize2 <- 300
## Operator 3 -- BLX-alpha recombination
recpars3 <- list(name = "recombination_blxAlphaBeta", alpha = 0.4, beta = 0.4) mutpars3 <- list(name = "mutation_rand", f = 4)
popsize3 <- 230
## Operator 4 -- Eigenvector-based binomial recombination
recpars4 <- list(name = "recombination_eigen", othername = "recombination_bin", cr = 0.9) mutpars4 <- list(name = "mutation_best", f = 2.8)
popsize4 <- 85
To obtain one observation of the performance of the algorithm with a given operator, use the following commands:
where popsizeX, mutparsX a recparsX must be replaced by the appropriate variables. Report Format
Submit a report describing the experiment conducted for this case study. The experiment must include the following steps:
1. Formulation of the experimental hypothesis;
2
out <- ExpDE(popsizeX, mutparsX, recparsX, selpars, stopcrit, probpars) out$Fbest
2. Calculation of the Sample Size;
3. Collection of the experiment data;
4. Statistical Analysis and Hypothesis testing;
5. Estimation of the effect size and the confidence intervals;
6. Verification of the test assumptions;
7. Conclusions of the experiment;
8. Discussions of possible limitations of the experiment, and suggestion for improvement.
Do not forget to include code and raw data along when submitting your report.
3