Objective GA Background Sensitivity Analysis Cloud Model Acknowledgements

Determining Important Control Parameters of a

Genetic Algorithm

Andrea Haines

NIST

Information Technology Laboratory

Advisors: Kevin Mills & Jim Filliben

7 August 2012

Andrea Haines NIST

Determining Important Control Parameters of a Genetic Algorithm
Objective GA Background Sensitivity Analysis Cloud Model Acknowledgements

Outline

Objective

Genetic Algorithm Background

Part 1: Sensitivity Analysis

Problem Set

Experiment Design

Results

Part 2: Exploring a Cloud Simulation’s State Space for Failure

Scenarios

Acknowledgements

Andrea Haines NIST

Determining Important Control Parameters of a Genetic Algorithm
Objective GA Background Sensitivity Analysis Cloud Model Acknowledgements

Objective

The Big Picture

To use a classic Genetic Algorithm to search the large state space

(6132) of Koala, a cloud simulation, for settings that drive the

model into behavioral directions that indicate system failure and/or

degraded operations

How?

A classic Genetic Algorithm was developed by Kevin Mills,

using SLX (Extensible Simulation Language)

Lacking prior definitive studies, we needed to determine the

most important and best settings to use for 7 of the GA’s

control parameters

Conducted a sensitivity analysis on the results of the GA on

60 optimization problems

Andrea Haines NIST

Determining Important Control Parameters of a Genetic Algorithm
Objective GA Background Sensitivity Analysis Cloud Model Acknowledgements

What is a Genetic Algorithm?

GA Flowchart

P = # of individuals in population

t = generation #

P(t) = population of individuals

for generation t

t = 0

initialize P(t)

evaluate P(t)

while (not termination condition)

begin

t = t + 1

select P(t) from P(t − 1)

alter P(t)

evaluate P(t)

end

Andrea Haines NIST

Determining Important Control Parameters of a Genetic Algorithm
Objective GA Background Sensitivity Analysis Cloud Model Acknowledgements

Why Genetic Algorithms?

Classes of Search Techniques Advantages of Genetic Algorithms

Can search a large space

Can work well when the search

space is multimodal

Can provide a “good” solution

Can be useful for complex or

loosely defined problems

Andrea Haines NIST

Determining Important Control Parameters of a Genetic Algorithm
Objective GA Background Sensitivity Analysis Cloud Model Acknowledgements

Part 1: Sensitivity Analysis

Andrea Haines NIST

Determining Important Control Parameters of a Genetic Algorithm
Objective GA Background Sensitivity Analysis Cloud Model Acknowledgements

7 Factors (Parameters) –4 levels (Settings)

Andrea Haines NIST

Determining Important Control Parameters of a Genetic Algorithm
Objective GA Background Sensitivity Analysis Cloud Model Acknowledgements

Partial Problem List

60 numerical optimization problems from literature

The study started with 14 completed problems:

1 AxisParallelHyperEllisoid

(D = 15)

2 AxisParallelHyperEllisoid

(D = 30)

3 ChemicalReactor (D = 5)

4 ChemicalYield (D = 2)

5 DefectiveSprings (D = 3)

6 Morris (D = 10)

7 Morris (D = 20)

8 QuarticWithNoNoise

(D = 100)

9 QuarticWithNormalNoise

(D = 100)

10 QuarticWithUniformNoise

(D = 100)

11 SchafferF6 (D = 2)

12 ShekelM5 (D = 4)

13 ShekelM7 (D = 4)

14 ShekelM10 (D = 4)

Andrea Haines NIST

Determining Important Control Parameters of a Genetic Algorithm
Objective GA Background Sensitivity Analysis Cloud Model Acknowledgements

Problem Example

6-Hump Camel Function (D = 2)

f (n, x) = 4x

2

1 − 2.1x

4

1 +

1

3

x

6

1 + x1x2 − 4x

2

2 + 4x

4

2

Andrea Haines NIST

Determining Important Control Parameters of a Genetic Algorithm
Objective GA Background Sensitivity Analysis Cloud Model Acknowledgements

5D Animation – Defective Springs Problem (D = 3)

A Genetic Algorithm searching

for an optimal combination of

oven temperature, quench

temperature and carbon

concentration in a production

process, where fitness is

measured as the percentage of

non-defective springs produced

Visualization by Sandy Ressler (NIST Math Division)

Andrea Haines NIST

Determining Important Control Parameters of a Genetic Algorithm
Objective GA Background Sensitivity Analysis Cloud Model Acknowledgements

Experiment Design (l = 4, k = 7, n = 1024)

4

7−2 Orthogonal Fractional Factorial (OFF) Design

Each parameter setting level is used 1024/4 = 256 times

60 × 1024 = 61440 runs, instead of 60 × 16384 = 983040

Example:

2-level OFF

Design

2

7−4

Benefits of OFF Design:

Superior coverage & robustness when compared with

1-Factor-at-a-Time

Minimizes variation in effect estimates

Andrea Haines NIST

Determining Important Control Parameters of a Genetic Algorithm
Objective GA Background Sensitivity Analysis Cloud Model Acknowledgements

Andrea Haines NIST

Determining Important Control Parameters of a Genetic Algorithm
Objective GA Background Sensitivity Analysis Cloud Model Acknowledgements

Andrea Haines NIST

Determining Important Control Parameters of a Genetic Algorithm
Objective GA Background Sensitivity Analysis Cloud Model Acknowledgements

Andrea Haines NIST

Determining Important Control Parameters of a Genetic Algorithm
Objective GA Background Sensitivity Analysis Cloud Model Acknowledgements

Data Summary

Robustness

*Percentages summed for the levels (1-4) sometimes exceeds 100

because there was no significant difference between the means

Andrea Haines NIST

Determining Important Control Parameters of a Genetic Algorithm
Objective GA Background Sensitivity Analysis Cloud Model Acknowledgements

Conclusions

a. When the selection threshold (pressure) is too low, tournament

selection has an inferior performance

b. Rebooting the population too frequently (after 0.1 or 0.2 of the

generations) is not as good as not rebooting at all

c. Reducing the precision of the parameters can give good answers, likely

by reducing the size of the search space

Andrea Haines NIST

Determining Important Control Parameters of a Genetic Algorithm
Objective GA Background Sensitivity Analysis Cloud Model Acknowledgements

Part 2: Exploring the Koala State Space for

Failure Scenarios

The Big Picture (In Progress)

To use the optimized classic Genetic Algorithm to search the large

state space (6132) of Koala, a cloud simulation, for settings that

drive the model into behavioral directions that indicate system

failure and/or degraded operations

Andrea Haines NIST

Determining Important Control Parameters of a Genetic Algorithm
Objective GA Background Sensitivity Analysis Cloud Model Acknowledgements

Genetic Algorithms and the Cloud Model

How Genetic Algorithms Might Help

Anti-Fitness =

# of users who cannot be served

# total users

Andrea Haines NIST

Determining Important Control Parameters of a Genetic Algorithm
Objective GA Background Sensitivity Analysis Cloud Model Acknowledgements

Koala – Cloud Model

Koala attempts to allocate virtual machines that are requested by

users onto physical nodes provided by a cloud

Schematic of Koala IaaS Cloud Computing Model

Chris Dabrowski & Kevin Mills (Networking Division)

creators of Koala

Summary of Koala

Parameters

Andrea Haines NIST

Determining Important Control Parameters of a Genetic Algorithm
Objective GA Background Sensitivity Analysis Cloud Model Acknowledgements

GA-generated Koala Parameters (6132)

Sample Koala Chromosome Map

Andrea Haines NIST

Determining Important Control Parameters of a Genetic Algorithm
Objective GA Background Sensitivity Analysis Cloud Model Acknowledgements

Summary of the Summer

1 Part 1: Sensitivity Analysis

Implemented and tested 46 optimization problems

Analyzed data from all 60 problems

Determined the ranking for the 7 GA parameters and their

best settings

2 Part 2: Koala Cloud Model

Compiled list of 132 parameters and specified ranges and

precisions

Reflected changes into GA controller and generated a

chromosome map

Wrote code to convert chromosome map into Koala

parameters

Andrea Haines NIST

Determining Important Control Parameters of a Genetic Algorithm
Objective GA Background Sensitivity Analysis Cloud Model Acknowledgements

Acknowledgements

Kevin Mills

Jim Filliben

The SURF program and the SURF directors

Andrea Haines NIST

Determining Important Control Parameters of a Genetic Algorithm
Objective GA Background Sensitivity Analysis Cloud Model Acknowledgements

Questions?

Andrea Haines NIST

Determining Important Control Parameters of a Genetic Algorithm
Objective GA Background Sensitivity Analysis Cloud Model Acknowledgements

Other Problems

15 Ackley

(D = 10)

16 Beale (D = 2)

17 Bohachevsky

(D = 2)

18 Branin (D = 2)

19 Camel 3-hump

(D = 2)

20 Camel 6-hump

(D = 2)

21 Colville (D = 4)

22 Corana (D = 4)

23 Dekkers and

Aarts (D = 2)

24 Easom (D = 2)

25 Gear (D = 4)

26 Goldstein-Price

(D = 2)

27 Griewank

(D = 2)

28 Griewank

(D = 10)

29 Hartman

(D = 3)

30 Hartman

(D = 6)

31 Hosaki (D = 2)

32 Kowalik

(D = 4)

Andrea Haines NIST

Determining Important Control Parameters of a Genetic Algorithm
Objective GA Background Sensitivity Analysis Cloud Model Acknowledgements

Other Problems

33 Levy (D = 15)

34 Levy (D = 30)

35 Levy (D = 60)

36 McCormick

(D = 2)

37 Michalewitz

(D = 15)

38 Michalewitz

(D = 30)

39 Michalewitz

(D = 60)

40 Multimod

(D = 30)

41 Neumaier3

(D = 10)

42 Paviani

(D = 10)

43 Perm (D = 10)

44 Periodic

(D = 2)

45 Plateau

(D = 5)

46 Powell (D = 4)

47 Rosenbrock

(D = 15)

48 Salomon

(D = 10)

49 Schwefel3

(D = 3)

50 Shubert

(D = 2)

Andrea Haines NIST

Determining Important Control Parameters of a Genetic Algorithm
Objective GA Background Sensitivity Analysis Cloud Model Acknowledgements

Other Problems

51 Sinusoidal

(D = 10)

52 SphereModel

(D = 15)

53 SphereModel

(D = 60)

54 Step (D = 15)

55 Step (D = 30)

56 Step (D = 60)

57 Watson

(D = 6)

58 Zakharov

(D = 15)

59 Zettl (D = 2)

Andrea Haines NIST

Determining Important Control Parameters of a Genetic Algorithm