Categories
MURC MURC proposals

Scott’s MURC proposal – draft

To what extent does imitating biological evolution benefit genetic programming?

Genetic algorithms are a set of search algorithms that have been inspired by biological evolution [holland]. They have been used in applications from *** to creative logo design[blprnt], by using variations of biological mutation, fitness-based selection, and populations.

Over the years, the benefits provided by copying biology have been debated. For example, the inclusion of sexual recombination, which is a part of nearly all plant and animal reproduction, drastically degrades the performance of genetic algorithms [nordin] something which evolutionary biologists still don’t have a computationally sound explanation for in biology (R. Redfield, personal communication, February 4, 2010). On the other hand, biological evolution has produced solutions to many different environmental conditions – from the darkest sea-floors, to the driest deserts – which could be used to inform computer science.

There is already a selection of literature on genetic algorithms which would allow a review to explore which aspects of biological evolution are worth emulating, and which have been unhelpful to the field of computer science.

By summarizing the state of the art of genetic algorithms, and comparing that with an introductory understanding of biology, I hope to describe several mechanisms of biological evolution, how they transfer to genetic algorithms, and present a base comparison of whether they are useful in computer science. Due to the situational nature of the search problems to which genetic algorithms are applied, I would expect categorical classification of benefit of these mechanisms to be difficult.

[holland]
Holland, John H. Adaptation in Natural and
Artificial Systems. Ann Arbor, MI: University
of Michigan Press 1975.

[nordin]
Peter Nordin, Frank Francone, and Wolfgang Banzhaf, 1996, Explicitly defined introns and destructive
crossover in genetic programming, Advances in Genetic Programming 2, chapter 6, pp. 111–134, MIT
Press, Cambridge,MA, USA.

[blprnt] www.blprnt.com/variance/

Categories
Week 5

Crossover in biology and computer science

Last week, Rosie was talking about how biologists are uncertain about the benefits provided by sexual recombination. Particularly, she said something about how ‘the numbers’ don’t show any benefit to the organism for sexual recombination. If I recall correctly, sexual recombination is crossover (that’s how I’m going to treat it for this post and someone needs to correct me if I’m wrong).

Then, in my computer science class today, we were talking about Stochastic Local Search algorithms, of which Genetic Algorithms are a subset, and the lecture presented the introduction of crossover as the defining factor of GAs. The impression that I got was that, in computer science, crossover was assumed to be beneficial. And since computer scientists are generally good at calculating the generalized efficiency of algorithms, I assumed that there must be some fairly definite benefit provided by crossover, which contradicts what Rosie said about the mathematic benefits of biological crossover not adding up.

If GAs in computer science benefit from crossover and biological evolution doesn’t, then I see three possible outcomes. 1) The analogy between GAs and biology break down in this case – which is the default assumption. 2) The computer scientists haven’t done strict tests of crossover, and it will turn out to be unhelpful, as in biology. Or 3) GAs and biology both benefit from crossover, meaning that there will be mathematical models of the benefit of crossover from computer science which might be able to inform biology.

I have some discussion on these three possibilities. But I’m going to have to hold off for now.

Categories
Week 4

computer game that teaches an understanding of evolutionary processes?

So I spent the weekend making a computer game with a bunch of complete strangers. We went from nothing to a finished game in 48 hours, with things like sleep deprivation abounding.

In any case, with computer games on the brain, I am wondering how one might create a fun game that teaches the basic processes of evolution. Not the mechanics and dirty work of getting it running (that’s what engineers are for!), but the concepts it would try to incorporate and the abilities it might try to teach.

Let us assume that we are targeting high-school aged students who haven’t yet taken high-school biology. It is difficult to get them involved in studying (because it’s ‘boring’), but if they are really dedicated to the things they find fun and socially acceptable (like games!). They might already have all the formal biology education they’ll ever get, and know Evolution as ‘one of those theories about how animals, y’know, like, change.’

From the topics that we’ve covered so far, which ones would you consider most important? These can be within the context of biology or any other application of evolutionary theory.

How would you frame this in terms of a game?

(I’ll write my own response to this at some point, but I want to hear what others think first.)

Categories
Week 3

A response to the Lynch reading for Tuesday.

I’ve read the first couple sections, and the section on complexity and nonadaptive processes on page 8600, like Yana suggested. I haven’t read the rest of it.

My first impression was a bit of a “well, of course” situation. It makes perfect sense to me that not all changes are adaptive. It certainly sounds like complexity and directional evolution are contentious within the realm of biologists, which is good to be reminded of.

I found the examples of some species becoming ‘simpler’ really interesting. My first reaction was that of “How do we define ‘simple’ and ‘complex’?” It seemed like the argument in the paper was that of species becoming simpler over time showing that complex isn’t allways better. The examples being salamanders losing their legs and vent-worms going from having two opening to having one. These examples seem to be an assumption along the lines of the ‘if it looks like us it is complex’ complex. What if surviving with no legs or no mouth (in the cases of salamanders and vent-worms respectively) is ‘more complex’ somehow. For example, one might need a bi-directional digestive tract to deal with having just one opening, which takes a very complicated gut to deal with things. I can’t say if this is the case or not, but I am uncomfortable accepting the assumption that X change is a ‘simplification’.

Another question I have is based on the following statement:

“However, the effects of mutation and recombination are nonrandom, and by magnifying the role of chance, genetic drift indirectly imposes directionality ….”

Would someone be able to explain how mutation and recombination are nonrandom? I thought that they were by definition random events that were then selected for/against/neutral.

One last thing I’d like to propose is that maybe a better explanation for the survival/fitness of complex organisms can come from their relatively long life instead of them being better replicatiors? If complex multicellular organisms are not as good at replicating, maybe they just hang around because they take longer to be killed off?

-Scott

A response to the Lynch reading for Tuesday.
I’ve read the first couple sections, and the section on complexity and nonadaptive processes on page 8600, like Yana suggested. I haven’t read the rest of it.
My first impression was a bit of a “well, of course” situation. It makes perfect sense to me that not all changes are adaptive. It certainly sounds like complexity and directional evolution are contentious within the realm of biologists, which is good to be reminded of.
I found the examples of some species becoming ‘simpler’ really interesting. My first reaction was that of “How do we define ‘simple’ and ‘complex’?” It seemed like the argument in the paper was that of species becoming simpler over time showing that complex isn’t allways better. The examples being salamanders losing their legs and vent-worms going from having two opening to having one. These examples seem to be an assumption along the lines of the ‘if it looks like us it is complex’ complex. What if surviving with no legs or no mouth (in the cases of salamanders and vent-worms respectively) is ‘more complex’ somehow. For example, one might need a bi-directional digestive tract to deal with having just one opening, which takes a very complicated gut to deal with things. I can’t say if this is the case or not, but I am uncomfortable accepting the assumption that X change is a ‘simplification’.
Another question I have is based on the following statement:
“However, the effects of mutation and recombination are nonrandom, and by magnifying the role of chance, genetic drift indirectly imposes directionality ….”
Would someone be able to explain how mutation and recombination are nonrandom? I thought that they were by definition random events that were then selected for/against/neutral.
One last thing I’d like to propose is that maybe a better explanation for the survival/fitness of complex organisms can come from their relatively long life instead of them being better replicatiors? If complex multicellular organisms are not as good at replicating, maybe they just hang around because they t
Categories
language Week 2

Can linguistic phylogenies exist?

Is a historic (phylogenetic) tree a fair representation of the history of languages?

In a recent linguistics tutorial, we were talking about the formation of Pidgins and Creoles, languages that develop where different languages are forced to interact. The TA used a stereotypical story to try and illustrate how these languages develop, and I’ll recount it now as it helps to explain things.

++The story of Pidgins and Creoles++

Imagine an island where well to-do foreigners show up, set up banana plantations, and get the native locals to pick bananas for them. Neither people speaks the others’ language, and neither is particularly interested in learning the others’ language. The adults just want to conduct buisness as quickly as possible, and so develop a basic code for communicating.

The ‘Language’ that develops generally has little to no grammar. The words are usually taken from one language and then strung together in an arbitrary fashion. For example: “Three bushel banana, ten dollar.” Indicating a willingness to pay ten dollars for three bushels. The important thing here is that this is just a series of important words without grammar, they generally don’t get pluralized or otherwise modified. This is a Pidgin.

Later, the children born into this environment are brought up with most of the communication going on around them in this pidgin. Which means that they aren’t exposed to any grammar. The amazing thing is that without any exposure to a developed grammar they still create one of their own, using the words available but creating grammatical structures from scratch. This has been used as very strong evidence of the fact that every new generation has the potential to create a new language if there isn’t available data.

++Connected to what we’re talking about++

So what if languages are created from scratch? The concern discussed though was that, if languages are created from scratch each generation, how can we say that one language has decended directly from another? One can certainly claim that the majority of a language is similar to another one, but it seems like it would be more accurate to say that language X is 80% language Y, and 20% languages W and Z.

Unfortunately for anyone looking for parallels between linguistic and genetic evolution, this doesn’t seem like genetic evolution. Genetic evolution has a bunch of information passed from one individual to it’s offspring. Language is grown based on the available data, each generation.

So is this just a superficial difference? or perhaps it’s worth keeping in mind? I’ll try to remember to bring this up when we get around to linguistic evolution, and I’ll see if more information comes up in linguistics.

Categories
Uncategorized

testing complete

Well, it looks like nearly everyone has posted now. So that`s working

I`ve checked the settings, and it looks like anyone`s first post is held back for moderation, but after that you`re comments should be pretty much immediate.

Finally, there`s a tag for “unofficial readings” feel free to tag any posts with links as such, I`ve tagged Charlene`s and Greg`s existing posts with this.

-Scott

Categories
Uncategorized Week 1 - testing

Test

adsf

Spam prevention powered by Akismet