I’d like to present three articles on the topic of evolutionary algorithms.
All three were co-authored by Kenneth O. Stanley, and I found them on his personal homepage: https://www.cs.ucf.edu/~kstanley/.
This first article gives practical advice for simulating evolution. It introduces a new technique for representing unstructured data in genetic material, which was previously an open challenge. The article is very well written and won a “best paper of the decade” award.
Evolving Neural Networks through Augmenting Topologies
Kenneth O. Stanley, Risto Miikkulainen (2002)
https://doi.org/10.1162/106365602320169811
Free Full Text: https://www.cse.unr.edu/~sushil/class/gas/papers/NEAT.pdfAbstract
An important question in neuroevolution is how to gain an advantage from evolving
neural network topologies along with weights. We present a method, NeuroEvolu-
tion of Augmenting Topologies (NEAT), which outperforms the best fixed-topology
method on a challenging benchmark reinforcement learning task. We claim that the
increased efficiency is due to (1) employing a principled method of crossover of differ-
ent topologies, (2) protecting structural innovation using speciation, and (3) incremen-
tally growing from minimal structure. We test this claim through a series of ablation
studies that demonstrate that each component is necessary to the system as a whole
and to each other. What results is significantly faster learning. NEAT is also an im-
portant contribution to GAs because it shows how it is possible for evolution to both
optimize and complexify solutions simultaneously, offering the possibility of evolving
increasingly complex solutions over generations, and strengthening the analogy with
biological evolution.
This article justifies the field of “artificial-life” as a valid scientific endeavor,
and summarizes the state of the art of artificial-life.
Investigating Biological Assumptions through Radical Reimplementation
Joel Lehman, Kenneth O. Stanley (2014)
https://doi.org/10.1162/ARTL_a_00150
Free Full Text: http://eplex.cs.ucf.edu/papers/lehman_alife14.pdfAbstract
An important goal in both artificial life and biology is uncovering the most
general principles underlying life, which might catalyze both our understanding
of life and engineering life-like machines. While many such general principles
have been hypothesized, conclusively testing them is difficult because life on
Earth provides only a singular example from which to infer. To circumvent
this limitation, this paper formalizes an approach called radical reimplementa-
tion. The idea is to investigate an abstract biological hypothesis by intentionally
reimplementing its main principles to diverge maximally from existing natural
examples. If the reimplementation successfully exhibits properties resembling
biology it may better support the underlying hypothesis than an alternative
example inspired more directly by nature. The approach thereby provides a
principled alternative to a common tradition of defending and minimizing de-
viations from nature in artificial life. This work reviews examples that can be
interpreted through the lens of radical reimplementation to yield potential in-
sights into biology despite having purposefully unnatural experimental setups.
In this way, radical reimplementation can help renew the relevance of compu-
tational systems for investigating biological theory and can act as a practical
philosophical tool to help separate the fundamental features of terrestrial biology
from the epiphenomenal.
For context: The “Picbreeder” program generates images. Each image has an artificial DNA which describes how to draw the image and users can manually select images to breed together. It can make interesting images in a small number of generations, and the user can exert considerable influence over the image by selecting which images to breed together. However, they find that attempting to breed a specific image is very difficult because there are many intermediate steps along the way, and those intermediate steps do not look like the final image. Most optimization techniques try to get to the final result as fast as possible, but that will not work for problems with important intermediate steps.
On the Deleterious Effects of A Priori Objectives on Evolution and Representation
Brian G. Woolley, Kenneth O. Stanley (2011)
https://doi.org/10.1145/2001576.2001707
Free Full Text: http://eplex.cs.ucf.edu/papers/woolley_gecco11.pdfABSTRACT
Evolutionary algorithms are often evaluated by measuring and com-
paring their ability to consistently reach objectives chosen a priori
by researchers. Yet recent results from experiments without ex-
plicit a priori objectives, such as in Picbreeder and with the nov-
elty search algorithm, raise the question of whether the very act
of setting an objective is exacting a subtle price. Nature provides
another hint that the reigning objective-based paradigm may be ob-
fuscating evolutionary computation’s true potential; after all, many
of the greatest discoveries of natural evolution, such as flight and
human-level intelligence, were not set as a priori objectives at the
beginning of the search. The dangerous question is whether such
triumphs only result because they were not objectives. To examine
this question, this paper takes the unusual experimental approach
of attempting to re-evolve images that were already once evolved
on Picbreeder. In effect, images that were originally discovered
serendipitously become a priori objectives for a new experiment
with the same algorithm. Therefore, the resulting failure to repro-
duce the very same results cannot be blamed on the evolutionary
algorithm, setting the stage for a contemplation of the price we pay
for evaluating our algorithms only for their ability to achieve pre-
conceived objectives.
).