cm3020 Lecture Summaries: Topic 01

Summaries of the lectures in cm3020 Topic 01: Genetic Algorithms

Week One

1.001: Topic Intro

MYK starts with an autobiographical sketch of his interest in the topic, starting with undergraduate work in evolutionary theory and then a masters in evolutionary computation. He then did a PhD in using genetic algorithms and neural nets to understand how sounds are constructed and synthesized. He then demos the evolved creatures we’ll be building, and walks through the case study structure (repeated in the description above).

1.102: Bio-Inspired Computing

Defines bio-inspired computing (roughly), queries whether it is AI and points to the reading. Defines several key milestones in the field:

• 1950s: Cybernetics - “the science of control and communication, in the animal and the machine” - Weiner, 1948, from the Greek for steersman. Not so much about natural forms, more about function. “Co-ordination, regulation and control will be [the book’s] themes” - Ashby 1961. Cross-disciplinary field, applied to buildings, corporations etc.

• 1960s: Connectionism (neural nets!) - “The perceptron is a minimally constrained ‘neve net’ consisting of logically simplified neural elements, which has been shown to be capable of learning to discriminate and to recognize perceptual patterns”, Rosenblatt, 1960. The birth of neural networks.

• 1970s: Genetic algorithms - shows this on his summary but doesn’t discuss it, says that’s what we’ll look at in the other videos.

• 1980s: Artificial life - Talks about Barricelli’s work and points to Fogel’s history. Jumps to the 80s, “Life as it could be” (Langton, 1980s - no specific reference given), not about replicating existing life, but taking ideas from biological evolution and origins of life and thinking what it might be without biological constraints.

1.105: Summary of evolution theory

Describes three stages: 1) Population with variation and heredity; 2) Test/Selection; 3) Breeding. Defines the genotype - which encodes the range of characteristics of the individual. DNA = Nature, Environment = Nurture. Genotype is the DNA. Contrast with the phenotype, the actual individual manifest in the world. Shows a DNA sequence, describes its mapping to 21 different amino acids, which form strings that fold into proteins. The resulting creature is the phenotype. Phenotypes get tested in their environment. Fit phenotypes are more likely to survive to reproduce; the underlying genotypes provide the heredity.

1.108: Introduction to genetic algorithms.

John Holland credited with their invention in 1960s, published a book in 1975 that defined the field. Gives a definition:

[Genetic algorithms are] probabilistic search procedures designed to work on large spaces involving states that can be represented by strings. (Goldberg and Holland, Genetic Algorithms and Machine Learning, Machine Learning 3.2-3, 1988).

MYK equates the search with the selection process, the state with the phenotype, and the string representation as the genotype.

Introduces the ideas of search and state space, which are much more clearly introduced in Russell Norvig Chapter 03: Solving Problems by Searching.

Talks about how to encode a state in a binary string, with the example of an aeroplane wing with bits allocated to shape, length, and curvature. That gives us the genotype, but how do we test the phenotype? We need a simulation of the Task Environment with a measure of ‘fitness’, eg how much does the wing rise as a result of incoming wind.

Notes that this is an iterative search process, we need to do the selection stage. This can be done through roulette wheel selection, with the higher the fitness score the greater share of the wheel the genotype gets. The wheel is spun twice to produce two parents. Fittest individuals are more likely to be selected, but not guaranteed.

Now we need to do the breeding stage. We take the two parents and breed them. That involves 1) crossover where we take sections of each parent’s genotype and combine them to create a new genotype; and 2) mutation, where there’s a random chance of mutating a % of the genotype.

You go through this process multiple times to create a new population, then start again for the new generation. Repeat until targets are met.

1.110: Why Do Genetic Algorithms Work?

Introduces some issues with search in complex environments, and why genetic algorithms might do anything useful. There is a much deeper explanation in Local Search and Optimization Problems (Russell Norvig). See also their explanation of schema in Evolutionary Algorithms

Introduces the idea of hill-climbing algorithms, can get stuck in local maxima, genetic algorithms try to solve that. Defines some key terms:

Hyperplane sampling - the ability to break a solution into components and to test those components in multiple combinations with other components.

Schema theorem - compares a schema to a regex, schema theorem says that if you cut a plane through the state space by matching a schema you can then search in the hyperplane. The hyperplane covers the set of coordinates in the state space that match the schema.

Implicit parallelism - using a population model to maintain, optimise and even recombine multiple solutions at the same time. GAs allow different bloodlines to run in parallel to look for an optimal solution.

Computational parallelism - GAs lend themselves to being computed in parallel. We do this in the implementation in the topic.

1.112: Karl Sims Creatures

Intros Dawkins’ work arguing that evolution can evolve complex forms quickly from simple starting points. Demos an evolved creature running in the simulation.

Shows the directed graph data model for the creatures, with nodes and edges representing limbs and joints. Describes the neural architecture briefly, the creatures’ sensors and actuators.

Describes the different fitness functions, moving to a light, competition to get close to a ball, move distance. And how the breeding process works with the graphs.

Week Two

In 2.101 MYK gives an overview of the elements of the system we need to build and the practical work to come. He introduces the bullet library.

2.103 and 2.105: Introduction to Bullet

He walks through some basics of bullet. He explains the separation between the look of a shape and its behaviour in collision (via bounding boxes). These geometries can be separately specified.

He shows connecting to the GUI and creating a simple world with some objects:

import pybullet as p

p.connect(p.GUI)

#add a floor
floor_shape = p.createCollisionShape(p.GEOM_PLANE)
floor = p.createMultiBody(floor_shape, floor_shape)

#add a couple of boxes
box_shape = p.createCollisionShape(p.GEOM_BOX, halfExtents = [1,1,1])
box_object1 = p.createMultiBody(box_geom, box_geom)
box_object2 = p.createMultiBody(box_geom, box_geom)

#reposition correctly
p.resetBasePositionAndOrientation(box_object1, [0, -1, 2], [0, 0, 0, 1])
p.resetBasePositionAndOrientation(box_object2, [0, 1, 2], [0, 0, 0, 1])

#add gravity
p.setGravity(0, 0, -10) # x,z,y

#start running
p.setRealTimeSimulation(1)

2.107 and 2.109 URDF File Format

Introduces the Unified Robot Description Format (URDF), a document model for defining robots, including motors, limbs and joints, can reference external obj files.

Shows the pybullet data module: import pybullet_data as pd and show some standard robot files in the data.

Introduces ‘links’, which is a part of a robot (a node), and ‘joint’, which is a connection (an edge).

Introduces the skeleton of the URDF format:

<?xml version="1.0"?>
<robot name="first_robot">
    <link name="base_link">
       <!-- contents of the link element -->
    </link>
    <link name="sub_link">
       <!-- contents of the link element -->
    </link>
    <joint name="base_to_sub" type="fixed">
       <!-- contents of the joint element -->
    </joint>
</robot>

2.201 and 2.203 Movement and Control

Walks through the different types of joints. Pybullet doesn’t support all the join types from URDF, only those with 1 degree of freedom: revolute, prismatic, and fixed.

Shows how to start your robot moving with the setJointMotorControl2 method in bullet and how to inspect the joint information with getNumJoints and getJointInfo. You can either set a speed to have the joint start moving at that speed, or set a position in which case the joint will move to the position.

Week Three Lectures

3.101 starts with an overview of the ‘genetic encoding problem’ we’re tackling. First we have to decide parameters and their values that can represent a creature. Then we need to convert that into the directed graphs of Sims’ paper. Then we have to convert that into a URDF file. We need to add some kind of control that says what the motors will do over time. Then we need to load the control and the URDF schema into the environment for testing. We need to create a nice large search space for the GA to operate in.

He starts to walk through the paramterization process, which he does in more detail in the next lecture. Then he discusses the control system. We’ll simplify the Sims approach, we’re not going to have sensors, we’re just going to have signal generator controls that act over time. The signal generator will control the velocity fo the joint. We can vary the waveform, amplitude, and frequency as parameters here.

3.103 The Parameters

Introduces the idea of a developmental process, where the creature is gradually built, so that nodes may have more choices of what to connect to as the creature is built. Every new child node will have a choice of where its link connects to (param 6 below).

We develop 17 parameters as a first draft, all will have real values (likely [0,1]):

Link Parameters:

• 0. link-shape -> cylinder/box (binary value)
• 1. link-length -> [0,1]
• 2. link-radius -> [0,1]
• 3. link-recurrence -> [1,4]
• 4. link-mass -> (may assume later that there is one density so obsolete) [0,1]

Joint Parameters:

• 5. joint-type -> revolute/fixed (ignoring prismatic), binary
• 6. joint-parent -> [0, # links]
• 7. joint-axis-xyz -> [1,0,0] or [0,1,0] or [0,0,1]
• 8. joint-origin-r -> [0, 2pi]
• 9. joint-origin-p -> [0, 2pi]
• 10. joint-origin-y -> [0, 2pi]
• 11. joint-origin-x -> [0, 1]
• 12. joint-origin-y’ -> [0, 1]
• 13. joint-origin-z -> [0, 1]

Control Parameters:

• 14. control-waveform -> sine/pulse/ramp
• 15. control-amp -> [0,0.25]
• 16. control-freq -> [0,1]

3.201 introduces TDD and unit tests in Python. Nothing new from the SDD module.

3.203 and 3.205: Building the genome class and specification

MYK uses a painful version of TDD approach to writing a genome class. He defines the methods:

get_random_gene(length): returns a np.ndarray of the input length of np random floats

get_random_genome(gene_length, gene_count): returns a np.ndarray of the input size, containing random genes.

get_gene_spec(): returns a dictionary mapping parameter names to scaling factors and gene positions.

get_scaled_genome_values(): scales the raw numbers appropriately. (doesn’t get to this in the vid)

The gene spec he writes looks like this:

gene_spec = {
 "link-shape":  {"scale":1},
 "link-length": {"scale":1},
 "link-radius": {"scale":1},
 "link-recurrence": {"scale":4},
 "link-mass": {"scale":1},
 "joint-type": {"scale":1},
 "joint-parent": {"scale":1},
 "joint-axis-xyz": {"scale":1},
 "joint-origin-rpy-1": {"scale":np.pi * 2},
 "joint-origin-rpy-2": {"scale":np.pi * 2},
 "joint-origin-rpy-3": {"scale":np.pi * 2},
 "joint-origin-xyz-1": {"scale":1},
 "joint-origin-xyz-2": {"scale":1},
 "joint-origin-xyz-3": {"scale":1},
 "control-waveform": {"scale":1},
 "control-amp": {"scale":0.25},
 "control-freq": {"scale":1},
}
ind = 0
for key in gene_spec.keys():
  gene_spec[key]["ind"] = ind
  ind += 1

3.206: From flat genes to a graph.

We have two phases in the algorithm. The first phase goes from the genes to an array of ‘links’ ie nodes. The second phase will build up the connections in the graph, by expanding out the recurrence values:

Phase One: Iterate over the genes. For each gene create a link. Assign the link a unique name. Decide the parent link name. Add it to an array.

Phase Two: A recursive function that starts with a parent link, then gets its children. For each child it counts the recurrence value, then for every recurrence it adds it to the expanded array, then calls itself again, with the child as the new parent, and so on… This builds out the full graph.

3.208: Implementation

Implements a URDFLink class and a method in the genome class to expand a list of such links following the phase 2 pseudocode above.

#slightly amended implementation that adds the root node inside the method
@staticmethod
def expandLinks(parent_link, uniq_parent_name, flat_links, exp_links):
  #check if we're the root, if so we need to add it
  if parent_link.parent_name is None:
      exp_links.append(parent_link)
  children = [l for l in flat_links if l.parent_name == parent_link.name]
  for c in children:
    for r in range(c.recur):
      c_copy = copy.copy(c)
      c_copy.parent_name = uniq_parent_name
      uniq_name = c_copy.name + str(len(exp_links))
      c_copy.name = uniq_name
      exp_links.append(c_copy)
      Genome.expandLinks(c, uniq_name, flat_links, exp_links)

3.211 Genome Spec: Starts to build out the process of taking a gene and building a dictionary with the correct values, using the spec written earlier. Writes a method to take a gene list, and the spec, and returns an appropriate dict. Then does the same thing with the whole genome.

Then starts working on the developmental process, converting the genome dict into an object of the Link class.

3.213 Creature Class: Starts to work on building out the Creature class which will handle the conversion to XML (minute 6 in the vid).

Implements a set of higher level methods on the new Creature class that use the Genome class methods to create a genome and turn it into links.

3.215 to XML: Introduces an easy way to create DOM objects which can then be serialized very easily:

from xml.dom.minidom import getDOMImplementation
domimpl = getDOMImplementation()
dom = domimpl.createDocument(None, "robot", None)
geom_tag = dom.createElement("geometry")
geom_tag.setAttribute("length", "10")
weight_tag = dom.createElement("weight")
geom_tag.appendChild(w_tag)
geom_tag.toprettyxml() # serializes with pretty printing
geom_tag.toxml() # serializes without pretty printing

Builds out to_xml functions to build out links and joints and outputs them to xml. Loads first creatures into pybullet.

3.218 Fixing Geometry. Fixes the overlapping part problem where recursed links have the same physical location. Gives each link a sibling index and rotates the origin based on the index.

3.220 Adding motors: Creates a MotorType(enum) class. Our motors will have a PULSE or a SINE wave form.

Then creates a Motor class, which will have take a type, amplitude, and frequency (decided by the genome). It also has a phase so the output can be called by the simulation over time. Updates the Creature class to generate the motors.

Week Four Videos

4.101 Introduces the general plan, we’re going to have a Population class to store a bunch of creatures, and a Simulation class which will run pybullet in ‘direct’ mode to evolve the creatures quickly.

4.103 Generating the population. Implements the Population class, which just has a list of creatures for now.

4.105 Running the simulation. Creates a Simulation class to manage the simulation. Implements a run_creature method to reset the physics engine, write the input creature’s xml representation to disk, load the creature to the physics engine.

Writes an update_motors method to update the creature’s motors every 1/10th of a second.

Writes an update_position method to set the start position and last known position. Now we can track the movement of a creature over a fixed period, we can design the fitness function.

4.107 Implements a function to compute the distance travelled, then fixes some issues around the creature falling forever, or popping into the air. Suggests future developments could include amending the fitness function to take into account energy used (eg number of joints) or else some kind of competition.

4.109 Multi-process evaluation: sets up multi-threading. Creates a ThreadedSim class to run sims in parallel.

4.203 Roulette wheel: Implements a parent selector. Creates what he calls a fitmap, which is an array of elements representing a cumulative total of fitness scores, simulating the wheel segmentation. The projects a random number into that array, picking the element that it ‘lands’ on.

4.205 Crossover: Implements a Genome.crossover method that blends the two input genomes, splitting them at a cross over point. Then adds mutation methods:

• Point mutation: Genome.point_mutate(gene, rate, amount), where rate is the probability of mutation, and amount is a scale factor for the mutation.

• Shrink mutation: Genome.shrink_mutate(genes, rate), where if a random number is within the rate a random gene is removed.

• Grow mutation: Genome.grow_mutate(genes, rate), where if a random number is within the rate a gene is inserted.

4.207 The GA: Implements the GA itself in the test_ga.py file.

4.209 Elitism: Adds elitism, stores the fittest individuals in each generation and carries them through unchanged to the next generation. Changes the fitness function to depend on total distance moved, not distance from origin.

4.211 Saving the fittest: Implements the Genome.to_csv(dna, csv_file) method to store the input genome to a csv file. Implements the Genome.from_csv(file) method to parse a csv file to a genome object.

Week Five: The State of the Art

5.101: Beyond Sims Distinguishes between hard body robots - designing robots and then 3D printing them, and soft body robots - deformable body robots. Introduces Lipson and Pollack: Automatic Design where they manufactured the robots they designed through a GA.

Identifies several questions to ask of a GA paper:

• What’s the encoding scheme?

• How does the fitness function work?

  Introduces Hiller and Lipson: Automatic Design and Manufacture of Soft Robots (2012), and the idea of deformable robots. Then the new version in Cheney et al: Unshackling Evolution where a neural network is evolved to build the robot. Then Shah et al: A Soft Robot That Adapts to Environments through Shape Change (2021). Finally Lehman et al: Surprising Creativity of Digital Evolution.

5.104: Trends and Applications Introduces applications of GAs outside robotics. Introduces Miikkulainen et al: Evolving Deep Neural Networks (2017) where evolved NNs were competitive with human designed ones. Why bother? We’re reaching the limits of human design, a highly complex structure, trying different hyperparameters etc. Can we come up with more efficient designs? Complex and expensive to design them, but then more efficient to run?

Turns to evolving software in Petke et al: Genetic Improvement of Software. Finally mentions Molina et al: Evolutionary Algorithms for Global Optimization, looking at benchmarks and competitions.