Algorithm Parameters代做、代写R、R编程语言调试、代做Computer Sciences

日期：2019-07-11 08:34

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. ~ft ← f(Xt)

4. While (t < niter)

1. Vt ← mutation(Xt, mutpars)

2. Ut ← recombination(Xt, Vt, recpars)

3. ~jt ← f(Ut)

4. (Xt+1,

~ft+1) ← selection(Xt, Ut,

~ft, ~jt)

5. t ← t + 1

5. Output: (Xt,

~ft)

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:

install.packages("ExpDE") # from the internet

library(ExpDE) # loads the package

The fixed parameters for the algorithm (along the entire experiment) are given by:

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))

The recombination operators that should be compared are given by:

## 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:

out <- ExpDE(popsizeX, mutparsX, recparsX, selpars, stopcrit, probpars)

out$Fbest

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

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