Figure 1: The Basics of Genetic Algorithms. Candidate solutions are changed by
mutation and evaluated based on fitness to some task. Then the best (and some
of the worst) are recombined to create a new candidate set, unless the candidate
solution already meets all design constraints.
solution is found...
dish and their entire power requirements would consist of a little sugar water. It might seem impractical to compute with such things until we look at
the existence proofs nature presents. As
Sussman observes: “The precision and
reliability of embryogenesis in the face
of constantly dying cells, their replacements, and changes in the environment—is enough to make any engineer
green with envy” [ 8].
THE FUTURE IS OPEN
within a generation
Illustration by Aidan Daley
Designing self-adapting computing
platforms using evolutionary and other
heuristic approaches is in its infancy.
Yet autonomous computing is a natural
outgrowth of a world in which computational devices are cheap, chatty, and increasingly naturalistic. Writing the seed
programs for such autonomous swarms
will require great care to ensure that
they help the world instead of harming
it. The baton will soon be yours.
Dennis Shasha is a professor of computer science at the
Courant Institute of New York University where he works
with biologists on pattern discovery for microarrays,
combinatorial design, network inference, and protein
docking; with physicists, musicians, and financial people on
algorithms for time series; and on database applications in
untrusted environments. He has written several books and
co-authored more than 60 journal papers, 70 conference
papers, and 15 patents. He has written the puzzle column for
various publications including ScientificAmerican.
COMPU TING ON NATURAL SUBS TRATES
The fusion of nature with computing
works in two directions. First, natural
mechanisms such as evolution can be
embedded in computer hardware and
software as described above. But computational techniques can also be used to
control nature [ 5]. Consider viruses. Next
to nuclear war, they constitute the most
dangerous threat to human beings.
Gaining immunity to viruses requires a
slo w-growing virus used as an inoculant.
Finding weak viruses is difficult when
done by trial and error, as Jonas Salk discovered in the 1950s when he tested the
poliovirus on scores of monkeys.
Ribosomes translate the more frequent
triplets/codons to amino acids faster
than the less frequent ones. So, making
a gene with less popular codons means
that the protein as a whole will be man-
ufactured more slowly than otherwise,
yielding a weakened virus that could
work as an inoculant. It takes a pattern
of thought consistently oriented toward
optimization to conceive of designing
an inefficient virus.
Computer scientist Steve Skiena has
designed viruses out of the DNA code
itself [ 6]. He makes use of the fact that
proteins encoded in the virus consist of
amino acids and that each amino acid
can be encoded by a variety of triplets
of DNA bases. For example, GCT, GCC,
GCA, and GCG all code for the simplest
amino acid, alanine. Though multiple
codings exist, it turns out that certain
codons of a given amino acid are favored over others. The favoritism is spe-cies-specific. For example, in humans
the GCC triplet is used 40 percent of the
time for the amino acid alanine, making it by far the most popular choice.
Skiena’s work shows how to change
the speed of normal biological processes, but computer scientists have
collaborated with biologists to develop
entirely new computational substrates
made of genetic soup. For example,
Tom Knight—collaborating with Gerald Sussman and many talented students at MIT—has developed a concept
of “biobricks” whereby logic gates can
be implemented on top of synthesized
promoter-gene constructs [ 7]. The
promise of computation at the subcel-lular level is that a little logic can interact with muscles or organs to repair injury or even enhance performance.
Harnessing biological entities might
strike most computer scientists as
messy and imprecise. After all, cells die,
proteins degrade, and many of us have
bad memories from high school biology lab. But the potential benefits may
outweigh this messiness. If we could
compute with single-celled bacteria for
example, billions would fit in a small
[ 1] Shasha, D., Lazere, C. Natural Computing: DNA,
Quantum Bits, and the Future of Smart Machines. W.
W. Norton, 2010.
[ 2] Koza, J. R., Bennett III, F. H., Andre, D., Keane, M. A. Genetic
Programming III—Darwinian Invention and Problem
Solving. Morgan Kaufman, San Francisco, 1999.
[ 3] Stoica, A., Zebulum, R., Keymeulen, D., Tawel, R. Daud.
T., Thakoor, A. Reconfigurable VLSI architectures
for evolvable hardware: From experimental field
programmable transistor arrays to evolution-oriented chips. IEEE Transactions on Very Large Scale
Integration Systems 9, 1 (2001), 227–32.
[ 4] Mason, L., Poston, D., Qualls, L. System concepts for
affordable fission surface power. Paper presented
at S TAIF-2008, Space Technology and Applications
International Forum (Albuquerque, NM, Feb. 2008).
[ 5] Adleman, L. M. Computing with DNA. Scientific
American 279, 2 (1998), 54–61.
[ 6] Coleman, J. R., Papamichail, D., Skiena, S., Futcher, B.,
Wimmer, E., Mueller, S. Virus attenuation by genome-scale changes in codon pair bias. Science 320, 5884
[ 7] Weiss, R., Knight Jr., T. F., Sussman, G. Genetic process
engineering. In Cellular Computing, M. Amos (Ed).
Oxford University Press, 2004.
[ 8] Nagpal, R., Sussman, G. Robust engineering using
biologically-inspired models of cell differentiation and