GEESE: Grammatical Evolution Algorithm for Evolution of Swarm Behaviors
One of the researcher I admire on Twitter said that with every paper you publish write a blog post about it. People might not read you full paper but there are higher chances that they will read the blog post on it. So this blog post is about my paper “GEESE: Grammatical Evolution Algorithm for Evolution of Swarm Behaviors” which describes about an algorithm to automatically generate collective behaviors for swarms.
It is a notation technique to describe the syntax of language. It is represented by four tuples N, T, P and S
- N -> Represents the set of all non-terminals
- T -> Represents the set of all terminals
- P -> Represents the set of productions that map N to T
- S -> Initial start symbol
Below is the BNF grammar used for Santa Fe Trail problem.
<code> ::= <code> | <progs>
<progs> ::= <condition> | <prog2> | <prog3> |
<condition> ::= if_food_ahead(<progs>, <progs>)
<prog2> ::= prog2(<progs>, <progs>)
<prog3> ::= prog3(<progs>, <progs>, <progs>)
<op> ::= left | right | move
It is a fixed length sequence of number. It is grouped usually in 4 or 8 called codon. It defines the proceedings of left-derivation of the BNF grammar.
The figure above represents a genome of length 24 which is grouped into size of 4. Since this genome is represented by binary string, each codon can be converted into decimal value. These values are used in genotype-to-phenotype mapping.
Let c be the codon value, A denotes the left-most non-terminal in the derivation (grammar) and rA denotes the number of right-hand side rules associated with the production of A. Then the rule is
RHSRule = c % rA
The output from the mapping process is the phenotype. Phenotypes are the actual programs output. It represents a valid expansion of the BNF grammar. If we use the BNF grammar and genotype specified earlier then the phenotype would be if_food_ahead(move, left) from the mapping process. The figure below summaries the process that we discussed so far.
The the above figure we present a simple BNF grammar. The mapping process converts the genotype population to phenotype using the RHSRule specified earlier.
At first, we start with the Start symbol of the BNF grammar which is <code>. The first codon value is 3, the number of right hand side for this first rule is 2. Then using the RHSRule we get 1 from applying 3%2. So we choose last non-terminal symbol <progs>. Similarly, we move to second production rule <progs>. Similarly, following the above table, we finally get the phenotype if_food_ahead(move, left).
Above figure represents simple GE work-flow. At first, a random population based on the parameters is initialized. Then for each generation, n best individuals are selected then genetic operators are applied.
When the environment is huge, its really hard for single agents to explore and exploit the environment efficiently with a strict time constraint. When multiple agents are distributed in different spatial regions, the search for high-quality solutions can be accelerated if all the agents start in a different spatial location and interact with each other, sharing their knowledge of the search space accumulated so far. Distributed evaluation of fitness and searching different parts of the spatial domain suggest that a mult-agent GE may generate effective solutions. Traditionally, Grammatical Evolution (GE) algorithms are operated in centralized fashion. Though some variants of GE are distributed still they use the centralized population.
GEESE is inspired from “odNEAT”, a distributed and decentralized neuroevolution algorithm for online learning in groups of autonomous robots. Instead of evolving weights and network topology as of “odNEAT”, GEESE evolves executable programs based on the BNF grammar. Each agent has its own unique genetic instance and can run GE operators on its own, GEESE computation can be distributed. This algorithm has three main function: sense, act and update which are executed consecutively. During the sense step, the agents uses the sensors to gather information about the environment. If the sensors detect any neighboring agents, it will communicate with the agents to receive the genome from others. Thus, sense function will use sensor inputs to detect agents and gather genome from nearby agents. In the act step, the will check its memory to look for stored genomes. If the memory is greater than a threshold, then genetic operators like Selection, Crossover and Mutation are applied. During the update step, the current genome is replaced with the geneome with highest fitness value obtained after applying genetic operators if it exists. The overall pipeline for GEESE algorithm is shown in figure below.
We compare GEESE with variants of GE on the Santa Fe Trail problem and single source foraging problem. The graph below shows the results of GEESE and GE on Santa Fe trail problem.
Above figure demonstrates that GEESE converges to solution faster than standard GE. The solid line is the mean fitness. The shared region represents one standard deviation across the 50 trails. GEESE required fewer generations with a smaller effective population size to solve the Santa Fe Trail in comparison with Standard GE. The hit rate for GE is just 6% where as the its 57% for GEESE. One of the program evolve from GEESE was able to solve Santa Fe Trail problem in 324 steps which is fewer steps than any other known solution so far. Thus, GEESE outperforms standard GE in the Santa Fe Trail problem.
The above figure shows the performance of three different behaviors in single source foraging problem. The handcoded solution was able to collect 77 units of food where as the behavior evolved using GE was only able to collect 56 units of food. GEESE outperformed both of them by collecting 83 units of food. One of the reason for the GE to perform poorly is to the fact that the evolved program lacked communication behaviors, even though the grammar was capable of expression it.
For details, you can read the full paper at:
GEESE Paper pdf
and slides at: