Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

genetic programming v genetic algorithms

10 views
Skip to first unread message

MH4301

unread,
Sep 15, 1999, 3:00:00 AM9/15/99
to
Can someone tell me the differance between genetic programming and genetic
algorithms? Thanks,
Mike

A.Nonyme

unread,
Sep 15, 1999, 3:00:00 AM9/15/99
to
dialectics.

When you start playing around with G.A.s, you're doing G.P.


bv


MH4301 <mh4...@aol.com> wrote in message
news:19990914215853...@ng-cg1.aol.com...

Chase Saunders

unread,
Sep 15, 1999, 3:00:00 AM9/15/99
to
I disagree with the above answer...

Genetic Algorithms is the simulated evolution of potential solutions to
problems as data structures of various kinds. Genetic Programming, a kind
of GA, is the evolution of computer programs.

Chase


Eva Brucherseifer

unread,
Sep 15, 1999, 3:00:00 AM9/15/99
to MH4301
MH4301 wrote:
>
> Can someone tell me the differance between genetic programming and genetic
> algorithms? Thanks,
> Mike


in GP the an individial is represented as a tree,
in GA you work mostly on strings or numbers.

i.e. we work on the modelling of biotechnology processes
(we search for mathematical structures) and we use trees as
the representation form and so I am working in GP.

gruesse,
eva

Tim Tyler

unread,
Sep 15, 1999, 3:00:00 AM9/15/99
to
Eva Brucherseifer <e...@rt.e-technik.tu-darmstadt.de> wrote:
: MH4301 wrote:

:> Can someone tell me the differance between genetic programming and genetic
:> algorithms? Thanks,

: in GP the an individial is represented as a tree,


: in GA you work mostly on strings or numbers.

: i.e. we work on the modelling of biotechnology processes
: (we search for mathematical structures) and we use trees as
: the representation form and so I am working in GP.

This is a description of what I call "Koza-style" GP.

I see no reason why evolving computer programs should confine itself to
tree-shaped chromosomes - and indeed systems like Avida and Tierra seem
to evolve machine-code like systems using linear chromosomes quite
happily.

Similarly programs which evolve tree-shaped chromosomes need bear no
special resembalances to parse trees, or any other programming structure.

Using tree-shaped chromosomes appear to have disadvantages as well as
advantages - in particular one one has found a "sex" operator that behaves
remotely like the ones found by natural selection, and there's no clear
notion of what constitutes "alleles" within such models.

I'd like to consider chromosome shape, and the GA/GP spectrum to be
orthogonal to one another.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ t...@cryogen.com

Faster than a speeding ticket.

alain proux

unread,
Sep 15, 1999, 3:00:00 AM9/15/99
to
Genetic algorithms handle strings, with fixed lenght most of the time.
Genetic Programming handle trees, programs.
apx.

A.Nonyme a écrit:

> dialectics.
>
> When you start playing around with G.A.s, you're doing G.P.
>
> bv
>
> MH4301 <mh4...@aol.com> wrote in message
> news:19990914215853...@ng-cg1.aol.com...

> > Can someone tell me the differance between genetic programming and genetic
> > algorithms? Thanks,

> > Mike


DBFogel

unread,
Sep 16, 1999, 3:00:00 AM9/16/99
to

Dear Colleagues:

>Subject: Re: genetic programming v genetic algorithms
>From: Tim Tyler t...@cryogen.com
>Date: Wed, 15 September 1999 07:04 PM EDT
>Message-id: <FI4Iq...@bath.ac.uk>


>
>Eva Brucherseifer <e...@rt.e-technik.tu-darmstadt.de> wrote:
>: MH4301 wrote:
>

>:> Can someone tell me the differance between genetic programming and genetic
>:> algorithms? Thanks,
>


>: in GP the an individial is represented as a tree,
>: in GA you work mostly on strings or numbers.
>
>: i.e. we work on the modelling of biotechnology processes
>: (we search for mathematical structures) and we use trees as
>: the representation form and so I am working in GP.
>
>This is a description of what I call "Koza-style" GP.
>
>I see no reason why evolving computer programs should confine itself to
>tree-shaped chromosomes - and indeed systems like Avida and Tierra seem
>to evolve machine-code like systems using linear chromosomes quite
>happily.


And there is no reason why evolving computer programs should be confined
to the term "genetic programming."

No doubt common usage is exactly as John Koza has offered it, a special
case of genetic algorithms applied to tree structures interpreted as
programs. Of course, they could be interpreted in other ways and then
it wouldn't be "genetic programming." And there is no reason that evolving
programs should be constrained to trees -- witness several recent efforts
at "linear" program codes and even the earliest efforts in evolutionary
computation by Friedberg in 1958 to evolve machine language.


>
>Similarly programs which evolve tree-shaped chromosomes need bear no
>special resembalances to parse trees, or any other programming structure.
>
>Using tree-shaped chromosomes appear to have disadvantages as well as
>advantages - in particular one one has found a "sex" operator that behaves
>remotely like the ones found by natural selection, and there's no clear
>notion of what constitutes "alleles" within such models.

Nor is there any reason to believe that a recombination operator should be
of general use for a tree structure any more than for any other structure.
There are several experiments in the literature where the absence of
such recombination performs as well or better than relying on it heavily,
(see papers by Chellapilla or Angeline or Luke & Specter or Fuchs from
GP98) and cases where crossing over with random solutions performs better as
well. A good example comes in the paper in Nordin and Banzhaf (1995,
ICGA) which I cite in the 2nd edition of my book (Fogel, 2000).

>
>I'd like to consider chromosome shape, and the GA/GP spectrum to be
>orthogonal to one another.
>--
>

It might be more helpful to take a broader view and think about evolution
in more general terms than relying too strongly on trying emulate or
"borrow" genetics from a system that was evolved in an entirely different
context to anything that we have yet to construct on a computer.

__________
> |im |yler The Mandala Centre http://www.mandala.co.uk/ t...@cryogen.com
>
>Faster than a speeding ticket.
>
>
>
>
>
>

Regards,

David Fogel
www.natural-selection.com

References

Nordin and Banzhaf (1995) Int. Conf. on Genetic Algorithms
Fogel (2000) Evolutionary Computation, 2nd ed., IEEE Press.

Stephane Vermette

unread,
Sep 16, 1999, 3:00:00 AM9/16/99
to
Unless you already have, I suggest you give a look at:

"The Hitch-Hiker's Guide to Evolutionary Computation". This document is a
FAQ for comp.ai.genetic, let me quote the cover page:

PLEASE:
Search this document first if you have a question
and
If someone posts a question to the newsgroup which is answered in here
DON'T POST THE ANSWER TO THE NEWSGROUP:
POINT THE ASKER TO THIS FAQ
and finally
DON'T PANIC!


Enjoy!

MH4301 wrote in message <19990914215853...@ng-cg1.aol.com>...


>Can someone tell me the differance between genetic programming and genetic
>algorithms? Thanks,

>Mike

Tim Tyler

unread,
Sep 16, 1999, 3:00:00 AM9/16/99
to
DBFogel <dbf...@aol.com> wrote:
:>From: Tim Tyler t...@cryogen.com
:>Eva Brucherseifer <e...@rt.e-technik.tu-darmstadt.de> wrote:

:>: in GP the an individial is represented as a tree,


:>: in GA you work mostly on strings or numbers.
:>
:>: i.e. we work on the modelling of biotechnology processes
:>: (we search for mathematical structures) and we use trees as
:>: the representation form and so I am working in GP.
:>
:>This is a description of what I call "Koza-style" GP.
:>
:>I see no reason why evolving computer programs should confine itself to
:>tree-shaped chromosomes - and indeed systems like Avida and Tierra seem
:>to evolve machine-code like systems using linear chromosomes quite
:>happily.

: And there is no reason why evolving computer programs should be confined
: to the term "genetic programming."

It seems like the obvious term to use as a blanket term for evolving
computer programs.

Historical usage which explicitly confines the term to evolving
non-turing complete parse trees seems bizarre, given the meanings of the
words "genetic" and "programming".

: No doubt common usage is exactly as John Koza has offered it, a special


: case of genetic algorithms applied to tree structures interpreted as
: programs.

This could have something to do with Koza's involvement in founding the
field. In "Genetic Programming" he uses the term as though it applied
/exclusively/ to his own particular method of parsing structures related
to LISP S-expressions. This has caused other researches in the field to
abandon using the term in order to avoid having it confused with Kosa's
own curious usage.

Essentially I view this usage as an attempt to monopolise the (attractive)
terminology. Given the number of people who associate "Genetic
Programming" with tree-shaped decision diagrams *only*, the ploy
appears to have been largely successful.

: Of course, they could be interpreted in other ways and then


: it wouldn't be "genetic programming."

Or rather, it wouldn't be what de Garis, and I refer to as "Kosa-style
genetic programming".

: And there is no reason that evolving programs should be constrained to
: trees [...]

Indeed not.

:>Similarly programs which evolve tree-shaped chromosomes need bear no


:>special resembalances to parse trees, or any other programming structure.
:>
:>Using tree-shaped chromosomes appear to have disadvantages as well as
:>advantages - in particular one one has found a "sex" operator that behaves
:>remotely like the ones found by natural selection, and there's no clear
:>notion of what constitutes "alleles" within such models.

: Nor is there any reason to believe that a recombination operator should be
: of general use for a tree structure any more than for any other structure.

Though there /do/ appear to be good reasons for believing that a
recombination operator will frequently help in general.

: There are several experiments in the literature where the absence of


: such recombination performs as well or better than relying on it heavily,

Similarly, in nature, there are many asexual organisms, who reproduce
without any apparent need of recombination. However if you look at
complex organisms - or those that are seen as being highly evolved -
the occurrence of sex is /extremely/ frequent.

While not everyone in the biological community agrees, it seems fairly
clear that sex serves a purpose in these organisms - and there are no
shortage of theoretical ideas about what this purpose might be.

I think sex fulfills a very similar function in genetic algorithms.

In John H. Holland's 1975 book, Adaptation in Natural and Artificial
Systems, recombination operators were analysed - and showed to yield a
more effective search of the space under some circumstances.

: (see papers by Chellapilla or Angeline or Luke & Specter or Fuchs from


: GP98) and cases where crossing over with random solutions performs better
: as well.

IIRC, these results relate to "sex" among tree-shaped structures.

Here, "crossing over" refers to pruning and splicing different branches
between trees at random. This is a /very/ different operation to
replacing a section of a linear chromosome with another *corresponding*
section from another organism - and there appears to be no a-priori reason
to believe the operations would have very similar effects. Consequently
it is less-than-suprising that the operator fails to demostrate one of
the main functions of sexual recombination.

Now, I don't doubt there are many cases where recombination fails to have
advantages when using linear chromosomes. However, I see these cases as
being analogous to greenfly, dandelions, and some bacteria - asexual
organisms whose existence in no way affects the ubiquity or advantages
of sexual reproduction.

Asexual lineages are generally rare and shortlived - and with good reason:
asexuality is frequently bad, unhealthy; it prevents a good number of
important evolutionary mechanisms from operating.

:>I'd like to consider chromosome shape, and the GA/GP spectrum to be
:>orthogonal to one another.

: It might be more helpful to take a broader view and think about evolution


: in more general terms than relying too strongly on trying emulate or
: "borrow" genetics from a system that was evolved in an entirely different
: context to anything that we have yet to construct on a computer.

I still want to consider chromosome shape, and the GA/GP spectrum to be
orthogonal to one another. Basically AFAICS, they *are* independant
variables ;-) Terminology which confuses this issue muddies the water.

You seem to imply I am failing to take a broad view. Needless to say, I
don't see it like that.

I see sex as equally fundamental in genetic algorithms and in nature.

While I am not wedded to the idea that genetic algorithms should emulate
the mechanisms of nature, I /do/ think that nature has a great deal to
teach GA researchers.

In particular, I view sex as one of nature's main masterpieces.

Any notion that genetic algorithms can be broadly successful /without/
involving sex would appear to me to be very strange - and very wrong.
--

__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ t...@cryogen.com

Years of development: we finally got one to work.

DBFogel

unread,
Sep 16, 1999, 3:00:00 AM9/16/99
to
Dear Tim:

Apologies for the long posting here but there was much that I thought
I might clarify.

[..]


>
>: And there is no reason why evolving computer programs should be confined
>: to the term "genetic programming."
>
>It seems like the obvious term to use as a blanket term for evolving
>computer programs.

The "obvious" term is "evolutionary programming," but is also taken.
>
[..]

>This could have something to do with Koza's involvement in founding the
>field. In "Genetic Programming" he uses the term as though it applied
>/exclusively/ to his own particular method of parsing structures related
>to LISP S-expressions. This has caused other researches in the field to
>abandon using the term in order to avoid having it confused with Kosa's
>own curious usage.
>
>Essentially I view this usage as an attempt to monopolise the (attractive)
>terminology. Given the number of people who associate "Genetic
>Programming" with tree-shaped decision diagrams *only*, the ploy
>appears to have been largely successful.
>
>: Of course, they could be interpreted in other ways and then
>: it wouldn't be "genetic programming."
>
>Or rather, it wouldn't be what de Garis, and I refer to as "Kosa-style
>genetic programming".
>
>: And there is no reason that evolving programs should be constrained to
>: trees [...]
>
>Indeed not.

[..]

>
>: Nor is there any reason to believe that a recombination operator should be
>: of general use for a tree structure any more than for any other structure.
>
>Though there /do/ appear to be good reasons for believing that a
>recombination operator will frequently help in general.

I'm sorry but this is not correct. Any statement about a variation operator
of any type "helping in general" is not correct by way of no free lunch
arguments (Wolpert and Macready, 1997).

Without specifying more clearly the domain of application
and the match of the variation operator to that domain in light of the
representation, there is no amount of what amounts to hand waving that
will offer justification for using any particular operator.

>
>: There are several experiments in the literature where the absence of
>: such recombination performs as well or better than relying on it heavily,
>
>Similarly, in nature, there are many asexual organisms, who reproduce
>without any apparent need of recombination. However if you look at
>complex organisms - or those that are seen as being highly evolved -
>the occurrence of sex is /extremely/ frequent.

The problem comes in making any sort of useful analogy between
what goes on in nature and what goes on in a simple simulation
of an evolutionary process on a computer.

>
>While not everyone in the biological community agrees, it seems fairly
>clear that sex serves a purpose in these organisms - and there are no
>shortage of theoretical ideas about what this purpose might be.

see above.

>
>I think sex fulfills a very similar function in genetic algorithms.

You didn't remark on what, exactly, this function is.

>
>In John H. Holland's 1975 book, Adaptation in Natural and Artificial
>Systems, recombination operators were analysed - and showed to yield a
>more effective search of the space under some circumstances.
>

Let's be more clear here. Holland's book proposed one recombination
operator, the one-point crossover operator (a special case of the
recombination operators offered earlier by Fraser (1957)
and Bremermann (1962) and others).

Holland showed was that this operator would not disrupt short defining
length schemata. There is nothing in Holland's treatment that shows that
this property leads to a more effective search (see Vose, 1999; Altenberg,
1995, and many others).

No doubt, it will lead to more effective search in some cases (i.e., those
cases where it is advantageous not to disrupt short defining length
schemata). Unfortunately, there is no theory as to when those cases
can be identified a priori, except for the trivial case of completely linearly
separable problems. For those problems, there are much better
algorithms than evolutionary algorithms.

>: (see papers by Chellapilla or Angeline or Luke & Specter or Fuchs from
>: GP98) and cases where crossing over with random solutions performs better
>: as well.
>

[..]

>
>Now, I don't doubt there are many cases where recombination fails to have
>advantages when using linear chromosomes. However, I see these cases as
>being analogous to greenfly, dandelions, and some bacteria - asexual
>organisms whose existence in no way affects the ubiquity or advantages
>of sexual reproduction.

There is evidence against this. If you look to De Jong et al. (1995)
from FOGA95, the analysis there shows quite clearly how the effectiveness
of recombination on a linear chromosome is directly related to the
representation of data within that chromosome and the match to the
fitness function. The same data, when rearranged, can lead to increased
rates of convergence under crossover, or decreased rates (even worse
than random search for a number of generations).

>
>Asexual lineages are generally rare and shortlived - and with good reason:
>asexuality is frequently bad, unhealthy; it prevents a good number of
>important evolutionary mechanisms from operating.

You haven't specified what these might be.
On the other hand, it presumes a connection
between nature and simulation that is not clear.

>
[..]

>I see sex as equally fundamental in genetic algorithms and in nature.
>
>While I am not wedded to the idea that genetic algorithms should emulate
>the mechanisms of nature, I /do/ think that nature has a great deal to
>teach GA researchers.
>
>In particular, I view sex as one of nature's main masterpieces.

No doubt this is true for nature. When searching for the solution to
some optimization problem, however, this is a different set of environmental
conditions.

>
>Any notion that genetic algorithms can be broadly successful /without/
>involving sex would appear to me to be very strange - and very wrong.

There is a very long list of stochastic search algorithms that do not use
recombination that have been applied to a very wide range of problems
with success. Stochastic search is of the form:

x[t + 1] = s(v(x[t])), where x[t] is the current population at time t under
representation x, v is the variation operator(s), and s is the selection
operator. We can plug in proportional selection, one-point crossover, and
binary encodings, or we can plug in tournament selection, Gaussian
variation, and floating-point encodings, or some other choices. In the
end, all that matter is the probability mass function over the search space
at x[t + 1]. Analysis can shown when crossover can be usefully applied in
this way and when it is detrimental -- for example, there has been analysis
on "fitness distributions" of operators (see Nordin and Banzhaf, 1995;
Chellapilla et al. at CEC1999).

>--
>__________
> |im |yler The Mandala Centre http://www.mandala.co.uk/ t...@cryogen.com
>
>Years of development: we finally got one to work.
>

Regards,

David
www.natural-selection.com

Refs:

Wolpert and Macready (1997) "No free lunch theorems for optimization,"
IEEE Trans. Evol. Comp., vol. 1:1.

A.S. Fraser (1957) Austral. J. Biol. Sciences

H.J. Bremermann (1962) In Self-Organizing Systems, Spartan Books

Vose (1999) The Simple Genetic Algorithm, MIT Press.

Altenberg (1995) FOGA95

De Jong et al. (1995) FOGA95

Nordin and Banzhaf (1995) ICGA95

Chellapilla at CEC1999 (multiple refs)


Tim Tyler

unread,
Sep 18, 1999, 3:00:00 AM9/18/99
to
DBFogel <dbf...@aol.com> wrote:

:>: And there is no reason why evolving computer programs should be confined


:>: to the term "genetic programming."
:>
:>It seems like the obvious term to use as a blanket term for evolving
:>computer programs.

: The "obvious" term is "evolutionary programming," but is also taken.

I find "evolutionary" to be too much of a mouthful.

Since I subscribe to G. C. Williams' 1966 definitions of what "genetic"
means, these terms are effectively synonymous to me anyway.

:>: Nor is there any reason to believe that a recombination operator should be


:>: of general use for a tree structure any more than for any other structure.
:>
:>Though there /do/ appear to be good reasons for believing that a
:>recombination operator will frequently help in general.

: I'm sorry but this is not correct. Any statement about a variation operator
: of any type "helping in general" is not correct by way of no free lunch
: arguments (Wolpert and Macready, 1997).

I believe we've discussed our different perspectives on this matter in the
past here. NFL theorems apply to systems where there is no knowledge
about the problem domain *at all* (excepting, perhaps the maximum length
of the target solution).

I believe there are good reasons why the problems typically faced by
organisms are a very biased subset of the problem space Woplert and
Macready consider. This is (partly) because natural survival problems
typically decompose themselves into modular sections with less
interdependence between the parts than exists within them.

In terms of organism design, creatures frequently need to eat, move,
excrete, reproduce. These are largely independent operations, and - to a
certain extent - may be treated as independent problems.

Similar decomposition is true of problems commonly faced by organisms.
Eating food is broken down into largely independent sub-problems - for
example: finding food, killing food, cooking food, and eating food.

I don't think there is any justification for considering problems
organisms face to be "taken at random from the space of all possible
problems". On the rare occasions when organisms do find themselves
confronting such problems - i.e. problems where the best approach is
effectively trying solutions at random works as well as trying to apply
any of the search methods they are familair with - they are likely to give
up, and try to achieve their ends by finding an easier
route.

If organisms /were/ frequently presented with such problems, then we would
not find genetic algorithms to be broadly applicable to our problems, nor
would hill-climbing techniques, or simulated annealing work very
frequently.

That such techniques are even mentioned in textbooks is a sign that
organisms simply *don't* face problems with the distribution required
before NFL theorems can be invoked.

: Without specifying more clearly the domain of application


: and the match of the variation operator to that domain in light of the
: representation, there is no amount of what amounts to hand waving that
: will offer justification for using any particular operator.

The domain of application I consider to be "problems oganisms are
typically likely to face" - which is to my mind clearly a biased subset
of "all possible problems".

I don't feel the need to specify the match between my preferred variation
operator and the representation chosen, because - both in nature and in
genetic computation, organisms are at liberty to choose their own
representations of problems to a large extent.

:>: There are several experiments in the literature where the absence of


:>: such recombination performs as well or better than relying on it heavily,
:>
:>Similarly, in nature, there are many asexual organisms, who reproduce
:>without any apparent need of recombination. However if you look at
:>complex organisms - or those that are seen as being highly evolved -
:>the occurrence of sex is /extremely/ frequent.

: The problem comes in making any sort of useful analogy between
: what goes on in nature and what goes on in a simple simulation
: of an evolutionary process on a computer.

Both are instances of "evolution" 'attempting' to solve problems
faced by species. In the future, I believe these two processes
will effectively fuse together, rendering any distinction between
them rather meaningless ;-)

:>I think sex fulfills a very similar function in genetic algorithms.

: You didn't remark on what, exactly, this function is.

For one thing, sex speeds up evolution. In every textbook on evolution
I've seen there's a daigram (which I /think/ originated in G. C. Williams'
1975 book, "Sex and Evolution") indicating the conditions under which
sex may be expected to speed up evolution. This consists of four
diagrams illustrating all the combinations of sexual/asexual groups
and populations with a high frequency of advantageous mutations and
populations with a low frequency of advantageous mutations.

The "conclusion" of the diagram is that - in a stirred population with
more than a critical number of advantagous mutations per generation, sex
will act to combine these into a single individual and speed up evolution.

:>In John H. Holland's 1975 book, Adaptation in Natural and Artificial


:>Systems, recombination operators were analysed - and showed to yield a
:>more effective search of the space under some circumstances.

: Let's be more clear here. Holland's book proposed one recombination
: operator, the one-point crossover operator (a special case of the
: recombination operators offered earlier by Fraser (1957)
: and Bremermann (1962) and others).

: Holland showed was that this operator would not disrupt short defining
: length schemata. There is nothing in Holland's treatment that shows that
: this property leads to a more effective search (see Vose, 1999; Altenberg,
: 1995, and many others).

: No doubt, it will lead to more effective search in some cases (i.e., those
: cases where it is advantageous not to disrupt short defining length
: schemata). Unfortunately, there is no theory as to when those cases
: can be identified a priori, except for the trivial case of completely

: linearly separable problems. [...]

I believe you are overstating your case here. One condition that needs
to be met for sex to speed up evolution is for the solution to be made
up of "partly" linearly separable problems. *Complete* linear
separability is *not* needed.

Consider: "running fast" is often good... and "seeing well" is often good.

"Running fast" and "seeing well" are *not* completely independant problems
for an organism - both consume nutrients to build them and incur metabolic
costs to maintain them. However sex will still frequently offer
advantages to organisms by combining the relevant genes from an individual
with good vision and those from an individual with strong legs into a
single organism.

As for there being no theory as to when those cases can be identified
on a priori grounds - personally I find it relatively simple to look at
a system and evaluate to what extent it may be broken down into largely
independant sub-problems.

Indeed often, when this can *not* be done, there's often no good
reason to believe that direction of improvement is any guide to location
of the desired solution - and thus no clear reason to employ a genetic
search in the first place. Partial linear separability seems to me to
be a common reason for believing that genetic techniques will work at
all.

:>Now, I don't doubt there are many cases where recombination fails to have


:>advantages when using linear chromosomes. However, I see these cases as
:>being analogous to greenfly, dandelions, and some bacteria - asexual
:>organisms whose existence in no way affects the ubiquity or advantages
:>of sexual reproduction.

: There is evidence against this. If you look to De Jong et al. (1995)
: from FOGA95, the analysis there shows quite clearly how the effectiveness
: of recombination on a linear chromosome is directly related to the
: representation of data within that chromosome and the match to the
: fitness function. The same data, when rearranged, can lead to increased
: rates of convergence under crossover, or decreased rates (even worse
: than random search for a number of generations).

It is a good job that - in nature - evolution can rearrange the order of
genes on chromosomes in order to create linkage between the genetic
elements most closely related to interdependent phenotypic
functions, then.

I don't doubt if you force your own representation directly onto your
genome - without allowing the possibility of any developmental processes -
you can artificially create situations where recombination becomes
effectively useless.

However, I'm sure if you tie even more hands behind your back you can
self-impose even more constraints - and produce a representation where
even the mutation operator is next-to useless.

This doesn't happen in nature; and I can think of no good reason why
we should want to restrict our search techniques in this way.

:>Asexual lineages are generally rare and shortlived - and with good reason:


:>asexuality is frequently bad, unhealthy; it prevents a good number of
:>important evolutionary mechanisms from operating.

: You haven't specified what these might be.

For example, sexual selection, and cryptographic arms races with sexual
parasites. The latter remain possible in the absence of sex, but
generates selection pressures favouring the evolution of sex.

There are other mechanisms - see, for example
http://aics-research.com/research/males1.html for one take on the
evolutionary significance of sexual dimorphism.

: On the other hand, it presumes a connection


: between nature and simulation that is not clear.

Nature seems to me to have demonstrated a remarkable ability to solve
certain types of problem which - as yet - we can only observe enviously.

:>I see sex as equally fundamental in genetic algorithms and in nature.


:>
:>While I am not wedded to the idea that genetic algorithms should emulate
:>the mechanisms of nature, I /do/ think that nature has a great deal to
:>teach GA researchers.
:>
:>In particular, I view sex as one of nature's main masterpieces.

: No doubt this is true for nature. When searching for the solution to
: some optimization problem, however, this is a different set of environmental
: conditions.

It appears to me that the problems organisms will want to overcome
by using GAs will be essentially the same type of problem that they
have faced historically. The are the problems that evolution itself
has dealt with, and many of these problems clearly fulfill
the condition of partial linear separability, and are thus
likely to be suitable candidates for crossover operators.

FWIW, I view it as /possible/ that the role of sex will be somewhat
modified in the future as genetic engineering and intelligent design
become more widespread phenomena. However, intelligent design
only barely qualifies as an automataed search technique. I suspect
recombination will remain in use indefinitely.

:>Any notion that genetic algorithms can be broadly successful /without/


:>involving sex would appear to me to be very strange - and very wrong.

: There is a very long list of stochastic search algorithms that do not use
: recombination that have been applied to a very wide range of problems
: with success.

I'm aware of this. AFAIK, none of these offer the same sort of potential
for producing complex adaptive systems in the way that genetic techniques
do.

One reason why sex does not currently appear to offer many advantages,
is because sex requires large population sizes to be effective.
If you measure the effectiveness of an algorithm by haw many fitness
evaluations it requires, large populations will bump this figure up
significantly.

Such a metric is only appropriate when considering serial hardware.
If parallel hardware is available, multiple fitness evaluations may occur
simultaneously - and total number of evaluations becomes an irrelevant
statistic. When parallel hardware is more widely available, perhaps sex
will be better appreciated.

Another reason why sex does not appear to have the universal, broad
application it finds in nature is because the poor speed of most
affordable modern computers is dreadful, and completely inappropriate
for attacking most moderate-sized problems with evolutionary techniques.

Many small microorganisms don't bother much with sex; their complexity
does not warrant expenditure on it. Similarly most simple optimisation
problems have no major need for sex - they can be attacked without
bothering with it. It is only when larger problems become tractable
that the advantages of employing recombination will be more widely
recognised.

It appears to me that - in nature - sex was a necessary pre-requisite for
a high-degree of adapted complexity. Without sex, the length of
functional genomes organisms could maintain in the face of Muller's
ratchet was limted. Perhaps, without sex; there would have been
no "Cambrian explosion".


--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ t...@cryogen.com

Expert: one who avoids minor mistakes as he sweeps on to the grand fallacy.

Steve McGrew

unread,
Sep 18, 1999, 3:00:00 AM9/18/99
to
On Sat, 18 Sep 1999 13:38:15 GMT, Tim Tyler <t...@cryogen.com> wrote:
>[snip]

>One reason why sex does not currently appear to offer many advantages,
>is because sex requires large population sizes to be effective.
>If you measure the effectiveness of an algorithm by haw many fitness
>evaluations it requires, large populations will bump this figure up
>significantly.

I'm surprised to see you make this statement. I came into
this thread late, and I assume that when you say "sex" the term
includes "crossover". We find crossover to be very useful in many
problems, using populations in the range of 10 to 100-- which I would
consider to be small populations.

Steve

DBFogel

unread,
Sep 18, 1999, 3:00:00 AM9/18/99
to
Dear Tim,

For nettiquette, I'll need to start over here and just make a few observations
based on your last posting.

No doubt the difference in interpretations and positions between Williams
and Mayr underscores differences we have in interpreting facets of
evolutionary algorithms.

I'll offer a few short points here and then you have the last word if you
like:

1) The NFL theorems do not require a uniform distribution across all
problems (functions) (as proved by English 1996, and later by
Culberson). There are subsets of all problems where NFL also applies.
Since this is true, merely asserting that there is interest in some subset
(e.g., "real-world" problems, whatever those may be) is insufficient.
You may offer that you don't particularly care about the match between
the problem and the operator, but your algorithm does.

2) You may offer that you can make up for the difference in match between
operator and function by rearranging the representation. True, at least to
the extent that the rearrangement can offer phenotypic diversity. However,
this converts one search problem for another: search for the appropriate
variation operator for searching for the appropriate representation. Fogel
and Ghozeil 1997 offered some relevant work here that there are intrinsic
tradeoffs between representation and variation operators such that what you
change
in representation you can make up for in operators. Shifting to "making
it up" in the representation is something like looking at the same problem
in a mirror.

3) Sex is sex. One-point crossover is one-point crossover. Chromosomes
in nature are one thing. A binary (or whatever cardinality) vector is another.
That
sexual recombination may have some advantages in nature is not debated.
What those advantages are is debated. Since that debate belongs in
sci.bio.evolution the question here is of what relevance is a mechanism that
was evolved in a particular context in nature going to have when abstracted
somehow (sex = one-piont crossover??) and placed in a system that, say,
searches for weights of a neural network to classify data taken from
breast cancer patients? The phenotypic (behavioral) effect of an operator
depends entirely on the context in which it operates. Flapping wings is a
"master invention" of evolution, feathers provide ability for fine-tuned
control.
Yet we can glue all the feathers we want on a 747 to increase biological
fidelity but all we will do is increase drag. The last airplane I flew didn't
flap its wings. Function doesn't follow form.

4) I appreciate you citing Wirt Atmar's work
(aics-research.com/research/males1.html).
I encourage anyone who is interested to follow up on the issues that are
offered in this thread by looking to his paper in IEEE Trans. Neural Networks,
Vol. 5:1, 1994 (Notes on simulated evolution) as it addresses exactly the
points we have here in detail. And I'd be more than pleased to send anyone a
copy
of this paper if they like (just ask).

Regards,

David
www.natural-selection.com

Tim Tyler

unread,
Sep 18, 1999, 3:00:00 AM9/18/99
to
Steve McGrew <ste...@iea.com> wrote:
: On Sat, 18 Sep 1999 13:38:15 GMT, Tim Tyler <t...@cryogen.com> wrote:

:>One reason why sex does not currently appear to offer many advantages,


:>is because sex requires large population sizes to be effective.
:>If you measure the effectiveness of an algorithm by haw many fitness
:>evaluations it requires, large populations will bump this figure up
:>significantly.

: I'm surprised to see you make this statement. I came into


: this thread late, and I assume that when you say "sex" the term
: includes "crossover". We find crossover to be very useful in many
: problems, using populations in the range of 10 to 100-- which I would
: consider to be small populations.

Sex requires a population size of at least two - I was probably
overstating the issue by saying that sexual species *required*
large population sizes.

Sex /is/ more likely to offer benefits in large populations, though:

One condition for sex to be beneficial in terms of evolution speed is
that beneficial mutations should occur somewhat more frequently than
the time it takes for an individual beneficial mutation to spread through
the population. In a small population, beneficial muatations are likely
to occur less frequently, simply because there are fewer individuals
available for them to occur in.

In nature I understand that many species experience a biodiversity crisis
- with alarming and often catastrophic loss of alleles - if the population
sinks below a few hundred individuals. This figure comes from
"The Diversity of Life" by Ed Wilson.


--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ t...@cryogen.com

Married women make the best wives.

Sean Luke

unread,
Sep 23, 1999, 3:00:00 AM9/23/99
to
I think the problem here is that people are perceiving Genetic Programming
as a *technique*. It's not. It's a community.

When asked what GP is, I usually say it's a community of researchers
presently consisting of somewhere between the intersection and the union
of people interested in evolving computer algorithms/programs/functions
and people interested in evolving problem solutions which use tree
structures. That seems to fit the community pretty well.

Sean

0 new messages