14 August 2013
Lee, Tom, Kyle, Jake, Dave (scribe) , Dan
Some progress in Brevis. Moving along, but some trouble with scroll bars. A little faster, but looks about the same.
Lee noticed that it was stalling for a long time during genetic operators. Lots of lists used. Tom pushed an updated version that’s about 2X as fast.
Lexicase Elite Group Selection
- IF any two cases have same elites, they are part of the same elite group.
- Didn’t really work better, but pushed to master.
- Tried removing any groups that pick out a subset of another elite group.
- Sometimes getting 0 elite groups- might be a bug (fixed after meeting)
By Daniel Now at http://sites.hampshire.edu/ci-lab/ Wordpress page – possible to edit, rewind, etc. To replace wiki
Mult. Weight Updates Paper
- they made a lot of assumptions (infinite pop, random mating, etc.)
- in finite pop you lose and gain haplotypes over time- not a good assumption
- No geography
- Mixability is interesting idea, though – the evolve solutions robust to evolutionary operators
- What is the relationship between GP and MWU?
- What about ULTRA without mutation? without crossover?
- Can we try payoff matrix? (Kyle already tried something similar)
Les Valiant’s problem – 100 variables, 50 are relevant – are sum of bits for 50 even or odd? (Original 1000, 500) Big Question: Are you allowed to choose the test cases? May be trivial if you are allowed to choose, but paper does not specify selection method
(Calc problem: A fitness case is a sequence of button presses, output is what is displayed on screen: number or error). Each button tags some code. Tried lexicase selection and improvements some ideas:
- more tagging instructions
- don’t re-tag: later tag changes become a no-op
- binary branching for bushier trees
- re-think tests cases (separate error-flag from numerical; char based, not numerical error)
- Binary fitness?? (Wrong or right in each case — is it too little information)
Anyone who has any ideas is welcome to try them
Next meeting: 8/26 or 8/27 (28-30 not viable)
Read Dave’s Paper Brevis demo (Daniel): Bring site up to date and make it the new site redirect from Hampedia (Kyle): Ask Valiant if we understand description correctly
Read paper of Dave’s
Read multiplicitive updates in coordination games
50,000 lines of code paper to send to adam
Conjunctively optimal lexicase/ Pareto maximal:
to select parents, group together identical fitness/error vectors,
only retain that can be reached by some order of lexical
then pick randomly from pool, if pool has multiple, pick random from within
do for each parent picking
make smaller squares on floor/ soft floor texture
Next Lab meeting 1:30 Aug 14
Present: Lee, Tom (scribe), Kyle, Jake, Kwaku (hangouts)
Next lab meetings: 7/30/13 and 8/7/13.
Reading: Lee will send around a paper to read for the 8/7/13 meeting.
- Lee’s improvements:
- Idea: what’s important is case sequences, not cases by themselves.
- “Condensed” lexicase: Find all of the sets of elites that can be reached through lexicase, and then select one at random and a random individual from that set.
- Rough draft by end of week
- Ignore population size / test case stuff for now.
- Homologous selection and lexicase together?
Speedups are in the works.
- Stack traces are looking great!
- Tom will send Jake some stack traces of big (maybe real) programs.
- Jeff Clune – discussed connection costs in programs
- Kris Krawiec – GSXover discussion
- Stack-based workshop was small but some interesting ideas
- Leonardo Trujillo – discussion about novelty search to refine fitness function.
- includes program modality
- combines advantages of novelty search and guided by error search.
show certain stacks
Don’t show unused
problems if many cases that are equivalent
instead of shuffling, just choose random,
instead of random, spin roulette wheel, where section is wider the weirder the case is
How to measure weirdness: look at pop, for each guy in pop, look at each other case, and say if that guy in pop = elite on both cases or neither, then same as that case, but if we disagree about that being elite +1 idiocincrecy the more cases disagreed with, more idiosyncratic
pure random, improve slowly then continue to improve
right measure of idiosyncrasy may make all the difference
trouble balancing jobs with many different characteristics
lee code takes longer on more cores(maybe equal but not less), less cores going faster
increased number of slots available on 4 and 5 for jaime
= numbers of tasks running on jobs with same priority
commonly get to point, multiple individuals left, different programs with same error vectors, so lexicase would no longer get rid of cases
1. each step, checks remaining error vectors, if all same, quit and return random
2. check pop in beginning, anyone same, choose random before, same as choosing random after running
Present: Lee, Tom, Jake, Daniel, Bill (hangout)
These projects are small-ish things that could be taken on by someone (though some are already claimed).
Broaden the call!
- Climate change negotiation game
- We have basic infrastructure, it would be interesting to try to evolve something to play it.
Moving to WordPress by Daniel
- We don’t have a good, updated description of Push.
- The most recent publications that describe Push well are outdated, from 2005, 2001, etc.
- Daniel may take this on after updating the website.
This was started by Ian Herold in Clojure, but needs to be finished. It would be nice to have it done before GECCO in early July.
Still working on fixing some reflection problems.
ALPS Paper Discussion
- It seems that ALPS is a parent selection technique that tries to maintain diversity and search different parts of the search space.
- It also injects new individuals into the gene pool, and tries to give them a chance, which may be good or bad.
- We all agree that there are some questionable parameters and specifics of the implementation, but that the general idea might be worthwhile.
- There is definitely a comparison to island models with migration.
- Implementation in Clojush:
- Tom may work on this.
- It may be difficult to do this within the current Clojush population structure, but might not be too bad.
- Things that may need to be changed include: breed, parent selection, lexicase, trivial geography
- There should be checks in the system for things that may break if done together, such as ALPS + trivial geography.
- It may be worthwhile to do this “quick and dirty” to try it out, and then if we like it, do it “right” to incorporate into the main code base.
- Bill may also like to implement ALPS or another similar island model in his work.
- We need to review the multiobjective optimization literature.
- Should include looking into NSGA-II and SPEA-2 (i.e. pareto front things).
- There might be something called “lexicographic ordering”, where the user decides which objectives are most important.
- Wikipedia page might have some good info.
- Heatmaps: we might want to include these in the paper, unsure for now.
- Once per generation, figure out relative “specialness” of each test case
- This “specialness” is very similar to the “similarity” that Tom used previously in Historically-Assessed Similarity
- Then, you bias the lexicase ordering for “special” test cases nearer the beginning.
Optimization problems with Penumbra
Excess data types need to be removed
Need collision detection per different objects
Search: Warn on reflection
Paper to read for next meeting:
Greg Hornby – ALPS (Emailed to List)
Genetic Papers and Software Conference- October 2013 UCL
Lee gone starting July 3d for two weeks
Send final draft of Ultra Paper
Try Lexicase selection on intertwined spirals
Present: Lee, Tom (scribe), Daniel, Kyle
The lab’s wiki will likely be moved to a WordPress site, possibly by Daniel.
Using Leiningen for Clojush GP runs
In order to speed up runs through some sort of compilation magic, use “lein with-profiles production trampoline run …”.
- Kyle feels that lexicase is a variation of ordered bagging.
- Lee is using the similarity of eliteness vectors for weighting / skipping of test cases. This is somewhat related to Tom’s work on historically-assessed similarity.
Langdon and Harman Paper
- O-Binning is sort of similar to lexicase.
- Targeted variation is interesting, and may be relevant to our future work.
- Some stuff used here might not apply well to our work, since they’re using GP to improve human-written code for speed.
Present: Lee, Tom, Daniel (scribe), Kwaku.
- Jake may come and bring brevis into the group
- Several people are expressing intrest to join the group in the near future
- GPTP chapter deadline is 5/30
- needs update for new data
- Add Jamie and Daniel’s data to lexicase article
- GPTP token to Tom
- Lexicase and node selection are next for Tom
- Discussion of what Daniel should be doing
- weighted lexicase with previous algebra work
- try to do push work with environments
- do push for finite algrebra problems
- Lee has been communicating with Alberto Moraglio
- Alberto has been learning Push and Clojure very quickly
- He has been working on a system he thinks could solve a very difficult parity challenge
- Anyone is welcome to help work on this
- Lexicase selection seems to be demonstrably good in many cases
- It is even good in non modal problems
- Have looked at ways to improve lexicase selection
- All previous attempts at improving lexicase have been bad
Niche Elite Selection
- This is the system talked about in the previous meeting
- This system seems to be truly terrible
Newest Proposed System
- Instead of doing sorting of cases, sometimes can skip a case
- Discussion when and why you skip
- Decide want a low chance of skipping if case is unique
- This calls for a similarity measure; we decide to use mutual information
- Kwaku brings up this is a valuable metric about test cases in general
- Decide the specialness of cases shouldn’t be recomputed for smaller populations
- There will be a discussion next meeting about the genetic improvement paper that has already been sent out to the list
Present: Lee, Tom (scribe), Daniel, Kwaku (hangouts)
Reading for next meeting: Bill Langdon paper (emailed to list)
People Associated with Lab This Summer
- Kwaku (remotely)
- Ryan and David (new UMass grad students)
- Pratistha (Smith)
- Zeke (GitHub things)
Things for Lee to take note of
- Link to Zeke’s stuff on wiki
- When to have next lab meeting
- Get GPTP slides to Tom soon, preferably by early in the day Monday
- Send Tom calc code to do lexicase case usage visualization
- Lee makes slides
- Tag-team presentation
- Tom describes experiments and results
- Lee does everything else
Lee’s new selection: Maximal Polymath selection
- Uses elite cohorts
- Hopes to combat some of lexicase’s problems with number of test cases vs. population size problems.
- Pick random cohort, and then use random individual from that cohort, or use lexicase within that cohort
- Possible issues:
- Too much elitism?
- Too much emphasis on weak individuals that do well on single test cases that others do poorly on?
Kwaku visualization stuff
Sounds interesting – Kwaku will get it working and send new link
- Synthetic parent trials
- No-paren ULTRA / push
- Tree GP ULTRA
- Keep Cool
- Visualization (Push stack diagrams)
Present: Lee, Tom (scribe), Emma
- Not sure about funding for after this semester yet
How to make inferences in GP / initial populations / COSMOS
- The emphasis should be about how to make inferences about how well a GP system works, especially in comparison to another method or system.
- About the efficacy of GP.
- What you need to do to make claims about your system and comparisons.
- Not really about choosing a population size.
- Includes a new experimental procedure.
- Better on Pagie-Hogeweg and Bioavailability
- Program sizes are much lower.
- Tom will start writing this up soon.
GECCO Stack-Based GP Workshop
Multiple output multiplier
- Tom will work on getting this running in Clojush
- We decided that the current return_tagspace and return_tag_ instructions are enough for tags in environments.
- Maybe try PH or Bio if we have extra cluster cycles.
Lexicase-based Mate Selection
- We discussed briefly how we might do a non-random mate selection based on lexicase.