Transcript Short_course._Afternoon - Department of Computer Science

Introduction to Complex Systems:
How to think like nature
Course overview: part 2
Russ Abbott
Sr. Engr. Spec.
310-336-1398
[email protected]
 1998-2007. The Aerospace Corporation. All Rights Reserved.
1
Complex systems course overview
9:00–9:10.
9:10–9:25.
9:25–9:45.
9:45–9:55.
9:55–10:05.
10:05–10:15.
10:15–10:30.
10:30–10:45.
10:45–10:55.
10:55–11:00.
Introduction and motivation.
Unintended consequences – mechanism, function, and
purpose; introduction to NetLogo.
Emergence – the reductionist blind spot and levels of
abstraction.
Modeling; thought externalization; how engineers and
computer scientists think.
Break.
Evolution and evolutionary computing.
Innovation – exploratory behavior; initiative and
integration; resource allocation.
Platforms – distributed control and systems of systems.
Groups – the wisdom of crowds.
Summary/conclusions – remember this if nothing else.
2
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.
3
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.
4
Try it out
File > Models Library > Biology > Evolution > Peppered Moths
Click Open
5
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 is “evolution by natural (i.e.,
environmental) selection.”
– Darwin likened it to breeding. The
environment plays the rules of the breeder.
6
The nature of evolution
• Moths (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.
7
The nature of evolution. Four time scales
• 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.
• Biological evolution is generally slow.
• Markets are evolution speeded-up.
– Coke and Pepsi are rivals for
• Social/economic systems evolve at
consumer dollars, not adversaries.
medium speeds.
• They do not attempt to kill
– As rivals: a social system that does
each other’s CEOs or to
well for its members thrives and
sabotage each other’s delivery
expands.
trucks.
– As adversaries: social systems
sometimes compete for
• Warfare often super fast evolution.
resources—land in the past; now
– IED tactics and counter tactics.
other resources.
8
Application to engineering problems:
Since it’s simulated it’s even faster than military evolution
The Traveling Salesman Problem (TSP).
Connect the cities with a tour that is a
permutation of the cities.
A
20
• Starts and ends at the same city.
• Includes each city exactly once.
C
9
24
7
12
B
12
D
• The obvious tour will include the
sequence ACED-54 (or its reverse).
• No diagonals.
• The question is where to put B: ABCED55, ACBED-57, or ACEBD-56?
12
13
4
14
E
Why not n!
In this case the problem is easy to solve by inspection. In general, it’s
computationally explosive since there are (n-1)! possible tours.
9
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
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
10
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.
11
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.
12
Genetic programming: design and analysis
• The number of variables (and the structure of the possible
solution) is not fixed.
• Original goal was to generate software automatically.
– Not very successful, but hence the name.
• 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”
13
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).
14
Tom Lang:
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)
15