pyroFAERY: simulated robot optimization using Family Aware EvolutionaRY (FAERY) Algorithms and pyrosim

Family Aware EvolutionaRY (FAERY) algorithms provide a method of optimizing phenotypic fitness through a genetic algorithm while maintaining diversity within the population.

To run, clone and run python search.py in the terminal.

Currently, I am developing more FAERY algorithms to find better genetic algorithm optimization schemes.

Motivation

Local optima are frequently problems in optimization searches since there is often no way to determine if a given configuration at an optimum reaches a local or global optimum. To combat the while local optima are often unavoidable, maintaining diversity within the configuration population allows new designs to evolve and potentially reach other local optima or even the global optimum.

Towards this goal, here I present Family Aware EvolutionaRY (FAERY) algorithms, a set of genetic algorithms aimed at balancing optimization and diversity preservation. FAERY algorithms are a set of genetic algorithms that attempt to achieve diversity by remembering the lineages of individual configurations and restricting the number of children that are passed on to the next generation from each lineage. FAERY algorithms produce children by in some way mixing the genomes of parents and then mutating the child genomes to some degree. Ideally, through this process of maintaining diversity while optimizing, promising genetic lines are retained and mixed as the optimization process progresses while poorly performing lines are dropped. Additionally, randomly generated members are added to each generation of the FAERY algorithms to insert new genomes into the population.

Simulated robot evolution

Two FAERY algorithms were used to optimize the design of a simulated robot's neural network weights using pyrosim as part of the ludobots online course.

This courses uses the pyrosim library for simulating virtual robots. Hence, future development on these FAERY algorithms is being done under the name pyroFAERY.

Robot design

For the optimization, a simple quadrupedal robot was designed.

The robot's neural network consisted of a set of sensor neurons on the feet of the robot and a set of motor neurons at each joint telling the motor to which angle to turn. Additionally, a sinusoidally modulated sensation was input to the robot by overwriting the robot's torso's sensor neurons reading with a sine function, modelling the working of central pattern generators CPGs in biological nervous systems.

Optimization algorithm 1: pyroFAE1/ludoFAE1

pyroFAE1 belongs to the classifications of partial mating and gene averaging FAERY algorithms.

As a partial mating FAERY algorithm, each member in a generation is only mated to a subset of the members in the generation for producing children. In the case of pyroFAE1, this mating is chosen at random. Each member of each generation in pyroFAE1 is randomly mated to a user-defined number of randomly chosen members. There is an equally likely chance of the match being with any member of the generation.

As a gene averaging algorithm, pyroFAE1 produces child genomes by averaging the genomes of the parents in a match. The average is computed as a randomly weighted average between the two parent genomes. The formula for a child gene can be written as gci = pi * gp1i + (1-pi) * gp2i where

• gci is gene i in the child genome,
• gp1i is gene i in the first parent's genome,
• gp2i is gene i in the second parent's genome, and
• pi is the randomly chosen weighting for gene i.

After this gene averaging, pyroFAE1 mutated a single random gene by a random amount as directed by user-provided mutation rate and mutation magnitude specifications.

Optimization algorithm 2: pyroFAE2/ludoFAE2

pyroFAE2, like pyroFAE1 is a gene averaging algorithm using the same method of child gene production as pyroFAE1. However, pyroFAE2 is a full mating algorithm. Therefore, in pyroFAE2, every individual in a generation is mated with every other individual in the generation, including itself.

Optimization algorithm 3: pyroFAE3

pyroFAE3 is an algorithm derived from pyroFAE1. It is a partial mating algorithm; however, it uses a different method of combining parent genomes to produce offspring.

pyroFAE3 uses a beta distribution with parameters a=0.8, b=0.2 to obtain the weights of each parent's genes to be passed on. This has two effects.

1. It results in child genomes that are not averages of parent genes values but are rather dominated by one parent's gene.
2. It increases the weight of parent 1's genome, the parent who passes on their family name to the child, over the weight of parent 2's genome.

Optimization results

Running pyroFAE1 and pyroFAE2 with the specifications found here demonstrated that both algorithms were capable of optimizing a simulated robot to achieve a desired goal.

The above video demonstrates the pyroFAE2 algorithm; the pyroFAE1 algorithm produced similar results. Statistical analysis would be required to evaluate which algorithm performs better.

Future work

Future work on the FAERY algorithms includes:

• statistical analysis comparing FAERY algorithms and other optimization schemes
• the creation of more FAERY algorithms, including weighted partial mating FAERY algorithms
• the use of FAERY algorithms to optimize other objectives besides simple simulated robot neural network designs.

Special thanks to

• ludobots online course by Dr. Josh Bongard
• Artificial Life @ Northwestern University taught by Dr. Sam Kriegman