What is grammatical evolution + easy implementation

Most recently, I wrote an article in which, without explanation, I showed what the method of grammatical evolution is capable of. I fully agree that it is impossible to do this, but as I wanted to show the results of an interesting method. I thought "what would be better: translate the source or give my own explanation." Laziness got the better.

If someone is interested in evolutionary methods and the task of symbolic regression (and not only), then I ask you to read.

Backusa Naur Form

First you need to say what context-independent grammar is in the form of Backus-Naur (abbreviated BNF). About formal languages ​​and grammars on Habré there is already quite interesting article . I highly recommend reading. But our goal is to understand what the BNF is and learn how to use this form.
')
Wikipedia gives a completely adequate definition:

BNF is a formal syntax description system in which certain syntactic categories are sequentially defined through other categories. BNF is used to describe context-free formal grammars.

BNF has terminal and non-terminal symbols. Terminals - constants. We set them up and that's it, but with non-terminal symbols everything is much more interesting: they can be substituted into each other by the rules.

Consider an example. We have the following formal system for describing the syntax of context-free grammar:





In our example, many non-terminal characters


And the set of terminal symbols is represented as


The set S will contain one element.


This element will be the entry point for building and working with rules.

Now, having one non-terminal element, we can make constructions that will correspond to our grammar.

Watching the chains

1) <sntnce> => <adverb> <verb> => quickly <verb> => quickly ran

2) <sntnce> => <noun> <verb> => Peter <verb> => Peter fell

The question arises: on what basis do these substitutions occur? I will answer this question a little later.

Genetic algorithm

It seems to me that this algorithm is canonical in evolutionary circles. It is simple to implement and works well. Consideration of this algorithm is necessary in order to understand what the mechanism will be as a “engine” for the method of grammatical evolution. But (!!) in its place can be any other, convenient for you, evolutionary algorithm.

So, GA uses the behavior of nature. In fact, nothing new was invented. This algorithm has been running for millions of years. Thanks to him. After all, if not for him, then we would not be.

GA consists of several stages.

(1) Creating an initial population (creating a chromosome for each individual)

(2) Calculating the fitness function of each individual (it is this that shows who is best suited in a given population)

(3) Selection of the best representatives for the education of further offspring.

(4) Crossover

(5) Mutation

(6) After (4) we get children, some of which go through (5). At the exit we get offspring

(7) The selection of fathers and children in the new generation

(8) return to step (2) if the values ​​given by the children do not suit us

Chromosome is a coded representation of the information we need. In the source uses a binary representation. Those. if we need to find 4 parameters (each of them in the range from 0 to 15), then each parameter will require 4 bits (zero or one). And the chromosome itself will be 16. Everything is pretty primitive.

Important : you can use the decimal representation. I will do so for grammatical evolution.

Now a little about the operators in the GA and all sorts of fitness functions.

Fitness function - the functionality that we need to optimize. It varies from task to task. If there is a question in minimizing the functional, then for selection parents are needed who possess as little fitness function as possible.

The crossover is a cool thing. In genetic programming, by the way, this operator is almost the only one to produce offspring with the best qualities. The bottom line is that we take two parents (or rather their genotype). Divide it in half. And change places. I'll show you now.

There are two lists:






This was an example of a point crossover. There are other variations on this topic, but we will not discuss them.

Mutation is the process of accidentally replacing one or another gene.



Frequently used method of selection in the new generation is elite. We simply take the n best individuals from the list of children + parents. And then we supplement the population randomly to the desired amount.

Important: the size of the chromosome can be both fixed and arbitrary. The same applies to the size of the population.

Grammatical evolution

And now about the most important thing. What kind of method is it and what is it eaten with.
The very essence is that you have a task that needs to be solved. You build grammar in the form of Backus-Naur. Create an initial population in which each individual will have his chromosome, describing what rules when, where, to substitute. The importance lies in the fact that thanks to these rules you get a function that you can use for calculations. The value of this function with parameters set in advance by it (or not) can act as a functional (fitness function). The better the functional, the better the function, and hence the individual with his chromosome.

More about the chromosome.

Suppose we have the following grammar

<e> :: = <e> <op> <e> | <val>

<val> :: = x | 3 | 2

<op> :: = + | - | * | /

Next we have this chromosome


Initially, the symbolic representation of the function contains one non-terminal symbol: H = <e> (as a rule).

We take the first element from chromo: 2. We count how many rules are in the transformations in <e>: 2. Divide 2% 2 (modulo !!) = 0. So, instead of <e>, we substitute <e> <op> <e>. Thus H = <e> <op> <e>. Two from chromo throwing out. She is no longer needed.

The next step is one. and look again at <e>. 1% 2 (the number of substitution rules) = 1. So instead of <e> we substitute <val>. We get H = <val> <op> <e>.

If you make these simple manipulations further, you get such a chain






Next, we use this function to calculate the functionality and determine how much an individual with this phenotypic (so called function) and genotype (chromosome) suits us.

It's all. Yes, there are several substitution options: in depth (considered), in width, the so-called - substitution. But this is material for a separate article.

And now an example.

There is a time interval . There is a function . It is necessary to find a function that would give the minimal quadratic error - the functional of the given problem.

Look at the code

main module

# -*- coding: utf-8 -*- import GE def foo(x): return 1+x+x**2+x**3 interval = [-5, 5] values =[foo(e) for e in range(interval[0], interval[1])] if __name__ == "__main__": result = GE.GA( chromo_len=12, pop_len=100, count=20 )[0] print(result) 

The foo function generates values ​​that we will compare with those that will be obtained from the functions created by each individual.

Chromosome length = 15;

Population length = 100;

The number of iterations (evolution) = 20;

Parser module

 # -*- coding: utf-8 -*- import random import re def rand(num): return int(random.random()*num) def parse(chromo): l = len(chromo) j = 0 h = "<expr>" grammar = { "<expr>": ["<expr><op><expr>", "<val>"], "<op>": ["+", "-", "*", "/"], "<val>": ["x", "1"] } s = r"<+["+('|'.join(list(map(lambda x: x[1:-1], grammar.keys()))))+"]+>" pattern = re.compile(s) while j < l: elems = pattern.findall(h) if not elems: break el = elems[0] h = h.replace(el, grammar[el][(chromo[j] % int(len(grammar[el])))], 1) j += 1 while True: elems = pattern.findall(h) if elems: for elem in elems: el = elem if elem == "<expr>": el = "<val>" h = h.replace(elem, grammar[el][rand(len(grammar[el]))], 1) else: break return h 

The grammar dictionary contains rules for grammar. Further, the substitution algorithm, which I described above. After the while block is needed to complete the function. There are cases when the chromosome is over, and non-terminal characters remain. Here is the last cycle and is needed in order to replace all non-terminals with terminals.
Important : not the fact that the final function will turn out to be valid from the point of view of semantics (it can divide by zero and all that).


GE module

 # -*- coding: utf-8 -*- import random import math from parser import parse def rand(num): return int(random.random() * num) class Individ: def __init__(self, genotype): self.genotype = genotype self.phenotype = self.get_phenotype() self.fitness = self.get_mistake() def __eq__(self, other): return self.fitness == other.fitness def __ne__(self, other): return not self.__eq__(other) def __lt__(self, other): return self.fitness < other.fitness def __ge__(self, other): return not self.__lt__(other) def __str__(self): return "chromosome : {0}\nphenotype = {2}\nfitness = {1}\n".format(self.genotype, self.fitness, self.phenotype) def get_phenotype(self): return parse(self.genotype) def get_mistake(self): import main intr = main.interval vals = main.values f = eval("lambda x: {0}".format(self.phenotype)) f_vals = [] for i in range(intr[0], intr[1]): try: f_vals.append(f(i)) except: return 10000 return sum(list(map(lambda e: (e[0] - e[1]) ** 2, list(zip(vals, f_vals))))) def GA(chromo_len, pop_len, count): population = get_population(pop_len, chromo_len) while count > 0: childrn_chromos = get_children_chromose(population) mutation(childrn_chromos, 0.8) children = get_children(childrn_chromos) population = get_new_population(population, children) count -= 1 return population def get_genotype(gen_length): return [rand(200) for _ in range(gen_length)] def get_population(length, chromo_len): return [Individ(get_genotype(chromo_len)) for _ in range(length)] def get_children_chromose(parents): def tournament(): return [min([parents[rand(len(parents)-1)] for _1 in range(7)]) for _2 in range(2)] children_chromo = [] for _3 in range(int(len(parents)/2)): children_chromo += crossover(tournament()) return children_chromo def get_children(childrn_chromos): return [Individ(childrn_chromos[i]) for i in range(len(childrn_chromos))] def crossover(pair): p1 = pair[0] p2 = pair[1] d = random.randint(1, len(p1.genotype) - 2) return [p1.genotype[:d] + p2.genotype[d:], p2.genotype[:d] + p1.genotype[d:]] def mutation(chldrn_chromo, p): for j in range(len(chldrn_chromo)): if p > random.random(): i = random.randint(1, len(chldrn_chromo[j]) - 1) chldrn_chromo[j][i] = rand(200) return chldrn_chromo def get_new_population(population, children): l = len(population) buf = population+children buf.sort() c = math.trunc(0.2*l) new_population = buf[:c] tmp = buf[c:] ll = len(tmp) new_population += [tmp[random.randint(1, ll - 1)] for _ in range(c, l)] return new_population 

The usual implementation of the genetic algorithm.

The GA function is the entry point to the evolutionary cycle.

In general, the functions speak for themselves, and the implementation of each function is not very long. I note that the selection for the crossover is not standard. I just bother my parents and choose the first half of the mixed pile. For this task it is not very harmful, but it is better not to do so. There are a dozen (or even more) methods that allow you to select the best candidates for the crossover.

Each individual has three fields: genotype, phenotype, value of fitness function.

Eventually

getting function



which is identical



I note that the creation of an optimal grammar is not a trivial and very important task.

I hope it has now become clear what kind of “grammatical evolution” is for the method, and how to use it to solve problems. An interesting fact is that symbolic regression is applicable not only for functions. We can create instructions for robots, as well as build the structure of the neural network and adjust the parameters in it. We do not need a back propagation method for learning the network. Along with it, you can refuse from the functions of activations with a continuous first derivative. This is the so-called "neuroevolution programming".

Once again I give a link to the source . If anyone wants to further understand the method.