I have been here before. This is the point in the conversation where Roger
Critchlow explains to me what the hell is going or .... or, i die. Roger?
Is there a confusion here concerning what is the analogue of the individual in
the genetic algorithm?
Nick
Nicholas S. Thompson
Emeritus Professor of Psychology and Ethology,
Clark University (nthomp...@clarku.edu)
http://home.earthlink.net/~nickthompson/naturaldesigns/
http://www.cusf.org [City University of Santa Fe]
----- Original Message -----
From: Ted Carmichael
To: The Friday Morning Applied Complexity Coffee Group
Sent: 7/10/2010 7:11:35 AM
Subject: Re: [FRIAM] Real-world genetic algorithm example... help!
Well, in regards to (1), yes, I would guess elitism + mutation is a good
description. However, I believe that is enough to qualify as a GA. As I
recall, some GA practitioners believe mutation is best, some believe crossover
is best, and some feel you should have both, or decide based on the problem. I
would guess that it is a minority viewpoint to claim that mutation by itself is
not enough to be a GA.
For (3), you say that the genetic operators are not explicit, in the chicken
coop example. My understanding is that sometimes the genetic operator itself
is a part of the genotype, and is thus subject to mutation/crossover as well.
In such a case, it wouldn't really be explicit because it would vary across the
population. Of course, the final genetic operator is discoverable - i.e., it
is recorded in the final solution ... but this doesn't really matter to the
programmer. He has no knowledge a priori of what that operator will turn out
to be; and further, the final genetic operator is not the point of the GA.
Finding a good solution is the desired outcome - the operator is secondary at
best.
For (2), you correctly imply that a phenotype - or genotype - must be
explicitly defined in a computer. Well, sure. The computer is deterministic,
and so this information will be recorded somewhere as part of the code of the
solution. What I find interesting is this idea that the programmer has to know
and care and understand the final solution. I don't think that is the case.
Oh sure, in some instances the final solution is quite clear. For example, the
TSP will end up with a list of city-pairs that is easily understood. But I can
also imagine instances of a GA, say applied to computer code, or a mathematical
formula, that becomes so immensely complex that the researcher does not
understand why the final solution works. And, as pointed out above, he doesn't
have to understand why it works. That it does work well is good enough, isn't
it?
I just don't see any functional distinction between not caring why the final
solution works and - in the case of chickens - not being able to precisely
describe how it works or what it looks like. It's kind of like that DARPA
funded robot pack-animal ... they don't care, really, what all the final rules
are, as long as the robot can walk. In fact, I would suspect that some
flexibility in the 'final solution' is allowed, and that the machine learning
process is continuously running to some degree.
But I am enjoying the discussion, so thanks for that.
Cheers,
-Ted
On Sat, Jul 10, 2010 at 2:50 AM, Russ Abbott <russ.abb...@gmail.com> wrote:
It's not a good example as an illustration of GA because (1) the "selection"
mechanism to move from one generation to the next is essentially select the
best and shake it up. At best you might call that elitism plus mutation. But it
is not representative of GA. (2) it has no explicit representation of the
genome (3) there are no explicit genetic operators applied to one or more
parents to produce children.
The issue of whether there is mutation points out that there is no coop genome
that is being evolved. Since there is no coop genome, it's hard to say that
there is or is not mutation. It certainly isn't a good illustration of mutation
for a textbook.
You might make the case that the coop genome is the collection of the chicken
genomes and that the offspring coop genome is generated from the parent coop
genome by breeding the chickens. I guess you could call that mutation of the
coop genome.So the mutation operator on the parent coop genome is to breed the
chickens to get a new coop genome. But I think that's about as far as you could
push it.
If I were forced to describe this in GA terms, I would say that the coop genome
is the sequence, in some arbitrary order, of chicken genomes. To get an
offspring, take a coop genome and treat the segments that correspond to
individual chickens as separate genomes, mate them to get offspring, and then
concatenate the genomes of the resulting offspring to get a new coop genome.
I've never heard of a genetic operator like that, but I guess that doesn't mean
you couldn't claim it as a genetic operator.
The bottom line for me though is that the experiment is great biology, but it's
a pretty limited and confusing example of a GA.
-- Russ Abbott
______________________________________
Professor, Computer Science
California State University, Los Angeles
cell: 310-621-3805
blog: http://russabbott.blogspot.com/
vita: http://sites.google.com/site/russabbott/
______________________________________
On Fri, Jul 9, 2010 at 11:12 PM, Ted Carmichael <teds...@gmail.com> wrote:
Ha! I knew someone would complain about that.
First of all, Eric is correct: the main point of the story - beyond a nice,
illustrative example of how a GA works - is the need to properly define a
fitness function. In the case of individual chickens, the fitness function was
ill-defined and didn't work very well. In particular, this section points out
that it is not necessary to know why a good solution is good. Why doesn't have
to come into it ... the fitness function simply ensures that the best solution,
no matter what the reasons are for being the best, can emerge from this process.
In regards to Russ' complaints, I'm not sure I can agree that no
crossover/mutation occurred. I haven't read the original paper yet, just the
Huff Post treatment, so I didn't realize that the chicken clusters weren't
mixed. That is, I just assumed that more than one cluster was selected among
the best, and that they collectively produced the subsequent generations.
However, consider the case of mutation. Russ says there is no mutation within
the population elements - the clusters of chickens. But functionally, there
actually is mutation. This becomes obvious when we remember that a
second-generation chicken coop is different from the first-generation coop.
The genes were all there, but some of them weren't expressed ... that is, they
simply combined together in a different way to produce a different coop. It
doesn't matter that the kids have all the genes of the parents ... the kids are
still different.
And we know this is true because egg production went up. This couldn't have
happened unless there was something (crossover or mutation) that changed from
generation to generation.
Regarding James' point, I don't know how the roosters were handled from
generation to generation (something that is probably in the original paper).
But I suppose they could get the next generation roosters the same way they got
the next generation hens - by simply hatching a few eggs.
One final point: since GA originally got its inspiration from biology, I see no
reason why biology can be used to illustrate GA in a textbook. Thoughts?
Cheers,
-Ted
On Fri, Jul 9, 2010 at 10:03 PM, ERIC P. CHARLES <e...@psu.edu> wrote:
Russ,
Completely agreed.
I'm not sure how one would connect the chicken stuff in a pretty way to
standard computer genetic algorithms. I suppose one could relate them together
to suggest the need for variation in "selection" methods when using GAs. That's
Ted's part. I only claimed to know how the chicken part worked through (either
artificial or natural) selection for something other than best individual
production.
Eric
On Fri, Jul 9, 2010 09:18 PM, Russ Abbott <russ.abb...@gmail.com> wrote:
It's a great story, but it's not a genetic algorithm as we normally think about
it. It's really just breeding. For one thing, no computer was involved. The
point of the whole thing is to establish the notion of group selection, which
was forbidden in the biological world for a while. This experiment shows that
it makes sense.
In what sense was it just breeding? Well, what was bred was coops rather than
chickens. So the original population was 6 coops. The best one was selected
and propagated. The best of those was selected, etc. Not at all what GA is
about. There was no crossover or mutation between the population elements --
which are coops. Of course there is crossover among the chickens in the coop,
but it wasn't chickens that were bred. The fitness function was a function
applied to the coop.
So even though it is a very nice experiment and even though it makes a very
strong case for group selection, it's probably not a good example for a chapter
on genetic algorithms in a text book.
-- Russ
On Fri, Jul 9, 2010 at 4:25 PM, ERIC P. CHARLES <e...@psu.edu> wrote:
Shawn,
The two ways to answer your question would either be to invoke artificial
selection (i.e., because you can design a genetic algorithm to do anything you
want, just as chicken breeders can keep whichever eggs or to invoke Wilson's
"trait group selection." In trait group selection you break selection into two
parts, within-group and between-group selection. If you do that, you can, under
the right conditions, find that types of individuals who reproduce less well
within any group can still out-compete the competition when you look between
groups. Math available upon request. I have a vague memory that this has come
across the FRIAM list before.
Eric
On Fri, Jul 9, 2010 06:47 PM, Shawn Barr <sba...@gmail.com> wrote:
Ted,
I'm confused. Why would a genetic algorithm ever select a hen that produces
fewer eggs over a hen that produces more eggs?
Shawn
On Fri, Jul 9, 2010 at 2:57 PM, Ted Carmichael <teds...@gmail.com> wrote:
Nick, this is perfect. Thank you!
BTW - the reason for this request is, my advisor and I were asked to write a
chapter on Complex Adaptive Systems, for a cognitive science textbook. In it,
I talk briefly about GA, and put this story about the chickens in because I
thought it was a neat example.
I'll add the references now. Much appreciated.
-t
On Fri, Jul 9, 2010 at 12:28 PM, Nicholas Thompson <nickthomp...@earthlink.net>
wrote:
Ted,
Ok. So, if I am correct, this was an actual EXPERIMENT done by two
researchers at Indiana University, I think. As I "tell" the "story", it was
the practice to use individual selection to identify the most productive
chickens, but the egg production method involved crates of nine chickens. The
individual selection method inadvertently selected for the most aggressive
chickens, so that once you threw them together in crates of nine, it would be
like asking nine prom queens to work together in a tug of war. The chickens
had to be debeaked or they would kill each other. So, the researchers started
selection for the best producing CRATES of chickens. Aggression went down,
mortality went down, crate production went up, and debeaking became
unnecessary.
The experiment is described in Sober and Wilson's UNTO OTHERS or Wilson's
EVOLUTION FOR EVERYBODY, which are safely tucked away in my book case 2000
miles away in Santa Fe. Fortunately, it is also described in
Dave Wilson's blog
http://www.huffingtonpost.com/david-sloan-wilson/truth-and-reconciliation_b_266316.html
Here is the original reference:
GROUP SELECTION FOR ADAPTATION TO MULTIPLE-HEN CAGES : SELECTION PROGRAM AND
DIRECT RESPONSES
Auteur(s) / Author(s)
MUIR W. M. ;
Revue / Journal Title
Poultry science ISSN 0032-5791 CODEN POSCAL
Source / Source
1996, vol. 75, no4, pp. 447-458 [12 page(s) (article)]
If you Google "group selection in chickens," you will find lots of other
interesting stuff.
Let me know if this helps and what you think.
N
Nicholas S. Thompson
Emeritus Professor of Psychology and Ethology,
Clark University (nthomp...@clarku.edu)
http://home.earthlink.net/~nickthompson/naturaldesigns/
http://www.cusf.org [City University of Santa Fe]
----- Original Message -----
From: Ted Carmichael
To: The Friday Morning Applied Complexity Coffee Group
Sent: 7/9/2010 5:34:29 AM
Subject: [FRIAM] Real-world genetic algorithm example... help!
Dear all,
I'm trying to find reference to a story I read some time ago (a few years,
perhaps?), and I'm hoping that either: a) I heard it from someone on this list,
or b) someone on this list heard it, too.
Anyway, it was a really cool example of a real-world genetic algorithm, having
to do with chickens. Traditionally, the best egg-producing chickens were
allowed to produce the offspring for future generations. However, these new
chickens rarely lived up to their potential. It was thought that maybe there
were unknown things going on in the clusters of chickens, which represent the
actual environment that these chickens are kept in. And that the high
producers, when gathered together in these groups, somehow failed to produce as
many eggs as expected.
So researchers decided to apply the fitness function to groups of chickens,
rather than individuals. This would perhaps account for social traits that are
generally unknown, but may affect how many eggs were laid. In fact, the
researchers didn't care what those traits are, only that - whatever they may be
- they are preserved in future generations in a way that increased production.
And the experiment worked. Groups of chickens that produced the most eggs were
preserved, and subsequent generations were much more productive than with the
traditional methods.
Anyway, that's the story. If anyone can provide a link, I would be very
grateful. (As I recall, it wasn't a technical paper, but rather a story in a
more accessible venue. Perhaps the NY Times article, or something similar?)
Thanks!
-Ted
============================================================
FRIAM Applied Complexity Group listserv
Meets Fridays 9a-11:30 at cafe at St. John's College
lectures, archives, unsubscribe, maps at http://www.friam.org
============================================================
FRIAM Applied Complexity Group listserv
Meets Fridays 9a-11:30 at cafe at St. John's College
lectures, archives, unsubscribe, maps at http://www.friam.org
============================================================
FRIAM Applied Complexity Group listserv
Meets Fridays 9a-11:30 at cafe at St. John's College
lectures, archives, unsubscribe, maps at http://www.friam.org
Eric Charles
Professional Student and
Assistant Professor of Psychology
Penn State University
Altoona, PA 16601
============================================================
FRIAM Applied Complexity Group listserv
Meets Fridays 9a-11:30 at cafe at St. John's College
lectures, archives, unsubscribe, maps at http://www.friam.org
============================================================
FRIAM Applied Complexity Group listserv
Meets Fridays 9a-11:30 at cafe at St. John's College
lectures, archives, unsubscribe, maps at http://www.friam.org
Eric Charles
Professional Student and
Assistant Professor of Psychology
Penn State University
Altoona, PA 16601
============================================================
FRIAM Applied Complexity Group listserv
Meets Fridays 9a-11:30 at cafe at St. John's College
lectures, archives, unsubscribe, maps at http://www.friam.org
============================================================
FRIAM Applied Complexity Group listserv
Meets Fridays 9a-11:30 at cafe at St. John's College
lectures, archives, unsubscribe, maps at http://www.friam.org
============================================================
FRIAM Applied Complexity Group listserv
Meets Fridays 9a-11:30 at cafe at St. John's College
lectures, archives, unsubscribe, maps at http://www.friam.org
============================================================
FRIAM Applied Complexity Group listserv
Meets Fridays 9a-11:30 at cafe at St. John's College
lectures, archives, unsubscribe, maps at http://www.friam.org
