In this post, we will be diving into the world of context-free grammars to use in evolutionary algorithms.

What is context-free grammar?

Context-free grammar, also known as CFG, is a specific type of grammar used in computer science and linguistics. It is a set of production rules that define the structure of a language. CFG is made up of four components: a finite set of nonterminal characters , a finite set of terminal characters , a relation between the two , and a start symbol .

This is what it looks like in code form:

symbols = ['S','I','T','x']
grammar = {
    'S':['I+I','I-I','I*I','I/I'],
    'I':['I+I','I-I','I*I','I/I','(I)'] + ['T']*5,
    'T':['x'],
    'x':[str(float(x)) for x in range(1,10)]
}

I used multiple instances of the symbol as a generic pointer to a terminal symbol. Using just one instance can make the nonterminal characters more likely, resulting in expressions that never end.

attribute_size = max([len(x) for x in grammar.values()])
individual = [random.randint(0,attribute_size-1) for _ in range(30)]
print(individual)

Running it results in the following output:

[6, 5, 3, 5, 1, 8, 3, 7, 9, 3, 9, 2, 6, 9, 1, 8, 3, 0, 6, 3, 4, 8, 8, 6, 8, 5, 4, 9, 7, 3]

Now we must define a method of converting this list to a string. I checked for the case that it was done, by storing the string from the loop before and seeing if it has changed. Also, note that we can disregard how large the rule numbers can be because we can use the modulo operation to index over the rules.

def express(individual, symbols, grammar):
    expression = symbols[0]
    for branch in individual:
        expression_old = expression
        for symbol in symbols:
            if symbol in expression:
                i = expression.rindex(symbol)
                rules = grammar[symbol]
                replacement = rules[branch % len(rules)]
                expression = expression[:i] + replacement + expression[i+1:]
                break
        if expression == expression_old:
            break
    return expression

Then, our individual from earlier becomes:

7.0/1.0-4.0/9.0*2.0

Evolutionary algorithms using DEAP

Evolutionary algorithms describe the class of algorithms that use simulated evolution for the purpose of optimization. Given a fixed length of attributes, individuals can “breed” with each other using crossover points. After many generations, with an optional mutation factor, we arrive at increasingly optimal populations.

DEAP is a library for Distributed Evolutionary Algorithms in Python. I used their onemax example to write the code below to maximize arithmetic operations. In this case, I only made the individual long enough to result in two numbers, so the answer should be .

Results

Full code

See full code here.