Shown here are results for GALE/NSGA-II/SPEA2 for a single run each on the CDA simulation for the WMC3 framework (i.e. WMC3CDA).
Note that each single run evaluates every member of every population for comparison purposes, but with GALE, not every evaluation is necessary for optimization. Thus, each algorithm takes ~ about 4 hours to do a single run.
The results below are for a single run of the algorithm. A more complete analysis would require ~ 10 runs at the very least, or 20 to be minimally satisfying to put up a solid statistical comparison.
Results:
Dot Plots: 1
http://i.imgur.com/jyfLyDH.png
Line Plots:
GALE is on top. Bottom plots have messed up plot marker-choices, so read carefully.
http://i.imgur.com/LxkL6eh.png
Comments:
Although GALE reaches some lows not seen by the other algorithms, GALE has much larger variance, which could theoretically be fixed by removing random jiggles.
Note that the adjustments in making GALE deterministic (removing all randoms) are not used in these results.
Whats Next:
Need more Decision Variables!
- Different landing routes
- Radar Tower parameters?
Prune some objectives away? Focus on time lost instead of number of delayed/interrupted tasks.
NASA furloughs - no access to their servers for now. Need to get stuff working on my machines.
Showing posts with label GALE. Show all posts
Showing posts with label GALE. Show all posts
Tuesday, October 1, 2013
Tuesday, September 24, 2013
Bounce at "1 minus (east-west)"?
WMC3 - CDA
Recap Problem Statement: We're trying to use GALE to make safety-critical decisions in short time. We're using the CDA model from WMC3, built by Georgia Tech scholars, to learn what organizational structures within the cockpit (in terms of how the pilots should handle their taskload) best optimize objectives such as minimizing time of delay/interruptions in getting these tasks completed. This is a cognitive science domain.
Buggy dataset: http://i.imgur.com/GCZFxie.png. Takes about 12-15 minutes to run 100 times.
Comparing to results (example: http://i.imgur.com/znv2xzv.png) from http://cci.drexel.edu/NextGenAA/pdf/jcedm-2013-Pritchett-measuring%20fa.pdf. This is our main reference paper for sanity checks on the model.
Few obvious correlations. Sanity check.
Task: Figure out the bugs. Then we can take off.
GALE
What I did:
Took away all non-determinism (random injections).
Only randomness that exists is with regeneration of individuals - but this isn't really non-deterministic (probability bin distributions).
Results: No change.
Self-reflection: we're mutating some distance, usually going too far. Then we try to come back towards it, and we go too far. Repeat, bouncing back and forth across where we want to go.
Problem: How far do we really want to bounce to get to exactly where we want to go?
Solution: Our projection axis is typically 1.0 units long. In the optimal ideal world, east = 1.0, and west = 0.0 (or vice versa). Thus absolute difference is 1.0 - 0.0 = 1.0. Taking 1 minus this, this tells us how far we need to bounce. "1 - (east - west)".
Observations: In early generations, this bounce distance is on the order of 0.30. In later generations, it's very close to 0.0. In addition, once we get close to 0.0, we STAY there.
Hypotheses: In problems that are hard to optimize, we don't get close to 0.0. Bounce distance tells us on its own how good we're doing.
New Results:
Some standard Models (Osyczka2, Vienett2, Schaffer): http://i.imgur.com/MUUC2pD.png
POM3 Models: http://i.imgur.com/aSK1gWj.png
GALE POM3B Decision Chart: http://i.imgur.com/zoL8ZiW.png
Observations: Less variance in the dots. Clearer image than before (active v6 link: http://unbox.org/things/var/joe/active/active-v6.pdf)
Recap Problem Statement: We're trying to use GALE to make safety-critical decisions in short time. We're using the CDA model from WMC3, built by Georgia Tech scholars, to learn what organizational structures within the cockpit (in terms of how the pilots should handle their taskload) best optimize objectives such as minimizing time of delay/interruptions in getting these tasks completed. This is a cognitive science domain.
Buggy dataset: http://i.imgur.com/GCZFxie.png. Takes about 12-15 minutes to run 100 times.
Comparing to results (example: http://i.imgur.com/znv2xzv.png) from http://cci.drexel.edu/NextGenAA/pdf/jcedm-2013-Pritchett-measuring%20fa.pdf. This is our main reference paper for sanity checks on the model.
Few obvious correlations. Sanity check.
Task: Figure out the bugs. Then we can take off.
GALE
What I did:
Took away all non-determinism (random injections).
Only randomness that exists is with regeneration of individuals - but this isn't really non-deterministic (probability bin distributions).
Results: No change.
Self-reflection: we're mutating some distance, usually going too far. Then we try to come back towards it, and we go too far. Repeat, bouncing back and forth across where we want to go.
Problem: How far do we really want to bounce to get to exactly where we want to go?
Solution: Our projection axis is typically 1.0 units long. In the optimal ideal world, east = 1.0, and west = 0.0 (or vice versa). Thus absolute difference is 1.0 - 0.0 = 1.0. Taking 1 minus this, this tells us how far we need to bounce. "1 - (east - west)".
Observations: In early generations, this bounce distance is on the order of 0.30. In later generations, it's very close to 0.0. In addition, once we get close to 0.0, we STAY there.
Hypotheses: In problems that are hard to optimize, we don't get close to 0.0. Bounce distance tells us on its own how good we're doing.
New Results:
Some standard Models (Osyczka2, Vienett2, Schaffer): http://i.imgur.com/MUUC2pD.png
POM3 Models: http://i.imgur.com/aSK1gWj.png
GALE POM3B Decision Chart: http://i.imgur.com/zoL8ZiW.png
Observations: Less variance in the dots. Clearer image than before (active v6 link: http://unbox.org/things/var/joe/active/active-v6.pdf)
Wednesday, August 21, 2013
A Summer in Rear-view - Joe
NASA Ames Report:
In progress of developing a framework for NextGen aviation technology studies. This framework will investigate the integration of highly-necessary NextGen technology into current aviation policies.
Poster: https://www.dropbox.com/s/rghtyrqvgftqowk/nasa_poster_joe.pdf
Abstract: https://www.dropbox.com/s/71agln6id5h6otw/nasa_poster_abstract_joe.pdf
modeling for optimization:
Objectives:
[min] false alarm rate
[min] distance travelled
[max] granularity
[min] look-ahead time
[min] safe spacing distance
[min] crashes
[min] conflicts
Decisions:
num planes
homogeneous airspace {true, false} / num types of planes
num runways
percentage RNP
granularity
look-ahead time
safe spacing distance
[psych] scenario level {SC1, SC2, SC3, SC4, SC5}
[psych] function allocation {FA1, FA2, FA3, FA4, FA5}
[psych] cognitive control model {OPP, STR, TAC}
California Trip:
In addition to visiting NASA Ames campus, I've visited several other sites as well:
- Stanford
- Vegas
- Los Angeles
- San Francisco
- Golden Gate Bridge
- Napa Valley Area
GALE Paper Preview:
http://unbox.org/things/var/joe/active/active-v5.pdf
[culture] [crit] [crit mod] [init kn] [inter-D] [dyna] [size] [plan] [team size]
"New" Decision Bin Charts GALE vs NSGA-II:
POM3A&B: http://i.imgur.com/0CjGLwt.png
POM3C&D: http://i.imgur.com/sCmBrim.png
Sans Completion:
http://i.imgur.com/KrvGfA5.png {(just look at the stuff on the left)}
Looking Ahead:
Before end of 2013:
- Finish NASA Aviation Project
- "Upgrade" GALE into GALE2. That means identify current quirks with GALE1 and clean them out to enhance performance.
- Integrate NASA project into GALE2 for testing.
Spring 2014:
- Finish Ph.D.
Tuesday, June 25, 2013
Joe: Presenting GALE
Hello, my name is Joe Krall, phd student here at WVU. I'm currently away, near San Jose, California, on internship with the NASA Ames Research Center. My work there entails software research with intelligent systems design focusing on air traffic management (specifically, about avoiding airspace collisions between aircraft.)
My Ph.D. work here at WVU has largely been centered around gaming and procedural content generation for the aim and purpose of keeping players in the game (and providing fresher content to keep them around longer.) Procedural Content Generation can be the process of parameter tuning to some generative content algorithm. Thus, we lead into the problem of optimizing "fun" by tuning these parameters.
It is not timely or efficient to poll thousands of players about their experience while playing a game which utilizes some procedurally generated content. Players are often biased, or lie, or just don't care in their responses to surveys. It is often difficult to substantiate a lot of respondents. It has become a major necessity to be able to optimize in very few evaluations (< 50), as opposed to thousands.
For this purpose, I've worked and developed what I call GALE. It is capable of being used for my intents of exploring the optimization of procedural content generation algorithms, and in general, we can optimize things in less than 20 evaluations.
GALE is a powerful tool for evolutionary algorithms that optimize the solutions to problems. As a template, we consider problems to be simulations that have input parameters called Decisions, and output scores called Objectives. Whereas traditional evolutionary algorithms may require the use of the simulation thousands of times before it learns the best decisions to optimize the objectives, GALE requires a mere fraction of these number of simulation objective evaluations.
Our principle focus is to optimize POM3, a revised simulation of the requirements engineering process. POM3 can be split into POM3A,B,C,D, where each subset problem represents different kinds of software projects (for instance, POM3A represents all projects while POM3B represents small but safety-critical projects.)
GALE stands for Geometric Active Learning Evolution. It is based on techniques that use Response Surface Approximation methods to estimate objective score rather than evaluate them, without the use of a simulation that can be costly and timely to run. GALE makes the use of a Response Surface technique called RRSL (Rapid Recursive Spectral Learning), which recursively clusters in a tree-like manner, a population of unevaluated individuals by projecting them all onto a 1-dimensional line, and then discarding any dominated clusters (by choosing east and west representatives of each cluster, and using those to evaluate via the simulation.) The remaining non-dominated individuals of leaf clusters are mutated closer to "heaven" by examining each decision of each individual, and making the best choice of how to mutate it so that the individual is more optimized.
Illustration of GALE:
Plotting objective scores during evolution (50 runs). Each plot marker indicates the mean objective score for that generation (not necessarily the final generation of the algorithm - so we can get a clear picture of how objective scores evolve.) Vertical axes represent percentage of change for the better from initial, and horizontal axes are the number of evaluations. Shown here is a plot for ZDT1, one of our 11 evaluated problems.
Next: Frequency of decisions as chosen by GALE (top) are much more precise than NSGAII (bottom). GALE has the power to make very concretely defined decisions.
My Ph.D. work here at WVU has largely been centered around gaming and procedural content generation for the aim and purpose of keeping players in the game (and providing fresher content to keep them around longer.) Procedural Content Generation can be the process of parameter tuning to some generative content algorithm. Thus, we lead into the problem of optimizing "fun" by tuning these parameters.
It is not timely or efficient to poll thousands of players about their experience while playing a game which utilizes some procedurally generated content. Players are often biased, or lie, or just don't care in their responses to surveys. It is often difficult to substantiate a lot of respondents. It has become a major necessity to be able to optimize in very few evaluations (< 50), as opposed to thousands.
For this purpose, I've worked and developed what I call GALE. It is capable of being used for my intents of exploring the optimization of procedural content generation algorithms, and in general, we can optimize things in less than 20 evaluations.
Overview:
GALE is a powerful tool for evolutionary algorithms that optimize the solutions to problems. As a template, we consider problems to be simulations that have input parameters called Decisions, and output scores called Objectives. Whereas traditional evolutionary algorithms may require the use of the simulation thousands of times before it learns the best decisions to optimize the objectives, GALE requires a mere fraction of these number of simulation objective evaluations.
Our principle focus is to optimize POM3, a revised simulation of the requirements engineering process. POM3 can be split into POM3A,B,C,D, where each subset problem represents different kinds of software projects (for instance, POM3A represents all projects while POM3B represents small but safety-critical projects.)
Background:
GALE stands for Geometric Active Learning Evolution. It is based on techniques that use Response Surface Approximation methods to estimate objective score rather than evaluate them, without the use of a simulation that can be costly and timely to run. GALE makes the use of a Response Surface technique called RRSL (Rapid Recursive Spectral Learning), which recursively clusters in a tree-like manner, a population of unevaluated individuals by projecting them all onto a 1-dimensional line, and then discarding any dominated clusters (by choosing east and west representatives of each cluster, and using those to evaluate via the simulation.) The remaining non-dominated individuals of leaf clusters are mutated closer to "heaven" by examining each decision of each individual, and making the best choice of how to mutate it so that the individual is more optimized.
Illustration of GALE:
Results:
Average speedups for each algorithm and problem are show below. (We average about 80x fewer than state of the art.) Note: This is a slightly outdated result, due to some minor revising in the GALE algorithm. RHO indicates how long the algorithm had to run before it converged on optimization. The higher the RHO, the fewer the generations needed for convergence. Since GALE typically has a higher RHO, it has fewer generations and also fewer evaluations. (Also Note: IBD is our measure of quality on how good the optimization was - the lower the IBD, the better.)
Next: Frequency of decisions as chosen by GALE (top) are much more precise than NSGAII (bottom). GALE has the power to make very concretely defined decisions.
Wednesday, March 6, 2013
SBSE MOO in Few Evals: GALE
GALE = Geometric Active Learning Evolution
Hypervolume versus IBD and IBS
- IBD = how good we are
- IBS = how spread out we are
- Both based on IBEA indicator
- RRSL should be GALE, here
Analysis Notes:
- RRSL wins badly on NumEval
- NSGA-II outperforms RRSL in runtime for small MOPs that are cheap to evaluate. But when models become expensive (i.e. POM2), NSGA-II becomes slow and RRSL wins in runtime
- RRSL is a very decision-sided routine. For ZDT1 (30 decisions) and osyzcka2( 5 decisions ), the runtime of RRSL is punished
Paper "3/4 Draft":
- nothing in here, yet: http://unbox.org/things/var/joe/active/
- promise to be integrated in linux/latex fully by full draft time
- https://www.dropbox.com/s/y9ey0hr6agsolzt/solving_problems_in_few_evaluations.pdf?m
Hypervolume versus IBD and IBS
- IBD = how good we are
- IBS = how spread out we are
- Both based on IBEA indicator
More Results:
- added some more flavors just so we have one of every cookie
Notes:
- Left table shows the Raw Averages for everyone over 20 repeats
- Right table uses t-statistic to generate confidence interval (99%)
- 7-3-2 on wins-losses-ties when only considering IBD (quality)
- WIN or LOSS = no overlap of confidence interval- RRSL should be GALE, here
Analysis Notes:
- RRSL wins badly on NumEval
- NSGA-II outperforms RRSL in runtime for small MOPs that are cheap to evaluate. But when models become expensive (i.e. POM2), NSGA-II becomes slow and RRSL wins in runtime
- RRSL is a very decision-sided routine. For ZDT1 (30 decisions) and osyzcka2( 5 decisions ), the runtime of RRSL is punished
Paper "3/4 Draft":
- nothing in here, yet: http://unbox.org/things/var/joe/active/
- promise to be integrated in linux/latex fully by full draft time
- https://www.dropbox.com/s/y9ey0hr6agsolzt/solving_problems_in_few_evaluations.pdf?m
Subscribe to:
Posts (Atom)