Over the next little while, I will be publishing a series of posts that document some ideas and discussions that I have presented in talks and lectures over the last few years. This somewhat quickly-written post is a discussion of fitness landscapes and evolutionary computing, which expands on a part of a presentation titled ‘Emergence’ that I gave several times in 2008 & 2009.
Navigating Fitness Landscapes
Many of us, in one way or another, do things that require us to come up with good ideas. Indeed, most of us are looking not only for good ideas, but the best ones – within whichever framework or context we are operating in. How often, if ever, do we find that best idea? Are there strategies that we can use to find the best ideas faster, or more often?
Scientists are often faced with problems that have many solutions. They say that the ‘better’ solutions are more fit, and that the best solution is the most fit, or the fittest solution. A set of possible solutions for a problem, then, forms a fitness landscape of possible solutions. When we are facing a creative challenge of any kind, we are heading out into a similar landscape – high peaks of brilliant innovation and low valleys of mediocrity. Every point on this landscape represents a possible idea or solution; the ones higher up are better solutions than those which are lower down. While we hope to find a conceptual Mount Everest, we often find our upward limits on the tops of convenient grassy knolls along with perhaps the occasional noteworthy peak.
It would be nice if these landscapes were simple, with one obvious peak representing a single, best solution. We could set out into our landscape, and simply follow the upward path. When we got to the highest point, we’d be done. Best idea found! Lay out the picnic blanket, have a beer, and celebrate a job well done.
The problem, of course, is that our landscapes of ideas are populated with many summits – peaks that could be (and probably are) higher than the ones on which we are enjoying our congratulatory lunch. There might be one higher peak, or more likely, many. While one peak may indeed be a local maximum, it may remain a maximum as we expand our search to include all of the available options. Our travels become a combined problem of finding peaks, and deciding wether they are high enough to settle on.
Did I mention we are walking these landscapes blind? While our helpful overhead views show us that there are bigger & better ideas out there, from our spot on the top of our hill we can’t necessarily see those peaks – particularly the ones that are far away. Complete maps of fitness landscapes are rarely available – and those that are are usually made well after they would have been useful.
In practice, these fitness landscapes are often rugged and varied, with many sets of peaks, valleys, and plateaus. And, the bigger and more complicated the problem that we are working on is, the more vast these landscapes become. The more rugged the landscape is, the more difficult it is to successfully find the fittest point. Navigating through these solution terrains (blind) can be a tricky business. Luckily, science offers us a few strategies that are very useful in finding these elusive fitness peaks, and their associated good ideas.
The Power Law of Innovation
I believe that when most of us are working creatively, we follow a ‘Keep Going Up’ (KGU) approach to finding higher ground. We start with an idea, and gradually improve it – we change colours, adjust composition, re-work wording, or add and remove notes, and keep the changes that make our idea better. We move upwards, usually in small steps. This approach is an excellent one for finding local maxima – those peaks nearest to us that are the highest ones. But if we only ever go up, it is very easy to get caught on a small local summit, and not find a much taller one that might be near by.
A solution might be to take bigger steps. This way, we can cover a lot of ground, and have a better chance of getting out of local ruts, or onto higher peaks. However, with big steps, we also risk jumping off of a good area entirely.
A very good solution, as it turns out, seems to be to take big steps in the beginning of a search, and smaller steps as you get closer to a local maximum. The best transition from big steps to small steps appears to obey a power law distribution, which looks something like this:
Large, exploratory jumps around the landscape quite quickly settle into smaller, less-risky steps. There is some pretty evidence we see this kind of a strategy working in technology innovation. Stuart Kauffman uses the example of the bicycle – in the beginning of the bicycle’s development, there was wild variation in structure, shape and size. But as the optimum form was developed, we have seen bikes changing very little from generation to generation.
Kauffman calls this effect The Power Law of Innovation, and it certainly seems to be in effect in the web world. We have seen several waves of innovation of the web (conveniently numbered!) and in each wave we have had a huge variety of innovation in the beginning of the cycle, progressing to periods of very (very) little variability by the end. Companies like Google, Facebook & Twitter find high peaks in the web fitness landscape, and subsequent companies are often content to stake their claim close by this already proven ground. Similar patterns can be found in a lot of diverse fields, and go a long way to explaining trends in music, fashion, and art.
We are still faced with the problem of being stuck on a local maximum when there might be bigger, better hills somewhere on the landscape. This conundrum is compounded when we throw in a really large and particularly troublesome reality – these real-life fitness landscapes are constantly changing. Not only are we wandering through unmarked terrain blindfolded, that terrain is changing with every step we take. Even if we have found a really great, really high peak on which to pitch our tent, it may be that that peak is moments away from becoming a valley (some particularly large web companies & publishers find themselves in this situation today). How do we avoid getting stranded on these local maxima? A good answer might lay in the application of evolutionary strategies.
Again, with the Darwinism
When asked to summarize evolution in one phrase, most people would answer with this: Survival of the Fittest. However, this admittedly catchy phrase only describes one small (albeit necessary) part of the puzzle: competition.
In a survival of the fittest model, we’d take a population of possible ideas (this population makes up the landscape that we have been talking about so far), and choose the best ones. We could then take the best of those, and theoretically move towards an optimum solution. I think this is is how a lot of us work on a project – start with some initial ideas, choose the best two, battle with those until we settle on one idea (or until a client chooses one), then tweak it until we get a result we’re happy with. A model of that kind of a process looks something like this:
What we are really doing here is employing our KGU strategy – we will find local maxima very effectively, but we’re gambling on the fact that these local maxima are going to be good ones. Most often, we’re going to end up on the top of hills and not mountains.
To avoid this, we can include a few other aspects of an evolutionary approach. First, we can create a new population of solutions at every step. Rather than continually narrowing our pool of possible solutions, we are keeping our available selection broad and in doing so are offering more possibilities to find the best ideas. The other thing that we do with in an Evolutionary Creative Process (ECP) is to allow for mutation in every new generation of ideas. This allows us to occasionally take those big jumps across the fitness landscape that were successful for us in the beginning – but with the added safety net of a larger population of possible choices every generation.
A model of an ECP looks like this:
Keep making ideas. Combine the best results. Take risks. These somewhat common-sense approaches gain credence when placed together into an an evolutionary framework. This model is interesting because it can be applied and tested both conceptually and practically. We can heed this advice when were thinking and creating (evolving ideas) – but we can also put the model in direct application through the use of Genetic Algorithms (GAs).
Genetic Algorithms take a lot of the concepts that we have discussed so far in this post and put them into action on a computer. They use some of the principles behind evolution to ‘breed’ solutions to problems. GAs have been used in the past to assist in the design of NASA’s satellite antennae, to solve complex math equations, to fit the Mona Lisa into 140 characters, to design buildings, and to solve a pile of other tricky problems. They are particularly successful at solving problems with many, many possible solutions, and for which there aren’t any known answers (which seems to fairly accurately describe pretty much every creative problem, ever). A GA can be applied to any problem, provided that fitness can be measured (ie. we can tell that one problem is better than another) and that individual solutions can be encoded by a hybridizable genome (one solution needs to be able to be bred with another to give a set of results).
Fast computers running Genetic Algorithms can move through huge fitness landscapes incredibly quickly. However, assessing fitness of solutions can be difficult for a computer, particularly where judgements of aesthetic are concerned. A good solution may be to allow the computer to do the ‘grunt’ work; assessing solutions by machine judge-able criteria, then having our brains (which are far better suited to these kinds of tasks, for now) continue the process for other criteria. In this case, computers can be used to make a vast fitness landscape smaller and more navigable.
Into the Real World
For the last few months, I have been working on a project which quite literally applies the concepts that I have talked about in this post. Conceived by Alex Beim of Tanglible Interaction, the project involves the design of a 60m x 10m landscaped accessible outdoor playspace which will be built in Richmond, BC. We have built a tool (using Processing) which allows us to generate a near infinite number of possible playspace layouts (a landscape of landscapes!) – and then use a Genetic Algorithm to evolve the population, selecting for interesting and accessible results. Alex and I can evolve through thousands of generations of playgrounds in the course of an hour, saving favourites, then evolve these together to get new results.
This is a unique approach to designing a playground. It allows us to explore many more possibilities than we could with a conventional approach, while considering and managing a number of very important constraints. It’s also a first chance to take some of the ideas that I have been developing over the last few years and apply them to a incredibly interesting and dynamic problem.
The park will be built along the Fraser River later this year.
Links and resources
Stuart Kauffman’s Alone in the Universe: The search for the laws of self-organization and complexity is a great resource for learning more about fitness landscapes as well as many other fascinating (and controversial) topics.
The Wikipedia entry on Genetic Algorithms is a good place to start to explore Evolutionary Computing.
Darwin Rocks! is a cool Danish site designed to explain evolution in a fun way – great for younger readers.
A few years ago I built a prototype of a composition tool that employs an interactive genetic algorithm to assist in making simple graphical compositions like logotypes. Thought that project, Variance, didn’t get very far (though I’d love to see it resuscitated) but I think it’s an interesting model for how simple applications of evolutionary computing techniques could assist in the design process, with the designer acting as the judge of fitness.
I’ve made a couple of other projects over the years that involve GAs and evolution – Darwinstruments, Smart Rockets
The fitness landscape diagrams were made with a quick sketch I built in Processing.