Minh Hua's Blog

Introduction

During the last term of my M.S. in Computer Science program at Johns Hopkins, I took an Independent Study course with Dr. Wiley focused on Cellular Automata (CA). We investigated a total of five CA models, and this blog post serves as the first in a series of several documentations of those projects. In this post, I will present a CA implementation of Schelling's model of segregation. This blog is intended to be a companion to Frank McCown's excellent blog post on the same topic. The only difference is that my blog post's interactive component adds more control over the simulation (e.g. the ability to specify neighborhood type, boundary conditions, and colors).

Background

Cellular Automata

Since this is the first post in a series of posts about CA, we should start with a brief introduction on the topic. My summary draws straight from Hiroki Sayama's book on Complex Systems, so you should read chapter 11 if you want more details about CA. An automaton (automata is plural) is a theoretical machine with an internal state that changes according to its previous state and some input. The domain for the state is usually finite and discrete, and we often encounter the binary state space (0 or 1). Cellular automata (CA) are a collection of automata arranged on a grid (see the grid in the demo section). On a traditional two-dimensional CA grid, each automaton (hereafter also referred to as cell or unit) is surrounded by eight neighbors, which affects the cell's next state. The state of every cell on the grid is updated simultaneously using a state-transition function that takes as input the cell's current state and the current state of its neighbors. For example, consider a toy example where we have a grid of two cells, so that each cell only has one neighbor. A transition function might say "change your state to match your neighbor's if your states do not match. Otherwise, do not change your current state." The idea of CA is that simple transition rules can give rise to complex behaviors. Lest we forget our history, we remark that the idea of CA was originally invented by John von Neumann and Stanislaw Ulam in the 1940s and 1950s.

There are two other concepts that we should be familiar with before we close our discussion of CA. First, there are a few different neighborhood types that a CA model can have. For a two-dimensional CA, the two most common neighborhood types are von Neumann and Moore (see Figure 1). In a von Neumann neighborhood, each cell has four neighbors represented by the cells to the top, left, right, and bottom of the current cell. The more fun neighborhood is the Moore neighborhood, which adds four more neighbors in the form of cells to the top-right, top-left, bottom-right, and bottom-left of the current cell. Then, the neighborhood type determines the number of cells that affect the current cell's next state.

The final concept that we should discuss are boundary conditions. Since CA is a spatial as well as temporal model, we need to consider what happens to the cells at the edge of the CA grid. For example, consider the cell at the very top right corner of the grid. Does it have neighbors to the top or left of it? There are two important boundary conditions that we can consider. In a cut-off boundary condition, we assume that cells at the edge do not have neighbors beyond the boundaries. Therefore, our very top-right cell will only have three neighbors, i.e. cells to the left, bottom-left, and bottom of it. This is because there are no cells to the top-left, top, top-right, right, and bottom-right of that cell. Conversely, in a periodic boundary condition, we assume that the grid is wrapped around each spatial axis. Then, a one-dimensional CA grid becomes a ring and a two-dimensional CA grid becomes a torus. In this boundary condition, our top-right cell would have nine neighbors. Its top-left and top neighbors would come from the bottom right of the grid. Its top-right neighbor would come from the bottom left of the grid. Its right and bottom-right neighbors would come from the top-left of the grid. At least, this would be right if my mental math was correct. It is easier to visualize the periodic boundary condition in the one-dimensional case. The very last cell on the right has as its right neighbor the very first cell on the left, and vice versa.

Schelling's Model of Segregation

In 1971, American economist Thomas Schelling released a paper describing a model of how distinct populations segregate over time. Given two populations that exhibit differences (e.g. sex, age, income, language, color, taste, etc.) and the degree that each individual tolerates being near individuals from a different population, Schelling's model gives rise to various macroscopic behaviors.

We can readily implement Schelling's model using CA by designating each cell on the CA grid as an individual. Then, assume that each automaton can take on one of two values, each of which represents a population. The main mechanism that drives the grid's evolution is the fact that dissatisfied individuals will move whereas satisfied individuals will not. An individual's satisfaction is determined by their tolerance for the number of individuals from a different population in their neighborhood. For example, assume that each individual will only be satisfied if 50 percent of their neighbors come from the same population. In this sense, the individual in the middle of the neighborhood below will be satisfied because four of their neighbors are the same (50 percent of the neighbors are the same color as the individual).

However, the individual in the middle of the neighborhood below will not be satisfied because only three of their neighbors are the same (37.5 percent of the neighbors are the same color, which is less than the required 50 percent).

Since the board is populated with individuals as well as empty squares, any dissatisfied individual will move to an available empty square during each update. Every dissatisfied individual will move in the same iteration of the simulation, and a move is not guaranteed to keep every individual satisfied. The simulation continues running until everyone is satisfied, which is not always possible. I have listed below some example configurations that could arise from different parameter combinations (see Figures 4 and 5).

Interactive demo

To run the simulation, first use the sliders to tweak the parameters. On the left, the Similarity slider controls the percentage of similar individuals that an individual requires to be in their neighborhood to be satisfied. The higher the percentage, the harder it is to keep individuals satisfied. The Initial ratio determines the ratio of one population to the other. The Empty percentage determines the number of empty spaces that dissatisfied individuals can move to. The Delay control determines the delay between each frame when playing the animation. Finally, the Board size slider controls the number of individuals in the configuration.

On the right, the Neighborhood type dropdown determines the type of neighborhood that the model employs. The Boundary condition dropdown is also self-explanatory. Finally, the last three dropdowns allow the user to specify the color of the two populations and the empty spaces. Alternatively, users can also use the Random colors button to randomize the populations' colors.

Users can use the Reset button to reset the configuration. The Start button can be used to start the simulation, which will run until the user presses the Stop button or every individual is satisfied. To step through the simulation incrementally, press the step button.

In the most recent update, users can run simulations with more than two populations using the Populations dropdown menu. Choosing more than two populations will generate menus that allow for the specification of the ratios of the initial populations and their colors.