Transcript Evolutionary - Department of Computer Science

Introduction to Complex Systems:
How to think like nature
Evolution: how nature thinks
Russ Abbott
Sr. Engr. Spec.
310-336-1398
[email protected]
 1998-2007. The Aerospace Corporation. All Rights Reserved.
1
Peppered moths: evolution in action
• Originally, the vast majority of peppered moths
in Manchester, England had light coloration—
which camouflaged them from predators since
they blended into the light-colored trees.
• With the industrial revolution:
– Pollution blackened the trees.
– Light-colored moths died off.
– Dark-colored moths flourished.
• With improved environmental standards, lightcolored peppered moths have again become
common.
2
Peppered moths model
• The (very simple) model: at each time tick
– A moth’s probability of survival—not being eaten
by predators (not shown)—depends on:
• How close its color (1-9) is to the background
color (0-8).
• The “Selection” slider, which controls the
impact of the environment.
- The higher the slider, the more important the
environment.
– Moths both reproduce and die (of old age).
• During reproduction, they may mutate—have
offspring of a different color.
3
Try it out
File > Models Library > Biology > Evolution > Peppered Moths
Click Open
4
The nature of evolution
• Moth (and their colors) are
rivals, not adversaries.
– It’s more like a race than a
boxing match.
• They are rivals with respect
to their ability
– to survive and acquire
resources from the
environment.
• Moth coloring confers survival value (fitness)—which
depends on the environment.
– Hence Darwin’s “natural selection,” i.e., environmental
selection.
– The environment selects the winners.
• There may be multiple “winners.” All one needs is a
niche, not domination.
5
The nature of evolution
• Nature is not “red in tooth and
claw.”
– The moths and their colors don’t
compete with each other directly.
• There are no moth-on-moth
battles.
• Nor do the dark moths
attempt to convince the light
moths that it’s better to be
dark — or vice versa.
– Coke and Pepsi are rivals for
consumer dollars, not adversaries.
• They do not attempt to kill
each other’s CEOs or to
sabotage each other’s
delivery trucks.
6
The nature of evolution
• Biological evolution takes place among dynamic entities.
• Dynamic entities are “far from equilibrium.” That means they
need energy from the environment to persist.
• Biological evolution is fundamentally about energy.
• The simple view is: more energy, the more successful in
reproduction.
• It’s not a competition, but it is a necessity.
• More successful groups use more energy, possibly
crowding out others.
• But it’s possible to have a stable ecosystem.
7
Application to engineering problems:
The Traveling Salesman Problem (TSP)
Connect the cities with a path that:
• Starts and ends at the same city.
• Includes all cities.
A
• Includes no city twice.
20
C
9
24
7
12
B
12
D
12
13
4
14
• The obvious tour will include the
sequence: ACED-54 (or its reverse).
• The question is where to put B: ABCED55, ACBED-57, or ACEBD-56?
E
In this case the problem is easy to solve by inspection. In general, it’s
computationally explosive since there are (n-1)! possible tours.
8
Genetic algorithm approach
Create a population of random tours.
• AEBCD-59, ACBED-57, ADCBE-59, ACDEB-71, …
• In this case there are only 4! = 24 possible tours.
• Could examine them all. Usually that’s not possible.
20
A
An exchange (or reverse or mutation)
solves this problem in one step.
ACBED-57 → ABCED-55
C
9
24
7
12
B
12
D
Why not 5!
12
13
4
14
E
Repeat until good enough or no improvement. But beware local optima.
•Select one or two tours as parents.
− Ensure that better tours are more likely to be selected.
•Generate offspring using genetic operators to replace poorer elements.
− Exchange two cities: ACDEB-71 → ACBED-57
− Reverse a subtour: ACBED-57 → AEBCD-59
− (Re)combine two tours: AEBCD-59 & ACBED-57 → AEDCB-71.
• Possibly mutate the result: ADCBE-59 → ACBDE-70
9
Try it out: TSP.jar
• After starting a run, double click in the display area to add a
city or on a city to remove it.
– New cities are added to the tour next to their nearest neighbor.
• Stop and restart for new random cities.
– The number of new cities will be the same as the number of old
cities.
• The differences between the current best and its predecessor
are shown by link color.
– New links are shown in green.
– Removed links are in dashed magenta.
• No “geographical” heuristics are used. Just the structural ones
shown on the previous slide.
10
The evolutionary process
• There is a population of elements.
• The elements are capable of making copies
of themselves
– perhaps with variants (mutations) and
– perhaps by combining with other elements.
• The environment affects the likelihood of an
element surviving and reproducing.
• This results in “evolution by natural (i.e.,
environmental) selection.”
– Darwin likened it to breeding. The
environment plays the rules of the breeder.
11
Evolution differs from most science
• The process described on the preceding page is tautologically true.
– Darwin didn’t know about DNA.
• One doesn’t study evolution by taking something apart and seeing
how it works.
– There is no reductive explanation for it.
• There are no underlying mechanisms from which evolution can be
derived or upon which it depends.
– In that sense it is like a Game of Life Turing Machine.
• Evolution is an epiphenomenally emergent property of any level of
abstraction that satisfies the conditions on the preceding slide.
• Those conditions can be implemented in many different ways.
12
Genetic algorithms: parameter setting/tuning
• The number of variables is constant.
– Both the TSP and the peppered moths examples illustrate genetic
algorithms.
• Peppered moths: one parameter (color) to set.
• TSP: N variables. As a parameter setting problem think of each
tour as consisting of N variables, each of which may contain any
city number. The additional constraint is that no city may repeat.
• Often there are hundreds of variables (or more) or the search space
is large and difficult to search for some other reason.
• There is no algorithmic way to find values that optimize
(maximize/minimize) an objective function.
Terrile et. al. (JPL), “Evolutionary Computation applied to the Tuning of
MEMS gyroscopes,” GECCO, 2005.
Abstract: We propose a tuning method for MEMS gyroscopes based on
evolutionary computation to efficiently increase the sensitivity of MEMS gyroscopes
through tuning and, furthermore, to find the optimally tuned configuration for this
state of increased sensitivity. The tuning method was tested for the second
generation JPL/Boeing Post-resonator MEMS gyroscope using the measurement of
the frequency response of the MEMS device in open-loop operation.
13
Genetic Programming: design and analysis
• The number of variables (and the structure of the possible
solution) is not fixed.
• Originally attempted (not very successfully) to be applied to
generating computer programs.
• But applied successfully to other design and analysis problems.
– Circuit design
– Lens design
Bongard and Lipson (Cornel), “Automated reverse engineering of nonlinear dynamical
systems,” PNAS, 2007.
Abstract: Complex nonlinear dynamics arise in many fields of science and engineering, but
uncovering the underlying differential equations directly from observations poses a
challenging task. The ability to symbolically model complex networked systems is key to
understanding them, an open problem in many disciplines. Here we introduce for the first time
a method that can automatically generate symbolic equations for a nonlinear coupled
dynamical system directly from time series data. This method is applicable to any system that
can be described using sets of ordinary nonlinear differential equations, and assumes that the
(possibly noisy) time series of all variables are observable. …
“Symbolic regression”
14
The Human-competitive awards: “Humies”
• Each year at the Genetic and Evolutionary Computing Conference (GECCO), prizes
are awarded to systems that perform at human-competitive levels—including the
previous two slides.
– See http://www.genetic-programming.org/hc2005/main.html
• An automatically created result is considered “human-competitive” if it satisfies at
least one of the eight criteria below.
A. The result was patented as an invention in the past, is an improvement over a patented invention, or
would qualify today as a patentable new invention.
B. The result is equal to or better than a result that was accepted as a new scientific result at the time
when it was published in a peer-reviewed scientific journal.
C. The result is equal to or better than a result that was placed into a database or archive of results
maintained by an internationally recognized panel of scientific experts.
D. The result is publishable in its own right as a new scientific result — independent of the fact that the
result was mechanically created.
E. The result is equal to or better than the most recent human-created solution to a long-standing
problem for which there has been a succession of increasingly better human-created solutions.
F. The result is equal to or better than a result that was considered an achievement in its field at the time
it was first discovered.
G. The result solves a problem of indisputable difficulty in its field.
H. The result holds its own or wins a regulated competition involving human contestants (in the form of
either live human players or human-written computer programs).
15
Tom Lang and Laura Speckman:
Genetic Algorithm for Constellation Optimization (GACO)
• Finds optimal constellation orbits using a genetic
algorithm under multiple design constraints and
with multiple sensor types.
4 Satellite Constellations
Global Coverage, elmin = 0
4.5
For low number of sats, GA
arrangement is significantly
better than Walker
Max Revisit Time/Orbital Period
4
3.5
3
2.5
GA
Walker
2
1.5
1
0.5
0
0
5
10
15
20
25
30
35
40
45
50
55
60
Earth Central Angle (degrees)
16