Today’s post is about ring species and a useful discovery that Occupy Math and his collaborators found while trying to understand them. A ring species is spread out around a major barrier that it cannot cross, so that the members of the species are in a long, thin ring-shaped domain. Examples of ring species include larus gull populations around the north polar ocean or greenish warblers spread around the Himalayan massif. A picture of the greenish warbler’s distribution appears at the top of the post. The funny thing about ring species is that they are arguably one or several species.
The biological species concept says that a group that form a species must be able to breed with one another. In a ring species, adjacent groups in the ring can breed, but on the far side of the ring where the groups meet up again, they cannot. Mostly this shows that the biological species concept is a little too simple. We thought that wolves and coyotes were different species, for example, but there is a difference between “cannot breed” and “choose not to breed”. The hybrid coywolves show that coyotes and wolves can breed — when humans thin out the wolf population to where they cannot find mates that are wolves. Below the fold, we will get to how this led to mathematical research.
An Explanation for Why Ring Species are Rare
One of Occupy Math’s biological collaborators was interested in the phenomenon of ring species. A ring species starts at one point in the ring-shaped geography and spread both ways, meeting up at the far side. Ring species are pretty rare and somewhat difficult to document — you have to run breeding experiments at the point where the populations come back together and demonstrate that they cannot, or will not, breed. Occupy Math and his collaborators set up a simulation with artificial creatures placed in a small segment of a ring and allowed to spread around the ring in short jumps. In order to understand if the creatures on the ring were fertile, they needed to do something — if the children of two parents who were competent at a task were also competent, the parents were fertile with one another; in the simulation any two parents could “have children”, but to get competent children, the parents digital genetics need to mesh properly. The creatures were set the task of learning to push boxes against the walls. An animation of two of the evolved creatures appears below.
The results we found were that ring species are rare because they are transient. When the ring first closes on the far side, the two groups in the area that came different ways around the ring are not fertile with one another. There is gene-flow around the rest of the ring, however, and after a while — think a few thousand years — the groups at the meeting point of the ring become fertile. This is not inevitable; rather, the fertility at the joining point fluctuates. When the fertility wanders over a certain limit, mutual fertility is locked in, in the area where the ring closed. Below is the formal citation for the paper we published about this work. This is an example of using math to test, in simulation, a hypothesis that is difficult to test in nature.
D. Ashlock, E. Clare, T. vonKonigslow, and W. Ashlock, Evolution and instability in ring species complexes: an in silico approach to the study of speciation, Journal of Theoretical Biology, 264(4), 1202-1213, 2010.
There is More: the Ring Optimizer
The bulldozers-pushing-boxes problem is one Occupy Math has been studying for decades. It is a toy (small) artificial intelligence problem and it was the starting point for Occupy Math’s research that shows that the most critical part of using evolution as a problem-solving technique is the design or the digital genetics or representation used. Occupy Math has used about twenty different sorts of digital genetics for the bulldozer problem, many of which he invented for the purpose, and compared how well they worked. For the bulldozers used in the ring species simulation, we picked the best representation, a form of super-simple computer program that (because it is simple) can be programmed by digital evolution. Here is where we got a surprise.
The bulldozers found during the ring species experiments broke the performance record for the bulldozer problem. Ring optimization produced fifty different control programs for the bulldozers that were better than the current champion. This leads to other questions like, “is ring optimization only going to be this good for the bulldozer problem?” When something as complicated as an ecosystem simulation does something useful, it can be really difficult to figure out why it is doing the useful thing. The next surprise was that we found a good explanation and it is pretty simple.
Why Ring Optimizers Work So Well
In the ring optimizer, we start with a small group of creatures — think ten — next to one another in a ring with space for thousands of creatures. Nearby pairs are chosen as parents, have a child, and a slot for the child is chosen nearby in the ring. If that slot is empty, the child gets it. If the slot is full, the child gets the slot if he child solves the problem at least as well as the current occupant. This means that, as the population spreads about the ring, any child survives at first. As things fill in, competition set in, and the level of ability to solve the problem needed for survival rises. This shows why the ring optimizer works at all — but it does not explain why it works really well.
When we are using digital evolution, exploration represents behavior that discovers novel solutions to the problem in question. Exploitation is the term used to describe refining solutions already present in the evolving population.
This may be a novel use of the term “exploitation” for some readers — in this context it only means trying to improve what is already good. It is unfortunate that the same word is used for exploitation of human beings or resources, things we need to avoid. This terminology arose in the ivory tower and is now standard, a situation that merits an apology.
Both exploration and exploitation are needed for an effective evolutionary optimizer. In an evolutionary algorithm with a single population, where any two members are equally able to become co-parents, the trade-off between exploration and exploitation is managed by changing the size of the population and the rate at which mutations arise. We compared a standard algorithm to a ring-structured algorithm on another problem — classifying genetic data — and found that performance depended strongly on population size and mutation rate for the standard algorithm. The ring-structured algorithm was indifferent to these parameters. That was the clue we needed to figure out what is going on.
In the early stages of a ring optimization run, there are lots of empty slots. Almost all children survive and the algorithm is spreading out all over the space of solutions to the problem. In other words, the algorithm is highly exploratory. As a region of the ring fills in, children must equal or exceed current members of the population, a situation which strongly favors exploitation. This is the secret of the ring optimizer: as the ring fills in, the algorithm transitions smoothly from exploration to exploitation. Exploration happens before exploitation, regionally around the ring. The algorithm intrinsically manages the transition from exploration to exploitation via its geographic structure. This transition can be stretched out or compressed by changing the size of the ring. This means ring size is the one parameter of the algorithm we need to tune to the problem being solved.
Summing up, and the other posts in this series.
To recap, Occupy Math started off working with collaborators to simulate a biological phenomenon, the ring species. These simulations let us posit a theory about why ring species were rare; they break down over time. This led to a published paper, always a nice thing for an academic. At this point, we stumbled into serendipity. The problem we had given the simulated creatures to solve, so that we could assess their fertility, was solved to record-breaking levels.
This meant that our biological simulation could be re-purposed into a new type of optimization algorithm for solving problems. It has been tested on other problems, from trying to estimate contact networks in epidemics to creating evolved art. This post documents a marvelous example of finding new mathematical tools in the study of nature. We conclude with a list of the previous articles in this series.
I hope to see you here again,
So remember to wear your mask!
Daniel Ashlock,
University of Guelph
Department of Mathematics and Statistics
Occupy Math 