1 02-BioAnalogyOrigins

Previous: 01-ComputationalProblems.html


1.1 Big ideas

“How can computers learn to solve problems without being explicitly programmed?

How can computers be made to do what is needed to be done,
without being told exactly how to do it?”
- Arthur Samuel

Evolutionary algorithms are the most universally successful general learning algorithms in the known universe…

While that statement might only be true due to the generality constraint,
it’s still pretty cool!

1.2 Evolutionary Computing: Origins

1.3 Historical perspective

EC in the early 21st Century:
* 3 major EC conferences, about 10 small related ones
* 4 scientific core EC journals
* 1000+ EC-related papers published last year (estimate)
* uncountable (meaning: many) applications
* uncountable (meaning: ?) consultancy and R&D firms
* part of many university curricula


Main super-field, with numerous sub-fields


1.4 Main analogy

Natural evolution: Survival of the fittest
* A given natural environment is filled with a population of individuals that survive and reproduce.
* Fitness is an abstract quality that relates to how well they succeed in achieving their goals.
* The “fitness” of these individuals is circularly defined by which reproduce in the environment
* It is the “chances” of survival and of multiplying.

Problem solving method: Stochastic trial and error
* also known as generate-and-test
* In the context of a stochastic trial-and-error style problem solving process, we have a collection of candidate solutions.
* How well they solve the problem, defined as their “quality” determines the chance that they will be kept.
* Selected solutions are used as seeds for constructing further candidate solutions.

Natural Evolution Probleem Solving
Enivornment Problem
Individual Candidate solution
Fitness Solution quality

1.5 Darwinian Evolution

0. Genotype causes phenotype (genes encode, define, and cause physical form and behavior)
1. Reproductive inheritance (genes are inherited)
2. Mutation, diversity (genes randomly change and shuffle)
3. Differential survival (selection) - organisms which survive and reproduce, pass on genes that can continue to survive and reproduce

With these features, it is logically inevitable that evolution occurs.

1.5.1 Survival of the fittest

Environments have finite resources.
They can only support a limited number of individuals.
Therefore some kind of differential survival and reproduction “selection” is inevitable.
This is competition.
Ignoring the pervasive role of competition is a culturally common philosophical delusion.

Evolution as a circular tautology:
That which survives and reproduces,
can continue to survive and reproduce.
Thus, life forms that survive,
did so because their to basic cycles were geared towards survival and reproduction.

Those individuals that “compete for resources” most effectively,
have increased chance of reproduction.
Competition may be seemingly indirect.
Fitness in natural evolution is a derived, secondary concept.
Fitness is more like the fit of a glove,
rather than the fitness of an athlete.
This context retroactively assign a high fitness to individuals with many offspring.
It’s defined after having succeeded (breeded…)!
It’s a circular definition, and is circularly reinforcing.
That which survives and reproduces in the environment encountered,
will continue to have the opportunity to do so again.

1.5.2 Diversity is part of change

If phenotypic traits,
lead to higher chances of survival or reproduction, and
can be inherited,
then they will necessarily tend to increase in subsequent generations,
leading to new combinations of previously “useful” traits…

1.5.3 Summary

Population consists of diverse set of individuals.
Combinations of traits that are better adapted to the particular environment,
tend to increase frequency of representation in population.
Individuals are “units of selection” (or are they??).
Variations occur through random changes,
yielding constant source of diversity.
Coupled with selection, that means that evolution (environment-driven change) occurs.
Population is the “unit of evolution”.
In classic Darwinian evolution,
note the absence of a “guiding force”,
and more organic emergence of circular change.


“If you have variation, heredity, and competition,
then you must get evolution.”
- Daniel Dennet

Genetic natural selection:
What does a gene cause?
What is a gene for?
What is a gene?

If biological genes perform functions,
what function is selected for?

What is the unit of selection itself,
the smallest thing being selected?
The gene?
“Evolves for the good of the group” is a common fallacy.
The group is not the mechanistic driver of evolution.

Does the group selection fallacy logic apply to:
Slime molds?
Bee colonies?
What about when you have a brain, and can decide as a group?
In that case, which of the above would be selected for over time?
Is such selection inevitable?
Prisoners dilemma, tragedy of the commons.

What is the unit of evolution?
Gene, organism, population?
Selfish genes may propagate at the expense of the individual!


Let’s start with first principles:
In EC, we will talk deeply about fitness functions.
Fitness is a common notion in evolution.
“Survival of the fittest” is a common notion.

What makes an organism fit?
Do species get fitter over time?
What is valuable for an organism to do or be?
Does evolution progress?
Are brains the exception?

Humans have various notion of what is valuable.
Some values apply more broadly, more fundamentally than others.
How fundamental is any particular value or tendency, how broadly does it apply?
Is it shared by all cultures?
Is it shared by humans?
Is it shared by primates?
For example, play behavior, appearance focus, human logical fallacies shared by great apes?
Is it shared by all organisms?

There may even be biological rules:

Are there Physically intrinsic values?
Gravity (holding something up)
Magnetism (kids playing with magnets, what vocab do they use?)
Potential vs kinetic energy
Does matter want?
“Nature abhors a gradient”
Does nature “abhor”, “intend”, or “select” an organism “for” some purpose?

We’re back to the circular tautology:
That which survives and reproduces,
can continue to survive and reproduce.
That which does this is defined as fit,
has value being “selected for”.
This is broader than biology.

1.6 Adaptive landscape metaphor

(Wright, 1932)
Imagine population with n traits,
as existing in a n+1-dimensional space (landscape).
Why +1 ?

In the basic metaphor, one can imagine two genes,
the horizontal dimensions, x and z.
Each combination of horizontal x and z,
different individual (phenotype) represents a y single point,
on the landscape of x, y coordinates (vertical variation).
Population is therefore a spotty “cloud” of points, moving on the landscape over time as it evolves.
for two traits, x, y, the horizontal plane is defined.
Height (y) corresponds to fitness/value.

Any population that reproduces in given environment,
tends to move toward optima.
The idealized fittest individuals don’t always survive!
This process of survival operates “randomly”,
at the level of the individual.
Survival is determined not by what is globally ideal or statistically ideal,
but by the particular environment encountered.
The environment also includes other individuals!
Thus, a seemingly less fit individual may survive,
while a seemingly more fit individual may not,
given an “unlucky” particular context.
Nonetheless, given time and numbers,
fitness is selected.

Multimodal problems:
Optima can be local or global!
Notice the peaks in the image above.
Don’t get stuck!
Exploration versus exploitation.
A very general principle.

Genetic drift:
Random variations in feature distribution.
(+ or -) arising from sampling error.
Can cause the population “melt down” hills,
thus crossing valleys and leaving local optima
Populations can degrade, or get stuck,
sometimes due to too little genetic variability.

Common abstract model is a landscape of elevation,
which has to be maximized/minimized/searched (vertical dimension is fitness),
by a navigating entity (with two features/genes as horizontal axes),
which may get stuck in local minima.
Horizontal x and y as traits, which must be evolved,
to maximize the vertical dimension.

Matter undergoes inevitable processes.
Heat dissipates, balls roll down hills, matter decays, gradients diffuse.

Evolution of life is an aggregate amalgamation these inevitabilities,
and itself is mechanically, logically, necessary.
Given time, matter itself acts as an increasingly effective stochastic search mechanism,
to reach valleys, given the basic laws of energy and gradients.
For example, consider:
Heat always moves “downhill”,
that is, from hotter objects to colder objects,
unless energy is supplied to reverse the direction of heat flow.
Given time, evolution toward life-like growth,
is thermodynamically inevitable, and increase stochastically over deep time.
Does the organism burn, or intend and desire?
Behaviorism of brains, animals, materials?

“Nature abhors a gradient.”
Yet, nature maintains them, at great expense.
In thermodynamics, the Gibbs free energy (or Gibbs energy) is a thermodynamic potential,
that can be used to calculate a maximum amount of work,
that may be performed by a thermodynamically closed system,
at constant temperature and pressure.
It also provides a necessary condition for processes,
such as chemical reactions that may occur under these conditions.
Gibs free energy of an organism and it’s gradients?
Gibs and Cancer?

In light of our last lecture, can be consider:
Genetic evolution as search?
Evolution tends to “search” for the material configuration,
which survives best, creates entropy best, over the longest timescales,
which maximizes “desires” or tendencies of matter itself,
over the longest temporal term,
of the natural laws that govern the parts and pieces of organisms.

In light of our last lecture, can be consider:
Genetic evolution as optimization?
Multi-parameter optimization in genetic evolution?

Exists when one gene impacts multiple traits/functions.
For example:
Interleukins, brain, muscle, immune.
Fox domestication, spots.
Any such traits in humans?
Any genes that impact appearance, but also behavior?
Genes for red hair are expressed cutaneosly (skin/hair), and in brain only.
Embryonic Ectoderm turns into brain, eyes, and skin.

The inverse idea of pleiotropy.
A trait/function determined by more than one gene.

1.7 Genetics: Bio/Natural

The information required to build a living organism,
is coded in the DNA of that organism.
(or RNA for some).

Genotype (DNA inside the cells),
determines external physical and behavioral phenotype
For each gene, there may be different alleles,
values that gene can take.

For natural genes, phenotypic traits are a complex mapping:
One gene may affect many traits (pleiotropy).
Many genes may affect one trait (polygeny).

Changes in the genotype (specific base mutations),
lead to changes in the organism (e.g., height, hair color)
Sometimes the changes are subtle, to imperceptible.

1.7.1 Genetics: Genes and the Genome

Genes are encoded in strands of DNA called chromosomes.
In most cells, there are two copies of each chromosome (diploidy).
The complete genetic material in an individual’s genotype is called the Genome.
Within a species, most of the genetic material is the same.
Within all life, this is partly true too!
There are universal gene families!
These are old, fundamental, and indispensable;
if they are mutated, the organism dies…

1.7.2 Genetics: Example: Homo Sapiens

Human DNA is organized into chromosomes.
Human body cells contains 23 pairs of chromosomes,
which together define the physical attributes of the individual:

1.7.3 Genetics: Reproductive Cells

Gametes (sperm and egg cells) contain 23 individual chromosomes rather than 23 pairs.
Cells with only one copy of each chromosome are called haploid.
Gametes are formed by a special form of cell splitting called meiosis.
During meiosis the pairs of chromosome undergo an operation called crossing-over.

1.7.4 Genetics: Fertilization

Sperm cell from bio-Father.
Egg cell from bio-Mother.
New person cell (zygote).

1.7.5 Genetics: Crossing-over during meiosis

Chromosome pairs align and duplicate.
Inner pairs link at a centromere,
and swap parts of themselves.
Outcome is one copy of maternal/paternal chromosome plus two entirely new combinations.
After crossing-over one of each pair goes into each gamete.
Why is sexual reproduction the norm in all complex organisms?
It speeds up evolution, so we can defend against pathogens!
Sexual reproduction and recombination

1.7.6 Genetics: After fertilization

New zygote rapidly divides,
creating many cells all with the same genetic contents.
Although all cells contain the same genes,
depending on where they are in the organism,
they will behave differently.
This process of differential behavior during development is called ontogenesis.
All of this uses, and is controlled by,
the same mechanism for decoding the genes in DNA.

1.7.7 Genetics: Genetic code


“The genetic code is not a binary code as in computers,
nor an eight-level code as in some telephone systems,
but a quaternary code with four symbols.
The machine code of the genes is uncannily computer-like.”
- Richard Dawkins
All proteins in life on earth are composed of sequences,
built from 20 different amino acids.
DNA is built from four nucleotides in a double helix spiral:
purines A,G; pyrimidines T,C.
Triplets of these from codons,
each of which codes for a specific amino acid.

Much redundancy:
Purines complement pyrimidines.
The DNA contains non-coding regions (accumulated extra, regulatory, etc.).
43=64 codons code for 20 amino acids.
Genetic code = the mapping from codons to amino acids.

For all natural life on earth, the genetic code is the same!

“Human DNA is like a computer program but far,
far more advanced than any software ever created.”

- Bill Gates


1.7.8 Genetics: Transcription, translation

A central claim in molecular genetics:
Only one way flow.
Genotype –> Phenotype
Genotype <-X- Phenotype

Common/canonical paths in blue.
Rare paths in red.

Lamarckian (saying that acquired features can be inherited) is thus usually wrong (mostly).
There are a number of minor,
subtle instances of the reverse,
even transgenerational epigenetics.
Mention dutch famines, pesticide effects on males only, etc.

How do species form?
What drives speciation?
What is a species?
How do we model, track, and describe species?
Family trees.
Trees for all kinds of evolved things,
(languages, memes, quantum states, material itself, etc.).

1.7.9 Genetics: Mutation

Occasionally some of the genetic material changes very slightly,
during this process (replication error).
This means that the child might have different genetic material,
information not inherited from either parent.

This can be:

catastrophic: offspring in not viable (most likely).
neutral: new feature not influences fitness (next most likely).
advantageous: strong new feature occurs (rare).

Redundancy in the genetic code forms a good way of error checking.
Some mutations produce different properties,
often leading to disease:

90s big question, that faded into mere description (perhaps the right approach for big questions):
What is life? https://en.wikipedia.org/wiki/Life#Definitions

regulation of the internal environment to maintain a constant state;
for example, sweating to reduce temperature.

being structurally composed of one or more cells,
the basic units of life.

transformation of energy by converting chemicals and energy into cellular components (anabolism),
and decomposing organic matter (catabolism).
Living things require energy to maintain internal organization (homeostasis),
and to produce the other phenomena associated with life.

maintenance of a higher rate of anabolism than catabolism.
A growing organism increases in size in all of its parts,
rather than simply accumulating matter.

the evolutionary process whereby an organism becomes changes,
being better able to live in its habitat or habitats.

Response to stimuli:
a response can take many forms,
from the contraction of a unicellular organism to external chemicals,
to complex reactions involving all the senses of multicellular organisms.
A response is often expressed by motion;
or example, the leaves of a plant turning toward the sun (phototropism), and chemotaxis.

the ability to produce new individual organisms,
either asexually from a single parent organism or sexually from two parent organisms.

Does fire meet the criteria you chose?
What about prions?
Multi-part organisms?
What about Lichen?
How about viruses?
Derivative of us?
Does a fragment of a virus particle metabolize?
Their particles themselves harvest molecular energy
Is that metabolism?

What can evolve?
We can formulate a generalized version of the mechanisms of:
variation, selection, and heredity proposed by Charles Darwin,
so that they can apply to explain evolution in a wide variety of other domains,
including psychology, linguistics, economics, culture, medicine, computer science, and physics.

This process can be conceived as an evolutionary algorithm,
that searches the space of possible forms (the fitness landscape),
for the ones that are best adapted.

The process has three components:
1. variation of a given form or template. This is usually (but not necessarily) considered to be blind or random, and happens typically by mutation or recombination.
2. selection of the fittest variants, i.e. those that are best suited to survive and reproduce in their given environment. The unfit variants are eliminated.
3. heredity or retention, meaning that the features of the fit variants are retained and passed on, e.g. in offspring.

How about elementary physical particles?
Quantum Darwinism sees the emergence of classical states in physics,
as a natural selection of the most stable quantum properties.

What about ideas (memes)?
Do they: sequester resources, Manifest physically, maintain equilibrium (homeostasis), respond to stimuli, reproduce?
What about technologies we find useful?
What about languages?
Language family trees?
Can we evolve Molecules in a lab?
A common method in synthetic chemistry!

Evolution is an idea like a universal solvent (water, acetone, etc.),
that dissolves understanding across disciplines…
I hope this class does the same to your thinking.

1.8 Motivation for evolutionary computing

Inspiration, ideal computational solver characteristics, and studying evolution.

1.8.1 Inspiration

Nature has always served as a source of inspiration for engineers and scientists.
When looking for the most powerful natural problem solver,
there are two rather obvious candidates:

The primate/human brain
Answer 1: neuro-computing

The evolutionary process (that created the human brain).
Answer 2: evolutionary computing

1.8.2 Ideal solver properties

Developing, analyzing, applying problem solving methods, a.k.a. algorithms,
is a central theme in mathematics and computer science.

There is a need for algorithms that are:
applicable to a wide range of problems,
do not need much tailoring for specific problems, and
deliver good (not necessarily optimal) solutions
within acceptable time.

Evolutionary algorithms do all this.
Further, they tend result in explainable solutions and encoding
which is a lot more than can be said for neural networks,
which do very much the opposite
(hide the contents of their black boxes)!

Most other methods in ML, AI, produce solutions.
EC produces solvers themselves, not just solutions.
EC can and does also produce solutions to problems.

1.8.3 Studying evolution itself

Turning bio-inspired computing back into computational biology:
Reciprocal curiosity about the system being used as inspiration, Evolution itself.
Evolutionary processes are the subjects of scientific studies,
where the main objective is to understand how evolution works.

Evolutionary computing performs experiments differently from traditional biology.
Evolutionary processes can be simulated in a computer,
where millions of generations can be executed in a matter of hours or days,
and repeated under various circumstances.
These possibilities go far beyond studies based on excavations and fossils,
or even those possible in vivo.
The interpretation of such simulation experiments must be performed carefully.
Computer models represent the biological reality with limited fidelity.
Despite these caveats,
there is a strong tradition within evolutionary computing,
to ‘play around’ with evolution for the sake of understanding how it works.
Further, using simulations, one can make assertions broader than biology,
about evolutionary systems, and evolving things generally.

1.9 Some fun examples

Applications of EC.

1.9.1 Boom design

02-BioAnalogyOrigins/kean_96d.pdf (the actual paper)
EC applications in industrial design optimization.
We illustrat with the case of a satellite dish holder boom (arm).
This ladder-like construction connects the satellite’s body with the dish needed for communication.
It is essential that this boom is stable,
in particular vibration resistant,
as there is no air in space that would damp vibrations,
that could break the whole construction.

The above paper optimized this construction using an evolutionary algorithm.
The resulting structure is 20,000% (!) better than traditional shapes,
but for humans it looks very strange:
it exhibits no obvious symmetry,
and there is no intuitive design logic visible.
The final design looks like a random drawing,
and the crucial thing is this:
it is a random drawing, drawn without intelligence,
but evolving through a number of consecutive generations of improving solutions.

Discussion question:
* Why do you think the below designs seem so foreign?
* Do they appear more natural?
* Why do you think that is?

This illustrates the power of evolution as an accidental “designer”:
it is not limited by conventions, aesthetic considerations, or preferences for symmetry.
On the contrary, it is purely driven by circularly-defined quality,
and thereby it can come to solutions that lie outside of the scope of human thinking,
with its implicit and unconscious limitations.

Evolutionary design often supports reverse engineering.
Once a provably superior solution is evolved,
it can be analyzed and explained through the eyes of traditional engineering.
This can lead to generalizable knowledge,
i.e., the formulation of new laws, theories, or design principles,
applicable to a variety of other problems of similar type

1.9.2 Antenna design

02-BioAnalogyOrigins/Space2006Antenna.pdf (the actual paper)
Antenna gain as a fitness function.
Lengths and angles as genetic features to be evolved.
Sometimes messy and asymmetrical is a good thing!

1.9.3 Economics

Evolutionary computing can also be applied to simulation problems, that is,
to answer what-if questions in a context where the investigated subject matter is evolving,
i.e., driven by variation and selection.
Evolutionary economics is an established research area,
roughly based on the perception that,
the game and the players in the socioeconomic arena have much in common with the game of life.
The survival of the fittest principle is also fundamental in the economic context.
The term agent-based computational economy is often used to emphasize this aspect Sugarscape world (simulated economics)

Academic research in this direction is often based on a simple model called Sugarscape world.
This features agent-like inhabitants in a grid space, and a commodity (the sugar),
that can be consumed, owned, traded, and so on, by the inhabitants.
There are many ways to set up system variants with an economics interpretation,
and conduct simulation experiments.
For instance, we have seen how artificially forced sugar theft and redistribution (tax),
and evolution interact under various circumstances.

1.9.4 Stock trading

Evolve sets of rules for modeling the behavior of stock market traders.
As inputs use ten years of trading history,
in the form of daily statistics such as:
volume of trade, current price, change in price over the last few days,
whether this price is a new high (or low), and so on for a given company’s stock.

The evolved traders consisted of sets of condition -> action rules.
Each day the current stock market conditions were presented to the trader,
triggering a rule that decided whether stock was bought or sold.
Periodically a genetic algorithm is run on the set of (initially random) rules,
so that well-performing ones are rewarded, and poorly performing ones are discarded.

It was demonstrated that the system evolved trading agents that outperformed many well-known strategies,
and varied according to the nature of the particular stock they were trading.
Of particular interest, and benefit, compared to methods such as neural networks
(which are also used for this kind of modeling problem in time-series forecasting),
is the fact that the rule-bases of the evolved traders are easily examinable,
that is to say that the models that are evolved are particularly transparent to the user.

1.9.5 Other examples:

1.10 Features of EAs

1.11 General evolutionary theory

1.12 Extra Reading


Random mutation is just part of the picture of real biological evolution,
but there are many more powerful modular mechanisms in addition,
some even verging on Lamarkian or not-fully-random Darwinian mechanisms:

Charles Darwin. The Origin of Species. John Murray, 1859.
The world-famous book introducing the theory of evolution, based on Darwin’s observations from his trip on the Beagle.
Not actually really worth reading…

R. Dawkins. The Selfish Gene. Oxford University Press, 1976.
A pop-science classic, promoting neo-Darwinism as a synthesis of evolution with modern genetics. Its very gene-centric view of evolution, has been questioned by some.
Accurate, albeit boring.

J.Maynard-Smith. The Evolution of Sex. Cambridge University Press, 1978.
A good, readable introduction to the biological basics of reproduction in haploid and diploid organisms.

S.Wright. The roles of mutation, inbreeding, cross-breeding, and selection in evolution. In: Proc. of 6th Int. Congress on Genetics, vol.1, pp. 356–366. Ithaca, NY, 1932.
The paper introducing the idea of the adaptive landscapes.

D.B. Fogel, ed. Evolutionary Computation: the Fossil Record. IEEE Press, 1998.
Fascinating collection of early works in the field, interesting not just for historical insight.

S.A. Kauffman. Origins of Order: Self-Organization and Selection in Evolution. Oxford University Press, New York, 1993.
Offers a different perspective on the processes that led to the origins of life.

1.13 Exercises

Next: 03-MetaheuristicParts.html