Previous: 01-ComputationalProblems.html
“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!
They are also familiar to us, intuitive.
We have used them, indirectly and directly, deep into history.
EC in the early 21st Century:
Main super-field, with numerous sub-fields
https://en.wikipedia.org/wiki/Evolutionary_computation
https://en.wikipedia.org/wiki/Evolutionary_algorithm
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 |
The basics that are needed:
With these features, it is logically inevitable that evolution occurs.
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.
If phenotypic traits both:
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…
Populations consist of diverse sets of individuals.
Combinations of traits that are better adapted to the particular
environment,
tend to increase frequency of representation in population.
Variations occur through random changes,
yielding constant source of diversity.
Coupled with selection, that means that evolution (environment-driven change) occurs.
Individuals are “units of selection”.
Populations are 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
It is a logical inevitability so simple that it is nearly a tautology.
https://en.wikipedia.org/wiki/Natural_selection
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?
Organism?
Community?
Species?
“Evolves for the good of the group” is a common misunderstanding, the
“group selection fallacy”.
The group is not the mechanistic driver of evolution!
Nothing is driven forward, but through selfish mechanisms at the
smallest of scales, emerging upward.
Non-zero sum games can be reduced to zero sum games.
How does altruism arise?
Under what condititions would it arise over evolutionary time?
Under what conditions might it decay over evolutionary time?
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?
Why?
Does evolution progress?
Are brains the exception?
Humans have various notions of what is valuable.
Value is defined by a context, a scope.
A feature “X” is good, because it is “good for Y” some context.
Some values apply more broadly, more fundamentally than others,
across bigger scopes and contexts.
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 a feature shared by all organisms?
There may even be biological rules:
https://en.wikipedia.org/wiki/Biological_rules
Are there Physically intrinsic values?
Gravity (holding something up)
Magnetism (kids playing with magnets, what vocabulary 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?
https://en.wikipedia.org/wiki/Scientific_law
https://en.wikipedia.org/wiki/Scientific_law#Laws_of_biology
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.
(Wright, 1932)
Imagine a 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 to survive and reproduce is generall selected for.
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 across various fields of ML.
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.
A 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 physically inevitable processes.
Heat dissipates, balls roll down hills, matter decays, gradients
diffuse.
These are scientific laws:
https://en.wikipedia.org/wiki/Scientific_law
Evolution of life is an aggregate amalgamation of these
inevitabilities,
and itself is mechanically, logically, necessary.
Given time, the tendencies of matter itself act as an increasingly
effective stochastic search mechanism,
to reach more global valleys, given the basic laws of energy and
gradients.
For example, consider:
https://www.youtube.com/watch?v=DxL2HoqLbyA&t=1152
https://en.wikipedia.org/wiki/Second_law_of_thermodynamics
Heat always moves “downhill”,
that is, from hotter objects to colder objects,
unless energy is supplied to reverse the direction of heat flow.
https://en.wikipedia.org/wiki/Scientific_law#Thermodynamics
https://en.wikipedia.org/wiki/Entropy_and_life
Into the Cool: Energy Flow, Thermodynamics, and Life by Eric D.
Schneider and Dorion Sagan:
https://press.uchicago.edu/ucp/books/book/chicago/I/bo3533936.html
https://www.quantamagazine.org/a-new-thermodynamics-theory-of-the-origin-of-life-20140122/
https://www.quantamagazine.org/first-support-for-a-physics-theory-of-life-20170726/
https://en.m.wikipedia.org/wiki/Entropy_and_life
https://en.m.wikipedia.org/wiki/Jeremy_England
Life is an entropy pump.
Entropy pumps are determined by, created by multiple physical laws
interacting over time.
Given time, evolution toward life-like growth,
is thermodynamically inevitable, and must 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.
Gibbs free energy of an organism and it’s gradients?
Gibbs and Cancer?
https://en.wikipedia.org/wiki/Artificial_intelligence#Search_and_optimization
Can we consider genetic evolution as search?
Evolution tends to “search” for a 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.
Living entropy pumps will evolve to be better entropy pumps.
In light of our last lecture, can be consider:
Genetic evolution as optimization?
https://en.wikipedia.org/wiki/Optimization_(disambiguation)
Multi-parameter optimization in genetic evolution?
Pleiotropy
Exists when one gene impacts multiple traits/functions.
For example:
Interleukins, brain, muscle, immune.
Fox domestication studies selected behavior, but produced doggy
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.
Polygeny
The inverse idea of pleiotropy.
A trait/function determined by more than one gene.
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.
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…
Human DNA is organized into chromosomes.
Human body cells contains 23 pairs of chromosomes,
which together define the physical attributes of the individual:
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.
Sperm cell from bio-Father.
Egg cell from bio-Mother.
New person cell (zygote).
Sexual reproduction and recombination.
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!
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.
“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 are A,G
pyrimidines are 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
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?
Isolation.
What is a species?
It is more debated than you might think!
https://en.wikipedia.org/wiki/Competitive_exclusion_principle
How do we model, track, and describe species?
Family trees.
Trees for all kinds of evolved things,
(languages, memes, quantum states, material itself, codebases,
etc.).
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 either:
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
Homeostasis:
regulation of the internal environment to maintain a constant
state;
for example, sweating to reduce temperature.
Organization:
being structurally composed of one or more cells,
the basic units of life.
Metabolism:
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.
Growth:
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.
Adaptation:
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.
Reproduction:
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?
Self-assembly?
Does a fragment of a virus particle metabolize?
Their particles themselves harvest molecular energy
Is that metabolism?
What can evolve?
https://en.wikipedia.org/wiki/Memetics
https://en.wikipedia.org/wiki/Universal_Darwinism
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?
https://en.wikipedia.org/wiki/Quantum_Darwinism
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!
Can we create organisms from materials?
This is the question of synthetic life!
https://en.wikipedia.org/wiki/Symbiogenesis
We have actually observed this happening!
https://newatlas.com/biology/life-merger-evolution-symbiosis-organelle/
https://www.cell.com/cell/pdf/S0092-8674(24)00182-X.pdf
https://www.science.org/doi/10.1126/science.adk1075
https://en.wikipedia.org/wiki/Punctuated_equilibrium
https://en.wikipedia.org/wiki/Darwin's_Dangerous_Idea
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.
Inspiration, ideal computational solver characteristics, and studying evolution.
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
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.
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.
Applications of EC.
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
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!
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
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.
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.
Evolution is a broad conceptual super-category, beyond EC and Bio.
What kinds of selection are there?
These are not mutually exclusive:
Rate of evolution, and evolutionary plasticity
Modularity and biology, evolution?
In directed selection, what is selected for?
https://en.wikipedia.org/wiki/Darwin's_Dangerous_Idea
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:
https://aeon.co/essays/why-did-darwins-20th-century-followers-get-evolution-so-wrong
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.