tomh@proxftl.UUCP (Tom Holroyd) (06/02/88)
This is from sci.physics, where it grew from a discussion of molecular
modeling..
In article <1617@vaxb.calgary.UUCP>, radford@calgary.UUCP (Radford Neal) writes:
]Well, I've just gone out and (to some extent) read Holland's book
]("Adaptation in Natural and Artifical Systems"). I'll summarize
]his main algorithm, since this will illuminate the roles of cross-over
]and mutation.
]
]You've got a bunch of potential structures (e.g. organisms), each of
]which has a "goodness" (e.g. fitness). You're trying to find the
]best structure. You maintain a "population" of structures, and apply
]the following algorithm:
]
] 1) Fill the population up with randomly-chosen structures.
]
] 2) Repeat:
]
] a) Randomly select two structures, X and Y, from the population,
] biasing your selection in favour of "better" structures.
]
] b) Compute a new structure, Z, from X and Y.
]
] c) Add Z to the population, deleting a randomly (uniformly) chosen
] structure to make room.
]
]Structures are represented by linearly-ordered attributes (e.g. alleles
]of genes). Step (b) is accomplished as follows:
]
] A) For each attribute of X, randomly change it with some (rather
] low) probability (Mutation).
]
] B) Sometimes do the following: Randomly select a segment of X and
] reverse the order of attributes within it (Inversion).
]
] C) Sometimes do the following: Randomly select a segment of X and
] replace its attributes with the analogous attributes of Y (Cross-
] over).
]
]The resulting modified X is what is called Z in step (b).
]
]Roughly, the roles of (A) to (C) are as follows:
]
] (A) Mutation: ensures that no attribute disappears entirely from the
] population, or constantly cycles in new attributes if the
] number of possibilities is greater than can be held at once
] in the population.
]
] (B) Inversion: Moves around attributes so that closely-related ones
] can form closely-linked groups.
]
] (C) Cross-over: Combines attributes from various successful structures
] in a fashion that is unlikely to break up closely-linked groups.
]
]It all sounds very plausible. I may try it out soon on my current
]intractible optimization problem.
]
] Radford Neal
I have two questions for all you genetic engineers (I hope this is the
right place to post this):
1. Is this model of genetic evolution in keeping with current biological
thinking? (I know it's incomplete, I just want to know if it's crazy.)
2. It doesn't address the growth of chromosomes, or the creation of new
ones. In fact, it doesn't talk about chromosomes at all. What can you
say about a) where chromosomes "come from", and b) does their structure
play a role in evolution (as the term 'crossover' seems to imply)?
For b), it seems that keeping genes for different organs on distinct
chromosomes would be an advantage, since you wouldn't be wasting time
crossing eyeballs and fins. This is probably a simplistic view, but..
Tom Holroyd
UUCP: {uunet,codas}!novavax!proxftl!tomh
The white knight is talking backwards.c60c-5aa@web8h.berkeley.edu (06/02/88)
]Well, I've just gone out and (to some extent) read Holland's book
]("Adaptation in Natural and Artifical Systems"). I'll summarize
]his main algorithm, since this will illuminate the roles of cross-over
]and mutation.
]
]You've got a bunch of potential structures (e.g. organisms), each of
]which has a "goodness" (e.g. fitness). You're trying to find the
]best structure. You maintain a "population" of structures, and apply
]the following algorithm:
]
] 1) Fill the population up with randomly-chosen structures.
]
] 2) Repeat:
] a) Randomly select two structures, X and Y, from the population,
] biasing your selection in favour of "better" structures.
] b) Compute a new structure, Z, from X and Y.
] c) Add Z to the population, deleting a randomly (uniformly) chosen
] structure to make room.
]
]Structures are represented by linearly-ordered attributes (e.g. alleles
]of genes). Step (b) is accomplished as follows:
]
] A) For each attribute of X, randomly change it with some (rather
] low) probability (Mutation).
] B) Sometimes do the following: Randomly select a segment of X and
] reverse the order of attributes within it (Inversion).
] C) Sometimes do the following: Randomly select a segment of X and
] replace its attributes with the analogous attributes of Y (Cross-
] over).
]
]The resulting modified X is what is called Z in step (b).
]
]Roughly, the roles of (A) to (C) are as follows:
]
] (A) Mutation: ensures that no attribute disappears entirely from the
] population, or constantly cycles in new attributes if the
] number of possibilities is greater than can be held at once
] in the population.
] (B) Inversion: Moves around attributes so that closely-related ones
] can form closely-linked groups.
] (C) Cross-over: Combines attributes from various successful structures
] in a fashion that is unlikely to break up closely-linked groups.
]
] Radford Neal
>I have two questions for all you genetic engineers (I hope this is the
>right place to post this):
>1. Is this model of genetic evolution in keeping with current biological
>thinking? (I know it's incomplete, I just want to know if it's crazy.)
One of the things that is missing seems critical to me; duplication of
"genes" (bits of information). I think this is critical to evolution--
without it, things would be grossly slower. It enables a new function to
be rapidly evolved without loss of the old one.
>2. It doesn't address the growth of chromosomes, or the creation of new
>ones. In fact, it doesn't talk about chromosomes at all. What can you
>say about a) where chromosomes "come from", and b) does their structure
>play a role in evolution (as the term 'crossover' seems to imply)?
It's a model for a one-chromosome organism, like a bacterium. It wouldn't
be too hard to generalize to multi-chromosome organisms, however; different
chromosomes can just be treated as regions of a structure separated by
spacers of length sufficient to insure that they will be separated by
crossover 50% of the time.
>For b), it seems that keeping genes for different organs on distinct
>chromosomes would be an advantage, since you wouldn't be wasting time
>crossing eyeballs and fins. This is probably a simplistic view, but..
The model defines crossover as occuring between analogous regions of the
structure, ones with the same "genes", not between ones at the same position--
otherwise crossover will always tend to be lethal as soon as there have
been any inversions.
Real organisms don't segregate their genes neatly between chromosomes,
but there is a tendancy for closely-related genes to cluster. This may be
due to controlling regions held in common, to a tendancy of duplication
to produce new copies near the old one, or (as the discussion above implies)
to an advantage to keeping co-adapted alleles together rather than having
them constantly split by crossovers.
>Tom Holroyd
>UUCP: {uunet,codas}!novavax!proxftl!tomh
Hope this helps. I'm fascinated to hear that the biological approach to
optimization has applications elsewhere!
Mary Kuhner
graduate student in genetics, UC Berkeley
(I don't speak for them, they don't speak to me....)