Algebraic Signatures and GEP

I've been thinking about what structure describes the expressions evolved by evolutionary algorithms like GP and GEP for a while, and it looks like algebraic signatures fit the requirements very well. Certainly we can describe a grammar and say we are evolving words in the language generated by the grammar, but that isn't really satisfying (to me). In this post I'm going to go over them again (I describe them in a previous post as well) and show that they are a very natural structure to describe the expressions evolved by genetic programs.

So, what is a signature? A signature consists of a set of types (possibly generated by a grammar) as well as a collection of function symbols and relation symbols. The function and relation symbols each have an arity (the number of arguments they take (although for now we are thinking of this as a purely syntactic system)) as well as an ordering, which says which arguments are of what type. If the arity for a function symbol is 0 than it is a constant, which allows us to specify elements of a type (a constant that has a type is an element of that type).

A signature together with a set of axioms gives a theory. This allows us to describe some theory in math (the theory of Groups, the theory of Monoids, the theory of Categories, etc) as a mathematical object. The models of the theory (the mathematical objects that embody the elements and rules of the theory) are the actual groups, monoid, categories, etc.

If a signature has only relation symbol it will give a relational theory, and if it has only functional symbols it will give an algebraic theory, which is what we are concerned with in this post. If the terms generated from the types and the function symbols can have abstractions then the theory is functional (in the terminology used in "Categories for Types").

If we take an algebraic theory with one type than the terms consist of fixed arity functional taking all arguments of one type and returning something of the same type. This fulfill the closure property for GEP (all function involve only one type). If the axioms are also provided we might be able to automate the evaluation of the expressions by reductions given by the axioms. This would mean that using GEP (or more specifically RGEP) would involve specifying the theory that we are interested in, and perhaps an interpretation of the theory in order to map the resulting expression to an object (which we can then determine the fitness of).

More generally, in Genetic Programming we may have multiple types and more complex functions, but it seems like algebraic theories will cover them. I would love if this allowed a more systematic treatment of what goes on with Genetic Programming, as I find that AI can be a little ad hoc at times compared to my other interests in category theory, type theory, and functional programming.