One of Occupy Math’s claims is that academic research is too stodgy. This week’s post looks at a successful research idea that arose from a science fiction novel. This idea has supported more than ten peer-reviewed scientific publications and, in several of them, the reviewers made Occupy Math take the science fiction novel out of the references. One of the reviewers even said “No-one cares where you got the idea”, a notion with which Occupy Math disagrees. In fact, the most elusive quality Occupy Math tries to train into his students is having good ideas.
This post concentrates on one example application – generalizing a technology that makes pretty pictures. While more frivolous than trying to understand the wellsprings of creativity, it is another area of deep interest to Occupy Math. When looking at the pictures of cellular automata in this post, try to judge which ones look different and which ones look similar. A cellular automata is a simple model of calculating a new row of pixels from old rows of pixels — but the way the model works is not obvious, so Occupy Math uses tricky code to search for models that make interesting pictures.
If we want math and science to be appreciated, we cannot make the ivory tower too high or windowless!
The science fiction novel in question is Ethan of Athos by Lois McMaster Bujold one of Occupy Math’s favorite science fiction authors. Athos is a colony planet founded by a sect that feels that women are the source of all evil. Once the uterine replicator is invented, it becomes technologically possible to found a colony without women. Ovarian tissue cultures that produce egg cells are needed and the colony selected 20 women with good genetics who were also super-talented as tissue donors. The problem is that, 200 years after the colony’s founding, the ovarian tissue cultures are senescing (dying of old age) and someone has to go back to the main galactic techno-culture and purchase new ones. This novel won a lot of awards and deserves them all.
Occupy Math’s point of departure is wondering what it would do to the genetics of a population if, for 200 years, there were exactly 20 women who were all the mothers. This isn’t an experiment you could do, in either an ethical or a practical sense, with actual human beings. Occupy Math can do this sort of experiment — using evolutionary computation. The idea in Ethan of Athos can be tested in simulation. Occupy Math anticipated a paper that might go to the Journal of Theoretical Biology. Instead he got a tool for steering the behavior of evolving systems.
Adopting the idea inspired by Ethan of Athos yielded a powerful design tool.
The idea Occupy Math adapted from Ethan of Athos is to introduce into simulated evolution something like the ovarian tissue cultures. What you do is pick your “tissue donors” which are called ancestors. You then modify the part of the simulation that mimics sexual reproduction to permit the ancestors to participate. The difference is that the ancestors are not part of the evolving population and they never die. Occupy Math’s research group calls these single parent techniques. The practical effect is to make the ancestral genes pervasively available. They can breed back into the population at any time. Here are four examples of cellular automata evolved without single parent techniques.
An earlier post already introduced cellular automata. The automata Occupy Math is working with in this post are evolved to fit in a box. The boxes for the automata shown above are 401×401 pixels. Here is an experiment that demonstrates the effect of single parent techniques.
- Pick an interesting looking cellular automata to be the single available ancestor.
- Run an algorithm to evolve cellular automata with the “tissue culture” of that ancestor available.
- Since leaving the box the same size means that the good result is to just clone the ancestor, make the box larger. This creates a lot of pressure to use the ancestor’s good qualities without just duplicating them.
Let’s do this experiment and look at what happens!
The first picture is the ancestor, the four pictures after it are the descendants that arise using single parent techniques. The box for the larger pictures is 401×801 — they are twice as high. We start with a purple and light blue lantern pattern. The four pictures above will give you a sense about how much things vary without a single parent.
Clicking on the image will let you see these at full size. Let’s look at another grouping based on the solid blue dagger automata.
One more ancestor with four descendants. These are based on the green ghost automata.
Normally evolution searches broadly across the entire space of objects that the programmer makes available. As the first four cellular automata above show, in a rich space an evolutionary algorithm can find different things over and over. The single parent techniques permit us to focus the search strongly in the vicinity of the ancestors. The technique does better at preserving the local details and color of the cellular automata than the overall shape.
What is the point of using this technique to find groups of similar automata?
The amount of time needed to evolve an automata goes up directly as the size of the box that contains them. With single parent techniques, we can evolve a large number of automata in small boxes to find ones we like the appearance of. Having found an intriguing appearance, we can evolve much large automata with a similar appearance, avoiding the work of evolving lots of automata in large boxes. Assuming that finding automata with a particular appearance is a problem you want to solve, the single parent techniques save huge amounts of time.
Discovering single parent techniques is not a good thing or a bad thing — it is an available tool. What single parent techniques preserve changes from problem to problem. In the demonstration in this post, Occupy Math showed only the results of using one ancestor. If we use several ancestors then evolution can be used to combine their good qualities — just like selective breeding of corn or pigs — while letting evolution filter out the bad stuff. Occupy Math’s group is just starting to explore the results of using multiple ancestors.
What else can you do with this?
A cellular automata called Life, invented by John Conway and his students, has been shown to be a general purpose computer. In fact, while Occupy Math is making pretty pictures with cellular automata, they are able to do lots of different, and potentially valuable, things. The problem is that programming them properly is hard — but this is something that the single parent techniques make much easier.
In some of Occupy Math’s other applications of single parent techniques, more subtle qualities than appearance were also preserved — like the ability to predict thermal flow. Another demonstration of single parent techniques increased the speed with which evolution managed to perform an abstract programming task by several hundred thousand fold. Another quality that can be controlled is the ability of simple robots to solve box-pushing problems. All of this is preliminary proof-of-concept stuff. Next fall Occupy Math will work with a research student to apply these techniques to improving and speeding up the interpretation of large data.
There are two take-home messages in this post. The first is that you can get a good idea from all sorts of different places and being a stuck-up prissy person about proper sources of ideas serves no-one. The second is that following what seems like idle curiosity can lead to big things. The single parent techniques discovered by Occupy Math’s research team let us use stock breeding and plant breeding techniques to create a focused tool for engineering design, automatic content generation, and optimization and search.
Do you have ideas for where to apply single parent techniques? Is there a good book that contains potential research ideas? Occupy Math urges you to comment or tweet!
I hope to see you here again,
University of Guelph,
Department of Mathematics and Statistics