14 August 2013

Present

Lee, Tom, Kyle, Jake, Dave (scribe) , Dan

Brevis

Some progress in Brevis. Moving along, but some trouble with scroll bars. A little faster, but looks about the same.

ULTRA speedup

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)

Website

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)

Parity

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

Calculator

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

To do:

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

To Do:

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:

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

Brevis:

add shadows
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.

Lexicase

• 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.
• Paper
  • Rough draft by end of week
  • Ignore population size / test case stuff for now.
• Homologous selection and lexicase together?

Brevis

Speedups are in the works.

Visualization

• Stack traces are looking great!
• Tom will send Jake some stack traces of big (maybe real) programs.

GECCCO Report

• 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.

Push Visualization:

show certain stacks
Don’t show unused

Idio Lexicase:

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

Cluster Notes:

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

Lexicase Speedup:

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)

Projects

These projects are small-ish things that could be taken on by someone (though some are already claimed).

iOS Project

Broaden the call!

Keep Cool

• Climate change negotiation game
• We have basic infrastructure, it would be interesting to try to evolve something to play it.

Lab Website

Moving to WordPress by Daniel

Push Introduction

• 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.

Push Visualization

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.

Brevis

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.

Lexicase Paper

• 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.

Special Lexicase

• 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.

Brevis Project:

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)

Other Notes:

Genetic Papers and Software Conference- October 2013 UCL
Lee gone starting July 3d for two weeks

Action Items:

Send final draft of Ultra Paper
Try Lexicase selection on intertwined spirals

Present: Lee, Tom (scribe), Daniel, Kyle

Wiki

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 …”.

Lexicase

• 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.

Administrative

• Jake may come and bring brevis into the group
• Several people are expressing intrest to join the group in the near future

Future Work

• 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

GPSP

• 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

Selection

• 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

Reading

• 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

• Lee
• Tom
• Daniel
• Kwaku (remotely)
• Jake?
• Bill
• Kyle
• 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

GPTP

• Lee makes slides
• Tag-team presentation
  • Tom describes experiments and results
  • Lee does everything else

Selection

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

Upcoming Topics

• ULTRA
  • Synthetic parent trials
  • No-paren ULTRA / push
  • Tree GP ULTRA
• Brevis
• Tags
• Environments
• Keep Cool
• Visualization (Push stack diagrams)

Present: Lee, Tom (scribe), Emma

Administrative

• Not sure about funding for after this semester yet

GPTP

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.

ULTRA

• 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

Environments

• 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.