Posted by Kovas Boguta.
I had prepared some ideas for a live experiment at the minicourse. However, since the attendees were asking lots of good questions, I thought I would instead solicit a topic.
A number of people were interesting in traffic modeling and the general topic of diffusion, so I thought we could give it a try.
Now, a lot of work has been done using 1d cellular automata-like systems. So I thought it would be more interesting to look at a 2d cellular automaton that was set up to have multiple "lanes" of traffic. Essentially, all this means is that the array is much longer than it is tall.
The below picture shows an example of the evolution of such a system. We start off with a random arrangement of black cells on the right hand side, and over successive steps they tend to move over to the left.
This particular rule that I found is fairly interesting. The left hand side of the front moves at the maximum possible speed for this class of CAs. The front has a very simple structure, but dragging just behind it is a much more random-looking mass. The simple fronts move faster than the mass, yet the mass manages to generate new fronts as the old ones outstrip it.
Getting back to the original problem of diffusion, one obvious issue is that of having a conservation law. We could certainly construct a 2D CA that conserves particle number, for example along the lines used in NKS Chapter 9. But more interesting, I think, would be to search through the space of CAs for ones that roughly conserve the particle number -- where this conservation property is in effect an emergent phenomenon.
I had started to do this, and unfortunately we ran out of time. But I returned to this tonight, and searched a space of 100,000 random rules. There are 2^2^8 possible rules in this class, so really this search should be run overnight and allowed to look at tens of millions of cases. But I promised to post this before I go to bed :) .
The criteria was very simple: Evolve the CA. Take each step of the evolution, and total the number of particles there are at that step. Then, you simple take the max - min of that list. The end result is a number that represents how badly the CA violates the conservation of particle number.
Out of the original 100,000, I selected the 2000 rules with the best (lowest) score. And then I ran the search again on those, this time with more steps and trials. And out of those I selected the best 100.
At this point I was getting impatient for a better visualization mechanism. Its impractical to make the kind of picture above for 100 different rules. But there is an easy trick to compress that data. Each step of the evolution is a 2d array that is long and narrow. But we can take that 2d array, and turn it into a 1d line just by squeezing that narrow component together: for each column, you just add up the number of cells, this gives you a list of numbers. And then, we can neatly represent the entire time evolution in a single 2d picture.
The below are a sampling of the interesting cases from the set of 100 well-scoring rules:
The very first one corresponds to the rule I showed in the beginning. You can clearly see two dark lines that are moving at maximum speed to the left, followed by a fainter line (the third front), and then a more random mass. Interestingly, in this picture we can see that little sub-fronts are created and destroyed in the middle of that random mass during the course of evolution. Perhaps they are the opposites of congestion.
For comparison's sake, here is the same kind of picture made for randomly chosen rules:
With a better search we will be able to find rules that come much closer to conserving particle number. Even so, with this small scale effort I think we were able to find something interesting.
Comments