|
Author
|
Topic: MESA: Monotonic Evolutionary Simulation Algorithm
|
William A. Dembski
Member
Member # 7
|
posted 31. March 2002 23:31
[Note for Brainstorm Participants]
MESA is a work in progress. We will continue to add functionalities to the program. We solicit your feedback for strengthening the program as well as for interpreting its results. The Brainstorms discussion forum is the place for that feedback (minus troubleshooting issues which should be directed to micah.sparacio@iscid.org). Eventually, we may make MESA an open source code project.
MESA: Monotonic Evolutionary Simulation Algorithm
MESA models evolutionary searches that employ monotonic smooth fitness gradients. It presupposes a fitness landscape that converges gradually to a single optimum and asks how quickly evolution can locate the optimum when fitness is randomly perturbed and/or when variables are coupled. Its aim is to determine the degree to which fitness perturbation and variable coupling impede evolutionary searches.
To run this program you must have the Java Runtime Environment (JRE) installed on your machine.
For an overview of the program, click here.
For a quick guide to the program's functions, click here.
To download and run the program, click here.
JRE for Windows: http://java.sun.com/j2se/1.3/jre/download-windows.html
JRE for other systems: http://java.sun.com/getjava/others.html
Update 9/9/02
MESA Long Run
This program is functionally equivalent to the normal MESA program except that it automatically runs through 100 trials at each Coupling Degree and then increments the Coupling Degree by one. This automates the process of running long trials.
To download and run MESA Long Run, click here.
Copyright notice: ISCID retains copyright on the MESA program. MESA can not be redistributed or modified in any way without explicit permission from ISCID. Copyright 2002 by ISCID.
[ 09 September 2002, 07:10: Message edited by: Moderator ]
IP: Logged
|
|
Micah Sparacio
Member
Member # 6
|
posted 01. April 2002 15:21
An observation:
There are lots of parameters to play around with in MESA. Surely there are many surprises to be discovered that outdue this bland observation. In any case, I thought I'd put it up to share with other MESA users. Given the default values, I ran 20 simulations: 10 with crossover on and 10 with crossover off. When crossover is on, the system gets to the target ~2.6 times faster (by generation).
Here are the numbers:
Crossover On:
Generations, Mutations, Crossovers
69, 647, 2037
70, 681, 2099
64, 659, 2009
62, 633, 1873
67, 672, 2052
63, 653, 1892
62, 657, 1881
96, 971, 2910
83, 856, 2489
49, 496, 1530
Average: 69, 693, 2077
Crossovers Off
Generations, Mutations, Crossovers
189, 1826, 0
183, 1769, 0
179, 1791, 0
170, 1729, 0
186, 1842, 0
166, 1646, 0
176, 1788, 0
181, 1768, 0
174, 1782, 0
177, 1770, 0
Average: 178, 1771, 0
[ 01 April 2002, 15:26: Message edited by: Micah Sparacio ]
IP: Logged
|
|
Micah Sparacio
Member
Member # 6
|
posted 03. April 2002 14:53
I'd to like solicit the help of the Brainstorms community in running a MESA experiment:
Of course you will first have to download the program. Default parameters are set each time you open the program. We are going to leave all of these but two the same over the course of this experiment.
We are going to test the effect of "Coupling Degree" on the GA.
To begin, start by entering "5" in the first text box under "Coupling Degree" and "1" under "Total Couplings". Run the simulation by clicking on "Start"
Record the number of generations it took to get to the target, and whether crossover was on or not.
Next, run the simulation with the same settings, except this time "Turn On Crossover". Record the same information.
Continue this process while incrementing the "Coupling Degree" by one on each set of simulations. Go as high as you would like (once you are in the the high teens for coupling degree you may want to run simulations overnight or when you have other things to do between runs). When you are done, report your findings back here.
Here are some preliminary numbers that I got on an initial run through. Note that on duplicate runs there is a wide variance, and that your numbers will probably be very different than mine. Thanks for any time you put into this. I really don't know what to expect from the results...right now I'm just data mining.
Degree, Generations, Crossover On or Off
5,602,off
5,68,on
6,330,off
6,98,on
7,1048,off
7,1099,on
8,7064,off
8,2211,on
9,9280,off
9,1422,on
10,10044,off
10,3363,on
11,8975,off
11,12645,on
12,24425,off
12,10932,on
13,26240,off
13,12213,on
14,51128,off
14,27654,on
[ 03 April 2002, 14:59: Message edited by: Micah Sparacio ]
IP: Logged
|
|
Donald A. McLaughlin
Member
Member # 57
|
posted 04. April 2002 00:50
A couple of suggestions for the MESA program.
1. Add a reset button so that all values can be reset to defaults if we want to start over.
2. It would be helpful to have some way to take each result and have it recorded in either some pre-determined format or flipped into an Excel spread sheet or something.
3. A pull down help menu with terms and definitions.
Thanks
Donald M
IP: Logged
|
|
RalphW
Member
Member # 116
|
posted 05. April 2002 23:30
Another suggestion - support the creation of an input file that contains the specifications for multiple runs (including the names of the files in which the output should be saved). This would allow the job to run unattended for days at a time performing multiple simulations. The option to stop a batch run and then restart it where you left off would also facilitate doing large scale simulation runs.
IP: Logged
|
|
Micah Sparacio
Member
Member # 6
|
posted 08. April 2002 12:34
An explanation of coupling in MESA
The intuition behind coupling in the MESA program is that by requiring certain bits to mutate in tandem before conferring a fitness advantage, we may be able to simulate the need for coordinated mutations in biology.
"Coupling Degree" in the MESA program simply indicates the number of bits in a bit string that must mutate together to confer an advantage. "Total Couplings" indicates the number of groups there are. So if you were to choose a coupling degree of 30, and 1 total coupling, there would be 30 bits at the beginning of each bit string in the population that would be grouped together. These bits would all need to mutate to the target value together in order to confer an advantage.
One obvious way to make use of this system, is to map it onto words or letters. We can assume that each letter is 8 bits as is in the standard ASCII representation.
So, if we wanted to reproduce Dawkins' ME THINKS example, we could do so in a variety of ways.
(NOTE: this representation will not be completely analagous to Dawkins' example because Dawkins does not allow for subsequent mutation on "selected" letters)
First, we could select by individual character. There are 29 total characters in the following phrase:
ME THINKS IT IS LIKE A WEASEL
To simulate the selection of individual characters, we need a bit string consisting of 232 bits (29 * 8 = 232). We then simply indicate on the MESA program that we want a "coupling degree" of 8 bits and a "total couplings" of 29. My intuition is that the program will converge on the target in a relatively short period of time.
We could also simulate this program by selecting for words rather than letters. Let's take the Dawkins example again:
In order to select by words we need to calculate the total number of bits per word:
ME: 16 bits
THINKS: 48 bits
IT: 16 bits
IS: 16 bits
LIKE: 32 bits
A: 8 bits
WEASEL: 48 bits
SPACES: 8 bits each
Once again our string length will be 232. We then need three 16 bits couplings (Couple Degree: 16, Total Couplings 3), seven 8 bit couplings, two 48 bit couplings, and one 32 bit coupling.
Coupling Degree, Total Couplings
16,3
8,7
48,2
32,1
IP: Logged
|
|
Micah Sparacio
Member
Member # 6
|
posted 10. April 2002 19:00
The following note from a friend was sent my way regarding the reason that crossover has had an influence on the generation times it takes to get to the target:
"I think the reason the crossover speeds things up in your coupled simulation, is as follows. I noted that very quickly all the "uncoupled" bits go to zero and stay there. For the remaining coupled bits, you have, in fitness terms, a completely flat plateau, with only a single point that is advantageous. Hence with just mutation, you are effectively performing a blind search. The mutation rate is about 1 bit per genome, so if you have 10 coupled bits in a 100 bit string, only 1 in 10 mutations are going to make a difference (or 10 individuals on average in a population of 100). The expected time for the blind search to succeed should scale exponentially with the number of coupled bits. However there will be a large variance. If you introduce crossover, as your crossover operator operates on many segments in the string (e.g. 60% of the bits are crossover points), this of course means that every individual will change in the coupled area at each generation, and hence the "blind search" for the string of zeros will be much quicker."
IP: Logged
|
|
Micah Sparacio
Member
Member # 6
|
posted 15. April 2002 09:43
MESA and Stasis
When MESA randomly generates an initial population there is, for the large part, a heterogeneous group of organisms. This diversity in the population raises the probability that a solution to the target will be discovered quickly, even if there are coupled bits. However, due to selection, the population becomes largely homogeneous in short order, with diversity normally ranging over only a small number of bits. This new homogeneous state of the population makes it far less conducive to finding the target, and thus a long period of stasis normally (though certainly not always) sets in.
[ 15 April 2002, 12:47: Message edited by: Micah Sparacio ]
IP: Logged
|
|
Daniel R. Kuebler
Member
Member # 222
|
posted 16. April 2002 14:52
Although this is a bit outside my field, I have enjoyed playing around with the MESA algorithm. I have noticed that when the elitism is on and the uniform fitness perturbation is set to 0, that the algorithm stalls in its search to find a simple 10 bit coupling. It appears that once a string has the 90 uncoupled bits go to zero, it quickly spreads throughout the population because it is ensured to make it to the next generation without mutation when elitism is on. (This does not happen when elitism is off.) The algorithm seems to stall at this point with most or all of the strings being identical. I'm not sure what elitism is attempting to model as regardless of the fitness of a biological organism, it is never exempted from the possibility of mutation. It seems that this function, which in some cases may speed the algorithm up because it ensures the perservation of the best organisms, is not really relevant to the biology.
Another comment is that by randomly perturbing the fitness of a string, one has the mechanism by which a portion of a population may be able to traverse valleys in a fitness landscape.
Intuitively random perturbation makes sense as an excellent genome can be squashed by a chance meeting with a train at a railway crossing.) In MESA, the population is evolving toward all zeros (zero peak) and there is more or less a smooth fitness gradient leading up to the zero peak. Suppose however that there was also a ones peak such that a string with all ones would have the same fitness value as a string with all zeros. If this were the case, a valley would exist between the two peaks, the zero peak and the ones peak. If a population was halfway up the zero peak it would have to have a decrease in fitness to move toward the ones peak. This wouldn't happen without random perturbations to the fitness function. However, if 15-20% of the fitness of a string was due to random perterbations (this is probably not too far fetched from biological reality), it would be possible to move some strings across that valley to the base of the ones peak. Such an algorithm would allow for a portion of a population to traverse valleys in a fitness landscape. This random fitness perturbation is much closer to what happens in reality and has some interesting possibilities.
IP: Logged
|
|
Micah Sparacio
Member
Member # 6
|
posted 18. April 2002 17:35
DrawMesa
I've been playing around with the MESA system and have developed a little application that some of you might enjoy trying out. You get to draw a target picture and an initial starting picture and watch the GA converge from the initial picture to the target image. There are still a few little bugs, and I hope to add more functionality, but I am going on vacation for a bit and thought I'd let anyone who is interested play around with it in the mean time.
Just as a note, the initial load time after hitting start takes several seconds. Also, the convergence is not super fast.
[I've made an important update to the program 6:24pm Eastern US time on April 18]
Download DrawMesa.
[ 18 April 2002, 18:32: Message edited by: Micah Sparacio ]
IP: Logged
|
|
Donald A. McLaughlin
Member
Member # 57
|
posted 26. April 2002 12:46
How is the Mesa Draw program different from or similar to Dawkin's little draw program discussed in The Blind Watchmaker? Is there a way to experiment with one vs the other to obtain any meaningful results? After all, Dawkins went to great lengths to explain how his program demonstrated that natural selection alone could produce all sorts of novel life forms. It might worth trying to run some sort of comparative study and see what develops and what the results might mean.
Donald M
IP: Logged
|
|
Micah Sparacio
Member
Member # 6
|
posted 09. September 2002 07:17
MESA Long Run
This program is functionally equivalent to the normal MESA program except that it automatically runs through 100 trials at each Coupling Degree and then increments the Coupling Degree by one. This automates the process of running long trials.
I recommend starting off with a "coupling degree" of 2 and "total couplings" of 1. You can do whatever you'd like with the rest of the settings (including leaving them alone). In order to save the data and stop the run, you will need to press the "Stop" button.
Once you've pressed "Stop" a file called "mesadata" will be saved on your machine in the same directory as the MesaLongRun.jar file. This will contain important information regarding your experiment and I'd love for you to send it to me @ micah.sparacio@iscid.org
To download and run MESA Long Run, click here.
IP: Logged
|
|
|
|
Micah Sparacio
Member
Member # 6
|
posted 14. August 2004 09:15
Scott,
The project has been on hiatus, but I'd be happy to talk to you about how we might get it going again and what direction we might take it.
Send me an email:
micah.sparacio[a-.-t]iscid.org
Best to you,
Micah
IP: Logged
|
|
|
Printer-friendly view of this topic