Attendance:
Jake, Daniel, Thom, Frode, Kwaku

For future weeks:
Send note to group list, night before meeting, with brief update

Side Notes:
No meeting next week!
2 Paper Readings for 2 weeks: Push Forth/Other paper sent to list by Thom

Updates:
Daniel: Thinking about using ULTRA/Push on tree based programs
– Looking into “Rush Hour” program
Frode: Learning and understanding clojush and push forth
Lees Ideas –
Just implement push forth
Forget about push forth – work with clojush/push – create documentation

Present: Lee, Tom (scribe), Bill, Daniel, Jake, Karthik, Eddie, Frode, George, Omri

No meeting next week. The following week, Conor and Chris will be visiting our meeting, and will also talk from 4:00-5:30 that day.

Updates

Jake

• Working on Push visualization.
• Div 3: Growth + Animation

Omri

• SIMD and complexity theory
• Integer sequences and GP
• Evolving test cases?

Eddie

• Working on Python Push

Frode

• Reading about other evolutionary algorithms.

Bill

• Switching back to a developmental approach

Daniel

• Div 3: GP + mathematics
• When will GP solve a problem

Topics

Israel Trip

• Someone should look into Humies awards to see what makes good GP results.

Max-Points Bug

•  Because the pushgp argument (max-points) has a different name from the global variable (global-max-points-in-program), the global variable is not being reset when max-points is given as an argument
  • This is a problem for Push instructions that use the global variable to determine if a piece of code is too big to put on the code/exec stacks. In particular, many code stack instructions and exec_s and exec_y use it to limit the size of code on those stacks. Because of this bug, those instructions will limit code to 100 points during execution, even if max-points is set by a pushgp argument.
  • Fortunately, this bug does not affect genetic operators, which use max-points directly when it is passed to the breed function.
• Tom is going to fix this bug by changing all occurrences of “global-max-points-in-program” to “global-max-points”. He will also check if there are any other name mismatches between global variables and pushgp arguments.

 No-Paren Mutation ULTRA

• An initial look into no-paren mutation ULTRA looks good using the Change problem.
• But, since the Change problem doesn’t use semantic parens, we should test it on a problem that requires paren structure.
• Tom will test it on a synthetic problem that we discussed, which we will, for now, call the “damped oscillator tree” problem, which builds a program that looks like this:
  • (0 0 0 0 0 ((0 0 0 ((0) 0 0)) 0 0 0 0))
  • The problem will (initially) use overlap as the fitness function.

Calc Problem

• Alternative error measures like Levenshtein distance could be important.
• Which test cases should we use out of all of them?
  • For now, we want to try using a random subset of all the test cases each generation.
  • This will require validation of seemingly perfect solutions. It may be possible to do this in the problem-specific report.
  • Tom notes that Schmidt and Lipson tried random subsets of test cases in their co-evolved fitness predictors work, and they fared rather poorly.
  • If this works for Calc, we should also try it for WC.

Present

Lee, Tom, Bill, Omri (scribe), Kwaku, Jake, George

Grants, collaborations, visits

We have funding for collaborative projects aiming at human-competitive GP with Moshe Sipper (and his group) over at Ben-Gurion University. The funding alots for travel expenses for quite a few round trips to Israel. We should keep this opportunity in mind.

Lee will also be applying for Templeton funding for looking at “big” questions about life and its origins. Ventpods may come into play here.

Chris and Conner will be coming to visit sometime in the upcoming weeks. They will join for a research group meeting, and Lee may also try to set up a time and place for them to give a talk.

Status updates and such

Tom’s been working with the coin problem, and clojush doesn’t require anything beyond integer instructions to find a solution. So, it may not be quite the right problem for trying to get at “replacing the programmer”. Either way, now it’s an example problem in clojush.

Tom has also done some tests with “bagging” (ensemble voting) and it doesn’t look promising.

Jake’s been working on brevis with Kyle, and there will be a demo next week!

Omri has been looking into SIMD integer factorization algorithms.

Lee has been doing experimenting with “bushy” or “deep” program generation, and also experimenting with increasing no-op usage in the calculator problem.

Possible threads to follow

Evolving SIMD parallel algorithms.

Analyzing why no-ops seem to help the evolutionary dynamics in the calculator problem. More generally, considering experiments with adaptive representations.

Generating random code shapes.

Linear Push, some ideas for how to maintain recursion and expressive “chunking of stuff”:

• instructions with “baked-in” arguments
• instructions with structural taken from the stack like regular arguments
• some instructions scan for keywords like “end”
• some instructions scan for patterns
• make the execution environment dense with tags
• revisit tag space machines
• incorporate GOTOs
• recursion through environments

New ways to deal with parentheses and mutation in ULTRA:

• no mutation
• no mutation of parentheses (including no ability for things to mutate into parentheses)

Reading for next week

Maarten Keijzer’s Push-forth paper.

Library of Babel by Borges.

Uncompromising Problem

Term used for problems where Lexicase Selection is needed.

Geo-Lexicase Selection

Seems to be working well on Lee’s tests.

Tom

Tom still looking for simple programming problems to solve.

Sports Betting

The idea of creating a program that will intelligently bet on sports games was discussed as a possible next project.

Flea Markets and Meta-GP

Making a GP system that finds the most efficient GP system was discussed as a possibility.

To move forward with this idea we would need a simple enough game/market to attempt this.

Cluster Tutorial

At the end of the meeting we learn how to run our test on the cluster.

Meeting Notes

Present: Lee, Tom (scribe), Dave, Omri, Frode

Dave

Dave is moving on 🙁

Frode

Frode will be working on getting used to doing Clojush runs and getting back into writing Clojure code.

Omri

• Omri is trying some things related to using Xerox machines for SIMD parallelism using stacked transparencies.
• Unfortunately, adding new stacks in Clojush for just one example file is difficult, and therefore the easiest thing to do is to just change the global definition of the stacks.

Lee

• ULTRA with many noops. This sounds interesting and potentially useful for allowing evolution to determine the correct amounts of noops.
  • Adding noops effectively increases the alternation rate so that it can be set lower.
  • Tom suggests using a fixed program size to encourage homology.
  • A good project would be to look at evolving populations to see how much homology exists, especially comparing something like ULTRA with normal genetic operators.
• If anyone wants to work on calc or other software projects, talk to Lee!

Tom

• Implemented the change problem, which isn’t as difficult as it first appeared, since it may be possible to do without exec stack manipulations and only integer arithmetic.
  • Tom will try some runs with only integers.
  • Tom is interested in general in doing some sort of Linear Push with ULTRA, which may help with matching instructions that need structure with the right connections.
• Bagging and other ensemble techniques are potentially interesting!

Pre-Meeting Agenda

Things Tom wants to discuss:

• Using ML ensemble techniques to combine solutions from multiple GP runs into single solution
• Feature selection might be useful, especially for lexicase!
• The US Change Problem
  • implemented and started testing
  • no solutions so far, but some very close misses, such as some that miss 2 to 5 cases out of every 25
  • It seems that ULTRA is having a hard time using semantic parentheses for instructions that need them, such as exec_y, exec_if, and exec_do*times.
    • I would be interested in trying some paren-free PushGP, where instruction groupings are somehow baked into instructions that need them. Or maybe, those instructions always start a paren, and only the ending paren can vary.
• I’ve been timing the US Change runs, and am starting to get results as to which nodes of the cluster they are most efficient for.

Lee adds:

• Noops and ULTRA.
• Results for CREST/COW

Present

Lee, Tom, Jake, Dave, Dan, Frode, Bill, Eddie, Omri (scribe)

Events

• Lee will be attending COW in London (October 14-15)
• ClojureCup (September 28-30) signup is now open. We all agree that GP and/or Clojush webapps would be a good idea regardless, for the purposes of garnering general public interest

Grants

We discussed various possible grant proposals, including one to the Templeton Foundation. The Robust Intelligence grant will be due by October 15th.

Lexicase essay

Currently a priority and still some data to accumulate. We bounced around ideas for phrasing choices to frame why lexicase selection is important or different. Some different ways to describe the types problems that it solves: “test case ideal”, “multivariable regression”, “uncompromising”.

Geo-lexicase

Somewhat promising so far, but only using medium population and radius sizes. So it seems to be more effective, but not faster.

Brevis

…Is coming along.

Finding good problems

Tom is looking for good problems for GP to tackle. Specifically ones that could highlight automatic software development. Some problems discussed were I/O file manipulation, change decider, a simplified automated accountant, and a tic-tac-toe judge. The tic-tac-toe judge was our favorite.

Next meeting

September 11 2013 (no paper to read)

Present: Lee, Tom (scribe), David, Kyle, Jake, Daniel, Kwaku (he could see us, we couldn’t see him)

Semester meeting time: Wednesdays from 10AM to noon, starting next week.

Lee’s To Do:

• Edit info on website.
• Merge changes into Clojush, including Tom’s pull request and Kyle’s RNG code.

Clojush RNG

Things aren’t too bad, so we don’t have to do anything drastic like redo all of our runs. Kyle’s new code should solve the problem, at least as well as can be done using Java’s RNG.

Lexicase Speed

Tom will try out making error lists into error vectors, which should hopefully speed up lexicase. More news to follow after this has been tested.

FRIGHT Paper

• Uses rule-based evolution for ghost team vs. Ms. Pac-Man
• Uses ECJ!
• Seems related to other rule-based systems and learning classifier systems

Ventpods

• Lee has ideas for making ventpods create waste
• Programming is getting there.

Calc Problem Updates

• Something recently added is helping!
  • Single-digit and double-digit entry tests and single digit math seem to be evolving decently.
• Changes include:
  • Back to regular lexicase
  • Each “test” generates 2 cases:
    • Numerical difference from desired output
    • Levenshtein distance of string to desired string
    • Important to think about fitness function carefully!
    • Also, a meta test case that counts the number of other test cases that aren’t zero
• Many no-ops may be helpful!?!?
  • Homology / ULTRA / ???
  • May want to try some sort of ULTRA with pre-specified or evolved “crossover points”

Lexicase Subset Division (Dave’s Idea)

• Related to spacial co-evolution if we use neighborhoods like trivial geography.
• How to make lexicase faster by using fewer test cases?

Age-Enhanced Lexicase

Idea: make age a test case used in lexicase selection.

• Is one age case enough?
• Other added cases may be helpful!
• Try on other problems?

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.