Category Archives: genetic programming

Everybody loves a puzzle

Posted on by

A few months back Zee Spencer started think­ing about using evo­lu­tion­ary algo­rithms of var­i­ous sorts (notably GP) to solve Sudoku puz­zles—and more par­tic­u­larly to evolve solvers.

Inter­est­ing idea, not least because Sudoku solv­ing is a “solved prob­lem”, and noth­ing sets me off like one of those. There are well-known constraint-satisfaction meth­ods for con­struct­ing and solv­ing Sudoku grids; there are branch-and-bound and inte­ger pro­gram­ming approaches; you can even cre­ate, solve and type­set Sudoku grids by just typ­ing a lit­tle LaTeX code. And of course Peter Norvig has shown us all how to do it in his excel­lent and clear ped­a­gogic essay.

But of course all of those approaches make sense. Which is to say they’re ele­gant and no doubt ever so effi­cient and ratio­nal, but… well, they’re bor­ing, for lack of a bet­ter term.

Zee and I paired a few months back on a pre­lim­i­nary exper­i­ment he’d designed, in which he was evolv­ing solu­tions to fixed Sudoku puz­zles. And some­thing he said reminded me of an old unex­plored note­book ques­tion regard­ing constraint-satisfaction puz­zles gen­er­ally, which I brought up. This week I’m in Cleve­land work­ing with him on his inter­pre­ta­tion of that approach.

Cel­lu­lar Sudoku

All the extant Sudoku solver algo­rithms I’m aware of rely on what you might call “ser­ial atten­tion” and a tra­di­tional dynamic pro­gram­ming archi­tec­ture. That is, they scan over the ini­tial grid in some way look­ing for any of a num­ber of pat­terns: a block or row or col­umn that has almost every­thing filled in, or a cell where two or three con­straints over­lap to make a num­ber choice cer­tain, and they fill those num­bers in and start look­ing at the con­se­quences. The fancy ones keep a lit­tle “stack” of what-if explo­rations in mind, look­ing not merely at the currently-obvious constraint-overlaps but also check­ing for con­flicts and effects two or more steps into “the future”. This is in some sense the way many peo­ple actu­ally work Sudoku: a cycle of scan­ning for pat­terns, mak­ing judi­cious asser­tions, and maybe back­ing out if those asser­tions are “tricky” (as they can be in dif­fi­cult puz­zle exam­ples). And — at least in my case — prob­a­bly there’s some guessing.

Very nice. We’re not doing that.

In this exper­i­ment we’re look­ing for dis­trib­uted algo­rithms, a lot more like cel­lu­lar automata rules, that simul­ta­ne­ously update the choices avail­able to every cell in the Sudoku grid accord­ing to an (undis­cov­ered) deter­min­is­tic rule.

Here’s the way our hypo­thet­i­cal alien cel­lu­lar fel­lows will “solve” a given puzzle:

  1. Every cell in the grid is assigned a choice vector, which indi­cates which of the avail­able dig­its (1 – 4 for small Sudoku, 1 – 9 for stan­dard grids, and so on) that given cell might be at any given instant. The vec­tors aren’t prob­a­bilis­tic, just Boolean val­ues indi­cat­ing whether a cell could take a given value. If I rep­re­sent these Booleans with 1 and 0 for brevity, then for exam­ple in a 9x9 grid the ini­tial choice vector for any empty cell will be 111111111, and if the cell is a known hint (say a 5) the choice vector is 000010000—that is, that given cell’s choices are lim­ited to being 5.
  2. An Answer is a script of any num­ber of lines, each line con­tain­ing exactly one command. Com­mands have two parts: an argument and an operator.
  3. The argument is a string that refers to the rel­a­tive posi­tion of some other cell within the Sudoku grid: left, right, up, down, and also clockwise (cw) and counterclockwise (ccw). A cell’s left neigh­bor is the cell in the same row, one step to the left, mod­ulo the grid width; that is, the left neigh­bor of a cell in the left col­umn is the cell in the same row on the right col­umn. Sim­i­lar toroidal con­di­tions apply to right, up and down. The clockwise neigh­bor of any cell in the grid is its pre­ced­ing neigh­bor within its block, num­ber­ing in top-left-to-lower-right posi­tional order, row-first. So for exam­ple, in a stan­dard 3x3 block within a 9x9 Sudoku puz­zle, the cw neigh­bor of the cell in the upper right cor­ner is the left­most cell in the next row. The cw neigh­bor of the cell in the lower right cor­ner is the first block in the upper left, as well.
  4. The operator rep­re­sents a bit­wise boolean oper­a­tion to be car­ried out between the choice vector of the cell in ques­tion and that of the indi­cated argument cell. For exam­ple the com­mand "left and" applied to a given cell in the grid will replace that cell’s choice vector with the result of apply­ing bit­wise AND to its cur­rent choice vector and that of its left neighbor.
  5. For each line in an Answer, the choice vector of every cell in the grid is syn­chro­nously updated based on the cur­rent val­ues, start­ing from the ini­tial setup.
  6. After the last com­mand in the Answer has been applied, the result­ing grid is inter­ro­gated. That is, every cell is sent a decide! mes­sage, and emits (with uni­form prob­a­bil­ity) one of the choices encoded in its final choice vector. Cells that have ended up with no remain­ing choices emit a ? or 0 answer, indi­cat­ing they’re unable to respond.

Need­less to say by this time, this is an exploratory project, not an “opti­miza­tion” prob­lem. It’s not a case of “find the most effi­cient algo­rithm to do that”, but rather “is it even fea­si­ble that this might get closer to a solu­tion”? Our sus­pi­cion is that it might, but aside from a bit of hand-wavy dis­cus­sion of “infor­ma­tion prop­a­gat­ing across the grid” we have no frack­ing idea how a general-purpose Sudoku solver might work, if it can.

We’ll see.

In the mean­time, you might already sense a few places where this scheme can be relaxed or expanded. Yes, we thought about prob­a­bil­ity vec­tors instead of choice vec­tors. Yes, we’ll start with a sim­ple suite of operators like and, or, not, but we could get fancy with all 16 pos­si­ble binary oper­a­tors, or spread out into mul­ti­ple argu­ments. Yes, we’re start­ing with a local neigh­bor­hood around each cell to begin with, but we could let the argument of any com­mand be a phrase of con­sec­u­tive moves like "left up left ccw". We could include access to the past state of a cell in the neigh­bor­hood def­i­n­i­tion as well. We could apply dif­fer­ent rules to dif­fer­ent cells at each time-step.

We have no clear idea what might hap­pen until we give it a shot. Which will prob­a­bly be the next thing we talk about.

How do we know what’s hap­pen­ing, and whether we think it’s good or bad?

Pizza Eating Strategies, Part 2

Posted on by
Reply

In the pre­vi­ous episode, I spent a few min­utes jot­ting down some sto­ries that describe what I’m inter­ested in learn­ing in this project: I’m using GP to develop play­ers of Peter Winkler’s “Pizza Eat­ing Game”, and the algo­rith­mic part of those GP Answers will use a novel archi­tec­ture called Tag Space Machines from Lee Spec­tor. And as a kata for myself (and a bit of a tuto­r­ial for the occa­sional per­son I encounter who hasn’t done test-driven design before) I’ll be using rig­or­ous BDD, record­ing all the lit­tle messy details here.

So. I think I’ll start with some low-hanging fruit, not least because I’m wrestling with learn­ing a new text edi­tor, and try­ing to get all the fid­dly bits hooked up is prov­ing chal­leng­ing. So I think I’ll build a Pizza class first.

Look­ing over the sto­ries, I’m going to assume the pizza is just some kind of wrap­per around an Array of slice sizes, with some fancy meth­ods that per­mit initialization/reset and “eat­ing”. Let’s start with initialization/reset.

# pizza.feature
Feature: Pizza

  Background:
    Given I have a new pizza

  Scenario: pizza slicing
    Given a list of slice sizes [1,0,7,9,3,12,33,0,0,0,2.88,2.12]
    When I slice the pizza
    Then there should be 12 slices
    And the pizza should weigh 70
    And the pizza should be whole

The pizza is “whole” because Alice hasn’t eaten the first slice, and it’s going to be treated as an array with “wrap­ping” bound­aries by her yum­mi­ness function(s).

Cucum­ber reports that the first pend­ing spec is Given I have a new pizza, so I cre­ate the appro­pri­ate step definition.

# pizza_steps.rb
Given /^I have a new pizza$/ do
  @pizza = Pizza.new
end

This fails, since I have no Pizza class.

#pizza.rb
class Pizza
end

And it passes. The next pend­ing step is Given a list of slice sizes [1,0,7,9,3,12,33,0,0,0,2.88,2.12].

# pizza_steps.rb
Given /^a list of slice sizes (\[.+\])$/ do |slices|
  @slice_list = eval(slices)
end

That passes, since it’s not invok­ing the library at all, just set­ting a vari­able within the scope of the test. When I slice the pizza is next.

# pizza_steps.rb
When /^I slice the pizza$/ do
  @pizza.slice(@slice_list)
end

This calls for a tiny bit more struc­ture in the Pizza class, but not too much.

#pizza.rb
class Pizza
  attr_accessor :slices

  def slice(size_array)
    @slices = size_array
  end
end

Next pend­ing step is Then there should be 12 slices.

# pizza_steps.rb
Then /^there should be (\d+) slices$/ do |count|
  @pizza.slices.length.should == count.to_i
end

Which passes already. And the pizza should weigh 70

# pizza_steps.rb
Then /^the pizza should weigh (\d+)$/ do |weight|
  @pizza.weight.should == weight.to_f
end

That calls for another bit if Pizza struc­ture. But is it an attribute, or a method? I’m think­ing method; the slice weight array itself is already stored, and I assume the play­ers will have some sort of #eat(left_slice) method that mod­i­fies that Array directly on each turn. I’ll return the sum of all slice values.

#pizza.rb
class Pizza
...
  def weight
    @slices.inject(0) {|sum,w| sum+w}
  end
end

Last step is And the pizza should be whole.

# pizza_steps.rb
Then /^the pizza should be whole$/ do
  @pizza.should be_whole
end

Inter­est­ing ques­tion: when is Pizza#whole? going to be true? As soon as my pizza is first sliced, surely. But maybe also when it’s ini­tial­ized (“baked”)? Then again, the ini­tial­iza­tion method (which I haven’t needed yet) might be more use­ful to set up partially-eaten un-whole piz­zas for test­ing or train­ing. I’m all for postponing.

#pizza.rb
class Pizza
  attr_accessor :whole
  ...
  def slice(size_array)
    @slices = size_array
    @whole = true
  end

  def whole?
    whole
  end
end

All steps pass.

So Alice and Bob will be eat­ing par­tic­u­lar ele­ments of Pizza#slices. And the sto­ries make it clear there are two modes: the first slice, and then the left_slice vs right_slice. I sup­pose I should start with the first slice. In addi­tion to mak­ing the pizza no longer whole?, this ought to “unwrap” the cir­cle to cre­ate the left_slice and right_slice linearity.

# pizza.feature
...
Scenario: eating the first slice unfolds the circle
  Given the pizza is sliced into [1,2,3,4,5,6,7,8]
  When I take out piece 6
  Then the pizza should not be whole
  And the left slice should weigh 7
  And the right slice should weigh 5

I’ve made a new step here.

# pizza_steps.rb
Given /^the pizza is sliced into (\[.+\])$/ do |slices|
  @pizza.slice eval(slices)
end

That passes already, from work done in the pre­vi­ous sce­nario. Now When I take out piece 6 is the next pend­ing step.

# pizza_steps.rb
When /^I take out piece (\d+)$/ do |which|
  @pizza.eat_first_slice(which.to_i-1)
end

I need to add Pizza#eat_first_slice to the library, though this step doesn’t actu­ally call for it to do anything.

#pizza.rb
class Pizza
...
  def eat_first_slice(which)
  end
...

Then the pizza should not be whole

# pizza_steps.rb
Then /^the pizza should not be whole$/ do
  @pizza.should_not be_whole
end

Seems a sim­ple thing to make that pass.

#pizza.rb
class Pizza
...
  def eat_first_slice(which)
    @whole = false
  end
...

And the left slice should weigh 7. Basi­cally the “left” slice is the stub-end of the unwrapped cir­cle I get when I snip out the eaten piece, and the “right” slice is the piece remain­ing to its left. First the steps I need (both at once, just because the sym­me­try is so clear):

# pizza_steps.rb
Then /^the left slice should weigh (\d+)$/ do |weight|
  @pizza.left_slice.should == weight.to_f
end

Then /^the right slice should weigh (\d+)$/ do |weight|
  @pizza.right_slice.should == weight.to_f
end

And the library code to make these pass. I fid­dle a bit with the bounds-checking, but I think this will do.

#pizza.rb
class Pizza
...
  def eat_first_slice(which)
    open_circle = @slices[which+1..-1] + @slices[0...which]
    @slices = open_circle
    @whole = false
  end
...

And that seems to have done the trick.

Pizza Eating Strategies, part 1

Posted on by
1

This is the first in a (hope­fully short) series in which I’m prac­tic­ing my BDD in a Ruby-based exper­i­ment where I want:

Some sto­ries

I’m start­ing from an empty can­vas: I’ll need to think about the rep­re­sen­ta­tion of the prob­lem domain, not just the archi­tec­ture of the TSM answers and GP sys­tem. I spend some time read­ing over the arXiv paper that sparked my curios­ity and Lee’s descrip­tion of TSMs. I come up with a few sto­ries, and some notes as I jot them down.

Eat­ing the first piece isn’t like later pieces:
Before the first game move (when the pizza is whole), Alice can pick any piece at all. After she does, Bob and Alice can only pick one of the two neigh­bors of the grow­ing gap.

As I men­tioned when I launched this side-project, I’m think­ing about the way these agents play the game as being some kind of “field gen­er­a­tion” process. Their cal­cu­la­tions impose some kind of “yum­mi­ness field” on the (cur­rent) set of pizza slices, and then when that cal­cu­la­tion is done they eat the slice with the high­est yum­mi­ness value. Fur­ther, I think I want to try a local process, a sin­gle cal­cu­la­tion con­ducted with “this piece of pizza” as the focus, with ref­er­ences to the traits of other pieces being spa­tially relative.

The inter­est­ing thing of course is the topo­log­i­cal dif­fer­ence between the whole pizza and the partially-eaten one. The whole is cir­cu­lar, with “left” and “right” being well-defined all the way around. But once a piece is eaten, the thing becomes “lin­ear”, and the only choice before the agents is between the two “end” pieces of that ordered set of pieces.

In deter­min­ing the “yum­mi­ness field”, this feels like it might be impor­tant. But it’s also lim­it­ing the set of agent behav­iors: the first move is some kind of eat_first_piece, and all sub­se­quent moves are eat_left_piece or eat_right_piece.

Pizza slices have weights:
every pizza slice has a numer­i­cal weight, which can be 0

This seems pretty straight­for­ward: the goal of the play­ers is to con­sume a max­i­mum pro­por­tion of the total pizza, and “weight” seems as good as any­thing for tal­ly­ing this up. Bet­ter than “crust”, surely… though of course they will sort in the same order.

Agent decision-making:
Agents have two yumminess func­tions, one for pick­ing the first piece, and the other for later moves. The yumminess func­tion is invoked with a ref­er­ence to a spe­cific index of the cur­rent pizza, and returns a float value. One yum­mi­ness value is cal­cu­lated (in par­al­lel) for each slice.

I’m think­ing the basic yumminess cal­cu­la­tions might include some boolean logic and arith­metic; we’ll work our way up from there as needed. The index of a slice is the input, but the algo­rithm can have instruc­tions to inter­ro­gate the attrib­utes of slices, things like its index, its weight, that sort of thing. Heck, maybe the yumminess of one slice can refer to the yumminess of its neigh­bors… but that may end up being complicated.

Because of the clear topo­log­i­cal (and strate­gic) dif­fer­ence between the first slice and the later ones, I’m will­ing to start with a lit­tle extra com­plex­ity and have two sep­a­rate func­tions. This seems to imply I’m think­ing that every agent can play “Alice” or “Bob” roles in what­ever scor­ing tour­na­ment I come up with. Why not? Let’s see what happens.

Yum­mi­ness ties are bro­ken randomly:
When the max­i­mum yumminess is assigned to mul­ti­ple avail­able slices, one is picked at ran­dom with uni­form probability.

In other words: when in doubt, flip a coin or draw straws.

Yum­mi­ness func­tions are Tag Space Machines:
One for each. The appro­pri­ate ref­er­ences to exter­nal val­ues are set up based on the slice index, the TSM is run, and then the top­most [num­ber] is emit­ted as the output.

I’m not sure which “num­ber” this might be. Do I need to dif­fer­en­ti­ate between int and float? Really? I don’t have a lot of infor­ma­tion yet about what the TSM lan­guage is going to be like. Maybe this will become more appar­ent as I work on that.

TSM math instructions:
The TSM should rec­og­nize float val­ues, and have basic math instruc­tions: add, subtract, divide, multiply, min, max, maybe a few more.

Do I really need integer as a type? After all, the notion of an “index” in the tag space itself depends on the math­e­mat­i­cal “floor” func­tion. Why not use floats for indices as well, tak­ing the floor (or ceil­ing) as needed? Maybe this is just reals, and we’ll skip the dif­fer­ence until we need it.

TSM pizza instructions:
The TSM should be able to get the index and weight of the slice on which it’s applied. It can use weight_of and index_of with a numeric argu­ment (pos­i­tive or neg­a­tive) to obtain val­ues of neigh­bor­ing slices.

I have an intu­ition this may not be enough. But we’ll see. It’s not that hard to imag­ine run­ning the cal­cu­la­tions for each slice in lock-step, and let­ting one TSM inter­ro­gate its neigh­bor­ing TSM’s state, like with real_of to copy over a real from a neigh­bor­ing slice’s stack into its own. But no need to over-design yet.

TSM log­i­cal instructions:
The TSM should have basic Boolean logi­cian func­tions: and, or, not, that sort of thing.

Makes sense, because we’ll have com­par­isons to make.…

TSM com­par­i­son instructions:
The TSM should have com­par­isons like less_than, greater_than, equal and so on for reals and any other types for which they make sense.

These will cre­ate bool outputs.

TSM dynam­ics:
When the TSM is acti­vated, it pops one item from its x stack; if it’s a con­stant it’s pushed to the appro­pri­ate stack, and if it’s an instruc­tion it exe­cutes that instruc­tion imme­di­ately. This con­tin­ues until the x stack is empty.

This is just the def­i­n­i­tion of how TSMs run. But it does raise the ques­tion (from expe­ri­ence): Will there ever be TSM “pro­grams” that don’t ter­mi­nate? Will I need a step counter, and some sort of dead­line? We’ll see, I guess.

TSM tag spaces:
The tag_space stack holds tag_space instances. TSM instruc­tions for stor­age and lookup exist, and refer to the top tag_space in the stack based on numeric index. Each tag_space is a key-value pair store, sorted by numeric key. Lookup is inex­act, return­ing the value for the small­est key larger than the search tag, or the first key of no key is larger. No value is returned if the tag_space is empty.

Feels as though I’ll need to cre­ate a sub­class of Ruby’s Hash for this, main­tain­ing the sort order and deal­ing with the inex­act lookup. Shouldn’t be too com­pli­cated, but will demand some care­ful checks.

TSM tag­ging instructions:
There are instruc­tions store, store_pair and lookup for writ­ing and read­ing from the top tag_space. (see update below)

Based on Lee’s descrip­tion, it sounds as though his ts_tag imaps arise some­how from the “genome” of a TSM: that is, they appear fully-formed in the x stack before we start run­ning the code. This feels strange but inten­tional, and so I’ve asked him if I’m miss­ing something.

In the mean­time, I’m more com­fort­able hav­ing instruc­tions that make those asso­ci­a­tions from argu­ments just like other instruc­tions would use, except that the argu­ments for store and store_pair come from the x stack rather than the typed stacks. For instance, I’m imag­in­ing store pulls a “tag key” from the reals stack, and the next item from the x stack, and stores the item as a value asso­ci­ated with that key in the top­most tag_space.

What am I missing?

Well, of course I’ve not defined any­thing about how these sup­posed pizza-eating experts are going to be scored, nor how many and what kind of pizza they’ll be asked to eat, or any of that. But it feels like enough to get started with, espe­cially as I’m wait­ing for Emma Tosch and Lee to help me out of the con­fus­ing bits.

In the mean­time, I’ll start on the pizza first….

Update (later that day):

After a cou­ple of clar­i­fi­ca­tions from Lee, I’ve got a bet­ter han­dle on how the tags and tag­ging instruc­tions should work.

TSM tag­ging instructions:
There are three kinds of what I’ll call macro instruc­tions: store_at(N), lookup_at(N) and store_pair_at(N), where (N) is a fixed floating-point num­ber, not an argu­ment. These numer­i­cal val­ues can (and prob­a­bly will) vary between instances of these instruc­tions, but not over the “life” of the indi­vid­ual instruc­tion instances.

So basi­cally what’s hap­pen­ing here is that the stor­age and retrieval of items in a tag_space always includes a par­tic­u­lar address, not a numeric argu­ment. This is a design deci­sion from Lee, and seems per­fectly valid to work with.

I think I can get away with a bit of abbre­vi­a­tion when writ­ing TSM code, and use >8.2 to indi­cate the macro instruc­tion store_at(8.2), use <-3.9 to indicate lookup_at(-3.9), and >>991.55 to indicate the macro store_pair_at(991.55).

Applying GP to Winkler’s Pizza Eating Game

Posted on by
1

(Code to be posted at github as I move forward)

A recent arXiv preprint enti­tled “How to eat 4/9 of a Pizza” caught my eye. It’s an inter­est­ing lit­tle answer to a chal­lenge from game the­ory (and geom­e­try, I sup­pose) posed by Peter Win­kler, who’s a con­stant source of inspiration.

Hun­gry, Hun­gry Alice & Bob

Sup­pose we have a cir­cu­lar pizza, already cut into wedge-shaped slices (from the cen­ter to the crust). These are extremely pre­cise slices, and in fact they can have “0 width”, or some small epsilon close enough to 0 to be entertaining.

There are two hun­gry play­ers, Alice and Bob. Alice chooses a piece to eat first. Bob and Alice alter­nate eat­ing pieces of pizza after that, until it’s gone, but they must both always choose one of the two pieces adja­cent to the grow­ing gap.

The arXiv preprint describes a strat­egy by which Alice can eat at least 4/9 of the pizza, regard­less of the slices or how smart Bob’s strat­egy is. She may be able to eat more than 4/9, depend­ing on the slices and Bob’s mis­takes. And of course she’s only guar­an­teed to get that much if she’s fol­low­ing a prov­ably opti­mal strategy.

Agents: Rep­re­sent

See, I’ve been writ­ing this book, and there are a num­ber of lit­tle side-projects like this one that have come up, but prob­a­bly won’t make the cut for the final edit. The six large-scale projects I’m work­ing on keep me busy enough, but at the same time I’m try­ing to pol­ish and refine my “sim­pli­fied” approach to GP project management.

So this is me think­ing in Ruby about one of those lit­tle side-projects.

I’ve also recently been watch­ing Lee Spector’s expla­na­tions of Tag Space Machines unfold. Tag Space Machines (TSMs) are a rep­re­sen­ta­tion scheme for GP lan­guages he’s imple­mented in his lab’s work. I think I may work with TSMs here.

Pizza

The pizza is mod­eled as an Array of “slice weights”. An uneaten pizza is con­sid­ered to be cir­cu­lar, and the first player (“Alice”) can eat any piece she wants. Eat­ing the first piece “unfolds” the pizza, restruc­tur­ing the array so that the start and end val­ues are the pieces on the “right” and “left” of the gap. After that, play­ers can only choose to eat one of the two end pieces.

In other words, the player agents have only three actions (besides “plan­ning”): eat_first_piece, eat_left_piece and eat_right_piece. And they don’t even get free choice among those three, since the first is mutu­ally exclu­sive with the last two.

How to think about eat­ing pizza

The big design ques­tion here is, how do play­ers think about the pizza?

A slightly more tra­di­tional approach might have them han­dling arrays and iter­at­ing and stuff. But hav­ing mod­eled game-play before, I know there’s also more dis­trib­uted (if less intu­itive) approach I’m won­der­ing about here: since there are so few choices in the game, what if a “think­ing” or “strat­egy” were a scalar field cal­cu­lated locally for each of the pizza slices indi­vid­u­ally, and which slice is cho­sen by a given agent was deter­mined by the highest-scoring pizza slice accord­ing to that agent’s slice field algorithm?

In other words, sup­pose Alice has eat_first_slice field def­i­n­i­tion that is a func­tion applied to each ele­ment of the pizza slice array (treat­ing it as cir­cu­lar). The argu­ments are the weight of “this” slice, and weights and dis­tances of slices to the rel­a­tive left and right of “this” slice, and the num­ber of slices over­all. Maybe her eat_first_slice field is the weight of a slice plus the aver­age weight of its six neigh­bors on either side.

Alice’s first turn begins with her cal­cu­la­tion of this field for the given pizza, and then she selects the highest-scoring slice. If Bob and Alice then have a (pos­si­bly dif­fer­ent) func­tion for scor­ing the slices of the non-circular pizza, the same dynam­ics can apply to their sub­se­quent choices of left_slice over right_slice. In cases of ties, we pick at random.

Might this approach work? I have no idea. It feels as though it has some flex­i­bil­ity. We’ll see.

I’ll post updates as I make progress.

Sketch of an “artificial scientist” project

Posted on by
Reply

One of the things you real­ize after a while is that projects drop into your lap faster than they can be com­pleted. Some sources of inspi­ra­tion are things you encounter all the time: your work (I know a lot about mol­e­c­u­lar design and phar­ma­ceu­ti­cal lead com­pound dis­cov­ery), your hob­bies (I know a lot about image recog­ni­tion and seg­men­ta­tion for OCR of dig­i­tized books), and things you see other folks doing and just want to try (I’ve enjoyed my years doing Sym­bolic Regres­sion because so many other peo­ple have paved the way, while leav­ing other paths less trav­eled and thus more interesting).

I’m find­ing that writ­ing the intro­duc­tory mate­r­ial for the book is dif­fi­cult. In fact I’ll prob­a­bly post­pone releas­ing the intro until more of the core guts are writ­ten. Mainly the intro­duc­tory mate­r­ial has been about that peren­nial ques­tion, “How do I find and pur­sue ideas?” My core argu­ment is that GP is use­ful for accel­er­at­ing the fruit­ful inves­ti­ga­tion of your ideas, but the chal­lenge for many folks is rec­og­niz­ing the heuris­tics I per­son­ally take for granted. Some of this means I’m revis­it­ing Polya’s How To Solve It: A New Aspect of Math­e­mat­i­cal Method, but I find that it’s not philo­soph­i­cally com­pat­i­ble with the agile stance I per­son­ally pre­fer, so I’m actu­ally find­ing Andrew Abbott’s Meth­ods of Dis­cov­ery: Heuris­tics for the Social Sci­ences more use­ful, not least because he sug­gests Aristotle’s four causes and Kant’s schema as inter­est­ing “kicks to the head”. And there’s Michalewicz and Fogel’s excel­lent How to Solve It: Mod­ern Heuris­tics, which goes in a more tech­ni­cal direc­tion (and closer to GP) tan Polya was able to do.

But I look over all that good advice, and I find it trou­bling. So I’m up in the air about it.

I decided more than a month back to change some­thing impor­tant in the book. I still think Learn­ing by Doing is cru­cial and impor­tant. But I can’t see a way to pro­vide accep­tance tests alone (with no pseudocode or worked-out exam­ples) in an enticing-enough way that pro­vokes rea­son­able responses from the read­ers. That is, I got a lot of push­back from poten­tial audi­ence mem­bers who don’t actu­ally know how to write their own code based on accep­tance tests.

Le sigh.

So I’m try­ing what Ron Jef­fries did in his Extreme Pro­gram­ming Adven­tures in C#: describ­ing what I am think­ing, what moti­vates me, what I actu­ally do, and as a result I hope to make the process itself more trans­par­ent, not just the exter­nally vis­i­ble steps. As Ron pointed out a few weeks back when we chat­ted about it, this smacks of arro­gance. Who am I to think other peo­ple care about the mis­takes I’m mak­ing, or want to be mis­led by watch­ing me do stuff I sub­se­quently undo? Just to prove I “learn some­thing” from it?

Them’s the breaks. The alter­na­tive would be the crap one already has: pseudocode pre­sented as if it were the one “right” way to do stuff, and the inclu­sion of idiomatic (or worse, generic) libraries that the reader should re-create them­selves for every project, not bor­row and re-use indis­crim­i­nately just because it hap­pened to be in a book. In other words, bet­ter sorry than unsafe.

So inspi­ra­tion is a thing I’ll set aside and talk about sub­jec­tively, not in terms of heuris­tics which (as Abbott points out in his excel­lent account) can quickly become fos­silized and rit­u­al­ized as though they were “cor­rect” instead of use­ful.

So I picked up a book

I seem to like math­e­mat­i­cal recre­ations. Just the other day I sketched a lit­tle game thing that some­body should pick up and run with. If it sits around long enough, maybe I’ll do it myself, but not until the book is far­ther along.

In the pile of inter­li­brary loans that I picked up the other day was a trea­sure trove in one vol­ume: Geo­met­ric Fold­ing Algo­rithms: Link­ages, Origami, Poly­he­dra. Now the math­e­mat­ics of origami and stuff is all mod­ern and weird and “advanced” to my gen­er­a­tion; most of the actual math­e­mat­i­cal results came after I grad­u­ated from Uni­ver­sity, and appeared in fancy eso­teric math­e­mat­ics jour­nals even then. But there’s a con­stant cho­rus in New Sci­en­tist and Sci­ence News and stuff about new results, and there’s this other thing I used to do when I was a struc­tural biol­o­gist that involves fold­ing and abstrac­tions of phys­i­cal real­ity sur­pris­ingly sim­i­lar to those in origami. Which is the Holy Grail of a multi-trillion dol­lar indus­try at the moment, by the way.

I’m try­ing to put my fin­ger on what it is about some books— Mar­tin Gardner’s or Cliff Pickover’s or Ivan Moscovitch’s, for exam­ple — that makes them so inspir­ing. Is it the den­sity of open ques­tions? A tone that makes you won­der before dis­clos­ing any­thing? Some­thing inher­ent in this semi-abstracted recre­ational game stuff that makes it clear how to write a sim­ple com­puter pro­gram but unclear how to solve a prob­lem? Some­thing about puz­zles? I have no idea.

At any rate, this one has that same stuff on it. It’s fun.

I picked it up from the stack this morn­ing, opened to a ran­dom page, and started read­ing about one-dimensional origami. Now this is a book that’s fram­ing new work in mod­el­ing phys­i­cal sys­tems like folded paper (and pro­teins) by set­ting up the math­e­mat­i­cal con­structs and abstrac­tions in a tra­di­tional way. But there’s a heuris­tic I find myself adding to the other handy “kicks to the head”, espe­cially use­ful for GP work: What would it take to build a soft­ware sys­tem that “did” this?

So let’s think about one-dimensional origami for a second.

Does it fold?

Before they even get very far in the for­mal math­e­mat­ics of paper-folding, Demaine and O’Rourke talk a bit about rep­re­sent­ing one-dimensional folded struc­tures. You know, the tra­di­tional nec­es­sary and suf­fi­cient con­di­tions for deter­min­ing whether a thing is what you call it or not. Those core con­cepts, the stuff hang­ing off the “triv­ial” parts of tra­di­tional sci­ence and engi­neer­ing that you often elide because you’re just defin­ing your terms, that’s where there’s often low-hanging fruit for GP projects.

I rec­om­mend a browse through the excel­lent book, or just peek at Erik Demaine’s lec­ture notes on the sub­ject. We’re talk­ing about what starts out as a line seg­ment, which we crease at cer­tain (arbi­trary) points, and then press flat so that it pro­duces a sort of accor­dioned stack of squig­gles. Think of a cross-section through a piece of folded paper.

Let’s use paper, for a minute, and just assume for now we are fold­ing it only in the ver­ti­cal direc­tion. Just to get a slightly more vis­ceral sense of it.

Plop a (big) sheet of paper down on the table in front of your mind’s eye for me, OK?

We can make “moun­tain” or “val­ley” folds. Think of a “val­ley” fold as tak­ing either the left or right edge of the paper and fold­ing it upwards and across towards the oppo­site; think of “moun­tain” folds as tuck­ing the right or left edge down under­neath the stack. You can make these moun­tain or val­ley folds any­where between the edges of the paper, and as long as the creases are par­al­lel with the left and right sides you’re mim­ic­k­ing one-dimensional fold­ing. Just peek at the end of the sheet to lose the extra dimension.

There’s a tricky bit of math­e­mat­ics hid­den inside this simple-seeming phys­i­cal model, though: how do we cap­ture the phys­i­cal con­straint that keeps paper from pass­ing through itself?

Demaine and O’Rourke’s con­tri­bu­tions are emi­nent and inter­est­ing and well-considered. There are cunningly-crafted con­straints that cap­ture the phys­i­cal­ity of paper’s inabil­ity to cross itself, and iden­tify fea­si­ble flat fold­ings (and implic­itly fold­ings that aren’t “flat” at all), while main­tain­ing the integrity of the paper itself. In other words, you carry on that direc­tion, and you have a for­mal rep­re­sen­ta­tion that lets you do some fas­ci­nat­ing math­e­mat­ics and modeling.

But what would it take to build a soft­ware sys­tem that “did” this?

By “this” I mean the work of estab­lish­ing nec­es­sary and suf­fi­cient con­di­tions for real­is­tic folded lines. The implicit and tacit stuff a human being takes for granted when they have some notion of “cross­ing” or even “fold­ing” in their heads already.

Does this make sense?

So let’s ask a GP sys­tem to look at a stack of line seg­ments of var­i­ous lengths and “merely” say whether there is any way a sin­gle line seg­ment could have been folded that way, with­out cross­ing itself. Heck, there are prob­a­bly long-range sit­u­a­tions in which a partially-folded crum­ple would inter­fere with itself; let’s ignore those.

So here’s a quick sketch to help out:

1D-origami.png

The top two squig­gles are actual folded line segments.

The first is def­i­nitely fea­si­ble, in the sense that you can imag­ine crunch­ing up a pipe cleaner or fold­ing the edges-only paper I men­tioned above and mak­ing the cross sec­tion look like that.

The sec­ond it infea­si­ble, because the mid­dle leaf is too big for the space it’s in, and pro­trudes through the crease.

But I think we need to go far­ther for this to be rea­son­ably inter­est­ing. Think about how you would rep­re­sent these objects or sit­u­a­tions in your GP sys­tem. What is a “folded stack”? Do you start from a line seg­ment and intro­duce moun­tain and val­ley folds at cer­tain posi­tions in some order? Or do you start from the folded stack and rep­re­sent it as a series of orders in cer­tain posi­tions, like those I’ve shown below?

I’ve sketched five lit­tle sit­u­a­tions down there in the bot­tom, indi­cat­ing with the dot­ted green lines where the nom­i­nal “crease” points are. Which of those five might be fea­si­ble? Which of them are fea­si­ble but rep­re­sent a line seg­ment that’s not the same size as the orig­i­nal shown in the top two? Which if them is infea­si­ble even when you allow the raw mate­r­ial to be any size at all?

See how this works? Those are all rea­son­ably inter­est­ing ques­tions. I can totally see a set of a few hun­dred (or thou­sand) exam­ples and coun­terex­am­ples for each cat­e­gory. Some exam­ples (I assume) from every com­bi­na­tion of feasible/infeasible, same/different, congruent/incongruent, single/multiple pieces. It’s an inter­est­ing algo­rith­mic exer­cise to fill in that chart with dia­gram­matic exam­ples. Train­ing and test data are yours for the tak­ing then.

But what this sort of project wants from us, as GP folks, is a bit of onto­log­i­cal work.

I’m the one who does this for a liv­ing, so let me pre­empt your ver­sions now:

  • a Diagram is a list of Stretches
  • each Stretch has a numeric length attribute, and a list Segments attribute
  • each Segments list con­tains inte­gers rep­re­sent­ing the seg­ments present, in top-to-bottom order, num­bered from 1 at the top and increas­ing downwards

So for the five exam­ples I’ve shown, each would have three Stretches. Say their lengths are 4, 11, and 5 respec­tively. And the Stretches would con­tain these Segments lists, respectively:

  1. [1],[1,2,3],[2]
  2. [1],[1,2,3],[3]
  3. [1,2],[1,2],[1,3]
  4. [1,3],[1,2,3],[3]
  5. [1,2],[2,3],[2]

Notice that the only dif­fer­ence between the fea­si­ble and infea­si­ble exam­ples (the first two) is the third Segment. What sort of “think­ing work” does your GP-developed algo­rithm need to do in order to dif­fer­en­ti­ate use­fully between these?

Notice that the first and third are both fea­si­ble, but that the third doesn’t add up to the same amount of mate­r­ial. Again, what does your GP-developed algo­rithm need to “know” to be able to iden­tify which dia­grams might and which might not be the same line? On the other hand, if we think of the Segment lengths as pro­por­tions rather than explicit mea­sure­ments, we’re sud­denly allow­ing the third dia­gram as well; in some sense it’s con­gru­ent to the first, but not identical.

And so on.

What sort of manip­u­la­tions of these input struc­tures might a general-purpose clas­si­fi­ca­tion algo­rithm do? What, in other words, is the Answer Lan­guage like?

Eureqa II, aka Formulize

Posted on by
4

Some­how in the last few months I’d missed the seri­ous update of Michael Schmidt’s Eureqa pack­age for sym­bolic regres­sion. Now avail­able for Win­dows, Linux and Mac plat­forms, and fea­tur­ing a very nice cloud inte­gra­tion for addi­tional pro­cess­ing, this looks like a ground-breaker for usabil­ity and under­stand­abil­ity in Sym­bolic Regres­sion applications.

Here’s an intro­duc­tion video. Michael does a much bet­ter job explain­ing it suc­cinctly than I’ve seen before:

Inter­est­ingly, I stum­bled across Michael’s update because I was writ­ing to Cosma Shal­izi, fish­ing for feed­back from the Very Impor­tant Thinkers attend­ing the Ockham’s Razor Work­shop regard­ing (mod­ern, multi-objective) sym­bolic regres­sion of the style Michael’s project embod­ies. A lot of these same notions of Pareto Sym­bolic Regres­sion were devel­oped orig­i­nally by Mark Kotanchek, Katya Vladislavl­eva and Guido Smits from Dow Chem­i­cal and Evolved Ana­lyt­ics, recently released in Data­Mod­eler for Math­e­mat­ica.

It’s fas­ci­nat­ing to me how lit­tle pro­fes­sional atten­tion crosses in either direc­tion between the machine learning/statistical the­ory folks and genetic pro­gram­ming folks. Impor­tant work in both fields is essen­tially invis­i­ble across that divide. As the years go by the dichotomy is get­ting some­how deeper, to the point where I expect they’re just going to run into one another headed the other way, when they both cir­cum­nav­i­gate the net­work of All Pos­si­ble Approaches to Sci­ence and Engi­neer­ing in their rush apart….

Note, as clar­i­fi­ca­tion: I am not includ­ing any chap­ters on sym­bolic regres­sion in the book. Sym­bolic regres­sion is an amaz­ing and rapidly matur­ing field, and I count it pretty much “done” with the release of Data­Mod­eler and For­mulize. From here on, it’s a field in its own right, not least because the tricks and tech­niques use­ful in address­ing quan­ti­ta­tive mod­el­ing projects like these are quite dif­fer­ent from the qual­i­ta­tive and struc­tural mod­el­ing projects we’re doing in the book.

Still, down­load and play with Eure­qua II, and see what you can understand.

Protection against surprise

Posted on by
3

The fol­low­ing is an extract from the immi­nent Prag­matic GP book. I’m post­ing it because it’s the first place I’ve man­aged to tie together some­thing that’s been bug­ging me for years, about the fail­ures so many Very Smart pro­gram­mers and com­puter sci­en­tists have expe­ri­enced, over and over in some cases, when try­ing to build use­ful, inter­est­ing, robust GP sys­tems that solve com­plex prob­lems. I sus­pected that part of the prob­lem was in their pro­gram­ming style, but I real­ize here that col­lab­o­ra­tion habits are really the key to suc­cess in GP. More on that later; now I’m going to go pub­lish the rest of this project.

This Cargo-bot project will be the first of a half-dozen we will work through together, so it seems impor­tant to say a bit about what I expect.

As I said, my inten­tion for this effort is that you learn by doing, that is by build­ing your own GP sys­tems, bottom-up, more or less from scratch. But it’s the nature of com­puter pro­gram­ming that it’s sur­pris­ingly dif­fi­cult to com­mu­ni­cate, except by exam­ple. There are some abstruse math­e­mat­i­cal ways, and some hand-wavey (but over-constrained) indi­rec­tions like that awful pseudocode crap, but really in the end I think the only way for you to purely learn by doing would be to write code with me — in person.

More­over, there are a lot of inter­est­ing and impor­tant sub­jec­tive aspects to suc­cess­fully build­ing a GP project, that don’t come across in code as such. Why is that there? What does this do? How did you make that jump? Indeed, the lack of those sub­jec­tive aspects in the other writ­ing on GP are what’s sparked me sit­ting here typ­ing today: they’re cru­cial; they’re the Lan­guage of the Project.

So at least for this first project, I’ve decided to write the code myself. There is still no oblig­a­tion that you use the same pro­gram­ming lan­guage (Ruby) that I will — in fact, I hope you won’t. I hope you’ll re-write the code in some other lan­guage I’ve never heard of, and post it on GitHub, and share it with the other folks out there as more exam­ples of how this can be done. But what­ever you do, it had bet­ter still have all the same accep­tance tests I’ll be describ­ing myself, and demon­strate (auto­mat­i­cally!) that all those fea­tures are present in your code, and the tests pass.

Beyond the fact that it will sur­face some of the impor­tant sub­jec­tive aspects of the project that are nor­mally elided in descrip­tions of GP, there’s a sec­ond (and more impor­tant) rea­son I’m going through this process of writ­ing the code in plain sight.

Peo­ple don’t like being sur­prised. Remem­ber what I’ve said a few times already: GP (when it works) accel­er­ates the process of dis­cov­ery, which is to say you being sur­prised by some unex­pected result or pat­tern.

I’ve found that many well-trained folks, young and old, who have learned and inar­guably mas­tered com­puter sci­ence and pro­gram­ming to the point where they can squint real hard at a prob­lem and smash-key their way into a text edi­tor and in a few hours pro­duce some exotic self-contained crys­talline beauty of an algo­rithm… well, those peo­ple often react poorly to being sur­prised. They are so used to being right, to intu­it­ing what they’re going to do, and then doing just that; they ham­mer out the code they envi­sion (though maybe hit­ting the back­space key a lot) with­out ever hav­ing to speak to another per­son or do much more than rtfm now and then.

In my expe­ri­ence, those peo­ple have the most trou­ble build­ing and using a GP sys­tem. This is noth­ing to do with their cod­ing abil­i­ties, or their under­stand­ing of sys­tem design or syn­tax or parsers or any of that com­put­ery stuff. It has a lot to do with them see­ing the thing they build — the GP soft­ware process — make the same sort of blue-sky, intu­itive, often sur­pris­ing design deci­sions that they make. Any well-made GP sys­tem will quickly spit out “design deci­sions” that may or may not make sense (it’s hard to tell some­times), but which in any case are noth­ing like what the pro­gram­mer expected. And in my expe­ri­ence Very Smart pro­gram­mer folks are not often equipped to deal with that.

This is a prob­lem of com­mu­ni­ca­tion, not code-writing. I think it may be asso­ci­ated with a bun­dle of habits Very Smart pro­gram­mers develop in our cul­ture, which tend to keep them from hav­ing to dis­cuss what and why they are writ­ing all the indi­vid­ual lit­tle incre­men­tal bits of code they write. They’re often so smart, they need not have any help visu­al­iz­ing an entire start-to-finish solu­tion in their heads, or do any explicit intro­spec­tion, or spell out why they have made one deci­sion ver­sus another. But if any­body with some dif­fer­ent vision of an equally effec­tive start-to-finish solu­tion starts chang­ing their code­base, or changes the rules or goals in mid-project, or argues with them about their basic toolkit… well, it doesn’t go well. More often than not they freak out, as a mat­ter of my expe­ri­ence. Some­times there is slamming.

This is not a crit­i­cism, but rather a diag­no­sis: Very Smart pro­gram­mers are, in my expe­ri­ence, eas­ily thrown off track by hav­ing unex­pected changes made to the project they’re work­ing on. Or by cop­ing with unex­pected or emer­gent behav­ior that arises dur­ing a project. Or by hav­ing their fun­da­men­tal assump­tions about a domain ques­tioned. Or by hav­ing to inte­grate or adapt to an alter­na­tive design approach.

Any well-built GP sys­tem, work­ing on any inter­est­ing project, will most def­i­nitely do all those things.

I am not a Very Smart pro­gram­mer. I’ve had to stum­ble my way through all the cod­ing I’ve ever done, and I have very poor visualizing-everything-start-to-finish-in-my-head skills. So in the last decade or so, pro­gram­ming in my not-Very-Smart way, I’ve been obliged to speak with other peo­ple a lot, and explain what it is I’m doing in each iter­a­tive deci­sion I make, and ask them what they meant by what they were doing, and all those other things Very Smart pro­gram­mers are able to do auto­mat­i­cally with­out con­sult­ing other people.

Along the way, I’ve dis­cov­ered that there is a set of tools for that. Com­mu­ni­ca­tion and col­lab­o­ra­tion tools. And I’ve found that those same tools, or at least very sim­i­lar ones, help to deal with this weird “col­lab­o­ra­tion” thing one needs to do with a GP sys­tem. It’s not col­lab­o­ra­tion, and it’s not com­mu­ni­ca­tion; but it is some­thing a lot like the mutual men­tal mod­el­ing we do when we speak to one another (which, you may be amused to dis­cover, is some­times referred to as Prag­mat­ics).

So as I go along, in my not-Very-Smart way, I am going to be build­ing in some of those safe­guards I’ve learned, and using tools that were orig­i­nally designed to fos­ter col­lab­o­ra­tion between human beings work­ing together on code. You, since you may be Very Smart, might not have encoun­tered these before; in my expe­ri­ence many pro­gram­mers who work in the Uni­ver­sity or other uncol­lab­o­ra­tive set­tings may have missed them. Worse, you may have encoun­tered them (for exam­ple as prac­tices that form part of the method­ol­ogy referred to as Agile by some folks), and dis­missed them as being unim­por­tant to you in your work-life.

They form a cru­cial buffer­ing inter­face, one that will help you avoid being sur­prised into fail­ure. Do not ignore them.

The Three Languages of GP

Posted on by
3

[This is a draft of an intro­duc­tory chap­ter of the book; expect some changes as I fin­ish up the first par­tial release. Also, I note some links and cross-references don’t trans­late to the blog directly.]

Three Lan­guages

I like to say that suc­cess on GP project involves work­ing in three lan­guages. Look again at the 3×5 card, and you’ll see hints of them all there. I call them the Lan­guage of Answers, the Lan­guage of Search, and the Lan­guage of the Project.

The Lan­guage of Answers: What?

A GP sys­tem itself doesn’t “think”. It’s a sys­tem for accel­er­at­ing the explo­ration of alter­na­tive answers to a formally-stated ques­tion. A sin­gle project will often shift to explore sev­eral dif­fer­ent ques­tions: mat­ters of whim­si­cal open-ended curios­ity or earnestly ded­i­cated pur­po­sive sci­ence. But you should pay atten­tion to only one at a time.

To be able to treat any par­tic­u­lar ques­tion using GP, and explore the vast num­ber of diverse alter­na­tive answers, you will need to write code that embod­ies your inter­ests and goals.

Set­ting up a GP project obliges you to do some cod­ing work. Usu­ally the major­ity of your work will be the design and imple­men­ta­tion of a domain-specific lan­guage. It doesn’t have to be very com­pli­cated, but it will need the flex­i­bil­ity and capac­ity to describe any inter­est­ing answer to your project’s ques­tion of the moment — the “smart” answers, and also the “dumb” ones. After all: your prob­lem is inter­est­ing because you don’t know which answers are smart and which dumb.…

I pre­fer to call the scripts you write in this domain-specific lan­guage — as inter­preted in the con­text of your prob­lem — “Answers”. In the GP lit­er­a­ture you’ll see them called “indi­vid­u­als” and “genomes”; those are his­tor­i­cally impor­tant terms, but they carry a lot of poten­tially mis­lead­ing metaphor­i­cal bag­gage. Here we’ll stick with the term Answers, to remind us that they are con­tin­gent on the prob­lem you’re considering.

You’ll have seen folks list­ing some of the poten­tial appli­ca­tion of GP, talk­ing about evolv­ing “pro­grams” and “strate­gies” and “puz­zle solu­tions” and “mol­e­cules” and “con­trollers” and “robots”… all kinds of com­plex actual things. As language-using humans, some­times we mis­take our rep­re­sen­ta­tions of con­cepts for the con­cepts them­selves. Remem­ber: a script doesn’t do any­thing until we run it on a par­tic­u­lar inter­preter or com­piler, and even then only with cer­tain vari­ables bound to mean­ing­ful values.

A strat­egy is a mean­ing­less poem until you invoke it in the con­text in which it was con­ceived; we can­not mean­ing­fully read a “pure strat­egy” with­out know­ing what war or game or busi­ness it was meant for. A real mol­e­cule is not a string of “ACGT”, or even a pretty col­ored pic­ture of lit­tle candy balls on sticks, but nonethe­less when we “evolve mol­e­cules” we’re evolv­ing balls on sticks or strings of let­ters… then inter­pret­ing those in some mol­e­c­u­lar sim­u­la­tion. A con­troller for a robot is only a string until you upload it to a phys­i­cal robot or a sim­u­la­tion so you can see what might hap­pen when it runs. A plan for trad­ing stocks is mean­ing­less — and risky — with­out also con­sid­er­ing the par­tic­u­lar his­tor­i­cal con­text and the spe­cific trade exe­cu­tion sys­tem for which it was devel­oped. And so on. An Answer needs both pieces of infra­struc­ture: a state­ment or script writ­ten in a domain-specific lan­guage (often one you design), and also a for­mal set­ting in which the func­tion embod­ied in a script can be expressed and explored meaningfully.

If the Answers in your project are sim­ple DNA sequence strings like ACGTCTAGCA..., you’ll also need to obtain (or write) a sim­u­la­tor that trans­lates those strings into pro­teins, or folds them, or tests them for tox­i­c­ity, or does what­ever a com­puter needs to do in order to deter­mine the salient aspects of their func­tion. If you want to evolve robot con­troller scripts, you’ll need a real or a sim­u­lated robot that can exe­cute your con­troller scripts and reveal their function.

This is true even for the sim­plest and most com­mon appli­ca­tion of GP1, sym­bolic regres­sion — fit­ting math­e­mat­i­cal func­tions to train­ing data. The most com­mon approach is to rep­re­sent these math­e­mat­i­cal equa­tions as S-expressions, a form famil­iar to many Com­puter Sci­en­tists who learned to pro­gram in Lisp. For exam­ple, ( + x ( / 2 9 ) ) is an S-expression rep­re­sent­ing the func­tion $y=x+\frac{2}{9}$.

But notice that the S-expression script ( + x ( / 2 9 ) ) is not in itself the math­e­mat­i­cal func­tion (unless you hap­pen to be run­ning a Clo­jure inter­preter in your head or some­thing). Even though it’s very close to the runnable code, it’s not fully an Answer until you express it by pars­ing and eval­u­at­ing its out­put value in an inter­preter — one in which $x$ has a num­ber assigned to it.2

Even when there’s a “general-purpose” GP-ready full-featured lan­guage avail­able — some­thing like Clo­jush or even a human-readable lan­guage like Java—you’ll usu­ally need to expand it with libraries or cus­tom code to include domain-specific vocab­u­lary. And for rea­sons we’ll dis­cover in the first project, some­times when you use a full-featured lan­guage, you’ll also need to trim back its capacity.

Focus for a moment on the phrase “domain-specific” and how it needs to cut both ways: You don’t typ­i­cally find for...next loops or set-theoretic oper­a­tions in sym­bolic regres­sion projects, because peo­ple are ask­ing for arith­metic Answers, and those peo­ple rarely see for...next loops in arith­metic. You can fit data algo­rith­mi­cally using loops and Boolean oper­a­tors and bit-shifting — after all, that’s how com­put­ers them­selves do it. But you won’t find a shift_right oper­a­tor in most off-the-shelf sym­bolic regres­sion pack­ages, because the Answers that arise which use it to explore the prob­lem would “feel weird”.

If you’re work­ing on a project where you want to explore string-matching algo­rithms to clas­sify DNA into genes and introns, your Lan­guage of Answers will prob­a­bly include some­thing about reg­u­lar expres­sions. Not a lot about sin() and cos().

If you’re work­ing on a project where you want to explore game-playing algo­rithms for a text-based dun­geon crawl, your Lan­guage of Answers will prob­a­bly include prim­i­tives like look and if and fight. And maybe if you’re fancy, you’ll roll in a library for cre­at­ing deci­sion trees so your adven­turer can learn. But again, not a lot of sin() or cos() hap­pen­ing in the ol’ Crypt of Creatures.

And just to prove I’ve got noth­ing against trigonom­e­try as such: If you’re work­ing on a project where you want to explore the set of plane geom­e­try dia­grams which can be con­structed using a straight-edge and com­pass, you will almost cer­tainly want some sin() and cos() float­ing around in the mix.

So GP is “auto­mated” how exactly?

No escap­ing it. In almost every GP project, you will need to hand-code this Lan­guage of Answers. Both parts: not just the “scripts” but also the con­tex­tu­al­iz­ing sys­tem used to inter­pret scripts and express their func­tions meaningfully.

Does this seem like a lot of effort? It’s not, when you put it in per­spec­tive. Real­ize that when you explore a prob­lem with GP, you should expect to exam­ine mil­lions of alter­na­tive Answers. In tra­di­tional approaches to problem-solving, you might (if you’re Ever So Smart), be able to con­sider a few dozen— the ones you can keep in your head and note­books. Even if you use algo­rith­mic tools like lin­ear pro­gram­ming, real­ize they are para­met­ric explo­rations of dif­fer­ent con­stant assign­ments… within one Answer at a time.

If you want access to the mil­lions instead of the dozens, you need to put in the up-front work to pro­gram­mat­i­cally rep­re­sent the struc­ture of Answers, and also hook up the mech­a­nisms needed to express them func­tion­ally. That’s the invest­ment you make.

The Lan­guage of Search: How?

“Lan­guage of Search” is my catch-all for the innu­mer­able tricks of the GP trade. I count any­thing that changes the sub­set of Answers you’re con­sid­er­ing, includ­ing ran­dom guess­ing and assign­ing them a score based on their per­for­mance in context.

There’s all the famil­iar biologically-inspired stuff like crossover, muta­tion, selec­tion, and the more fan­ci­ful manip­u­la­tions. And also the idiomatic tools we use to imple­ment learn­ing or evolv­ing or improv­ing: pop­u­la­tions, back-propagation, selec­tion, sta­tis­ti­cal analy­sis, 1+1 Evo­lu­tion­sstrate­gie.… Basi­cally any­thing and every­thing that reduces the amount of per­sonal atten­tion you need to pay to all those alter­na­tive Answers.

There is no par­tic­u­lar “right way” to use or com­bine these com­po­nents. They’re really all design pat­terns, and they are used dif­fer­ently in dif­fer­ent geo­graph­i­cal regions and schools; they are most like the mythic mar­tial arts styles you see in movies, and the par­tic­u­lar moves one school or Mas­ter may teach his stu­dents. But just as the mar­tial arts share a pur­pose (if not an atti­tude), the many parts of the Lan­guage of Search address one ques­tion: Based on what you have dis­cov­ered already, how do you iden­tify new Answers that will be more satisfying?

Every GP project uses selec­tion in one form or another, so let’s look at that more closely. Say we’ve built a GP sys­tem with a pop­u­la­tion of 100 Answers, and we want to design a process to pick “par­ents” in order to breed a new gen­er­a­tion. There are lit­er­ally hun­dreds of approaches, but here are four. We might:

  • …pick two par­ents with equal prob­a­bil­ity and remove them from the pop­u­la­tion; breed them to pro­duce two or more off­spring; keep the two best-performing family-members (includ­ing, pos­si­bly, the par­ents), and replace those win­ning fam­ily mem­bers back into the population.
  • …pick two par­ents ran­domly from the pop­u­la­tion, using a bias towards better-scoring ones; breed those two par­ents to pro­duce one off­spring, and set it aside in a new “gen­er­a­tion”; con­tinue (with replace­ment of par­ents) until you have as many in the next gen­er­a­tion as you did in the last.
  • …pick two par­ents at ran­dom from the pop­u­la­tion, with uni­form prob­a­bil­ity; breed them, and return the par­ents and the off­spring to the pop­u­la­tion; con­tinue until the pop­u­la­tion size is dou­bled; destroy half the pop­u­la­tion, culling it back down to the size where it started.
  • …pick ten dif­fer­ent indi­vid­u­als from the pop­u­la­tion with uni­form prob­a­bil­ity; choose the best one of that tour­na­ment to be the first par­ent; repeat for the sec­ond par­ent; breed, and then… (&c &c)

These are all per­fectly rea­son­able and prac­ti­cal ways of choos­ing answers to breed and cull from a pop­u­la­tion. Three of them have for­mal names, even. Occa­sion­ally one may feel “bet­ter” than another for a given project, but none is intrin­si­cally bet­ter in all situations.

My point in list­ing them is to high­light the obvi­ous fact that they’re all just recipes in a for­mal lan­guage: the lan­guage I’m refer­ring to as the Lan­guage of Search. The “prim­i­tives” in this lan­guage are things you can surely see in my ver­bal descrip­tions: eval­u­a­tion, sub­set­ting and sam­pling, breed­ing (itself a whole blan­ket process that usu­ally refers to “mix­ing up Answer scripts with one another”)… and of course the basic pro­gram­ming infra­struc­ture of iter­a­tion and con­di­tional exe­cu­tion and sort­ing.

All nor­mal com­puter pro­gram­ming stuff, though maybe a bit more sto­chas­tic than you’re used to. But note that the Lan­guage of Search isn’t lim­ited to code: There’s an impor­tant class of GP sys­tems known as “user-centric” or “inter­ac­tive”, in which a real live human being makes con­scious deci­sions as part of the algo­rithm. This is a valu­able tool for explor­ing mat­ters of aes­thet­ics and sub­jec­tive judge­ment. (And we’ll build some­thing like that in a later project.)

The Lan­guage of Search is huge, but it’s not oner­ous. While you almost always need to design and imple­ment your project’s Lan­guage of Answers, even the most “advanced” tools in the Lan­guage of Search toolkit are sim­ple in com­par­i­son. Things like “chop up a string and mix up the parts” or “change a token in a script to a ran­dom value” or “assign a score to an Answer by run­ning it in con­text, given spe­cific input conditions”.

When I keep say­ing GP is sim­ple, that’s what I mean: the Lan­guage of Search is sim­ple. It’s really just a big cat­a­log of small parts you cob­ble together, and there’s absolutely no rea­son you should try to learn all the tools any­body has ever tried, or use more than three or four basics in a given project.

And that would be your cue to ask: Why then does GP have a rep­u­ta­tion for being so hard?

I’m glad you asked.…

The Lan­guage of the Project: Why?

Almost all GP writ­ing focuses on the Lan­guage of Search, either spelling out new tools and algo­rithms, or hav­ing lit­tle bench­mark­ing con­tests between vari­a­tions. A bit of the writ­ing — mostly the­o­ret­i­cal Com­puter Sci­ence — touches on the Lan­guage of Answers under the head­ing “rep­re­sen­ta­tion theory”.

As far as I know, very lit­tle has been writ­ten about this stuff I’m call­ing the “Lan­guage of the Project”. Yet I argue it’s the most impor­tant of the three — not least because it’s the decid­ing fac­tor when it comes to pre­dict­ing whether a project will suc­ceed or fail.

The Lan­guage of the Project is the lan­guage we use to talk about our­selves, in our roles as part of the project. It’s the fram­ing we use to express what we want, and why. It’s our expres­sion of the rea­sons one Answer is more sat­is­fy­ing than another, and our con­sid­er­a­tion of the pos­si­bil­ity that no sat­is­fy­ing Answer exists. It’s the lan­guage we use to process the sur­prises GP inevitably throws our way.

Big chunks of my Lan­guage of the Project fall in the realm of well-studied dis­ci­plines: “user expe­ri­ence”, “project man­age­ment” and “domain mod­el­ing”. Why do I feel it’s impor­tant to con­coct a catch-all neol­o­gism just to lump together those esteemed fields for this spe­cial GP junk? Worse: why is a tech­ni­cal com­put­ing book about “arti­fi­cial intel­li­gence” get­ting all touchy-feely and psychological?

Sim­ple answer: Because peo­ple don’t like being surprised.

That may ring a bell, since when you check you will see that the sub­ti­tle of this very book is “The Engi­neer­ing of Use­ful Sur­prises”. And I specif­i­cally argued ear­lier that GP is “a pros­the­sis for accel­er­at­ing innovation” — innovation in the sense of sur­prises.

Yup. And that’s the biggest obsta­cle in the way of broader adop­tion of GP, and also the biggest obsta­cle you per­son­ally will have work­ing on your own projects: Peo­ple don’t like being sur­prised.

You and your habits

A lot of folks seem to have decided that GP is “auto­matic”; that it’s used for “auto­matic search”, or “auto­matic pro­gram­ming”, or build­ing “inven­tion machines” that spit out inven­tions that are of “human-competitive” qual­ity. Those folks won’t think my third Lan­guage is worth their attention.

To them, GP — and arti­fi­cial intel­li­gence more gen­er­ally — is a sort of self-contained box of magic think­ing stuff. I won­der if maybe those peo­ple have read post hoc reports of suc­cess­ful GP (or AI) projects, with­out con­sid­er­ing all of what hap­pens over the course of an actual project: a lot of non-artificial human think­ing, typ­ing, com­pil­ing, swear­ing, whiteboard-scribbling, and con­ver­sa­tion… fil­tered through a series of iter­a­tive pro­gram­ming attempts and argu­ments and writ­ing, until even­tu­ally an encour­ag­ing result was pub­lished. If you don’t count that as part of the project, then of course you shouldn’t think a GP (or AI) sys­tem includes the project team rewrit­ing the algo­rithms, or the plan­ning sketches, or the con­ver­sa­tions and read­ing, or the re-starts with dif­fer­ent set­tings to try to get more con­sis­tent results, or the sta­tis­ti­cal analy­ses try­ing to “tune” or “speed up” the thing, or even the story writ­ten down in the paper that describes what hap­pened.

And if you’re will­ing to draw the bound­ary around the sys­tem that way, in a way that leads you to think GP (or AI) is a self-contained magic box of think­ing stuff that peo­ple stand in front of and pat and hug and even­tu­ally coax intel­li­gence out of… well you ought to get started now, because time’s-a-wastin’.

But while you’re occu­pied in pat­ting and fos­ter­ing self-organized cre­ative urges, muse about it my way for a minute.

Recall that the Lan­guage of Answers is some­thing you will almost always build from scratch. It’s not just domain-specific, it’s often problem-specific. The only time you can get away with using a pre-cooked Lan­guage of Answers is when you’ve uncon­sciously selected a prob­lem that makes it eas­ier to stom­ach reuse, or reduced the domain-specific qual­i­ties to raw num­bers and true/false decisions.

Given that reminder: How do you design the con­stants, vari­ables and oper­a­tors to use in your project’s Lan­guage of Answers? Which instruc­tions will be more help­ful in mak­ing inter­est­ing Answers? Which will be too weird? How do you ensure every Answer will be syn­tac­ti­cally cor­rect, or seman­ti­cally con­sis­tent? Or do you have to? How do you know whether your Lan­guage of Answers is capa­ble of rep­re­sent­ing any sat­is­fy­ing Answer at all, let alone an “opti­mal” one? How do you tell and what do you do when your GP sys­tem is ignor­ing impor­tant tools you want to see it use?

Those are ques­tions from the Lan­guage of the Project. No mat­ter where you draw your sys­tem lines, a per­son needs to ask and answer these ques­tions. Every time, for every project, for every prob­lem. And a per­son needs to design and imple­ment the solu­tions to them, using the other tools at their dis­posal. None of that is “automatic”.

And you may also recall that the Lan­guage of Search is a bulging toolkit, full of lit­er­ally thou­sands of design pat­terns and rules of thumb for manip­u­lat­ing answers in context-dependent use­ful ways. I can describe six­teen muta­tion algo­rithms with­out break­ing a sweat; then you’ve got crossover, and sim­u­lated anneal­ing, and steady-state pop­u­la­tion dynam­ics, and demes, triv­ial geog­ra­phy, hill-climbing, ini­tial­iza­tion bias­ing, multi-objective sort­ing, par­ti­cle swarms, automatically-defined func­tions, ver­ti­cal slic­ing, age-layered pop­u­la­tions.… Any rif­fle through any GP book will give you fifty more.

Given that reminder: How do you pick the mech­a­nisms for search and learn­ing in your project? How do you know which com­bi­na­tion may be best or even use­ful for your prob­lem? What do you even watch in order to decide whether a GP search is “work­ing” or not? Should you let your cur­rent search run longer, or start it over again? If you start it over, should you change the para­me­ters a bit, or try a dif­fer­ent design pat­tern? What do you do when it gives you an answer that “solves the prob­lem” in a totally stu­pid way?3

A per­son needs to mind­fully adapt the struc­ture of the project to fit the dynamic con­text of their wants and knowl­edge, and man­age the sys­tem into giv­ing them the answers they will find satisfying.

My “Lan­guage of the Project” isn’t iden­ti­cal with user expe­ri­ence, or project man­age­ment, or domain mod­el­ing, or even their union. Those dis­ci­plines are admirable, but they are designed for unac­cel­er­ated human-powered projects.

“Excuse me: What just happened?”

You write soft­ware. I know this, or you wouldn’t bother read­ing this far. If a project isn’t giv­ing you sat­is­fy­ing answers — whether it involves GP or not — then you (per­son­ally) need to check that it’s imple­mented cor­rectly. And when you’re con­vinced it is run­ning as intended, you then (per­son­ally) need to reflect and decide whether it’s doing what you want it to. And if you decide that it isn’t, then you (per­son­ally) need to either change how it’s writ­ten, or change what you think it’s for.

In non-GP projects — soft­ware devel­op­ment or finan­cial or home improve­ment or med­ical research projects — there’s a rea­son­able sense that one can “re-start”. But of course in the con­text of human-powered projects, “re-starting” is never mis­un­der­stood to mean “from the same ini­tial con­di­tions”. You (per­son­ally, with all the other human beings on your team) “re-start” hav­ing learned some­thing use­ful and help­ful. You intend to do some­thing dif­fer­ently the sec­ond time around, and you don’t have to con­cen­trate very hard on remem­ber­ing to change stuff.

This dif­fer­ence between you-before-the-first-try and you-after-the-first-try doesn’t get men­tioned, because it’s such a fun­da­men­tal fact of life that it goes with­out say­ing. But notice that you (per­son­ally) are under­stood intu­itively to be part of the problem-solving sys­tem before and after the “re-start”.

Just the other day I was work­ing on the code for a later sec­tion of this book: the part where we will evolve Conway’s Game of Life. I found that the GP sys­tem I started with was hav­ing a lot of trou­ble pro­duc­ing inter­est­ing answers. I worked a few days, try­ing to get it to do what I expected.

And then I real­ized that it had been work­ing the whole time. I mean totally work­ing. It gave me the best pos­si­ble answer, every time.

Only then did I real­ize that the ques­tion I was ask­ing was super bor­ing. There was only one right answer, and the GP sys­tem I built kept giv­ing me that answer. Imme­di­ately.

Now if you are one of the folks who want to think GP is a self-contained box of magic think­ing stuff, this might seem like a good out­come, and not a prob­lem. Who wouldn’t want an “opti­miza­tion algo­rithm” to give them The One Right Answer?

Well, me. And you, I expect.

I would sound like this, if I were on stage at the Amaz­ing Answer Machine Show: “Ladies and Gen­tle­men, I am think­ing of a spe­cial algo­rithm! I have pro­vided this, The Box of Magic Think­ing Stuff, with 512 carefully-chosen exam­ples and a col­lec­tion of use­ful tools, none of which in itself is the algo­rithm. By recom­bin­ing those tools in a very com­pli­cated way while I stand over here, The Box will now guess the func­tion I’m think­ing of in a mat­ter of mere moments.…”

A card trick. Boring.

What did I do then? I revised my notion of the project’s goals. I “re-started”, and in doing so I changed the story I’d been telling myself, the ques­tions I was ask­ing, and I expanded the Lan­guage of Answers accordingly.

The answer my GP sys­tem gave me was a sur­prise. One I wasn’t men­tally pre­pared to under­stand, not least because it hap­pened in a mat­ter of sec­onds where I was expect­ing it to take some time. When I finally parsed what it kept repeat­ing, I had a sec­ond sur­prise: the ques­tion I had asked was boring.

If I had been work­ing in a tra­di­tional unac­cel­er­ated way — with a white­board or a yel­low legal pad, chew­ing on the end of a pen and pac­ing with my hands behind my back like a think-tank car­i­ca­ture — I might have frowned and erased some stuff, or crum­pled up a page or two and made a cup of tea.

I wouldn’t have been surprised.

Mixed bless­ings

Intro­spec­tion is hard. Most peo­ple, for what­ever rea­son, don’t like to ques­tion their assump­tions. They like cer­tain­ties and prov­able cor­rect­ness, famil­iar mod­els and known best prac­tices, math­e­mat­i­cal rigor pre­sented on a buoy­ant comfort-cushion of assumptions.

That’s what I mean when I say they don’t like to be surprised.

Sur­prises aren’t just pleas­ant eureka moments, they’re also the oh shit moments. GP can be use­ful as an “inno­va­tion pros­the­sis” because it short­ens the time between those eureka surprises.

GP feels com­pli­cated and dif­fi­cult and annoy­ing because it also short­ens the time between oh shit sur­prises. And it can’t tell the difference.

GP projects often fail because novices run into oh shit sur­prises before any eureka ones. They’re cul­tur­ally mal­adapted to cope with this dis­or­der: they’re often Very Smart Com­puter Sci­en­tists or early-adopter domain experts, and they can pick up some infor­ma­tion from the books or the nerds down the street, and they start dab­bling in what I’ve called the Lan­guages of Answers and Search.

But nobody ever tells them about these inevitable oh shits.

I going to focus on this cobbled-together “Lan­guage of the Project” exactly because of those issues. I’ve watched dozens of Very Smart engi­neery peo­ple dive in and (metaphor­i­cally) drown in GP. We need to erase the tra­di­tional bound­ary between what you think of as “the project” and you (per­son­ally), the “researcher”.

This is not to advance some Agilist social agenda, but rather as a cop­ing mech­a­nism. Your best and most use­ful habits as a Very Smart Per­son are based on your expe­ri­ences think­ing very hard and hand-coding solu­tions to prob­lems one at a time, and con­sid­er­ing a few dozens of alter­na­tives. With­out any thousand-fold enhancement.

I see it often: Smart per­son down­loads some pack­age; writes some code; fol­lows along with a tuto­r­ial and builds a GP sys­tem and—boom—it starts spit­ting out ten thou­sand reasonable-sounding solu­tions every hour. Already they’re way out­side the range of what their habits pre­pare them for. But they’re Very Smart, and so they look at the answers they have so far, and they fid­dle with some things and change some para­me­ters… and—boom—in an hour they have ten thou­sand com­pletely dif­fer­ent answers.

“What just happened?”

When it works, answers emerge from a GP sys­tem, in the sense of emer­gent behav­ior. Good Answers and bad ones. But real­ize they can’t emerge from a GP sys­tem of the sort I’m teach­ing you about — the sort that includes you (per­son­ally) as one of the com­po­nents — until you (per­son­ally) exam­ine those Answers and even­tu­ally decide you’re sat­is­fied. You can’t suc­ceed unless you can cope with the acceleration.

Here’s one of the core ques­tions in GP (and AI) research, a deep and trou­bling one that many man-years of research have been spent con­sid­er­ing: How do you know whether you should (a) keep a GP sys­tem run­ning, on the off chance it will get bet­ter soon and give you new unex­pected answers, or (b) stop it and start over from dif­fer­ent ini­tial conditions?

If you think GP (and AI) is a self-contained magic box of think­ing stuff: You don’t.

If you real­ize you’re a core com­po­nent in the GP sys­tem: Pick the one that is more sat­is­fy­ing to you at the moment, and try the other if that doesn’t work out.

And here is a deep-rooted prob­lem affect­ing all of search and opti­miza­tion, not just in AI but all com­pu­ta­tional approaches: How do you know a pri­ori which search tech­nique will pro­vide reli­ably bet­ter answers for a given problem?

If you think of the pro­gram as a self-contained box of opti­miza­tion tools (and magic think­ing stuff), the proven4 answer is: You can’t.

GP is sim­ple. Reg­u­lar old human-scale problem-solving is hard enough that peo­ple will tell you you’re a Very Smart Per­son if you demon­strate even occa­sional com­pe­tence. But cop­ing with a thousand-fold accel­er­a­tion will break your model of your­self and what you think you’re doing.

So. Let’s start breaking.

  1. So com­mon that the old Wikipedia page for Sym­bolic Regres­sion now redi­rects to the one for Genetic Pro­gram­ming. Am I allowed to put a “facepalm” in a book? ↩

  2. I worry there’s a bit too much sub­tlety here: In some projects, an Answer may well be a for­mal func­tion that is not eval­u­ated with vari­able assign­ments — a project involv­ing alge­braic trans­for­ma­tions, for exam­ple. It’s the goal of sym­bolic regres­sion to fit par­tic­u­lar train­ing and test data; assign­ing those par­tic­u­lar val­ues is part of inter­pret­ing an Answer in that con­text. ↩

  3. Let me share a sym­bolic regres­sion result I was given by a sys­tem I was test­ing. I was just putting it through its paces, and so I was look­ing for func­tions that fit ten sam­pled data points from $y=x+6$. It came up with the per­fectly rea­son­able answer that started with $y=(2x — \frac{72x}{32x^2\div4x+\dots}$ and went on for four more lines after that. When I sim­pli­fied it, it meant the same thing as $y=x+6$, although along the way it added sev­en­teen con­stants together, mul­ti­plied them by 166, and divided by a huge num­ber to mul­ti­ply some extra terms by 0. This was the sort of sur­prise I mean. ↩

  4. This is an impor­tant result, and it pisses peo­ple off because it chal­lenges some of the same mod­els of self and project that I’m call­ing into ques­tion. It’s called the No Free Lunch Prob­lem for Search and Opti­miza­tion. Among other things, it demon­strates that for any per­for­mance cri­te­rion you can develop, the aver­age per­for­mance of any search algo­rithm — over all prob­lems — is no dif­fer­ent from the aver­age per­for­mance of any other algo­rithm. ↩

What is GP?

Posted on by

The fol­low­ing is a draft of the intro­duc­tion from the book.

What is Genetic Programming?

I’ve noticed that when you look up “genetic pro­gram­ming” at Google and read the top hits, it often sounds as though the writer imag­ines you already know what he means by the phrase. After twenty years, here’s what I think: Nei­ther you nor they know what they mean by the phrase.

But then I’m not even sure I know.

I use the phrase, of course. “Genetic Pro­gram­ming.” “GP.” And I act as though I know what I mean. It’s what I do.

Let’s try some more research. It seems like maybe you have an Inter­net where you are, and your copy of Wikipedia isn’t bro­ken. Go see what they say about genetic pro­gram­ming there.

Come back when you’re done. I’ll be here.

❧

OK, so as I read it — at least as of this writ­ing, and Wikipedia being what it is — “Genetic Pro­gram­ming” is some kind of computer-sciencey thing that does arti­fi­cial intel­li­gence with genes that con­nect ‘+’ signs and stuff in lit­tle trees. If you read closely, there’s some­thing about com­puter pro­grams that write them­selves auto­mat­i­cally. Plus there’s a lot of dif­fer­ent alter­na­tive approaches to it… what­ever it is. And based on the word­ing and the edit his­tory of the Wikipedia page some ways of doing it are clearly bet­ter than oth­ers… at some­thing… even I don’t quite under­stand what.

Also there’s muta­tion and crossover.

Yeah, that sounds tech­ni­cal enough, right? Can we agree to move ahead with that?

Ah, yes.… I thought not. Let me look around for a bit.

❧

How about this? Here is a very good book I rec­om­mend to all my stu­dents: The Field Guide to Genetic Pro­gram­ming by Ric­cardo Poli, William B. Lang­don and Nic McPhee. It’s avail­able elec­tron­i­cally! You can read it now.

❧

No? Not quite done?

All right, let’s bring out the big guns. How about Sean Luke’s Essen­tials of Meta­heuris­tics. I vouch for it whole­heart­edly: it’s full of inspir­ing machine learn­ing things, all explained sim­ply. And also avail­able elec­tron­i­cally. Read that!

❧

Before we go any far­ther, let me tell you how this is going to end:

The stuff we call “genetic pro­gram­ming” is an inco­her­ent suite of tech­ni­cal habits — design pat­terns, mod­els, idioms — most often used to accel­er­ate human inno­va­tion.

All that; not that

The sen­ti­ment isn’t new. It just doesn’t get repeated often enough.

It’s a cliché when the author of a a tech­ni­cal work starts off by say­ing he’s a “bit of a heretic”, imply­ing that what he’s about to impart will prob­a­bly get the reader in trou­ble if repeated in the wrong com­pany.

For one thing it helps pro­mote a sense that the for­mal dis­ci­pline as “dynamic” and “lively”. You know, with beardy codgers and plucky upstarts con­ven­ing in lux­u­ri­ous Vic­to­rian audi­to­ria to threaten one another with walking-sticks before rac­ing to the Pole to show those fools what a real dinosaur looks like.

Also a nasty back-handed recruit­ing trick, if you ask me. I’ve been to way too many meet­ings, and they would have all been much bet­ter if we’d had walking-sticks, let alone dinosaurs.

The prover­bial “bit of heresy” can also be help­ful when the author is feel­ing self-conscious about play­ing fast and loose with details, or wants to puff up his own author­ity, or might even be fail­ing to give credit to col­leagues who deserve it. I write these words on the anniver­sary of one par­tic­u­larly noto­ri­ous exam­ple of the lat­ter, so don’t think it doesn’t hap­pen: being an “out­sider” sug­gests to the inno­cent reader that you might have thought all this stuff up on your own.

Telegraphed “heresy” can also be ped­a­gog­i­cally use­ful. If only they keep read­ing, the read­ers might be let in on a juicy bit of gos­sip about you know… that whole Leib­niz – New­ton thing, or… have you heard about how Alexan­der the Great really com­pared as a ruler to his dad? Keeps them from falling asleep or skip­ping to the answers in the back of the book.

But then — and you can’t tell me you didn’t see this com­ing: some­times it’s true.

So this is my hereti­cal ver­sion of What Genetic Pro­gram­ming Actu­ally Is:

I have no damned idea.

It’s all over the place. No, seri­ously — you have no notion what a bur­den it can be, try­ing to write one one of these intro­duc­tory overviews.

First we would have to review some his­tory. I’d point out that seven or eight (or a dozen) inde­pen­dent thinkers invented Genetic Pro­gram­ming through the last fifty years. They each called their vari­a­tion some dif­fer­ent thing1, and the details of imple­men­ta­tion were all dif­fer­ent, and some of the vari­a­tions are little-known while oth­ers are huge stars. None is everything.

Then to be fair I would have to say not only what all those inven­tors did back then, but also sum up all the impor­tant things the ten thou­sand sub­se­quent peo­ple work­ing with GP did in their papers and books and arti­cles and con­fer­ence posters on the sub­ject. Plus there’s all the domain-specific appli­ca­tion work. Plus the com­mer­cial and pro­pri­etary meth­ods, each one vying for authen­tic­ity and authority.

But that’s just a raw fact-dump. So next I’d need to cover the trends and cul­tural norms, themes and motifs, note­wor­thy genealo­gies and regionally-distinct Schools of Thought.

And then I’d need to fix some of your mis­con­cep­tions because “Genetic Pro­gram­ming” may be the most mis­lead­ing tech­ni­cal name in the whole world. I’d point out that it’s not genetic algo­rithms even though it sounds the same. It’s not really any­thing like math­e­mat­i­cal pro­gram­ming or con­straint pro­gram­ming. It’s not philo­soph­i­cally any­thing like bio­log­i­cal evo­lu­tion, even if you squint. It’s not quite the same as machine learn­ing (or it is, depend­ing on who you ask), not least because say­ing so pisses off the Sta­tis­ti­cians (who know bet­ter). It’s not just evolv­ing LISP trees, it’s evolv­ing all kinds of struc­tures and plans and algo­rithms and ideas and art. It’s not just sym­bolic regres­sion. It’s not a lot of things, apparently.

So what is it?

No, really

What­ever it isn’t, I can say that Genetic Pro­gram­ming is the cumu­la­tive work of a huge num­ber of very smart peo­ple. Thou­sands of researchers and prac­ti­tion­ers around the world. They have almost all been pas­sion­ate vision­ar­ies, and have all done amaz­ing things to… well, to achieve what­ever Genetic Pro­gram­ming turns out to be for in their diverse indi­vid­ual cases.

I am reminded that the soci­ol­o­gist Andrew Abbott pub­lished a very inter­est­ing and read­able book in 1988, which has helped me quite a bit to under­stand what GP actu­ally is. Abbott’s book is called The Sys­tem of Pro­fes­sions: An Essay on the Divi­sion of Expert Labor.

What? Why shouldn’t I define it with a soci­ol­ogy book? How is it you have paid so lit­tle atten­tion to the rant thus far?!

Any­way, in Sys­tem of Pro­fes­sions, Abbott describes the dynam­ics of pro­fes­sion­al­iza­tion. That is, how tech­ni­cally astute peo­ple with over­lap­ping tech­ni­cal roles come to self-identify and pro­mote their shared inter­ests by cre­at­ing (and even­tu­ally polic­ing) a pro­fes­sion. In Abbott’s model, pre-professional “fields” arise when­ever diverse peo­ple find them­selves explor­ing and exploit­ing par­tic­u­lar new oppor­tu­ni­ties — espe­cially new tech­ni­cal inventions.

His story of the stages of pro­fes­sion­al­iza­tion includes the devel­op­ment of regional and social com­mu­ni­ties of shared inter­est, then com­mu­ni­ties of prac­tice… then at some point they name them­selves. Then the boundary-setting starts, and the self-definition, and the author­i­ta­tive self-regulated train­ing and cre­den­tial­ing sys­tems, and finally — as a pat­tern, not a rule — we find them build­ing legal infra­struc­ture, rang­ing from Asso­ci­a­tions to Unions to state-licensed reg­u­la­tory bod­ies.2

No, this isn’t a digres­sion. You asked. Well, OK, I asked rhetor­i­cally for you: What is Genetic Programming?

And I answer, not at all rhetor­i­cally: Genetic Pro­gram­ming is a “field” emerg­ing from the inter­ests of diverse peo­ple, who find them­selves explor­ing and exploit­ing a par­tic­u­lar new oppor­tu­nity. It is their shared prac­tices and norms, their habits and their goals.

I could define GP as “the search for for­mal algo­rith­mic struc­tures by using meta­heuris­tics inspired by bio­log­i­cal evo­lu­tion”, but it can­not merely be that. Because (as you’ll learn first-hand) you don’t have to use evolution-like things to search.

I could try to uniquely iden­tify GP as “meta­heuris­tic opti­miza­tion of struc­tures, as opposed to tra­di­tional para­met­ric search or analytically-derived opti­miza­tion algo­rithms”. But (as you’ll learn first-hand) we some­times use those other things too. GP can’t just be evolv­ing pro­grams, because some peo­ple evolve anten­nas and bridges and molecules.

GP can’t just be for data min­ing, because some peo­ple evolve com­pletely abstract proofs. It isn’t about the tools or techniques.

It is, in fact and not just metaphor­i­cally, a com­mu­nity of self-identified peo­ple who share a way of try­ing to solve problems.

Ask­ing what GP “is” at this point in its pro­fes­sional his­tory is like ask­ing what “pro­gram­ming” is: Pro­gram­mers use com­put­ers to solve prob­lems for peo­ple. They don’t do it in any par­tic­u­lar way, except that most of them type on a key­board.

But “typ­ing” is not pro­gram­ming. Just as “evolv­ing code” is not GP.

Look at pro­fes­sional com­put­ing. You can eas­ily see pro­fes­sional bound­aries between the many peo­ple who write pro­grams. There are Soft­ware Engi­neers, and Com­puter Sci­en­tists, Pro­gram­mers and Ana­lysts. And of course there are those who pre­fer the label Soft­ware Devel­op­ers, so they can self-differentiate them­selves as the ones who actu­ally know how to col­lab­o­rate and make pro­grams that peo­ple can actu­ally to use to do stuff.3

I’m quite seri­ous: “Genetic Pro­gram­ming” lives some­where a bit ear­lier in the same pro­fes­sion­al­iza­tion story. As Rick Riolo has said many times: “It’s an art try­ing to become a craft.”

If you ask them, most will say they are doing auto­mated search for abstract struc­tures that solve prob­lems. But the details vary wildly, and every real or the­o­ret­i­cal prob­lem is still a spe­cial case.

So for the time being Genetic Pro­gram­ming is what peo­ple do, who self-identify as “using Genetic Programming.”

Tozier, that isn’t really very helpful

Yeah, trust me: I am totally on your side.4

But I have writ­ten this book, and you are read­ing it. Rather than think­ing you and I are both crazy, explain it this way:

If we play our cards right, we can our­selves define Genetic Programming.

I don’t mean to imply “GP is what you think it is”. I mean the field is so young and mal­leable, that you can learn to do amaz­ing things with­out ever being told you’re doing it wrong.

In these last twenty years I’ve seen for­tunes made, dis­ease treat­ments invented, patentable inven­tions piled thou­sand deep, philo­soph­i­cal and the­o­ret­i­cal prob­lems set­tled, space probes launched, robots that learn to walk in their dreams.…

Peo­ple can use GP to cre­ate things they could oth­er­wise only imag­ine. Here’s my lit­tle True Heresy, stated another way: Those peo­ple are not using GP to “auto­mat­i­cally invent” things. It isn’t a magic inven­tion machine.

It’s an accelerator.

I’ve hung out with a num­ber of these folks, through the years. They’re not smug geniuses… as a rule. Rather, they walk around in a sort of daze, telling one another how sur­prised they were by what they were shown when they started using GP.

A human being invents when she uses GP to con­sider a mil­lion out­ra­geous struc­tures and lay­outs no sane design engi­neer could incre­men­tally develop. The “inven­tion” hap­pens when she — a standard-issue human being—notices that some of those mil­lion designs is interesting.

That’s the same thing a tra­di­tional design engi­neer does, but faster. The effort is in a dif­fer­ent place.

A human being explains some­thing the world when he uses GP to con­sider a thou­sand novel mod­els of data, in less time than a tra­di­tional sta­tis­ti­cian can eval­u­ate two. The “expla­na­tion” hap­pens when he — a standard-issue human being—notices that some of the best mod­els invoke rela­tion­ships between vari­ables that nobody else had never mentioned.

That’s the same thing a tra­di­tional sta­tis­ti­cian work­ing with a domain expert does to explain the world, but faster. The effort is in a dif­fer­ent place.

And so on: an artist explores a thou­sand com­po­si­tions; a bio­med­ical researcher exam­ines a dozen or a hun­dred genomes and a mil­lion gene expres­sion pro­files; a trader mon­i­tors a mil­lion port­fo­lio man­age­ment rules.

The same thing they would nor­mally do. But more. The effort is in a dif­fer­ent place: on the think­ing.

Genetic Pro­gram­ming doesn’t auto­mate think­ing or cre­ativ­ity or any of those things. It helps peo­ple notice things.

GP is a prosthesis

Think about writ­ing — you know, with a pen, on paper. Writ­ing isn’t “auto­mated mem­ory”. Or think about pro­gram­ming com­put­ers. It isn’t “auto­mated arithmetic”.

Writ­ing and pro­gram­ming extend your mind. Writ­ing is a pros­the­sis in the sense that it offloads mem­o­ries to a long-term exter­nal stor­age medium. Pro­gram­ming is a pros­the­sis in the sense that it cal­cu­lates stuff really really fast.

But nei­ther one is “auto­matic”. Harry Pot­ter notwith­stand­ing, there are no self-writing pens, and no self-programming computers.

See what I did right there? There are no self-programming com­put­ers. That includes Genetic Pro­gram­ming, regard­less of what you may have heard from the nerds down the street.

I can’t tell you how many peo­ple I’ve seen come to GP, hav­ing read the hype about auto­mated inven­tion and stuff. Like a per­son who wants to write bet­ter, so she gets a really pow­er­ful pen. The per­son who wants to learn to pro­gram games, so he gets a really pow­er­ful com­puter.

How do you learn to write? How do you learn to pro­gram? Same with GP. Through guided prac­tice. We think a bit, we try some­thing, we learn if we’re lucky, and maybe we solve some problems.

And if we’re very good problem-solvers, we can use GP to help our­selves become use­fully surprised.

  1. Evo­lu­tion­ary pro­gram­ming, genetic pro­gram­ming, some Ger­man ones I can’t recall the names of at the moment… no many doubt oth­ers. ↩

  2. Ellen Mazur Thom­son pro­vides a lovely exam­ple of this same pro­fes­sion­al­iza­tion dynamic in her well-written his­tor­i­cal case study of the print­ing and graphic design trades: The Ori­gins of Graphic Design in Amer­ica, 1870 – 1920. ↩

  3. Though even they are frag­ment­ing on the basis of method­ol­ogy and domain.… ↩

  4. If only we’d had walk­ing sticks at the con­fer­ences these last twenty years, it would have all been so much more effi­cient.… ↩