Full Name: Laura Cyckowski
Username: lcyckows@brynmawr.edu
Title: Emergence in Ant Colonies
Date: 2006-05-03 13:52:54
Message Id: 19208
Paper Text:
<mytitle>
Emergence
2006 Course Projects
On Serendip
THE EMERGENCE OF:
Organization without an organizer, Orchestration without a conductor, Direction without a director
ANT COLONY BEHAVIOR
The simulation here aims to show that organized behavior is capable of existing without direction from above, but instead can result in a bottom-up manner from a collection of agents interacting with one another while following very simple rules.
I. Motivations and purpose
II. The story
III. The code
IV. Conclusions and resources
I. Motivations and purpose
The motivation for the model here comes from work done by researcher and ant expert Deborah Gordon of Stanford University (see Resources).
As described above, the model attempts to simulate emergent organization in the absence of direction or instruction. More specifically, the model attempts to simulate two interesting and perhaps unpredictable (based on individual ant behavior alone) characteristics of ant colonies: task allocation and colony stability.
II. The story
1. Task Allocation
One of the first things noted by scientists studying colonies of ants was that somehow work was divided consistently among ants. In nature, ants outside the nest are commonly engaged in one of the following activities: patrolling-- which to an on-looker basically looks like aimless wandering about; midden work-- transporting debris and dead ant remains to confined piles; and lastly, foraging-- scouting the larger surrounding nest area for food and other resources.
It wouldn't be crazy to think that maybe ants are born with a destiny (or fate, depending on how you look at things) to perform the same task day-in and day-out. In this way, task allocation would be decided by genetics. An ant colony has a set number of foragers, for example, and if we were to remove them all the colony might die because it would have no ants to find food.
However, a closer look shows that ants aren't fated to perform the same task. They may switch from day-to-day, hour to hour, or even minute to minute.
How do they decide what to do? And how do they decide when to switch?
Maybe someone tells them to-- like the queen. But the queen usually stays hidden beneath ground deep within chambers, and sometimes ants stay outside of the nest for the entire day. So, unless ants are telepathic, the answer would have to lie somewhere outside the nest. Perhaps in the patrollers, who seem to wander around without purpose anyway?
Scientists have asked all these questions and attempted to answer them by removing the queen ant or by removing individual ants. And when this didn't lead to answers, even by removing entire groups. When this is done, however, the remaining ants continue on with work, albeit after a little adjustment to fill the void left from those removed.
If there's no one then telling an ant that there's not enough or too many other ants doing a certain task, perhaps she (all ants of a colony are female) decides for herself by keeping track of how many ants are performing her task.
This might be possible, since scientists noted that when ants encounter each other, their antennae touch the body of one another. So, it seems like ants might be able to communicate information to each other.
Again though, this idea has been rejected. First, ants aren't considered capable of having such great memories. Second, some colonies can reach over 1,000 ants. Given this, determining one-by-one what every other ant is doing would not be very efficient.
Not all hope of finding a reasonable explanation is lost though. The next important observation by scientists was that the body of an ant (specifically where antennae are likely to hit) has on its surface a unique kind of chemical (called "cuticular hydrocarbons", a waxy substance) which they found to differ from task to task.
Still unsure of why ants would switch tasks, they synthesized their own hydrocarbons and dropped them into a nest in the form of beads to see what would happen.
If an ant really went around asking other ants what they are doing, and monitoring how many ants are doing this task or that, then she would probably ignore these droplets since they don't look much like ants. At the very least, if she mistook them as other ants (many species are blind), in order to mimic an entire force of ants doing one task it would take quite awhile for her to get around to contacting each droplet (remember, some colonies can have over a thousand workers outside of the nest alone).
Dropping a bead or two into the nest had little effect. What researchers discovered, though, was that when more were added, and ants contacted a relatively larger number of them in a shorter span of time, they suddenly changed tasks.
Might task switching be based on something as simple as frequency of contact with other ants? If so, would this be enough to lead to organized behavior?
~~~~~~~~~~
Click on "Setup patches/clear all" to setup the environment (or to start over after you've run a simulation).
This divides the world into three areas: on the right, a larger green area for foragers, on the top left a gray area for patrollers, and on the bottom right a brown area for midden workers.
The three setup buttons below add ants to their respective locations. You can vary how many ants are added ("NumberOfAnts") with each click, but try starting out with a smaller number to see how the model is set up. The total number of ants, "Total ants", at any given time is represented under the plot.
The ants show up as different colors to set them apart from the background and to make it easier to visualize how they are dispersed. Foragers will always turn red, patrollers blue, and midden workers purple.
Clicking "Step" will run the program through one cycle and clicking "Go" will run the simulation continually until it is un-clicked.
You'll see that the ants move around the screen in different directions and generally stay confined to their designated task area.
In the model here the ants do not have specific "tasks", but you can imagine their movement within one general area as representational of their engagement in a task (patrollers wander around surveying the area just outside the nest entrance, midden workers collect debris from all over the place, and foragers explore). What they actually do is unimportant for purposes here. The most important thing is the spatial variable which affords ants the potential for interaction. On that note, the world also wraps, so sometimes an ant may disappear from one edge of the screen and reappear on the other. Select "Watch an ant" to follow a randomly-chosen ant; if you want to follow a different ant or return to the original view just hit the adjacent "Reset view" button.
If you let the program run for awhile you'll notice that within one task some ants come while others go (they momentarily set their colors to yellow and pink so they're easier to spot). The "Task Allocation" plot and the three neighboring monitors display and track the percentages of ants broken down by task (green = foragers, brown = midden workers, gray = patrollers).
~~~~~~~~~~
Now back to our question: Is changing tasks based only on the frequency of encounters with other ants enough to organize everyone?
Find out for yourself: Test out different initial configurations of the world but try keeping the total population constant to begin with and watch what happens.
You might try setting up the world with 100 ants all starting as foragers. What happens? At first they all just stay engaged in the same task, but if you wait a bit, a few ants will switch to patrolling or midden work. (If you want to keep track of time, the "Clock" monitor keeps a record of how many iterations the program has run; additionally, holding the mouse over the plot will show the step number for any point on the x-axis; the y-axis will show distribution percentages.) Eventually, more ants will leave foraging, and sometimes the percentage of foragers will drop pretty low before it returns to a steady state. The distribution seems to always come out at around 50%/25%/25% for foraging, patrolling, and midden work, respectively (with normal fluctuations of give or take 5%).
Now try starting out with a different initial configuration, but keep the total population the same as before.
What happens?
No matter how we set the world at the start-- all ants doing the same thing, only two tasks with ants, or perhaps 90% patrollers and 10% midden workers, and so on-- eventually, given enough time, we wind up with the same distribution.
Reaching equilibrium
Did someone plan this? Did one individual cause this? Is there an elite handful of ants running around keeping tabs on everyone else?
You can test some of the same ideas and run similar experiments as the scientists described above did.
Unfortunately, there's no queen represented here but you can add a version of "hydrocarbons" and add or remove ants while the simulation is running.
Hydrocarbons: Clicking "Add hydrocarbons" will add 3 beads, which are always added to the midden work area. "Remove hydrocarbons" deletes them. See if you can determine how many are required to have a noticeable effect on task allocation by adding them in gradually.
Hydrocarbons
Adding ants: You can similarly add ants to respective tasks during simulation by clicking "Add foragers", "Add midden workers", or "Add patrollers". Clicking once will add the number designated by the "NumberOfAnts" slider used in setting up ants.
Removing ants: Lastly, you can remove ants during the simulation by clicking "Remove foragers", "Remove midden workers", or "Remove patrollers". The number removed is determined by the corresponding slider which is based on a percentage.
~~~~~~~~~~
If you've tried to find a directing ant and given up, you'll probably not be surprised to know at this point that there isn't one. The ants aren't programmed to do anything but switch tasks based on encounter frequency (see The Code section). The equilibrium emerges as a collective property of the individual ants interacting with one another.
Don't believe it? There's more to play around with. Next to the percentage monitors are sliders labeled "ForagersEncounterThreshold" and so on. You can change overall thresholds to be higher or lower for all ants, or you can adjust each task differently. This adjustment makes changes to each ant's individual set of rules.
Try changing around the encounter thresholds, and again start with different configurations to see if the same pattern emerges.
Equilibrium at different thresholds
When you're convinced that what's happening is emergent, below is a sketch of the algorithm each ant is programmed with. It's very basic and pretty simple and has only two variables: an "encounter" and a "time elapsed" variable. Furthermore, ants don't know anything about other ants, the only information she has access to is her own*:
Go forward one space
Add + 1 to "time elapsed"
Check to see if there's another ant on the current space
If there is, add + 1 to "encounters"
If "time elapsed" > x, reset "time elapsed" AND "encounters" to 0
If "encounters" > x, go to a new task
If not, Turn in a random direction
Loop
("x" is the variable defined by the EncounterThreshold sliders)
Notice that resetting the ant's "time elapsed" variable and subsequently "encounters" prevents an ant from keeping a tally of each and every ant. Therefore, switching tasks can happen only if the ant meets a certain number (threshold) of ants before its "time elapsed" variable resets itself and cannot happen by determining the total number of ants doing a task.
*With one exception being a Boolean "Alert" variable. However, this variable is not one used for the behavior described above; see below.
2. Stability
A second interesting property that scientists noticed about ant colonies was their stability. They noted that when they disturbed colonies-- be it by adding hydrocarbons, adding ants, removing ants, or after an intrusion from a neighboring colony-- older colonies tended to re-establish equilibrium faster than younger ones.
Maybe this is because older colonies are more mature, wiser, more experienced, or used to disturbances, while younger colonies are somewhat ignorant. Ants of older colonies have learned how to quickly get back on track after an interruption.
Scientists making these observations were comparing colonies as young as 1-2 years old with colonies up to 10 years old. So, after ten years one would think a colony might have learned a thing or two in its lifetime.
The problem? The lifespan of an ant is only about one year. Maybe a really healthy ant might live a year and a half or so, but certainly never as many as ten.
What could be causing younger colonies and older colonies to behave differently then?
~~~~~~~~~~
Explore the model and see if you can find any parameters that could have a bearing on stability. You can monitor stability in the following way:
When you add ants using the "Add foragers" etc. buttons, the "Capture % foragers" reports the percentage of ants engaged in foraging before the addition of new ants. When the colony has reached equilibrium again the "Time to restabilize" will show how many iterations re-stabilization took (it can be reset with the adjacent "Reset"). (As a side note, you'll want to wait until ants reach an equilibrium before introducing new ones for this number to be most meaningful.)
~~~~~~~~~~
What could account for older colonies being more stable if their ants are the same age as those in younger colonies? Task allocation emerges without an organizer, but perhaps there's a directing ant that facilitates a return to normal behavior after a disruption.
Or, could this behavior too be emergent?
Not surprisingly (or surprisingly?): Yes, it can be. The only difference between the younger and older colonies researchers noted was a difference in population. As colonies age, they steadily grow larger.
If you haven't already, try running two simulations of differing sizes and see how quickly the group as a whole returns to equilibrium after a disturbance.
If you want a summary of what happens, below is a graph comparing the results of multiple runs.
For all these trials, foragers were added for a 50% increase in the starting total population after exactly 500 cycles of the simulation was run (to allow the group to reach equilibrium). Also, the encounter threshold for each task was held at 50.
Finally, here are some additional tools and suggestions to play around with.
Intrusions: You can add enemy or "intruder" ants from hypothetical neighbor colonies by clicking "Add intruders" buttons and adjust their numbers using "IntrudersToAdd". Intruders will show up as black and will always be added to the foraging area. They are programmed to stay in this area, so they will never invade the entire colony. They will also almost always leave (unless the colony for some reason abandons a specific task...) because when they meet a certain number of members from the colony they leave (die). Though, they operate on the same basic principle of frequency as the colony ants do. So, they don't know the total size of the colony they're invading...
"IntruderPersistence" dictates how many ant encounters within a certain time period it takes for them to leave; "AntAlertness" is a variable for the colony ants. When an ant meets an intruder, it becomes "alert" and passes this information on to other ants. But, it only remains on alert for a certain period of time unless it runs into an other intruder.
Remember, all the variables control the algorithm of each individual ant. By changing "AntAlertness", for example, you're not telling the colony as a whole to do anything specific. You're only telling each ant to adjust her and only her behavior alone.
What happens with larger and smaller intrusions? What happens to task allocation in the colony when intruders appear? What happens after they're gone?
Response to an intrusion
In some colonies, ants stay longer in the foraging area after an intrusion... are these colonies more "vigilant" than others? "smarter"? Are the individual ants smarter? Is the colony smarter? In both smaller and larger setups, all ants follow the same, simple set of rules...
There are many variables in the model to play around with. See if you can find any other interesting behavior that might emerge...
III. The code
To prove that there's no director responsible for any organized behavior that you see, below is the code for the program. The first is a basic description of what's going on for those unfamiliar with the NetLogo programming language. The second is the raw code for programmers or others wanting hard evidence.
1. Each ant holds 5 variables, and can access the value of her and only her variables (with the Boolean Alert being an exception as noted earlier): Encounters, Time Elapsed*, Task, Alert, and Alert Clock.
Each time the program iterates once, the following commands are executed (x's represent the user-adjustable values) by each ant:
Determine task: Look at the color square you're on. If you're on a green square you're a forager, brown you're a midden workers, gray you're a patrollers.
Interact: Add +1 to Time Elapsed. If there are any other ants on your square add +1 to Encounters. If your Time Elapsed has reached 50, set it to 0 and also set Encounters to 0.
Work: Turn in a random direction. If the square ahead corresponds to your task, move forward one. If not, turn 180 degrees to the right and move forward one.
Check task: If the value of Encounters is > or = than x, run the commands for Change-task.
Change-task: Move forward one. If the color of the current square is different than before, set Distance Traveled to 0 and set Encounters to 0. Move forward a random number of spaces, but no greater than 15. If the color of the current square is not different than before turn in a random direction and run the commands for Find-new-task.
Find-new-task: Jump forward a random number of places, but no more than 5. If the color of the current square is different than before, set Task to the corresponding task, set Distance Traveled to 0, and set Encounters to 0. If the color of the current square is not different than before, re-run the commands from Change-task.
Check for intruders: If there is an ant of color black on your square, set Alert to 1.
Check alert status: If Alert = 1, set Encounters to 0.
Check alert status: If Alert = 1, add +1 to Alert Clock .
Check alert status: If Alert = 1 and Alert Clock = x, set Alert Clock back to 0, and set Alert to 0.
Check alert status: If there is another ant on your square, and her Alert = 1, set your Encounters back to 0.
Loop.
The intruders hold 2 variables of their own: Time Elapsed and Collisions.
Check variables: If Time Elapsed = 150, reset it to 0 and set Collisions to 0.
Move: If the square ahead is the same color, move forward one. If the square ahead is not the same color, turn 180 degrees to the right and move forward one. Turn in a random direction.
Check for colony ants: If there is another ant on the same square, add +1 to Collisions.
Check variable: If Collisions > x, die.
*In the NetLogo code below this variable is termed "patchestraveled", which may look misleading. The ants are not remembering encounters for certain distances traveled, but over a certain amount of time as described above. Since an ant moves at least one square every iteration, time is coded through this parameter.
2. The NetLogo code:
<--- begin --->
globals [ time distribution stability intrusionclock ]
breeds [ ants hydrocarbons intruders ]
ants-own [ encounters patchestraveled task alert alertcounter ]
intruders-own [ collisions patchestraveled_intruders ]
patches-own [ location ]
to setup
ca
ask patches [ if (pxcor > 0) [set pcolor green] if (pxcor < 1) and
(pycor < 1) [set pcolor brown] if (pxcor < 1) and (pycor > 0) [set
pcolor gray]]
ask patches [ if (pcolor = green) [set location 1] if (pcolor = brown)
[set location 2] if (pcolor = gray) [set location 3]]
set-default-shape ants "bug"
setup-plotting
end
to setupforagers
ask random-n-of NumberOfAnts patches with [location = 1] [sprout 1 [set breed ants set task 1 set color red - 1]]
ask ants [ set heading (random 360) ]
ask ants [ set encounters 0 ]
ask ants [ set patchestraveled 0 ]
end
to setupmiddenworkers
ask random-n-of NumberOfAnts patches with [location = 2] [sprout 1 [set breed ants set task 2 set color magenta - 1]]
ask ants [ set heading (random 360) ]
ask ants [ set encounters 0 ]
ask ants [ set patchestraveled 0 ]
end
to setuppatrollers
ask random-n-of NumberOfAnts patches with [location = 3] [sprout 1 [set breed ants set task 3 set color blue - 1]]
ask ants [ set heading (random 360) ]
ask ants [ set encounters 0 ]
ask ants [ set patchestraveled 0 ]
end
to-report totalturtles
report (count ants)
end
to setup-plotting
set-current-plot "Task Allocation"
end
to go
move-turtles
runclock
intrudercommands
end
to move-turtles
setuptask
do-plot
interact
work
ask ants [if (task = 1) and (encounters > ForagersEncounterThreshold ) [change-task]
if (task = 2) and (encounters > PatrollersEncounterThreshold ) [change-task]
if (task = 3) and (encounters > MiddenworkersEncounterThreshold ) [change-task]
]
ask ants [if any? intruders-here [set color cyan set alert 1]]
ask ants [if alert = 1 [set encounters 0]]
ask ants [if alert = 1 [set alertcounter (alertcounter + 1)]]
ask ants [if alertcounter = AntAlertness [set alertcounter 0 set alert 0]]
ask ants [if any? other-ants-here with [alert = 1] [set encounters 0]]
end
to setuptask
ask ants [if (pcolor = green) [set task 1 set color red - 1] if (pcolor = brown) [set task 2 set color magenta - 1] if (pcolor = gray) [set task 3 set color blue - 1]]
end
to interact
ask ants [ set patchestraveled (patchestraveled + 1) ]
ask ants [ if any? other-ants-here [set encounters (encounters + 1)]]
ask ants [ if any? other-hydrocarbons-here [set encounters (encounters + 1)]]
ask ants [ if (patchestraveled = 150 ) [set patchestraveled 0 ]]
ask ants [ if (patchestraveled = 0 ) [set encounters 0]]
end
to work
ask ants [set heading (random 360)]
ask ants [
if (task = 1) [ifelse (location-of patch-ahead 1 = 1) [fd 1] [set heading heading rt 180 fd 1]]
if (task = 2 ) [ifelse (location-of patch-ahead 1 = 2) [fd 1] [set heading heading rt 180 fd 1]]
if (task = 3) [ifelse (location-of patch-ahead 1 = 3) [fd 1] [set heading heading rt 180 fd 1]]]
end
to change-task
set encounters 0
fd 1
ifelse (location-of patch-here != task) [set color yellow set encounters 0 set patchestraveled 0 fd random 7] [set color pink set heading (random 360) find-new-task]
end
to find-new-task
jump (random 5)
ifelse (location-of patch-here != task) [stop set patchestraveled 0 set encounters 0]
[change-task]
end
to-report foragers
ifelse any? ants with [task = 1]
[report (count ants with [task = 1] / count ants) * 100]
[report 0]
end
to-report middenworkers
ifelse any? ants with [task = 2]
[report (count ants with [task = 2] / count ants) * 100]
[report 0]
end
to-report patrollers
ifelse any? ants with [task = 3]
[report (count ants with [task = 3]/ count ants) * 100]
[report 0]
end
to do-plot
carefully [set-current-plot-pen "foragers"
plot (count ants with [task = 1] / count ants) * 100
set-current-plot-pen "middenworkers"
plot (count ants with [task = 2] / count ants) * 100
set-current-plot-pen "patrollers"
plot (count ants with [task = 3] / count ants) * 100] [print error-message]
end
to addhydrocarbons
ask random-n-of 3 patches with [location = 2] [sprout 1 [set breed hydrocarbons set shape "drop" set color white]]
end
to removehydrocarbons
ask hydrocarbons [die]
end
to removeforagers
ask random-n-of (PercentForagersToRemove * count ants with [task = 1]) ants with [task = 1] [die]
end
to removemiddenworkers
ask random-n-of (PercentWorkersToRemove * count ants with [task = 2]) ants with [task = 2] [die]
end
to removepatrollers
ask random-n-of (PercentPatrollersToRemove * count ants with [task = 3]) ants with [task = 3] [die]
end
to followanant
watch random-one-of ants
end
to resetperspective
reset-perspective
end
to-report clock
report time
end
to addforagers
set distribution (count ants with [task = 1] / count ants) * 100
ask random-n-of NumberOfAnts patches with [location = 1] [sprout 1 [set breed ants set task 1 set color red - 1]]
ask ants [ set heading (random 360) ]
ask ants [ set encounters 0 ]
ask ants [ set patchestraveled 0 ]
set time 0
end
to addmiddenworkers
set distribution (count ants with [task = 1] / count ants) * 100
ask random-n-of NumberOfAnts patches with [location = 2] [sprout 1 [set breed ants set task 2 set color magenta - 1]]
ask ants [ set heading (random 360) ]
ask ants [ set encounters 0 ]
ask ants [ set patchestraveled 0 ]
set time 0
end
to addpatrollers
set distribution (count ants with [task = 1] / count ants) * 100
ask random-n-of NumberOfAnts patches with [location = 3] [sprout 1 [set breed ants set task 3 set color blue - 1]]
ask ants [ set heading (random 360) ]
ask ants [ set encounters 0 ]
ask ants [ set patchestraveled 0 ]
set time 0
end
to-report currentdistribution
report distribution
end
to runclock
if (stability = 0) [if
(distribution < (count ants with [task = 1] / count ants) * 100 + 1) and
(distribution > (count ants with [task = 1] / count ants) * 100 - 1)
[set stability clock]]
set time (time + 1)
end
to-report timetorestabilize
report stability
end
to resettimetorestabilize
set stability 0
end
to addintruder
ask random-one-of patches with [location = 1] [sprout IntrudersToAdd [set breed intruders set color black set shape "bug" set collisions 0 set patchestraveled_intruders 0 ]]
end
to intrudercommands
if (any? intruders)
[
ask intruders [if patchestraveled_intruders = 150 [set patchestraveled_intruders 0 set collisions 0]]
ask intruders [ifelse (location-of patch-ahead 1 = 1) [fd 1 set heading (random 360) set patchestraveled_intruders (patchestraveled_intruders + 1)] [set heading heading rt 180 fd 1]]
ask intruders [if any? ants-here [set collisions (collisions + 1)]]
ask intruders [if (collisions > IntruderPersistence) [die]]
]
end
to-report intrusionduration
if (any? intruders) [set intrusionclock (intrusionclock + 1)]
report intrusionclock
end
to resetintrusionclock
set intrusionclock 0
end
<-- end -->
IV. So what?/Resources
You might be asking yourself "what's the big deal?" These are just ants, why should their behavior be relevant or applicable to anything else? That's just the thing, though. They are just ants. Not very intelligent or complex on their own, but combined...
Can you think of other instances of seemingly complex or intelligent behavior that involve a collection of agents or units interacting with each other? Can you think of behavior that appears to an outside observer as so complex/intelligent that one assumes it needs an organizer, a director, a conductor?
How about: Termite mounds? Bird flocking? Schools of fish? Slime mold? Urban development? Embryonic development? The brain? Humans?...
...Life in general? That you'll have to decide for yourself. But hopefully this model has shown that such behavior/organization is possible without a central force holding it all together, without anyone or anything telling it what to be...
Suggested resources:
The Gordon Lab-- website of Deborah Gordon, Professor of Biology/Behavioral Ecologist at Stanford University; includes descriptions of her research and list of publications.
Ants At Work: How An Insect Society Is Organized, by Deborah Gordon (1999)
Emergence: The Connected Lives of Ants, Brains, Cities, and Software, by Steven Johnson (2001) -- many examples of emergence (including ant colonies) from a wide range of disciplines
Full Name: Sunny Singh
Username: ssingh@haverford.edu
Title: Using a Neural Network to Crack Various Encryption Algorithms
Date: 2006-05-03 13:53:43
Message Id: 19209
Paper Text:
<mytitle>
Emergence
2006 Course Projects
On Serendip
*****************
** 1.0: PRIMER **
*****************
1.1: Purpose
The goal of my project was to use a neural network in an attempt to 'crack' different encryption algorithms. In order to implement this idea, I needed to devise a way to numerically represent letters. Since there are 26 letters in the alphabet, I assigned each letter a five bit number. Additionally, I decided to restrict my dataset to 10 letter words, in an attempt to make my life a little bit easier. As a result, I designed the network such that there are 50 input/output nodes and 25 hidden nodes.
1.2: Algorithms
The two enciphering algorithms I used were the Caesar Cipher and the Vigenere Cipher. The Caesar Cipher is one of the oldest, and weakest, encryption algorithms; it was developed by Julius Caesar as a means to communicate with his military personnel. This cipher is a simple substitution/shift cipher in that each letter in the plaintext message is replaced by the nth subsequent letter in the alphabet. For example, if the shift value was 1, A would go to B, B to C, etc. Similarly, a shift of 26 would cause the ciphertext to be the same as the plaintext. In general, the enciphered value for a letter would be given by En(x) = (x + n) mod 26, where x is the value of the letter in question (A=0...Z=25) and n is the value of the shift. Thus, decryption is given by Dn(x) = (x - n) mod 26. What this basically amounts to is that the Caesar Cipher is relatively easy to crack. A code-cracker would merely need to cycle through, at most, 26 possible shifts in order to find the 'right' message (generally, the one that looks coherent). In the addition to the 10 letter restriction, I decided to encode my dataset with a shift of 15. I could have presumably studied various shifts, but I 'randomly' chose 15 for this study (I guess it wouldn't be random if I have unconscious predisposition to the number 15.)
The Vigenere Cipher is a polyalphabetic cipher that actually makes use of the Caesar cipher. Instead of using a fixed number to equally shift each letter in the plaintext, a keyword is used to encrypt the message. The keyword must be of equal length as the plaintext itself, or it must be repeated until it is of equal length. The Vigenere cipher can be represented graphically by a table with 26 rows: each row contains the alphabet, but is cyclically shifted over one. In the end, the table represents the 26 different Caesar ciphers. To encode a message using this cipher, each letter in the plaintext is 'matched' up with the corresponding letter in the key (remember, the plaintext and key have the same length!) So, if the first letter in the plaintext is N and the first letter in the key is E, one would look at row N and column E to obtain the enciphered letter--which happens to be R. Mathematically, if A=0...Z=25, the ciphertext is given by: Ci = (Pi + Ki) mod 26; similarly, the decrypted message is given by Pi = (Ci - Ki + 26) mod 26.
1.3: Issues
I originally tested the network by hard-coding 7 input/output pairs into the program. After consulting Doug Blank, I realized I needed to train the network on a much more massive dataset. With the 10 letter restriction in mind, I could only come up with a handful of 10 letter words. Feeling lost, I did a Google search and found a list of 20,301 10 letter words. I spent a fair amount of time writing a script to parse the massive list into the appropriate format, but it was doable and I now have a significantly larger dataset. This subsequently leads to a much slower network. Despite the network being rather sluggish, it managed to recognize all 20,301 enciphered patterns for both encryptions in just under roughly 2000 epochs. The learning rate and tolerance were both set to .01, which I thought would be sufficient. When presented with new inputs, however, the network merely spits out an incorrect answer--an answer that is nowhere near the plaintext message. I cannot pinpoint the reason why it is doing this. When
I propagate the network with new inputs, the program returns a list of 50 numbers, each between 0 and 1. I wrote a function to take the list and round each element either up or down--.99999 clearly rounds to 1 and .000000000034 should surely be 0. There may be a problem with the discrepancy when it comes to rounding either up or down. I was not sure if, for example, .33 should go to 0 or 1 (traditionally, it would go to 0). I set my threshold to .45--below .45 would be 0 and above would be 1. This could potentially be problematic with values that could go either way; however, I wouldn't attribute the overall failure of the network to this. Even when I look at the list of 50 numbers before the rounding and convert them with the various discrepancies in mind, I still do not get the correct output. Another postulation was that the tolerance and learning rate needed to be lower. I decreased both to about .00001 and I've been running the network for a few days. As of this writing, both networks are at 3750 epochs and both have 0.0000 correct.
1.4: Concerns
I am unsure as to how 'interesting' this project is. How applicable is this? First, if I needed to crack secret codes, chances are the messages would not have a fixed length. Although my 10 letter restriction makes my life easier, it significantly takes away from the applicability of the network. Furthermore, if I was hired to crack a certain code, why would I program a neural network WITH complete knowledge of the exact cryptosystem in mind?
1.5: Further Investigations
Instead of using the network to crack the actual code, I think a more realistic implementation would be to use a neural network to learn whether a string of letters is coherent English or not. Earlier this year a Haverford student presented a project in which he used brute force to crack a message encoded by the RSA algorithm. He used a mathematical model called Markov chains, which used various probabilities and weights to determine which of the potentially decoded messages made sense. Though I don't fully understand the workings of Markov chains, I believe they are somewhat similar to neural networks. Though such a project would be centered heavily on upper level mathematics, I think it would be worthwhile to use a network to strictly learn coherent English.
1.6: Updates
I originally tested my network with 1000 nodes--which was a bit excessive. I shrank the hidden layer down to 25 to see if that would allow the network to generalize. Although the network can learn both encryption schemes in under a few thousand epochs, it can only do so with a relatively high learning rate and tolerance. When presented with new data, it still cannot make the generalization. If I decrease the tolerance to 10^-4, the neural net ceases after 5000 epochs without any progress.
*****************
** 2.0: HOW-TO **
*****************
Consult readme.txt for a tutorial.
CaesarNN.py is the neural network for the Caesar Cipher.
VigNN.py is the neural network for the Vigenere Cipher.
Ciphers.py is the program used for creating new test data for the Vigenere and Caesar neural networks.
*********************
** 3.0: Resources **
*********************
Dataset: www.esclub.gr/games/wordox/10.html
Encryption methods: http://en.wikipedia.org/wiki/Caesar_cipher
http://www.trincoll.edu/depts/cpsc/cryptography/caesar.html
http://en.wikipedia.org/wiki/Vigen%C3%A8re_Cipher
http://www.trincoll.edu/depts/cpsc/cryptography/vigenere.html
Full Name: Stephanie Hilton
Username: shilton@brynmawr.edu
Title: The way a trend spreads
Date: 2006-05-05 11:47:17
Message Id: 19239
Paper Text:
<mytitle>
Emergence
2006 Course Projects
On Serendip
Abstract:
For my project I wanted to develop a model for trend cycles. When thinking about trends I first thought that I would make a model in which one person simply spreads a trend. Then I thought logically about how trends really worked. If a company produces a product, they advertise. Hopefully the advertisement will reach out to a few people scattered about their marketing area. Let's say this product is a new hat. If a person, named Sally, that was influenced by the advertisement goes out, buys the hat and then wears it to a party with all her friends perhaps some of her friends will be influenced to go buy that hat too. Then so on and so fourth a trend spreads. To model a trend spreading is easy and predictable, there is nothing a model could show us about a trend spreading that we wouldn't already know. The interesting aspect about my project is that I added a feature to represent a trend dieing out. Just like the ever-changing fads in our everyday lives, if a trend isn't encouraged, it will die out. If Sally stops wearing her hat and then her other friends decide they don't like it either because they don't see their friends wearing it then it is a possibility that the trend won't spread any more and just stop. My model is interesting because the starting percentage of trend-setters and population can be changed. There are some very surprising things that will happen when the sliders are changed. I thought that all outcomes would be relatively predictable but after playing with the model it wasn't too long until I encountered some unexpected outcomes.
The way it works:
The model starts off with a population determined by a slider that the user can change. Then a percentage of the population (which can also be changed by a slider) will start off red. The red people represent those who know about a trend; trend-setters. The blue people represent those who haven't caught onto the fad (yet). When the "go" button is pushed the people all move one space in a random direction. As the people move there are meetings of clusters of red and blue people. If a person in this group is a red person, 4 of the 8 neighboring people around that person will turn red, spreading the trend. Then the people all move one space again in a random direction. If one of the newly red people comes in contact with a group of blue people 4 out of the 8 neighboring people will turn red, etc. If after the red person moves there are no other red people on the 8 neighboring spaces then the person will turn blue. This last part is to represent at an accelerated faction, how trends die out.
Interesting findings:
Though most of these findings are logical to the concept, I did find some interesting variations.
-As long as the population is large enough (usually anything above 150), no matter what the starting percentage of trend-setters is the trend will never die out. On the other hand, if the trend is small enough (usually around 150) the trend will almost always die out. This is logical because if a trend is started in a town of a small farming population (let's say) where the people don't always come into contact with one another, trends aren't really relevant. If a population is large, like that in New York City, where people are coming into contact with hundreds of other people in a single day it is almost impossible for a trend to die out.
-When the population size is large enough (around 250-300) a very small starting value for the trend-setters will result in about a 50% of the population catching onto the trend.
-Even when the population is at the highest setting and the "trend-setters" are at 100% the trend will not stay at 100% saturation. This is because everyone isn't touching everyone else after every movement. If I were to make the population size able to be larger, then the trend would potentially be able to stay at 100%.
Conclusion:
This true-life model could be developed to show how trends actually spread and die out. With some research from marketers, this model could be used as a learning device. Marketers could use it to determine where to advertise their product. It doesn't make sense to push an advertisement on TV in a very rural area because the trend has no where to spread. It was very interesting to see the outcomes of different settings of populations and different percentages of trend-setters. My project didn't always product an expected outcome and therefore shows emergent properties. If I were to modify my project I would have a graph to store the information from many cycles of my model and compare them. This may show some emergent properties as well.
You can view my model at: http://bubo.brynmawr.edu/~shilton/shilton_trends.html
Full Name: Leslie McTavish
Username: lmctavish@brynmawr.edu
Title: Synchronizing Fireflies
Date: 2006-05-05 13:34:32
Message Id: 19243
Paper Text:
<mytitle>
Emergence
2006 Course Projects
On Serendip
Synchronizing Fireflies
Full Name: Ben Koski
Username: bkoski@haverford.edu
Title: The Dynamics of Propagating Memes Through Social Networks
Date: 2006-05-06 16:46:03
Message Id: 19272
Paper Text:
<mytitle>
Emergence
2006 Course Projects
On Serendip
Dynamics of Propagating Memes Through Social Networks
The Dynamics of Propagating Memes Through Social Networks
A Final Project for the Bryn Mawr College Emergence Course, Spring 2006
By Ben Koski, Haverford College '06
Background
We are all familiar, at least indirectly, with the evolution of cultural trends.
We know that songs become popular and then fade away, technologies come and
go, clothes come into and then go out of style. What sorts of dynamics
affect the dissemination of these trends? Using the concept of a "meme," can
we model how these trends move through groups of people?
As a user of the Internet, you may be familiar with the concept of an "Internet
Meme," usually observed as short-lived, faddish e-mail forwards of the
likes of the Nike
Sweatshop meme or the Goodtimes
Virus meme. The concept of a meme, however, extends well beyond the Internet
to cover all sorts of knowledge transmission or dissemination. Formally defined,
a meme is "any unit of cultural information, such as a cultural practice, idea
or concept, which one mind transmits (verbally or by demonstration) to another
mind." Memes can be small and trivial (for instance, a song, catchphrase, or
fashion could qualify as such "low-brow" memes), or broad and significant
(examples of these sorts of memes might be an economic system or a technology--say,
cars).
Regardless of scope, memes are defined both by their cultural payload and,
perhaps most interestingly, their evolutive properties. The concept of a meme
was introduced in 1976 by Richard Dawkins, as the sort of sociocultural counterpart
to the gene. Dawkins argued that one could view "cultural entities (people,
churches, schools) as replicators of ideas." When a cultural entity transmits
a meme to another entity, it is meaning is slightly changed: "memes do not
always get copied perfectly and might indeed become refined, combined, or otherwise
modified with other ideas--resulting in new memes." This interaction between
old and new memes leads to what is known as "memetic evolution": if the new
version of a meme is better at replicating or transmitting itself than an older
meme, this new version will spread farther and wider. As the new meme spreads
through the network of cultural entities and interacts with older versions
of the meme--as well as other memes--the cultural payload is shifted and evolved.
What affects this ability of memes to diffuse? The literature outlines six
broad factors that may affect a meme's ability to replicate and diffuse through
a network:
- Correlation with experience. If a particular meme correlates
well with a cultural entity's experience, it is more likely to "stick" and
thus
be
propagated out to other cultural agents.
- Happiness. Memes which bring people pleasure are more
likely to spread than memes that do not.
- Fear. If a meme inspires fear in cultural entities, they
are more likely to remember it--and more likely to propagate it to other
entities.
- Censorship. Censorship can act as a brake on a meme's
diffusion, but it often cannot stop it entirely. This censorship could either
take the form of broad, sweeping control exercised by a government or other
central authority, or could be quiet self-censorship induced
by social pressures.
- Economics. Cultural entities who are economically successful
have a better chance of propagating a meme to another entity. Those who are
successful inspire emulation: other entities give greater credence to the
habits of those who have achieved success.
- Distinction. Memes that are unique are more likely to
"stick" and be propagated.
The goal of this model is simulate the process of meme diffusion by modeling
these factors affecting a meme's ability to diffuse through a social network.
Such a model should allow us to gain an understanding of the relative importance
of each of these factors in determining a meme's evolutive fitness.
Inspiration for this project--as well as quotes for this background section--were
derived from the "memes" Wikipedia
article.
How was this model implemented?
Basic Tools
Since building and analyzing networks was well beyond the capabilities of
NetLogo, I chose to implement this model in Python using NetworkX--an advanced network
analysis and visualization tool.
Model Implementation
The model begins by constructing a virtual "social network" of a specified
size and average connectedness. This network can either be built as a random
network,
or a scale-free network. The random network construction algorithm creates
the specified number of nodes, and then continues to add random connections
between
nodes until the desired average connectedness is reached. The scale-free network
construction routine is based on a built-in NetworkX library function, whose
construction algorithm is described in a paper by the authors found here.
Though the scale-free network more faithfully models known patterns in human
social networks, random networks also have utility in testing the factors affecting
diffusion of memes through social networks. After network generation is
complete, the network is checked to ensure that it is fully connected. If it
is not, connections
are added between the disconnected
subgraphs until the network is fully connected.
Once the social network has been built, a variety of characteristics are assigned
to each node:
- Experience. A node's experience is based on a wrapping
integer value between 0 and 255. This number is not meant to quantify anything
other than the relative distance of two "experiences." One node might have
an experience
of 25, another of 200: this does not tell us anything, except that the experiences
of these two nodes are radically different. A propagation routine assigns
experience values to nodes. This algorithm is designed to ensure that
neighbors have similar experiences. Similarity of experience is an key
part of modeling social networks, since most connections within a social
network are based on some sort of common experience.
To propagate experience, an arbitrary number of random
experience seeds are assigned to random nodes in the network.
Then,
the routine
propagates
an experience value to the neighbors of each of these seeds--plus or minus
a value within a certain iteration range. The process continues until all
nodes have been assigned an experience. By limiting the change in experience
values between neighbors to a specified range, most neighbors will have similar
experience values. The few jumps at the edges of random "experience" pockets
effectively models those connected in a social network with dissimilar
experiences. A visualization of experience values propagated through a randomized
network
demonstrates the result of this routine:
In this diagram, pockets of similar experiences are highly clustered, jumping
at the edges of these clusters to other pockets of clustered experience.
- Economic class. Each node is assigned an integer between
0-4 to represent its economic class: 0 indicating the lowest class, and 4
indicating the highest class. Class is propagated through the network using
an algorithm similar to the experience propagation routine. Several random
economic class seeds are placed in the network. These values are then propagated
to the seeds' neighbors. There is a slight chance (by default, 10%)
that economic class will increase or decrease by one when the class value
is propagated--mirroring the improbability of conncetions in social networks
that cross socioeconomic class
lines.
This propagation continues until all nodes are assigned a class value.
- Happiness. All nodes are randomly assigned a 1 or a 0
to represent whether or not the node is reacts to the happiness embedded
in the meme. While a meme might make some people happy, it may not
affect others in the
same
way. This boolean value is designed to account for cases
in which a cultural entity does not experience the happiness induced by a
particular meme.
- Fear. An integer between 0 and 5 is
randomly assigned to each node to represent its fearfulness. If a node's
fear factor is 0, it is not fearful at all--and the appeal of a meme to fear
is lost on the node. If a node's fear value is 5, the meme's appeal to fear
has a strong effect on the node.
Several constants are defined for meme itself:
- Base weight. The base likelihood that a meme will be
adopted by a neighbor.
- Distinctiveness. A weight representing the meme's distinctiveness.
- Censorship. A value signifying the inhibitory effect of
censorship on the spread of the meme.
- Fear. A weight specifying the meme's appear to fear.
- Happiness. A weight specifying the additional likelihood
that a node will adopt the meme if the node is affected by the meme's happiness.
- Economic class. This weight represents the additional
probability that a neighbor will adopt the meme if the propagator is of high
economic class.
- Target experience value. The experience (0-255) that a
meme will most appeal to.
- Experience tolerance. The range above and below the target
experience to which the meme will also appeal.
- Experience weight. This weight specifies the additional
likelihood that a node will adopt the meme if it correlates with its experience.
The sum of all additive weights (that is, the weights for distinctiveness,
fear, happiness, economic class, and experience) must be greater than zero,
but less than or equal to 100. This sum represents the likelihood that a node
will adopt the meme if all values apply (e.g. if the meme correlates with
the node's experience, is propagated by a node of the highest economic class,
appeal's
to the node's sense of fear, and makes the node happy). Thus, if the sum of
all weights is 100, a node will always adopt the meme if all values apply.
If the sum of all weights is 0, a node will never adopt the meme.
After setup of the network and the meme is complete, a number of nodes are
randomly seeded with the meme. These seeds attempt to propagate the meme to
each of their neighbors in a randomized order. The sum of weights is calculated
for each node, based on its properties (e.g. using the node's experience, fear,
happiness, etc. values). A random integer is chosen between 0 and 100; if the
random integer is less than or equal to the sum of weights, the node accepts
the meme. If the node does not accept the meme, the attempt is recorded. Once
a node has exceeded the maximum number of attempts
(by default,
15), neighbors
no longer attempt to propagate the node. Once all seeds have attempted to propagate
the meme to their neighbors, another iteration begins. During this iteration,
every node that has adopted the meme makes an attempt to propagate the meme
to its neighbors.
Iterations
continue until all nodes have seen the meme, all nodes that have not seen the
meme have exceeded their maximum number of attempts, or until the maximum number
of iterations (125 by default) is reached. At this point, the model run
is complete.
So what's interesting about this?
Pattern of Connection is Significant
The first version of the model relied on my random graph generator
to create the nodes and connections of the hypothetical "social network." Upon
the
suggestion
of Prof. Blank, however, I added
the capability of generating scale-free social networks to my model (upon further
research, it turns out that random scale-free graph generation is built in
to the Network X library), with the idea that scale-free
networks are much more
similar in their topology to a real social network. Human networks are, in
actuality, not randomly connected networks (as illustrated in (a) below). Rather,
people tend to cluster into
tightly connected groups surrounding a central "hub" that connects out to other
network members (illustrated in (b) below).
I was curious: did the network topology significantly affect the time necessary
to propagate a meme through a network? How did network types affect the
completeness of a meme propagation? To investigate, I created a program to record
the number of iterations necessary to completely propagate a meme for a progressively
larger average connectedness values. The size of the
network was set at a firm 1,000 nodes, and the total of the weights was set
to 0.5
(including
a
0.2 base
weight). All other settings were left at their default. If a particular network
topology was much better at diffusing memes, we should see a lower number of
iterations required at every degree of average connectedness. The results of
this investigation are surprising:
Though the scale-free network diffused the meme at a significantly
faster rate at low average levels of connection, the number of iterations necessary
to complete a diffusion converges with the rate of the random network near
an average connectedness of 15. Presumably, scale-free networks are better
at
diffusing
memes with low
connection
rates
since the network's clustering allows the "hub" nodes to rapidly diffuse the
meme to a large number of neighbors. However, I did not expect the performance
of a randomly generated network to match that of a scale-free network, even
at high levels of connection. One possible explanation for this observation
is that, at a high level of average connectedness, random networks develop
properties similar to a scale-free network where some nodes have large numbers
of connections and can serve as "hubs" for diffusion. Or, perhaps the performance
of a scale-free network degrades as connectedness is increased and the special
properties of the scale-free network become less pronounced. Likely, the answer
lies somewhere in the intersection of these to explanations.
In this experiment, I also investigated the total number of nodes
that had seen the meme at the completion of the model run:
Since the model completes its run when either:
- All nodes have seen the meme, or
- All nodes that have not seen the meme have already seen the maximum amount
of attempted propagations (by default, 15 attempts are made before the neighbors
stop trying)
a run may complete without all nodes having seen the meme. Interestingly,
though scale-free networks diffuse at a faster rate, they do not diffuse
as completely. The most plausible explanation for this phenomenon
is that if critical nodes in a scale-free network (e.g. those that protect
access
to additional "hubs") max out their attempted propagations, the meme will likely
not diffuse to that hub--and all of its densely clustered neighbors. This makes
sense, because the incomplete diffusion in a scale-free network is most pronounced
at low levels of average connectedness, where there would be high numbers of
these "critical nodes." Beyond an average degree of two or three, the performance
of the scale-free network is roughly equal to that of the random network.
This is also a surprising property: though scale-free networks are efficient
in diffusion, they are not always the most complete. More importantly, however,
this investigation suggests that the ability of a meme to diffuse through a
social network is highly dependent on the network's structure--a factor not
clearly identified in available literature.
Cycles in Results of Meme Seeding Experiment
Based on my previous observations, it seemed that the placement--and number--of
initial meme seeds would be important in determining the speed of a meme's
diffusion. It seemed to me that significantly increasing the number of memes
seeded into the network before iteration began would logically lead to a significant
decrease in the amount of diffusion time required--particularly in scale free
networks, where a large number of initial seeds could avoid the problems of
blockages by "critical" nodes. So, I wrote another test program to record
the number of iterations required for diffusion in models with progressively
more random seeds. The run was conducted with a scale-free network, 1,000 nodes,
average connectedness of 2, and all other values at their defaults. The results
here, too, are quite surprising:
Instead of a directly inverse relationship as I would have expected, we see
cycles emerging! Some of the cycles in independent trials are in phase; others
are noticeably out of phase. Though I do not have any proposed explanations--even
after pondering over these observations for some time--they are very surprising!
My only thought is that the cycles are likely produced by some sort of emergent
pattern (rather than an artifact of randomness), which is supported by the
fact that some of the trials are in phase--even though they were conducted
using
entirely
different random seeds
Want to try this on your own?
Python source for the model is available here.
What do I need to install?
To make the project work, you'll need the following:
- Python. To simplify the process, I recommend downloading
and installing
Enthought python, which preinstalls
several key libraries. If you're good with this sort of stuff, you can use
your own python and then install the dependencies
for matplotlib on your own. I used python 2.3; I don't see any reason
why another version shouldn't work. Precompiled Win32 binaries for NetworkX
are only available up to python 2.3 as of April 2006, which may limit your
choices--of course, you could always compile NetworkX on your own.
- NetworkX, a network analysis library from Los Alamos National
Laboratories. Information is here;
a link to download here.
The precompiled binaries work great; compiling and installing from source
also isn't that tricky.
- Matplotlib, in order to visualize the results of propagating
the meme through the network. Information here;
download here. This
installation turns out to be the trickiest part of the project: I wasted
at least two weeks trying to get this to install on OS X using source, precompiled
binaries, and fink--to no avail. Eventually, I gave up and just installed
the Win32 binaries on to a Windows XP machine, which worked flawlessly in
about 10 minutes. If you've got access to a Windows machine, I'd strongly
recommend this route...but perhaps you'll have better luck than me.
How do I run the program?
Once you have all of the dependencies installed and working, simply navigate
to the folder and type python memes.py.
This will run the program, and produce any selected output. Note that output
files will be written to the directory in which the source file resides. Once
you have it running, open up the source and play with some of the variables!
Full Name: Julia Ferraioli
Username: jferraio@brynmawr.edu
Title: Evolving Rulesets for the Game of Life
Date: 2006-05-06 23:01:36
Message Id: 19273
Paper Text:
<mytitle>
Emergence
2006 Course Projects
On Serendip
write_up
Intent:
I wanted to create a program using python that would evolve rulesets
for the game of life. I am steering rather carefully away from using
words such as "purpose" or "goal" in this section, since we are
technically not supposed to have either of those. However, I feel that
the word "intent" skirts the connotation of having an endgame in mind.
Conway, when he developed his rules, observed that those particular
ones made for interesting patterns when applied to a board, or a
population. Conway's rules can be generalized easily into categories; I
wanted to see if an evolved ruleset might be able to be categorized as
well.
The original game of life may be
described as 2
9 rules, since each
position around the cell (8) and the cell (1) is counted, like
the picture below:
The resulting entry in the ruleset table for the blue square in the
above diagram will be:
This particular entry could result in the blue square changing to a
zero in the next step of the board, or it staying a one, depending on
the ruleset. Therefore, there are 512 rules possible that may be
applied to the
board. After applying the ruleset to a particular cell, based on its
own state and the state of its neighbors, it will either be on or off
in the new board. These possibilities do not change in my
implementation, but I try to evolve the output of the cells. In other
words, the 512 possibilities remain static, but their output evolves.
Implementation:
To do this, I first needed a way to represent the board, so the GA
could see what it evolved play out. I created a class for the board, as
well as for the ruleset, so that I could manipulate them abstractly.
The board is simply a two dimensional array, with a couple of functions
to apply a ruleset to each individual cell and to step through an
entire board. The ruleset class is just an array of 512 0's and 1's.
Since each entry in a ruleset may be considered a binary number, we may
use that as the index into the array. In the above example, it would
have been the 281st entry in the ruleset array, since the bits
'100011001' convert to 281 from binary to decimal. You
may take a look at the code for this program here.
The fitness function was the hardest to come up with. Theoretically, as
long as the more correct a ruleset is and the higher the number it
gets, the genetic algorithm should work well. I decided to try to
evolve a ruleset which would take a board and output one that has the
bits inverted. Therefore, the more positions in the board that had a
different bit in the finishing board than in the starting board, the
higher its fitness should be.
This genetic algorithm is never "done," because there is no "correct"
solution to which we are comparing the results. Having something with
which to compare it would undoubtedly speed up the process, but it
would also eliminate the "emergent" component since we would have a
definite goal. We therefore rely on the value of maxGeneration to cut
off the running of the algorithm.
If you wish to run this program, save the above file and type "python
total_pgm.py" at the command prompt, like this:
[username@localhost ~] python total_pgm.py
You should start to see output like this:
crossoverRate = 0.600
mutationRate = 0.060
populationSize = 200
elitePercent = 0.100
maxGeneration = 40
================================================================================
------------------------------------------------------------
Initial population
Fitness: Total 100.22 Best 0.60 Average 0.50
Worst 0.37
Elite fitness: [0.56000000000000005, 0.56000000000000005,
0.56000000000000005, 0.56999999999999995, 0.56999999999999995,
0.56999999999999995, 0.56999999999999995, 0.56999999999999995,
0.56999999999999995, 0.56999999999999995, 0.56999999999999995,
0.56999999999999995, 0.56999999999999995, 0.57999999999999996,
0.57999999999999996, 0.58999999999999997, 0.58999999999999997,
0.58999999999999997, 0.58999999999999997, 0.59999999999999998]
------------------------------------------------------------
It will take quite a while to run
based on the values of maxGeneration, the size of the board and how
many times you wish to step through the board in order to evolve it.
Results:
The highest fitness that I ever got for the program set at the current
values was .70, starting from about .60. It would usually go up a few
hundredths of a point fairly quickly, but take up to ten generations to
go up one hundredth of a point after that. Either .70 is where the
algorithm is stable, or it would take a much higher value for
maxGeneration for it to show any more progress. The fitness of just a
random ruleset is around .50, which makes sense because I use the
function randrange(i,j) to fill it with 0's and 1's and that would fill
it up about half and half. So the difference is at most .20, which does
not seem like a significant difference, at least not as significant as
I would have hoped.
Here is an example of how two different rulesets applied to a matrix
can change the behavior of the resulting matrix:
| Evolved Rules |
Randomized
Rules
|
Starting Board:
1 0 1 0 0 0 0 0
0 0
1 0 0 1 0 1 1
1 1 1
0 1 0 0 0 0 0 0
0 1
0 0 1 0 1 0 1 0
1 1
1 0 0 1 0 0 0 1
1 0
1 0 1 0 1 0 0 1
1 1
0 0 0 0 0 0 0
1 0 1
0 1 0 1 0 0 0 1
0 1
1 0 1 1 0 1 1
1 1 1
0 1 0 1 0 0 0 0
1 0
|
Starting Board:
0 1 1 1 1 0 1 1
0 1
1 1 0 1 0 1 1 0
0 0
0 0 1 1 0 0 0
0 0 0
1 1 0 1 0 1 1
0 0 1
0 1 1 0 1 0 0 1
1 0
0 0 0 0 0 0 1
0 0 1
0 1 1 1 1 1 0
0 0 1
1 0 0 0 1 0 0
1 0 0
1 1 0 1 1 1
0 0 0 0
1 0 1 0 1 1 0 1
0 0 |
Ending Board:
1 0 1 1 1 0 0
0 0 1
0 1 1 0 1 1 0 1
0 1
0 1 1 0 1 1 0 0
1 1
1 0 0 1 0 1 1
0 0 0
1 0 0 0 0 1 0 1
0 1
0 1 1 1 0 0
0 0 0 0
1 0 1 1 1 1 1 0
0 0
0 1 0 0 0 0 1
1 0 0
1 1 1 0 0 1 1 1
1 1
0 0 1 1 0 1 0
1 1 1 |
Ending Board:
0 0 1 1 1 1 1
0 1 1
0 1 1 1 0 1 0
0 1 0
1 1 1 1 0
1 1 0 0 1
0 0 0 0 0 0 0 0
0 1
0 1 1 0 0 1 1
0 0 1
0 1 1 1 1 1
1 1 0 0
0 0 0 0 1 1 1
0 1 1
1 0 1 0 1 0
1 0 1 0
1 1 1 1 0 0 1
1 1 1
0 0 1 1 1 0
1 0 1 1 |
Fitness
for evolved board is: 0.69
|
Fitness for
randomized board is: 0.54 |
Surprises (or lack thereof):
What I found surprising was how my fitness function did not quite work
as well as I thought it would, considering how I found it fairly
straightforward. True, there are quite a few variables, and playing
with the values of all of them would be something to try to fine-tune.
But apparently, there is such a thing as a "correct" fitness function,
whereas I thought that there could be multiple fitness functions which
would work equally well.
I did not really find anything very interesting with my implementation
of the game of life. True, it is hard to analyze a ruleset consisting
of 512 members, but I half-expected some distinct pattern to jump out
at me. However much I assured myself that I would be happy with even a
negative conclusion, I was disappointed with the fact that I did not
find anything that struck me as new and surprising. My boards did not
give me anything that I did not necessarily expect, my rulesets did not
have an overwhelming abundance of 0's or 1's, and my overall fitness
was not excitingly great. While my evolved rulesets did perform better
than the randomized rulesets, they were not spectacular or reveal
anything exciting about the GA process.
Opportunities for Exploration:
As was suggested during my presentation, my obsession with even numbers
may have tripped me up during my search for the perfect parameters.
Experimenting with odd numbers as well might prove interesting as well
as fruitful. Could the GA evolve an inverter in a relatively small
number of steps, as long as the number of iterations on the board was
odd? Perhaps. Another task to try would be to set maxGeneration to a
high number and then split the program up onto a cluster so that we
would not have to wait forever for results. Maybe these variables are
set just too low to get very interesting results, and higher values
would produce fascinating output.
Other opportunities for exploration include writing different fitness
functions. Checking for the stability of a board might be a possibility
for a fitness function (i.e., how much change does the board undergo
from one iteration to the next), or possibly looking at the
distribution of 0's and 1's throughout the board. Both of these fitness
functions would require a more involved look around at the entries
around one entry, which would add to the expense of evolving a ruleset.
However, there are endless possibilities for exploration with different
functions and variable settings.
Full Name: David Rosen
Username: david@wolfire.com
Title: Emergent Tree Generation
Date: 2006-05-07 01:25:07
Message Id: 19274
Paper Text:
<mytitle>
Emergence
2006 Course Projects
On Serendip
For my project, I decided to generate three-dimensional trees based on emergent ideas. I programmed my own graphics engine in C++ and OpenGL, and implemented the tree as a hierarchy of nodes. At first there is just a seed node, which creates an apical node and a root node. The apical node wanders upwards, leaving a trail of stem nodes behind it. It occasionally creates smaller clones of itself that branch off in different directions, and they can recursively make smaller clones of themselves as well. The program renders the tree by drawing each node as a circular cross-section, and then "skinning" bark over this framework. This resulted in a convincing representation of a leafless tree, but it still had several issues.
First, it was not balanced. Real trees tend to grow in such a way that the center of mass is roughly over the trunk, to provide stability. Since trees do not have any sort of centralized intelligence, there has to be an emergent explanation for this. In my model, each node is affected by the strain on the previous node, and branches are more likely to grow away from the direction of strain. This resulted in a more even branch distribution that looked much more natural and realistic.
Second, it had no leaves. I decided to draw leaves in clusters. Because each tree has thousands of leaves, and this simulation is meant to run in real-time, it is not feasible to draw every single leaf individually. To get around this problem, the simulation calculates the leaf density around each node, and then draws a cluster of leaves around it with the given density. The leaf density is determined by the amount of sunlight reaching the node; leaves are less likely to grow in areas shaded by other leaves; it would be very inefficient. Making the leaves grow based on sunlight made the trees look much more natural.
The end result was a very realistic-looking tree that could be efficiently grown and rendered in real-time, and modified by many different parameters such as branching probability, leaf and wood coloring, growth rate, height, spread, maximum age, shade tolerance, and so on. This project was very relevant to the ideas of emergence because these trees grew in a biologically efficient manner without any kind of central planning directing the individual nodes. The end result looks much like real trees, and theoretically, with more computing power and programming time, there is no reason why they could not eventually become identical to real trees. This model helps illustrate how real plants can grow in a similarly self-organizing fashion, and use energy very efficiently without any kind of design.
Full Name: Laura Kasakoff
Username: lkasakof@haverford.edu
Title: A Random Walk Through The Game of Life
Date: 2006-05-07 22:01:12
Message Id: 19279
Paper Text:
<mytitle>
Emergence
2006 Course Projects
On Serendip
A Random Walk Through the Game of Life
A Random Walk Through The Game of Life
Adding an Element of Randomness To Conway's Game of Life...
Background
John Conway discovered
(or invented, depending on your philosophy) the Game
of Life in 1970. The game illustrates how a simple rule set can exhibit
complex, even lifelike behavior.
The Rules
If a square is dead:
It becomes alive only if exactly three of its neighbors are alive.
If a square is alive:
It stays alive if exactly two or three neighbors are alive. (survives)
Otherwise it dies. (from loneliness or overcrowding)
Phenomena
Out of these simple rules emerge a plethora of interesting “life” forms. There are still life objects whose configurations remain
stable under the rules of the Game of Life. A 2-by-2 square is an example of
a still life object. There are also oscillators in the Game
of Life, objects that do change from step to step, but repeat and “oscillate” within a given period. Finally there are gliders who give the
impression of "motion."
In order to see examples of the various life forms mentioned here, simply go
to the applet, click the “Setup Blank” and then click either the
“Glider,” “Oscillator,” or “Still Life” button, and then click on the grid with your mouse to add one of these figures.
Then click “Go Forever” to see how these objects behave under the
Game of Life.
Goal
The Game of Life is completely deterministic. That is, if you start out with
a specific pattern on the grid, the rules of the Game of Life will always take
that starting pattern to a predetermined end state. Try it out. Use the “Create
Life” button to draw a specific pattern, and you will see that no matter
how many times you start with that pattern, the end result will be the same
each time. Try the “R-pentomino”; the R-pentomino consists of only five cells but takes1103 steps before reaching its end state.
So what happens if we add an element of randomness to the Game of Life? We have
seen that the Game of Life is deterministic. If we add an element of randomness,
could the Game of Life still be deterministic? Would gliders and still life
objects behave the same way? Would the final density of life be the same in
the end states of both versions? Let’s explore the applet.
This applet was created with created with NetLogo.
Note: This model is a modified version of a model found in the NetLogo Models
Library. Download this applet and view the source code for copyright information.
Methods
The “Go Random” buttons add an element of randomness to the normal
game of life. By changing the value on the birth-randomness slider, the likelihood
that a cell with 3 neighbors will stay alive or be born decreases with the percentage.
Similarly, decreasing the value of death-randomness increases the chance that
a cell that was supposed to die will live.
The “Go Random2” buttons act the same as the “Go Random” buttons. The only difference is that the number of increments by which you can
adjust the randomness of the death and birth is increased. Finally, the “Go
Limited” button simply acts on living cells, increasing the likelihood
they will die when birth-randomness is decreased.
Note: When the birth-randomness and death randomness are at their maximum value
(either 100 or 1000 depending on the version you use), then the rules operate
like the normal Game of Life.
Results
Surprisingly, our results show that by even adding just an iota of randomness
to the system, the defining characteristics of the Game of life deteriorate.
Try starting with a random setup by clicking the “Setup Random” button, and then play with the birth-randomness and death-randomness sliders.
To see the game of life with a random element press the “Go Random” button.
Provided below is a table of results for varying death-randomness and birth-randomness
percentages. The results are in the form (x, y), where x is the final density
and y is the number of iterations it takes to reach the final density. The infinity
sign indicates that the grid oscillates erratically at the given final density
from the beginning and continues on in a similar fashion forever. The initial
density was 50% for the following results.
Birth-Randomness vs. Death-Randomness (Final Density, Steps)
| Birth Randomness % |
Death Randomness |
| |
0 |
25 |
50 |
75 |
100 |
| 0 |
(1, < 20) |
(.70, ∞) |
(.30, ∞) |
(.20, ∞) |
(0, < 20) |
| 25 |
(1, < 20) |
(.75, ∞) |
(.40, ∞) |
(.25, ∞) |
(0, < 20) |
| 50 |
(1, < 20) |
(.75, ∞) |
(.50, ∞) |
(.30, ∞) |
(0, < 20) |
| 75 |
(1, < 20) |
(.75, ∞) |
(.55, ∞) |
(.40, ∞) |
(0, < 20) |
| 100 |
(1, < 20) |
(.75, ∞) |
(.60, ∞) |
(.45, ∞) |
(.03,1100) |
As expected the final entry has values like the normal Game of Life (.03,1100).
We see that none of the trials with randomness behave remotely like the normal
game of life.
Note that the initial density of life did not seem to have a statistically significant
effect on the end result of the Game of Life. An experiment of 25 runs shows
that the average final density is:
| Average (25 Runs) |
Initial Density |
Final Density |
Steps |
| 35% |
3.24% |
1236 |
| 50% |
2.92% |
1144 |
Our intuition confirms this finding since a little five cell figure like the
R-pentomino with negligible initial density can result in a much more substantial
final density.
Things to Try
We looked at a nice smattering of trials with various birth-randomness and death-randomness
values, and saw that they did not behave like the game of life. They did not
end at a pre-determined relatively stable state with a low density of life.
Try our random life buttons with as little randomness as possible.
- Set “birth-randomness” and “death-randomness” to
99 and “Go Random Forever.”
- Then set “birth-randomness2” and “death-randomness2” to 999 and “Go Random2 Forever.”
In both cases the game looks a bit like our normal game of life, but it never
reaches a final determined state. Randomness still devours the heart of the
Game of Life.
It is interesting to see how random rules of life act on gliders, oscillators,
still life objects and the R-pentomino. I found that random behavior destroyed
the way in which these objects behave under the normal rules of life.
You could also try the “Go Random Limited” button which will increase
the probability that a cell that should live will die. My intention of including
this button was to limit the random behavior solely on the area of the grid
that had life on it. However, I found the results uninteresting since usually
all life dies out. Perhaps you can think of a way to contain the randomness
to a particular portion of the grid.
Further Thoughts
The Game of Life changes fundamentally when mixed with a random element. Could
there be a way to add a random element without fundamentally changing the Game
of Life? Perhaps there is a way to rein the randomness so that the entire grid
is not overcome by a detrimental wave of unpredictability. Is this random element
fatal specifically to the Game of Life or is there ever away to add randomness
to a deterministic system? Hopefully through better modeling and increased understanding,
the answers to these questions and others unasked will emerge!
References
Wonders of Math:
The Game of Life, 2000-2005.
Exploring Emergence,
Epistemology and Learning Group, MIT, 1996.
Full Name: Sarah Malaya Sniezek
Username: ssniezek@brynmawr.edu
Title: NetLogo Basketball
Date: 2006-05-10 14:10:03
Message Id: 19300
Paper Text:
<mytitle>
Emergence
2006 Course Projects
On Serendip
WHAT IS IT?
This model is a simplified depiction of a basketball game. There are two teams of five players, one blue and one green. One team has the ball at a time. The team with the ball has the ability to move randomly and the team without the ball will follow. The ball is either passed to a random player on the same team shot at random in a 2 pass to 1 shot ratio. Once the ball is shot the probability of making it is a function of the number of passes and the distance from the hoop. After a shot is taken the other team gets the ball whether made or missed.
This model is intended to depict the emergent aspects of athletics, within the context of the sport of basketball. A model of a simplified basketball game is set up where the goal of each team is to score points by making shots. The ability to make a shot is a random function, but also influenced by how far the shot is taken from the basket and the number of passes within a possession. Although making shots is the general goal, by incorporating a learning mechanism the blue team players synthetically "learn" how to maximize their ability to make shots. While the blue team has this ability to "learn", the green team does not; therefore, the two can be compared to see the effects of changing one's actions based on prior results.
HOW IT WORKS
Upon setup, the turtles are set up randomly; however, they can be moved via mouse throughout the world. The blue team always starts with the ball and when play commences the two teams have an equal likelihood to either pass or shoot, as well as an equal likelihood to make shots; however both functions change for the blue team as the game is played.
The equation for the probability of making shots is based on two factors. First, the court is split up into three distances from each team's respective hoop. The close_distance has an inherent value of 90, the medium_distance, 60, and the far_distance, 30. The shot is always taken from one of these three regions and the value of the region is labeled the shot%, which is put into the shot probability equation. The second aspect of the shot equation is the number of passes from the time the team receives the ball to the shot. Therefore, one side of the equation is: (number of passes) x (shot %). Also, at the time of any shot a random number between 0 and 300 is chosen. If this number is less than the value derived from the equation above (passes x shot %), then the shot is made, if not, it is missed. This ceiling of 300 can be changed to make the game more difficult or easier. The Overall Shot probability equation is: ifelse random 300 < ( shot% * passes) [make] [miss].
The Green team is set up in such a way that the team will shoot the ball 1 out of every 3 times and pass it 2 out of every three times. The learning mechanism for the blue team is set up to influence the amount of passing in which the blue team will do. Initially, the ratio of pass to shoot is the same for the blue as it is for the green, 1 out three is a shot. However, the blue team's equation is different such that it takes into consideration prior makes and misses. Instead of the green team's equation for shooting: ifelse random 15 < 5 [shoot pass_in wait 1][pass], the blue team equation is: ifelse random 100 < (33 - (missedshots * 5) + (score * 2) ) [shoot pass_in wait 1][pass]. This means that the amount of shots missed multiplied by 5 is subtracted from the original pass threshold of 33, while the number of shots made multiplied by 4 (which is equal to score x 2) is added to the threshold. Ultimately, the more shots missed, the more likely to pass, and the more shots made, the more likely to shoot. In effect, the blue team learns how to maximize their shoot to pass ratio, in order to maximize their ability to make shots.
HOW TO USE IT
Two buttons, SETUP and PLAY, control execution of the model. As in most NetLogo models, the SETUP button will put the players randomly on the court and create the two hoops. The PLAY button, a forever button, will then run the model. The MOVE BLUE PLAYERS (taken from Mouse Click & Drag Example in Models Library)button will move the blue players where ever on the court, because some times when they are setup, they are all on one end of the court. BLUE T-PASSES is the total number of passes the blue team has made the entire game. BLUE PASSES is the number of passes in each possession by the blue team. BLUE SHOTS is the number of total shots taken by the blue team throughout the entire game. BLUE MISSED SHOTS is the number of shots the blue team has missed throughout the entire game. BLUE TEAM SCORE is the total number of points (shots made * 2) the blue team has in the game.
GREEN T-PASSES is the total number of passes the green team has made the entire game. GREEN PASSES is the number of passes in each possession by the green team. GREEN SHOTS is the number of total shots taken by the green team throughout the entire game. GREEN MISSED SHOTS is the number of shots the green team has missed throughout the entire game. GREEN TEAM SCORE is the total number of points (shots made * 2) the green team has in the game. PASSES PER POSESSION is a graph of the number of passes per possession as a function of time. It has two lines, one blue, representing the blue team, and one green representing the green team. COMMAND CENTER displays the values for the shot probability equation. It shows the shot%, number of passes, and the two multiplied together for every shot. It also shows which turtle took the shot.
THINGS TO NOTICE
The major two things to look at are the command center and the graph. From the command center one can see how the overall shot probability value (shot% x passes) is effected by passing. It is also good to look at the values for the blue team compared with those of the green team as the game moves on.
The graph is the most important thing to look at. The graph shows the passes for every possession. As the game goes on, the number of passes should increase for the blue team, while for the green team, it will remain constantly low. However, the blue team will eventually find an equilibrium, and the number of passes will generally stay within a certain range. At times there will be drops in the blue passing level, but it should usually be followed by an increase in passing once the team has reached its equilibrium.
THINGS TO TRY
Although no sliders were created in this model, different values should be manipulated by the user to see the effects that those changes might have. One major value that can be changed is the random sample number for the shot probability. The default is 300. Increasing the value would make making a shot more difficult. One could also change the shot % values.
Second, one could change the pass threshold for the blue team. Its default value is 33 of 100, but it could be raised or lowed to make shooting or passing more probable respectively. More importantly one can change the made shot and missed shot multipliers. There are 4 and 5 respectively. By changing these numbers the blue agents will put more emphasis on the effects of making or missing a shot. This will greatly change how they learn as well as the equilibrium in which they achieve.
Also, it is important to note that the distance from the basket influences the probility of making a shot. Therefore, if one wants a "fair", he or she should set up the players equal distances from the baskets. At the same time one can make it more difficult for the blue team by setting the further from their basket, and see if they learn to overcome their handicap.
EXTENDING THE MODEL
Because basketball is such a complex game, there are endless amounts of features that could be added to make the game more realistic. Here are a few things. First momentum can be made a factor by building in a factor into the shot probability equation that takes into account the amount of made shots made in a row, or missed in a row. A shot clock can be implemented so that a team just can't pass forever. With that the team can learn to minimize shot clock violations. Also, to discourage too much passing, 1 out every 10 passes can result in a steal by the other team. Furthermore, it can be set up so that passes are more likely to go to players closer to the basket. As of now there are only three regions where players have different shooting percentages. This can be increased to 7 or 8.
Something that would be extremely interesting would be to have different types of players. Some that tend to shoot more, some that pass more, some that steal the ball more, some that tend to stay close to the basket, etc, and allow the user to choose 5 players from any type. It can then be seen under which combination of players does a team succeed most.
RELATED MODELS
In the models library:
*Biology
-Aids
-Disease Solo
-Virus
*Code Examples
-Mouse Click & Drag Example
-Plotting Example
-Shape Animation Example
CREDITS AND REFERENCES
Sarah Sniezek's NetLogo Basketball Game
Full Name: Angad Singh
Username: adsingh@haverford.edu
Title: NetLogo Segregation Models
Date: 2006-05-10 14:37:50
Message Id: 19302
Paper Text:
<mytitle>
Emergence
2006 Course Projects
On Serendip
"Racial integration is the only course which explicitly seeks to achieve a single nation rather than accepting the present movement toward a dual society" - Kerner Commission
Framing the Issue:
In conducting research to inform my NetLogo model, I first wanted to confirm my suspicion that racial segregation in America was a worthy topic to pursue. I read sociology essays and perused government statistics. Because this background information is only tangentially related to the project assignment itself, I'll focus more on brevity than thoroughness. There is a plethora of statistical evidence suggesting that segregation causes key indicators such as education, employment, and health to suffer. I'll only briefly delve into the issue of education with the intention of it being representative of other social ills potentially associated with racial segregation [from government statistics and George Gaister's essay "Polarization, Place, and Race"].
In terms of education, black youths are 30 percent less likely to finish secondary school than whites, and Hispanic youth are 170 percent less likely. The education gap between black and white Americans widens further in college, where college completion rates for whites is 85 percent higher than for blacks. This is due in part to the large concentration of minority youth in large urban school districts. For a number of reasons, the clustering of minority students itself is a determinant of their educational success. For the nation's largest forty-seven school districts, the dropout rate is about twice the national average. The racial composition of the largest eleven school districts is majority non-white, with Denver being the most white at forty-one percent.
Phrasing the issue as one of segregation, to some extent, misses the point of these NetLogo models. It may be more effective to approach the issue as community clustering, with the understanding that minority communities tend to be apart from white communities in older, core municipalities of metropolitan areas.
Model 1: Assimilate
available at, with some instructions and model description: http://bubo.brynmawr.edu/~asingh/assimilate.html
This model is based on the NetLogo Segregation model. The primary modification is that turtles on the peripheries of their communities become accustomed to turtles of different color through repeated interactions with them. Depending on the set "assimilate-rate", a red turtle may lose its preference for red turtles within one to three iterations. Color preference, in this model, is incrementally lost if and only when a turtle of a particular color is in the vicinity of a majority of turtles of a different color. For instance, a red turtle will incrementally lose its color preference if surrounded by three green turtles and two red turtles. Of course, a red turtle will only have green neighbors if it resides on the periphery of a red community.
Some interesting aspects of the model:
• A higher turtle mobility results in a higher initial segregation peak. Increased mobility allows red and green turtles to more readily realize their ideal environment, which under the settings of this model is a segregated community.
• Time scale: consider each turtle to be a family unit. The children in each family inherit the same color predisposition of the parents. If each family moves 3 times per generation and it takes one generation to lose color preference (assimilate-rate set on 3), then every 3 iterations is one generation. Within just a few generations, we see many boundaries dissolve - but it takes hundreds of iterations to dissolve all communities!
• Percent-green: The percent-green isn't as important as what it shows. Set the green-percent to 0.6 or 0.7. With a smaller overall red population, we see only small red communities that are easier to dissolve. The percent-similar indicator should be ignored because the high prevalence of green turtles will necessarily yield inflated percent-similar numbers. Instead, the visual representation of small red communities quickly dissolving should suffice.
Much of the writing in urban policy and sociology attempts to suggest reasons why segregation has remained persistent in America. Among the suggestions are: interracial economic disparities, preferences for whites to live in predominantly white neighborhoods, and illegal racial discrimination by public and private parties. What this NetLogo model suggests as being incredibly important is the size and density of white and minority communities. This may seem readily apparent and abundantly obvious, but I have not come across it in any literature. The larger, homogeneous communities are difficult to penetrate, and the process by which their peripheries dissolve is painstakingly slow. This is by far the most interesting and surprising outcome of my NetLogo modeling career. The importance of the size and population density of homogeneous communities has been overlooked by academic and popular literature because of its structural and systemic bias. What emergence and my NetLogo model reinforce, instead, is that a large group of individuals are operating under certain predispositions to produce the larger pattern of segregation in America.
Model Two: Allies
available at, with some instructions and model description: http://bubo.brynmawr.edu/~asingh/allies.html
This project grew out of a program sponsored by Haverford, Bryn Mawr, and Swarthmore. It is formally known as the Winter TriCollege Multicultural Institute, though it is more typically referred to as Winter TriCo. It is an intensive, 8-hours a day program for students, faculty, and staff of the three participating colleges. In many of the workshops, persons identified as holding greater power or societal influence were termed "allies" if they utilized their influence in the interest of a subjugated population. In a relatively silly workshop, persons wearing masks aided those not wearing masks, because in that fictional society, persons with masks were granted certain enumerated privileges not available to those without masks. Each masked person thus represented an all: "a person of one social identity group who stands up in support of members of another group; typically a member of a dominant group standing beside member(s) of a group being discriminated against or treated unjustly" (Wikipedia).
Some interesting aspects of the model:
• Unlike the previous model (Assimilate), allies are able to penetrate large swaths of red or green turtles. Though a bit strained, it reminds me of something like an enlightened despot or celebrity on a turtle-based computer-model scale. This ability mitigates the importance of the size and population of segregated communities. I don't think this model is a replacement for the assimilate model, but it serves instead as a complementary supplement.
• It is also interesting to observe the behaviors of blue turtles (termed apathetic because they exhibit no color preference). If the majority of red and green turtles retain their color preference, then there will be a large prevalence of segregated communities. In the narrow regions between these communities is open space for blue turtles to populate. So even though the blue turtles have no internal color preference, they tend to cluster much like the red and green turtles.
Areas of Improvement:
There are a couple levers I could include to make the models more functional or more closely related to reality.
• Racial preference between whites and blacks is not the same. 95% of black Americans would be willing to live in a neighborhood that is 85% white. In opposition to this, only 16% of white Americans are willing to live in a neighborhood that is 57% black. So one possible improvement would be to include differential color preferences. Presently, the color preferences for all turtles as a whole can be manipulated through a slider, but the same level of preference becomes instilled in turtles of all colors.
• Another reality in America is the differential earnings of blacks and whites. This is important for my NetLogo models because it places constraints on mobility. White Americans are more able to move into a neighborhood of their liking, resulting in the phenomenon known as "white flight". Black Americans, on the other hand, are on average less able to move to a neighborhood of their liking.
And of course there are an infinite other possible improvements to these models. Because they are the first computer models I've ever created, I'm unfamiliar with a lot of the possibilities with programming. If you have any suggestions, or just want to tinker with the code, please go ahead.
Full Name: Jesse Rohwer
Username: jrohwer@haverford.edu
Title: Visual Modelling in NetLogo of Methods for Searching a Space
Date: 2006-05-11 16:30:58
Message Id: 19325
Paper Text:
<mytitle>
Emergence
2006 Course Projects
On Serendip
In this paper, I explain the objective of my project, give a general description of how I built my model in NetLogo, briefly summarize the concepts behind various search methods, report on the outcome of my efforts, and offer some ideas based on my findings.
I started my project with the objective of creating a flexible model in NetLogo that would visually illustrate the performance of agents searching a 2-dimensional solution space. I wanted to create a model that would be both an easy-to-follow graphical model of the search and a statistical tool that could help the user discover which of the four search methods we discussed in class (hillclimbing, simulated annealing, computational temperature, and genetic algorithms) was best-suited to different types of fitness landscapes (i.e. different types of fitness distributions over the 2-dimensional solution space). The project went well, except that I have not yet completed the genetic algorithm search option, so my model illustrates comparisons between only the first three methods.
My first problem was finding an easy way to generate fitness landscapes. I wanted the user to be able to quickly and easily distribute fitness across the solution space in a way that allowed the creation of different types of fitness landscapes but that was also fairly predictable, so that the user could choose which type of landscape they wanted to generate. I needed to find some way to parameterize the general qualities of a fitness landscape relevant to agents searching it. The first of these general qualities I addressed was smoothness.
When the landscape was first created, it was very "rough"¡ªI started the landscape with a random distribution of fitness, from 0 to 300 (since this range is large enough to realistically model many fitness functions, but does not exceed the 256 colors I used to represent fitness by enough to compromise the visual representation). Whenever the user made changes to the landscape that might affect the maximum and minimum fitness, my scaling function could (and should, for statistical purposes and to avoid a misleading visual representation) be used to map the new values back onto the 0 to 300 range.
To smooth the landscape, I let the user control the application of the NetLogo primitive ¡°diffuse¡± to the fitness of the entire landscape; this distributes a variable in one patch among the neighboring patches, modeling natural diffusion of a gas or liquid down its concentration gradient. This smoothing function created a gracefully curved landscape with relatively few local maxima and minima.
To introduce sharp edges, I created a function that caused the fitness of the landscape to separate at an adjustable point (set by default as half the maximum fitness). Thus, by clicking ¡°diverge¡±, the user could make half (by default¡ªany other fraction could also be attained) of the landscape decrease in fitness while the other half increased, creating ¡°cliffs.¡± More general ¡°roughness¡± could also be attained with the function ¡°scramble¡±, which simply reset the fitness of each patch randomly to a value within a user-determined range of the initial fitness.
Using a combination of these three functions (¡°smooth¡±, ¡°diverge¡±, and ¡°scramble¡±) and re-scaling the landscape appropriately after each change, it was possible to create a wide variety of landscapes. However, it smoothness was an all-or-none option, because I had not placed limits on the fitness (i.e. fitness could become arbitrarily small or large, and as soon as the patches were rescaled, it would still be smoothly distributed between 0 and 300). Thus, even when ¡°diverge¡± was used to create cliffs, these cliffs were still approachable and climbable, because there was always a slight slope following their rise or fall. To fix this problem and allow the user to create difficult-to-navigate plateaus, I created an option to prevent fitness from rising above 300 or falling below 0, so ¡°diverge¡± could be used to squash the landscape flat at the highest and lowest points. By adjusting the point from which the fitness diverged, the user could place these plateaus at whatever altitude they wanted.
The plateaus also inspired me to add another option: when the fitness exceeded the acceptable range, it could be inverted instead of kept constant at the floor or ceiling; this created a highly ¡°folded¡± landscape. With ¡°invert¡± on, diverging for a long time produced a pattern of concentric ridges and valleys.
Finally, I wanted to allow the user to partition the landscape even more severely, so that the difficulty of searching solution spaces with highly isolated or unpredictable maxima could be visually represented. To do this, I created a function for laying a set of lines of 0 fitness across the entire landscape, either horizontally or vertically, at an adjustable interval. With these functions, the a highly diverse array of landscapes could be generated.
I allowed the user to populate the landscape with any number of agents so that statistics for performance on the various landscapes could be averaged easily and quickly from a large sample (although with more than a few thousand the program would start to slow down significantly). The agents¡¯ progress could be tracked on a plot of agent fitness over successive iterations, or by comparing various monitors of average, best, and worst agent fitness to monitors of average landscape fitness and to the visual representation of the landscape. Or, the user could watch the progress of an individual agent following the algorithm for hillclimbing, simulated annealing, or computational temperature.
Hillclimbing is an algorithm in which the agent simply searches the immediately adjacent positions and moves to whichever is most fit. This makes sense, as the agent¡¯s current location on the landscape represents a solution to a problem. In the case of my model, the problem has two parameters. The agent¡¯s position along the x-axis is the value of one parameter, and the position along the y-axis the value of the other. So hillclimbing is simply trying out all the possible new combinations of output values (i.e. all other possible solutions) that are attainable by changing the current values (the current solution) by the minimum increment.
In simulated annealing, agents hillclimb with some randomness in whether or not they pick the best adjacent position. The randomness varies according to the ¡°temperature¡±, a variable that decreases with time. In my model, the user can adjust the temperature and the rate at which it falls as the agents are searching, allowing the user to experiment with the effects of different temperatures in real time.
Finally, computational temperature is like simulated annealing except that the temperature increases when the agent gets frustrated by getting stuck in the same position. In my model, I set each agent¡¯s temperature (or ¡°frustration¡± in my model) at 0 to begin, and increased it by an amount determined by their collective ¡°impatience¡± (a user-controlled variable) for each iteration that that individual agent chose to stay in its same location. Once an agent¡¯s frustration was sufficient for it to move, I decreased it¡¯s frustration by another adjustable variable, ¡°calmRate¡±, each time it moved to a new location.
Experimenting with these three search methods on a variety of different fitness landscapes was interesting. There wasn¡¯t as big a difference between the agents¡¯ performance with different methods as I had expected. In this paper¡¯s conclusion, I express some thoughts on how the methods could have been improved. However, despite being less that what it could have been, the difference was enough to be significant.
As I expected, on ¡°rough¡± landscapes with a moderate degree of randomness, simulated annealing and computational temperature outperformed hillclimbing, whereas on the smooth landscapes, hillclimbing was a much more efficient and reliable way of reaching the same solutions that simulated annealing and computational temperature were likely to reach.
What disappointed me was the failure of the second two methods to improve substantially on hillclimbing in highly partitioned landscapes. My implementations of simulated annealing and computational temperature were only marginally more successful than hillclimbing at escaping from local maxima and discovering the absolute maximum. Of course, if enough randomly seeded agents were used, some of them would always start in the ¡°right¡± position and attain the best solution. But I was unable to get the agents that had started in the ¡°wrong neighborhoods¡± to strike out, explore, and discover a new maximum. However, this problem could probably be solved:
A method that I think would be effective on smooth or rough landscapes at finding the absolute maximum regardless of starting position involves reverse hillclimbing, i.e. descending the hill instead of ascending it. It would be a simple matter for an individual agent to hillclimb until it gets stuck, record the coordinates of that maximum, and then descend, by the steepest route, to the worst solution. From there, it would hillclimb again. In some situations, since the steepest path down is sometimes also the steepest path up, the agent might need to make a few random choices at local minima to avoid always retracing its steps. In the same way, some randomness or memory of which ¡°directions¡± it had previously chosen might be needed when the agent is first descending from a peak to avoid setting out in the same direction and reaching the same local minimum, if that minimum has already been explored. Once the agent is finding no new maxima, it can simply choose the best of those that it has found and recorded. This same principle¡ªdeliberately relocating to the worst locally accessible solution in order to overcome partitions in the landscape¡ªcould be applied with simulated annealing and computational temperature.
Another search method that I had planned on including in the project but that I was unable to finish in time is the evolution of genetic algorithms. To me, the most obvious method of implementing a genetic algorithm in my model would be to have each unit of displacement along an axis be a ¡°gene¡±. Thus, crossover between two agents would place their offspring somewhere within the rectangle that had the two parent agents at the corners. Clearly, this would facilitate the exploration of the area between already-discovered local maxima, since those agents on the peaks would be the most fit and most likely to reproduce. Thus, genetic algorithms would probably do well on partitioned landscapes.
In conclusion, my model is a useful tool for visualizing the search of a solution space, but could certainly be improved to include more search methods and new types of fitness landscapes.
Full Name: Flora Shepherd
Username: fshepher@brynmawr.edu
Title: The Story of Modeling the Mommy Wars
Date: 2006-05-24 13:39:02
Message Id: 19418
Paper Text:
<mytitle>
Emergence
2006 Course Projects
On Serendip
I count things. For as long as I can remember, I have counted everything around me in my quest for patterns, for the rules of the world. Yellow and white lines on the street, tiles on the floor, lamps in coffeehouses, pretty much every set of discrete objects I saw, I was convinced, contained a secret. Mildly OCD, I made up systems of behavior around the patterns I saw around me, predicted the safety of my family based on which lane my Mom chose to drive in on the highway. Given this childhood, it is only natural I crave the comfort patterns of numbers give me in my gender studies classes. But, I have never read a feminist theory written in formulas. There are too many variables to consider in explaining social phenomena. Rhetoric captures the nuances of interlocking systems of oppression better than mathematics.
Emergent computer modeling combines the attributes of rhetoric and classical mathematics. The results of models are repeatable, like a good physical formula, but the outcome of an argument is extremely difficult to impossible to predict and requires interpretation, like a good piece of writing. Many scholars already employ computer models to test their theories in social areans. However, much of feminist theory includes a top-down approach to social phenomena: a overbearing system that dictates the behavior of men and women. Emergent models can only illustrate a system composed of many agents. I needed to find a feminist theory that gave women agency within the confines of a restricted environment and I found it in Deniz Kandiyoti's "Patriarchal Bargain."
In this article, Kandiyoti compares women's reactions to social change in various cultures. She concludes:
Women's strategies are always played out in the context of identifiable patriarchal bargains that act as implicit scripts that define, limit, and inflect their market and domestic options...A focus on more narrowly defined patriarchal bargains rather than on an unqualified notion of patriarchy, offers better prospects for the detailed analysis of processes of transformations."
In her analysis, women have agency and make decisions based on the options available to them. She does not view women as slaves to a dominating culture but rather as agents making the best of the world them have based on cultural and social boundaries. This is a theory that can be pushed into an emergent model.
I chose to model the current "mommy wars," the endless arguments between couples that choose to have a stay at home parent and couples that choose to have a double breadwinner family. By far, the most difficult part of constructing a model was breaking down the theory into programmable parts. I am more used to portraying the complexities of social interaction in words rather than quantities within an environment. I had to pick and choose which social factors to include and how to include them. Also, I fought very hard to keep my own political views out of the model. I did not want to favor one style of parenting over another. I wanted to create a world where the observer could change the environment in a great many ways and watch societal change unfold. Translating a rhetorical idea into logical processes agents could follow was an exciting mental exercise. I thought about many facets of the mommy wars argument in different ways than writing about them would cause me to.
I wanted to create an unpredictable Net-Logo model that was easy to manipulate. There are four variables in this world: single or double breadwinner families, childcare cost, class and family income. An observer can control the likelihood that a family will choose to be a single or double breadwinner family. This control symbolizes the cultural pressure from the society the agents live in. Childcare cost can be controlled as well, but the observer controls basic childcare cost. The cost goes up for families in higher classes and for double breadwinner families. Family income is determined by two variables. First, the class of the family determines the peak salary amount for the breadwinner(s) and the amount of high paying jobs determines each family's ability to receive the highest salary they are capable of. The minimum salary can also be controlled. This world is a simplistic one. It does not factor in added childcare costs of health problems, families incapable of having two breadwinners, any form of social discrimination and many other important social phenomena. I am a beginning programmer and this model is far from perfect. My aim was not to model the world but to model the decisions families make everyday. I am not a parent myself, but I based the ideas for the constraints of my model on my own observations and Kandiyoti's assertion that a family works within certain constraints.
My findings were quite upsetting. An upper class, wealthy society could be sent quickly into debt by skyrocketing childcare cost. However, this imbalance could be quickly corrected by switching childcare approaches. High childcare costs sent the society into single breadwinner mode while low childcare costs sent the society into double. This model further impressed upon me the complexities of social interaction. An effective analysis and model of society cannot be created using cultural ideology or economic structure alone. If the combination of the two was necessary for my model of a fake world, then they become even more important in daily life.
So, what did I learn about the Mommy Wars from my model? The issue is complicated, much too complicated to derive a right and wrong way to raise a family. I find it difficult to compare and contrast the families in my artificial world. Each one had a different set of circumstances. And, with each step, each generated a random number that was their likelihood to be a double breadwinner family. Depending upon where that number fell on the number line of the model society, they would make a certain decision. It was not the point of this model to prove that children need a stay at home parent in their infancy. I only sought to figure out how people make these decisions. And, whichever side a person may take, s/he will have to do more than spout ideology to make social change. The strongest factors in this model were societal and economic ones.
I think this model was most useful to me as a learning tool. I thoroughly thought through the issue that I wished to model. However, it would have to be greatly altered to be more useful and accurate in an academic or social setting. A more sophisticated version of this model would be able to accept real demographic data to simulate the impact of various societal changes. I do believe that this could be useful in a practical way. And, the results are quite interesting, so I think that academics would enjoy it as well.
Works Cited:
Kandiyoti, Deniz. "Bargaining with Patriarchy" Gender and Society, Vol. 2, No. #, Special Issue to Honor Jessie Bernard (Sep.,1988), 274-290.
Go to first comment or
Post a comment
|
To Emergence Course 2006 |
To Forums | To Serendip Home |
