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
Introduction to Complex Systems:
How to think like nature
Innovation: generalized evolution and
environmentally based resource
allocation.
Russ Abbott
Sr. Engr. Spec.
310-336-1398
[email protected]
 1998-2007. The Aerospace Corporation. All Rights Reserved.
16
Innovative environments
Net-centricity and the GIG
• Inspired by the web and the internet
• Goal: to bring the creativity of the web and the internet
to the DoD
Other innovative environments
• Market economies
• Biological evolution
• The scientific and technological research process
What do innovative environments have in common?
How can organizations become innovative?
17
The innovative process: exploratory behavior
If I were to give an award for the single best idea anyone has ever had, I'd
give it to Darwin, ahead of Newton and Einstein and everyone else.
In a single stroke, the idea of evolution by natural selection unifies the
realm of life, meaning, and purpose with the realm of space and time,
cause and effect, mechanism and physical law. Daniel Dennett, Darwin's Dangerous Idea
Innovation, including human creativity, is always the result of an
evolutionary process.
• Generate new variants (e.g., ideas)—typically by combining and
modifying existing ones.
– This is a random process in nature.
The easy part!
– But random or not isn’t the point.
– The point is to generate lots of possibilities, to explore the landscape.
• (Select and) exploit the good ones
– Allow/enable the good ones to flourish.
The hard part!
18
Exploratory behavior in nature
• Evolution.
• E. Coli navigation.
• The immune system.
• Termite nest building.
• Ant and bee foraging.
• Building out the circulatory and nervous systems.
19
Exploratory behavior: like water finding a way down hill
Microbes attempting to get into your body must first get past your
skin and mucous membranes, which not only pose a physical barrier
but are rich in scavenger cells and IgA antibodies.
Next, they must elude a series of nonspecific defenses—and
substances that attack all invaders regardless of the epitopes they
carry. These include patrolling phagocytes, granulocytes, NK cells,
and complement.
Infectious agents that get past these nonspecific barriers must finally
confront specific weapons tailored just for them. These include both
antibodies and cytotoxic T cells.
From a tutorial on the immune system from the National Cancer Institute.
Quite a challenge! We are very well defended. But we still get sick!
Some “invaders” will make it past these defenses. The problem is not
even that some get through, it’s that they exploit their success.
How do they find the open pathways? It’s not
“invaders” vs. “defenders.”
Through (evolutionary) exploratory behavior, if
there is a way, some will inevitably find it.
Innovation is the
(disruptive) invader
not the defender.
Innovative organizations make that inevitability work in their favor.
20
Exploratory behavior: recall evolutionary processes
• How can the human genome, with fewer than 25,000 genes
– fill in all the details of the circulatory and nervous systems?
– produce a brain with trillions of cells and synaptic connections?
• Cell growth followed by species-specific die-off produces webbing
in duck feet and bat wings but not in human fingers.
• Military strategy of “probing for weakness.”
• Ant and bee foraging: group is a perceptual organ for individuals.
• Scientific research.
• Corporate strategy of seeking (or creating) marketing niches.
The general mechanism is:
• Prolifically generate a wide range of possibilities
• Establish connections to new sources of value in the environment.
Mechanism
generation
Function
explore
Purpose
use result
Bottom up
21
Exploratory behavior and asymmetric warfare
• It is the nature of complex systems
and evolutionary processes that
conflicts become asymmetric.
• No matter how well armored one is …
• there will always be chinks in the
armor, … and something will
inevitably find those chinks.
• The something that finds those
chinks will by definition be
asymmetric since it attacks the
chinks and not the armor.
22
Exploratory behavior in humans and society
• As processes carried out by individuals
– Individual mental trial and error exploration.
– Modeling and simulation.
• As processes carried out by groups
– Market economies. (A speeded up form of evolution.)
– The scientific and technological research process.
• These give us enormous leverage and speed-up over
traditional evolution.
It’s better to let one’s hypotheses die in one’s stead.
—Karl Popper, source uncertain.
23
Exploratory behavior: groups and individuals
• Exploratory behavior typically requires autonomous individuals to
do the exploration.
• Much exploratory behavior is wasted effort.
– Successful group exploratory behavior typically requires multiple,
loosely coordinated, i.e., autonomous, individuals.
• One may hit the jackpot while the others drill dry holes.
• For a group to benefit from the discoveries of individuals, there
must be mechanisms that bring those discoveries back to the
group and allow them to take root.
– Mechanisms to internalize successful/promising discoveries must
be built into a group’s process.
Recall ant foraging and pheromone following.
– This frequently requires “creative destruction,” which may be more
difficult to accept—especially if it’s your job that is being destroyed.
– Markets are how we integrate creative destruction into society.
It’s amazing how well we have tamed destruction.
It is now an accepted part of our normal processes.
Joseph Schumpeter,
Capitalism, Socialism, and Democracy
24
How does this apply to organizations?
To ensure innovation:
Creation and trial
• Encourage the prolific generation and trial of new
ideas.
Establish the successful variants
• Allow new ideas to flourish or wither based on
how well they do—rather than political reasons.
Sounds simple doesn’t it?
25
Innovation in various environments
New ideas
aren’t the
problem.
Biological
evolution
Entrepreneur
Bureaucracy
Trying them out
Initial funding
Prospect of
failure
Capitalism in
the small.
Nature always
experiments.
Most are failures,
which means
death. (But no
choice given.)
Little needed
for an Internet
experiment.
Perhaps some
embarrassment,
time, money; not
much more.
Proposals,
competition,
forms, etc.
Approvals
Getting
good ideas
Establishment
established
None.
Bottom-up
resource
allocation
defines
success.
Few.
Entrepreneur
wants rewards.
Bottom-up
resource
allocation.
When 100%
Managers have
Mission Success
Far too
other priorities.
is the group goal,
many.
Top-down
who wants a
We save ourselves resource
failure in his/her by spin-doctoring
personnel file? and benign neglect allocation.
26
“Garages and laboratories, workbenches, and scribbled
napkins are filled with brilliant ideas unmatched with
determination, resources, and market sensibilities.”
Jack Russo, Silicon Valley intellectual-property lawyer.
• In 1999, when Nathan Myhrvold left Microsoft (formerly CTO; brilliant, but
he missed the importance of the web) he set himself an unusual goal.
• He wanted to see whether the kind of insight that leads to invention could
be engineered.
• He formed a company called Intellectual Ventures.
• He raised hundreds of millions of dollars.
• He hired the smartest people he knew.
• It was not a venture-capital firm.
– Venture capitalists fund existing insights. They let the magical process that
generates new ideas take its course, and then they jump in.
• Myhrvold wanted to make insights—to come up with ideas, patent them,
and then license them to interested companies.
Malcolm Gladwell (May 12, 2008) “In the Air,” The New Yorker, http://www.newyorker.com/reporting/2008/05/12/080512fa_fact_gladwell
Matt Richtel (March 30, 2008) “Edison ...Wasn’t He the Guy Who Invented Everything?,” New York Times,
http://www.nytimes.com/2008/03/30/weekinreview/30richtel.html
27
Planned invention?
• When Myhrvold started out, his expectations were modest.
• Although he wanted insights like Alexander Graham Bell’s, Bell was
clearly one in a million, a genius who went on to have ideas in an
extraordinary number of areas—sound recording, flight, lasers,
tetrahedral construction, and hydrofoil boats, to name a few.
• Invention has its own algorithm—some combination of genius, obsession,
serendipity, and epiphany. How can you plan for that?
• The original expectation was that I.V. would file a hundred patents a year.
• It’s filing five hundred a year and has a backlog of three thousand ideas.
• It just licensed off a cluster of patents for $80,000,000.
• Its ideas are not trivial.
–
–
–
–
Improved jet engines
New techniques for making microchips
A way to custom-tailor the mesh “sleeve” used to repair aneurysms
Automatic, battery-powered glasses, with a tiny video camera that reads the
image off the retina and adjusts the fluid-filled lenses accordingly, up to ten
times a second.
Malcolm Gladwell (May 12, 2008) “In the Air,” The New Yorker,
http://www.newyorker.com/reporting/2008/05/12/080512fa_fact_gladwell
28
The history of science is full
of ideas that several people
had at the same time
• Newton and Leibniz: calculus.
• No less than nine claimants: the telescope.
• At least six different inventors: the thermometer.
• Three mathematicians: invention of decimal fractions.
• Charles Darwin and Alfred Russel Wallace: evolution.
• Elisha Gray and Alexander Graham Bell: the telephone.
• John Napier, Henry Briggs, and Joost Bürgi: logarithms.
• Charles Cros and Louis Ducos du Hauron: color photography.
• Galileo, Scheiner, Fabricius, and Harriott: discovery of sunspots.
• Joseph Priestley and Carl Wilhelm Scheele: discovery of oxygen.
• Several individuals in England and in America: typewriting machines.
Invention does not
require genius.
Genius is efficient
invention.
• Fulton, Jouffroy, Rumsey, Stevens, and Symmington: the steamboat.
• Édouard-Léon Scott de Martinville and Thomas Edison: the phonograph.
• Mayer, Joule, Thomson, Colding, and Helmholz: formulation of the conservation of energy.
W. F. Ogburn & D. S. Thomas (March 1922) “Are inventions inevitable?” Political Science Quartly, 37, 83-98.
Malcolm Gladwell (May 12, 2008) “In the Air,” The New Yorker, http://www.newyorker.com/reporting/2008/05/12/080512fa_fact_gladwell
Matt Richtel (March 30, 2008) “Edison ...Wasn’t He the Guy Who Invented Everything?,” New York Times, http://www.nytimes.com/2008/03/30/weekinreview/30richtel.html
29
Practical organizational innovation
Hamel and Skarzynski: an innovation architecture.
•
An innovation pipeline for managing and opportunities
•
A core set of people trained in the processes of innovation
•
A systematic process for generating and managing strategic insights
•
The right evaluative criteria at every stage of the development process
to prevent potentially valuable ideas from being killed off prematurely
•
Ideas that are sufficiently radical to deliver breakthroughs
•
Mechanisms for rapidly reallocating resources behind new opportunities
•
Mechanisms to manage growth opportunities with different timescales
and risk profiles
•
Metrics to measure innovation performance
•
Linkages between innovation and management compensation
•
A self-sustaining enterprise capability and a tangible core value
Prediction. Within 20 years to survive outside a protected environment an
organization will need a successfully functioning innovation architecture.
Corollary. Some organizations will focus on preserving their environments.
30
Simplified model of successful organisms/organizations
• Lower levels discover opportunities through exploratory behavior.
– New initiatives often grow from the “edges,” where perception occurs.
– Constrained by “rules of engagement,” which protect them from harm.
– Must be possible for initiatives to originate at all levels—even the top.
• Higher/broader levels provide perspective, impose constraints,
shape direction, and add or withhold resources as events develop.
– They do not primarily issue commands.
• This is primarily a bottom-up model of resource allocation.
– Decisions about increasingly significant commitments are made at
increasingly higher/broader levels. If the entire organism/organization
commits, becomes an entity-level goal.
• The top-level organism/organizational goal should be to stay
healthy and to build skills, resources, and capabilities that can be
recruited/applied/committed when needed.
Just what your mother always told you: eat right, exercise,
get plenty of sleep, study hard, practice, and save money.
31
C2: innovation in the military
• Our military is deliberately mission driven—where
the missions are determined by civilian authority.
• We don’t want our military to take the initiative to
find new missions for itself.
• What kinds of initiatives does it make sense for the
military to take?
– Initiatives that further already agreed upon
missions—or derived missions. I.e., internal
initiatives that make it more effective at doing what
it is charged to do.
– It isn’t clear how success can be made self-defining
in the same way as making money or reproducing
is self-defining. Need a way to aggregate
resources/success bottom-up.
– Establish a military-specific innovation architecture.
32