🚀 go-pugleaf

In article <1jlmb2INNjp4@gaia.ucs.orst.edu> choup@ava.bcc.orst.edu (Ping Chou) writes:

>        Or the development of genetic algorithms has
>completed?

I doubt anyone would argue this.  For example, genetic
programming just came on the scene within the past
couple of years and it has the potential to churn up
the field significantly.

>        Don't you think you may be able to discover new algorithms from
>studying genetics?

Of course.  But geneticists calling us stupid and
telling us to go back to school doesn't help, does it?
In particular, I happen to be intrigued by the fact
that genes not only produce physical structure and
regulate cellular events, they effectively regulate
their own expression.  This sort of feedback should be
very interesting to investigate!

>        Do you really believe the complete genome of HIV is just a 4-state
>bits encoded string?

Well, in a sense, sure.  Why?  What do you know that we
don't?  How about educate us rather than chastise us!

>        Then please, give youself a chance, take a look at any modern
>genetics text book, and be a cross-discipline expert.

It is pretty arrogant to assume that people who work
with genetic algorithms have no knowledge of genetics!
Furthermore, different people have different interests,
and you can't be sure what each person ought to study.
For example, there is relatively little need for
someone interested in modelling the evolution of
populations to have a thorough understanding of, say,
molecular biology even though it relates to genetics.

>        BTW, I would appreciate any reasonable arguments because I'm trying
>to learn ai-genetic from the genetics side.

Well, I suggest you go back to school and take a course
in each of the following: programming, data structures,
algorithms, parallel algorithms, automata theory, etc.
etc. etc.  It's a joke, get it?

For those non-biologists interested in getting some
background on cell physiology and/or genetics, I highly
recommend "The Living Cell", by Christian de Duve from
the Scientific American library series.  It is getting
a bit "old" (1985?) but I assume the basic top-level
picture it presents is still mostly "correct".  More
importantly it is scientific without being pedantic and
boring and yet it is not too "popular".

And I would have to second Ping's suggestion to study
cross-disciplinarily.  It can be surprisingly useful.


--james, "Don't know much about biology 'cept what I
need to"

-- 
 james kittock :: stanford cs grad student :: duke '92 :: go blue devils!!
 "Adaptation is a recursive process in living systems." -- Alex. M. Andrew

In article <1993Jan21.092927.4669@CSD-NewsHost.Stanford.EDU> jek@Xenon.Stanford.EDU (James E. Kittock) writes:
>In article <1jlmb2INNjp4@gaia.ucs.orst.edu> choup@ava.bcc.orst.edu (Ping Chou) writes:
>
>>        Do you really believe the complete genome of HIV is just a 4-state
>>bits encoded string?
>
>Well, in a sense, sure.  Why?  What do you know that we
>don't?  How about educate us rather than chastise us!

Here's a start: its highly probable that variations in the physical
structure of the DNA are intimately involved in regulating expression,
both in the sense of levels (via histone binding) and process control
(start, stop, splice points). This physical structure is
simultaneously redundant (similar sequences can give rise to the same
physical structure, within the limits of protein binding resolution
anyway) but is also cross-correlated (you need <pattern-1> here, and
<pattern2> there in order to get the effect).

Although these effects are not completely lost by using a 4 state
representation, they are considerably less obvious.

>>        Then please, give youself a chance, take a look at any modern
>>genetics text book, and be a cross-discipline expert.
>
>It is pretty arrogant to assume that people who work
>with genetic algorithms have no knowledge of genetics!
>Furthermore, different people have different interests,
>and you can't be sure what each person ought to study.
>For example, there is relatively little need for
>someone interested in modelling the evolution of
>populations to have a thorough understanding of, say,
>molecular biology even though it relates to genetics.

Perhaps you could explain why you believe this to be so. I can think
of several arguments against this.

>For those non-biologists interested in getting some
>background on cell physiology and/or genetics, I highly
>recommend "The Living Cell", by Christian de Duve from
>the Scientific American library series.  It is getting
>a bit "old" (1985?) but I assume the basic top-level
>picture it presents is still mostly "correct".  More
>importantly it is scientific without being pedantic and
>boring and yet it is not too "popular".

If you can handle Alberts et al. "Molecular Biology of the Cell",
you'll get more up to date info, nice pictures and lots of references.
Also, see Ben Lewin's "Genes" for a mind-boggling view of just how
complex biological genetics really is. You don't need to understand it
all - just get a feel for the actual complexities.

-- paul (ex-theoretical mol.biologist turned operating systems
	 hacker and a-life private explorer)
-- 
hybrid rather than pure; compromising rather than clean;    | Militant Agnostic
distorted rather than straightforward; ambiguous rather than| I Don't Know
articulated; both-and rather than either-or; the difficult  |   and You Don't
unity of inclusion rather than the easy unity of exclusion. |   Know Either

Yes, GAs have learned alot from genetics, but GAs are abstract, and do not
have to follow the things they imitate exactly. Yes, the field of GAs may
still have more to learn from genetics, but taking 7 courses towards
a medical degree hardly seems worthwhile.
For a look at another field, which has been around a bit longer, try
neural networks. Neural nets were meant to imitate nervous systems{ in
animals, but often when neural net technology diverges from actual
neural systems in concet,xxxx concept, they are most successful.

Thus spake choup@ava.bcc.orst.edu (Ping Chou):
>
>        Isn't it true that selection/mating/mutation/chromosome/hybrid/
>genotype/phenotype/gene/... are taken from genetics?

No.  They are *inspired* by the biological processes of natural selection,
mutation, adaptation, speciation, etc.  They are meant to be analogous to
them, not rigidly isomorphic.

>        Don't you think you may be able to discover new algorithms from
>studying genetics?

Perhaps.  Cohoon, for example, has used such ecological notions as allopatric
speciation to motivate some of his work in parallel implementations of GA.
But GA is primarily concerned with solving problems, not mimicking nature.
If mimicking nature works best, so be it.  If it doesn't, none of us are 
going to lose sleep over the fact that our algorithm isn't "realistic".

>        BTW, I would appreciate any reasonable arguments because I'm trying
>to learn ai-genetic from the genetics side.

I'm not sure there *is* a genetics side, beyond the original motivation.
(I'm not sure there's an AI side, either; what's "intelligent" about a GA?)

David Tate

-- 
       David Tate        |"Something there is that doesn't love a wall,
 dtate@unix.cis.pitt.edu | That sends the screaming liner over it 
 Prof. of Story Problems | And spills the bleacher-dwellers from their seats."
 Member ORSA, TIMS, SABR |  	"Fenway Wall", Robert Frost          

In article <1jlmb2INNjp4@gaia.ucs.orst.edu>, choup@ava.bcc.orst.edu (Ping Chou)
writes:
> 
>         Or the development of genetic algorithms has completed?
> 
>         Isn't it true that selection/mating/mutation/chromosome/hybrid/
> genotype/phenotype/gene/... are taken from genetics?

   The words yes, but genetic algorithms go far beyond the biological genetic 
model.  There are a number of papers on Lamarckian genetic algorithms, for
example.  Lamarck is a discarded reject in genetic theory; in genetic algorithms
his ideas are useful.

   I suppose what I'm getting at here is the point Chris Langston makes when he
attempts to difine the field of Artificial Life.  He says Alife is an attempt
to study life as it can be rather than as it is.  The practical code-hacking
implications of this are that while biology has benn and will continue to
be a source of insparation one cannot let it be a strait jacket.

>         Don't you think you may be able to discover new algorithms from
> studying genetics?

   Well, biology in general actually, but yes I'd guesstimate a roughly 100%
chance that there are good ideas for genetic algorithms lurking in biology. 
The paper I mentioned last week (Iterated Prisoner's Dillemma with Choice and
Refusal) studies the effect of rational partner selection on a genetic
algorithm.  Our inspiration for this was mate selection behavior in biology.
The effect was startling - the algorithm converged to places it never went
before.

   The problem is that taking a pile of courses won't help.  I've taken courses
and they consist of irrelevant trivia and foundational material valuable to work
within the discipline.  They seldom give the gestalt one needs to rip off good
ideas.  I maintain reading Science and Science news is a better way to get the
cross specialization you need to be a better GA programmer.
 
>         Do you really believe the complete genome of HIV is just a 4-state
> bits encoded string?

   Since there are at least thousands of HIV pseudospieceis, no.  On the
other hand the hardware we evolve our stings on, like my DEC station 3100,
is considerably less sophistocated than the hardware an HIV virus runs on,
a human cell.  The biology used to "run" a virus is roughly totally unrelated 
to the hardware used to run a GA.
 
>         Then please, give youself a chance, take a look at any modern
> genetics text book, and be a cross-discipline expert.

   You seem confused as to the source of knowledge...   ...the very best thing
you can do is ask an expert a specific question and ask questions while he
answers until you understand.  Reading Science will prevent you from being so
ignorant that said expert will refuse to talk to you.

> --Ping
> 
>         BTW, I would appreciate any reasonable arguments because I'm trying
> to learn ai-genetic from the genetics side.

   Good luck.

Dan
Danwell@IASTATE.EDU

In article <1jlmb2INNjp4@gaia.ucs.orst.edu> choup@ava.bcc.orst.edu (Ping Chou) writes:
>        Don't you think you may be able to discover new algorithms from
>studying genetics?

>        Then please, give youself a chance, take a look at any modern
>genetics text book, and be a cross-discipline expert.
>
>--Ping
>
>        BTW, I would appreciate any reasonable arguments because I'm trying
>to learn ai-genetic from the genetics side.

Well, I'm glad to hear that we have genetics experts reading this
newsgroup. I've read the excellent book "Evolutionary Genetics" by John
Maynard Smith (OUP, 1989), and although I learned a lot about genetics,
its really not the same as looking at things from a GA viewpoint. A
geneticist is more concerned with `how things work in nature', while a
GA person wants to extract the _essential_ principles, and apply them
as directly as possible.

Natural genetic systems include various features which are not relevant
in the GA world. For example, there are many different ways in which
errors can occur in the process of DNA replication, and nature has
evolved many different mechanisms to repair these errors. Does this
mean that in a GA we must slavishly copy this process - ie introduce
lots of mutations, using different mechanisms, then repair most of
them?  No - what we do is extract the _essential_ principle that, after
replication has been completed, there will be a small chance that a
number of mutations remain unrepaired.

There may be yet other features of natural genetic systems which,
although essential in a biological context, in fact have nothing to do
with the _evolutionary_ potential of the system. Furthermore, there may
be features which, like the appendix, once performed a function, but
now do nothing.

Of course it can be very difficult to tell what category any particular
natural genetic feature falls into. I would particularly like to ask
the genticists out there for their opinions on the following two
topics:


Inversion. 

We know this takes place (occasionally), but to what extent is it
responsible for evolution? Holland, and other early researchers,
included inversion in their GAs, but more recently it has been notable
by its absence. Is this because nobody has been able to quantify its
advantages? Obviously it has some role to play in the evolution of the
karyotype (chromosome structure), but maybe this type of evolution is
occurring at rates which are orders of magnitude slower than evolution
of the genotype -- in which case it is probably irrelevant for present
day GAs.

Introns

These are redundant sections within genes. Present-day natural genes do
not work properly if introns are artificially removed. This shows that
chromosomes have evolved so that introns are essential _now_, but this
does not prove that it _had_ to happen this way. Were they essential in
the past? Do they add evolutionary potential, perhaps? They can alter
the crossover probability with respect to the operational part of the
gene (see Levenick, James, "Inserting introns improves genetic
algorithm success rate: taking a cue from biology", ICGA-91) - but a
similar effect might be achieved with mating tags. Is there something
special about introns as such which means that they ought to be
included in GA representations?


No doubt some of my reasoning is wrong here. But as an engineer
with no qualifications in biology, I would be grateful for some learned
discussion on these points.
--

David Beasley                          (David.Beasley@cm.cf.ac.uk)    
Department of Computing Mathematics 
University of Wales College of Cardiff                          __o
PO Box 916                                                      \<,   
CARDIFF    CF2 4YN                         ___________________()/ ()___  

In article <1993Jan22.170726.20115@cm.cf.ac.uk> David.Beasley@cm.cf.ac.uk (David Beasley) writes:
[ "an engineer with no qualifications in biology ]

As a person with insufficient education in both areas, despite time
working in both:

>Natural genetic systems include various features which are not relevant
>in the GA world. For example, there are many different ways in which
>errors can occur in the process of DNA replication, and nature has
>evolved many different mechanisms to repair these errors. Does this
>mean that in a GA we must slavishly copy this process - ie introduce
>lots of mutations, using different mechanisms, then repair most of
>them?  No - what we do is extract the _essential_ principle that, after
>replication has been completed, there will be a small chance that a
>number of mutations remain unrepaired.

The problem with this approach, IMHO, is that we don't know what the
_essential_ principles are. Specifically, given your example, it may
in fact be the case that error and error repair mechanisms are
fundamental to the evolutionary potential of biological systems.

One really interesting feature that I have observed from my own work
with a tierra-like system is the effect of a reproductive burden on
the speed of evolution. Traditional GA's (say, as "traditional" as
Koza's) do not make reproduction the responsibility of the evolving
algorithm. A system like Tierra does, and in the process, forces the
evolutions of all kinds of reproductive oddities like viruses and
parasites. 

The problem with forcing the "algorithm" to reproduce is that you slow
things down: any mutations or changes to its reproductive capability
can potentially reduce its overall fitness (when seen in terms of its
ranking in the population), even if its computational fitness is high.
This is bad, from a GA point of view, because you are effectively
selecting for a feature you don't care about: how well a system can
reproduce. So, in normal GA-land, you simply use the "hand of god"
approach: you reach in, and *you* do the reproduction, eliminating any
selection pressure on this feature.

But wait ! Perhaps, just perhaps, this reproductive feature is just
what you want. Its not very difficult to make a tierra-like system
evolve its own form of crossover. All kinds of other wierd and
wonderful reproductive mechanisms evolve too. It seems possible to me
that when evolution is viewed as explorations of a vast state space,
particular reproductive methods might be incapable of ever searching
some particular areas of that space. Leaving the system free to devise
its own reproductive strategies opens up the possibility of exploring
areas of the state space that "programmer/user-selected" methods might
not. 

What is very interesting to me about biological genetic systems is
that they have evolved systems with very high reproductive fitness and
very low computational fitness (bacteria, for instance, which
reproduce in seconds but don't do much other than reproduce in terms
of external effects on the world), as well as systems with very low
reproductive fitness and very high computational fitness (such as
mammals, which take years to reproduce, but carry out all kinds of
complex operations).

 [ Finding a way to tune my tierra-like system so that it can generate
   such diversity is a current goal of mine. ]

>Introns
>
>These are redundant sections within genes. Present-day natural genes do
>not work properly if introns are artificially removed. This shows that
>chromosomes have evolved so that introns are essential _now_, but this
>does not prove that it _had_ to happen this way. Were they essential in
>the past? Do they add evolutionary potential, perhaps? They can alter
>the crossover probability with respect to the operational part of the
>gene (see Levenick, James, "Inserting introns improves genetic
>algorithm success rate: taking a cue from biology", ICGA-91) - but a
>similar effect might be achieved with mating tags. Is there something
>special about introns as such which means that they ought to be
>included in GA representations?

My reading of introns, back from my days as a grad student studying
the relationship between DNA sequence and structure, is that they
serve at least two roles. One is alluded to by Levenick's paper, the
other is expression related. Introns are actually a lot less random
than coding sequences (measured, for instance, by entropy
calculations). They have many more "features" than coding sequences,
are the only regions containing the currently known control sequences
relating to transcription (unless you consider such sequences to make
the term "intron" inapplicable).

So, in a GA-like system, introns can only serve the sort of role that
Levenick describes. In a tierra-like system that contained programs
capable of using them for reproduction, they can be the basis of much
more sophisticated operations. 

In summary, I don't think we really know what the essential
characteristics of biological genetics are. We can either try to
invent our own, to use or subset of biological ones, or try to mimic
biology exactly, or some combination of all of these. There is no a
priori reason for using any particular combination, IMHO.

-- paul
-- 
hybrid rather than pure; compromising rather than clean;    | Militant Agnostic
distorted rather than straightforward; ambiguous rather than| I Don't Know
articulated; both-and rather than either-or; the difficult  |   and You Don't
unity of inclusion rather than the easy unity of exclusion. |   Know Either

I've worked both sides of this furrow (both genetics and GA) and I've
learned that GAs are related to genetics about the same way BP is related
to wet networks. In both cases, the AI community has created a simplified
and sometimes wierd analog to a naturally occurring phenomenum. JMS is
probably the right place to start, because the baroque complexity of
nature is likely to provide alternative ways of doing GAs that your
ordinary computer scientist is likely to have no clue about.

Cheers,
-- 
Harry Erwin
Internet: erwin@trwacs.fp.trw.com