Evolution and Complexity demystified by goats

goats-in-grass2-3

I was having tea with a professional goatherder the other day (who else would you expect to meet in Portland?) and I asked her,

“So tell me what you have learned from the goats?”

“Well,” she began, herding her thoughts together, “Whenever I want them to go to clear some part a field, I can’t make them do what I want. The goats will always cluster in some edge of the field near the fence and work their way across from left to right around the perimeter.”

(For context, Briana gets paid to set up a fence around some acres of land, bring in her herd of goats, and have them clear all the brush and weeds from it.)

My jaw dropped as she explained the pattern her goats naturally fall into for eating the field. The pattern turns out to be the same as what Melanie Mitchell’s genetic algorithm predicted as the best strategy for a very similar task.

goatherd_1526

(r)evolutionary programming

This approach to writing computer algorithms, which Melanie Mitchell calls ‘genetic algorithms’, copies evolution. Instead of programming the solution itself, it takes the problem and makes a game out of it. Games have a set of possible “moves” and a way to “score” the individual players. Some combinations of moves perform better than others. Winners are mushed together (AKA python-code-sex). A few (1%) are mutated, and these winning programs play the game again. The scores get better with successive generations, though they rarely get better in each generation. It might take 100 generations of no-improvement before the code has a breakthrough. Here is an example from Complexity: A guided tour by Melanie Mitchell:

robot problem

So imagine that the room full of empty beer cans that Robby the robot needs to clean looks like this:

robot stragety map

Some sets of moves do better than other, regardless of where in the room the trash is laying. The robot has five possible  moves, and a very limited set of information it can work with, fully summarized in this chart under the Actions:

genetic algorithm recipe - conditions table

So the “logic” that the robot can encode as a move depends on what is in the adjacent squares or whether there is a can in the current square. This is the situation that provides input and feedback. Note the robot has no memory of where it has been, only what is right next to it in the room.

The “individual” robot that plays the game of cleaning this room is nothing more than a series of 200 random moves. In the first generation all 200 moves are random, but in later generations these strings of moves will be some combination  drawn from previous robots that performed better than the rest of the pack (say, top 20%).

genetic algorithm recipe - individuals as code strings

So the “346” in the beginning of Individual #200  means “move up, move left, pick up can”, and so forth for the whole string. The overall design to any genetic algorithm (what I prefer to call evolutionary programming) is summarized here:

genetic algorithm recipe

So how well did the best robot strategy do? Melanie first wrote one “smart program” do have something to compare the evolving programs against. It moves randomly (but not backtracking), picks up a can if it is present, then moves to an adjacent site if there is a can there, and picks that one up. Her “smart” program got a score of 346. Anything higher is a program that performed better than what a human can intelligently design.

genetic results 1

So what was the most evolved robot doing to clean the room? Melanie writes:

[The best] Robby moves east until he either finds a can or reaches a wall. He then moves north, and continues to circle the edge of the grid in a counterclockwise direction until a can is encountered or sensed.

Second, Robby skips over cans in the middle of the room. Later, the can he didn’t pick up on the last move acts as a marker so Robby can “remember” that there are cans on the other side of it. He goes on to pick up all the remaining cans in the cluster when the perimeter has been circled.

Left: a highly evolved solution. Right: Melanie’s intelligently (human) designed solution

robot stragety map compare

(In her explanation below, GA is the robot ‘genetic algorithm’ and M is the default human-designed strategy with a score of 346):

genetic results 2

genetic results 3

And remember Briana’s goats? The ones she used to try and direct to clean certain parts of the field before the parts near the fences she’d erected? Well they actually do the same thing as the robot! Herd them as she might, they look for a the fence and eat along the perimeter, then the middle!

Goats and robots aren’t “smart” in the sense that the herd doesn’t consciously discuss their plan for eating, but they still follow the optimum strategy because of evolution. What began as random movement became synchronized and directional because they ate more food faster and avoided getting eaten by predators (herding behavior). All it took was a million years of goats needing to eat more efficiently in order to survive.

This is what I am here in Portland to learn this month. Melanie Mitchell teaches here at Portland State University, and I needed to isolate myself to learn something radically new, like (r)evolutionary programming. Watch it work:

You can see that this programming example is also taught at Duke University. And yet, in my 20 years of schooling, including a PhD in Neuroscience and two bachelors of Chemistry & Biochemistry (minors in psychology and biology) I never encountered this idea of copying evolution to solve real world programs.

Evolving, not designing, social solutions and government policies

The beauty of evolution is that copying the EVOLUTION PROCESS frees you up from the burden of believing you need to know the answers. You must become an expert on designing systems that learn instead. It turns out what matters is skill in making a “game” out of real-world problems, classifying “moves”, and then figuring out what defines a “good score” or a “bad score” in that game.

Scientists call the gamification of social problems “modeling” but I prefer to think of it as a game. Modeling is for control freaks who want to define everything and assign the importance of variables in their model. Evolutionary programmers want to model the possible moves and guess at the best way to score results (align the scoring with the actual thing you desire to happen). Good moves with a bad scoring scheme results in models that produce undesirable outcomes when applied to the real world problem. For example, Economists are excellent at defining great models with terrible “scoring”, leading to the whole field to being called the “Dismal Science”.

I’m interested in taking this idea and using it with data and language, to “evolve” more optimal ways of classifying sets of texts into a hierarchy. Stay tuned.

Read a book!

book coverComplexity- A Guided Tour- Melanie Mitchell-chapter9

What enables individually simple insects like ants to act with such precision and purpose as a group? How do trillions of neurons produce something as extraordinarily complex as consciousness? In this remarkably clear and companionable book, leading complex systems scientist Melanie Mitchell provides an intimate tour of the sciences of complexity, a broad set of efforts that seek to explain how large-scale complex, organized, and adaptive behavior can emerge from simple interactions among myriad individuals.

Advertisements

7 thoughts on “Evolution and Complexity demystified by goats

  1. Joy, that is a great blog post with these guidelines for innovation:

    Stay a little ahead of the competition while close enough to what customers can understand and incorporate. Here are some characteristics of innovations most likely to succeed at gaining support:

    Trial-able: The idea or product can be demonstrated on a pilot basis. Customers can see it in action first and incorporate it on a small scale before committing to replace everything.

    Divisible: It can be adopted in segments or phases. Users can ease into it, a step at a time. They can even use it in parallel with current solutions.

    Reversible: If it doesn’t work, it’s possible to return to pre-innovation status. Eventually you want life to be unimaginable without it, but at least in theory, it’s possible to go back to zero.

    Tangible: It offers concrete results that can be seen to make a difference in something that users need and value.

    Fits prior investments: The idea builds on “sunk costs” or actions already taken, so it looks like not much change is involved.

    Familiar: It feels like things that people already understand, so it is not jarring to use. It is consistent with other experiences, especially successful ones.

    Congruent with future direction: It is in line with where things are heading anyway. It doesn’t require people to rethink their priorities or pathways, even though of course it changes things.

    Positive publicity value: It will make everyone look good.

    These principles leave plenty of room to promote revolutionary ideas under cover of evolutionary change. But to find and grow a market for anything — whether green products or new health delivery plans — means staying close to what users can adopt easily and then leading them to the next iteration.

  2. From post-posting conversations:
    I definitely got heavy exposure to evolution and understood it inside and out. But none of the professors in the lab or the classroom ever “evolved” any of their methods or analyses using evolution as the process. IT was always a theoretical framework to explain biology (natural selection) or chemistry (i.e. evolution of the chemicals of life from inorganic roots) but never as the METHOD for discovery itself, as I talk about with algorithms and goats.

  3. In a conversation around my current evolutionary programming experiment,
    I said: “I can score, but I don’t have enough moves to mutate!”
    Response: “You should use that as a pickup line.”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s