A Study of Fitness Gains in Evolving Finite State Machines

Understanding the relationship between selection function and adaptive performance benefits from simplified models, such as the constructs of automata theory. For the levels of automata from Finite State Machines (FSMs) up to deterministic Turing Machines, successful evolution to recognise formal languages has been reported [5].

Finite State Machines (FSMs, also known as deterministic finite automata or DFAs) are one of the simplest such classes of entities. They have several advantages as a model of study:

• •

  They are simple in concept;

• •

  their structure can be communicated using clear diagrams (for low numbers of states);

• •

  their complexity can be measured unambiguously; and

• •

  measures of how well an FSM recognises a regular language provide readily comprehensible fitness metrics.

For these reasons, FSMs have been a viable research tool in constructing simplified analogies reflecting aspects of biological evolution. For example, Rasek et al. [6] have proposed a definition of FSM-species and studied their formation. In another study, Moran and Pollack [7] have created simple ecosystem models of lineages of FSMs interacting in competitive and cooperative modes. They found that some results exhibit indications of open-endedness, i.e. the absence of an apparent upper bound to evolving complexity.

However, seemingly unbounded increases in complexity of evolving computational entities is the exception, rather than the rule. The review of the literature by Packard et al. [8] states the realisation that evolutionary simulations and genetic algorithms tend to approach plateaus of complexity. In other words, the complexity of evolved solutions to a problem posed tends to level out as generations succeed each other. Most commonly, a state is reached where few novel solutions of higher complexity are generated by such algorithms.

On the one hand, the literature documents plateaus of evolution under fixed selection parameters. On the other, there are examples of (at least an impression of) open-endedness with more complex regimes such as co-evolution of three or more interacting lineages. This suggests a need for better understanding of the influence of the selection regime on the evolution of FSMs, especially in the case of several simultaneous selection pressures.

In order to investigate this, we constructed an experimental setup using two simple selection pressures acting in opposite directions:

• •

  maximise the correct recognition of strings in or out of a language, and

• •

  minimise the number of states in the FSMs.

We use this setup to study the effect of an aspect of selection on fitness gain.

A good metric for the complexity of regular languages is their ”state complexity” [9]. Unlike other proposed measures (see [10]), state complexity relates directly to the resources needed for recognition. The family of languages used in this study has one language for each state complexity value. This provides control over the selection pressure promoting the addition of states over generations.

The remainder of the paper is organised as follows: Section 2 provides definitions for the key concepts we have combined in our study, and the way these experiments have applied these ideas. Section 3 presents the algorithms for creation of sample sets, managing the process of evolution, and the mutation operator. Section 4 describes our experiments and their results. Section 5 includes discussion and interpretation of the results. Finally, section 6 presents our conclusions and proposes future work.

A Finite State Machine is a 5-tuple $(Q,\Sigma,\delta,q_{0},F)$, where

• •

  $Q$ is a set of states;

• •

  $\Sigma$ is a set of symbols used as an input alphabet;

• •

  $\delta:Q\times\Sigma\rightarrow Q$ is a transition function from one state to another depending on the next input symbol;

• •

  $q_{0}$ is the starting state; and

• •

  $F\subseteq Q$ is the subset of accepting states

The transition function $\delta$ can be extended to describe what state the machine transitions to if given each symbol of a string in succession. Using $\epsilon$ for the empty string, and $cs$ to denote the symbol $c$ followed by the trailing sub-string $s$, we can define the extended transition function $\hat{\delta}:Q\times\Sigma^{\ast}\rightarrow Q$:

An FSM ”accepts” a string $s$ if the extended transition function maps it from the starting state to an accepting state, i.e. the following is true:

The set of strings accepted by an FSM is termed its language; the machine is said to ”recognise” the language. For a machine $\mathcal{M}=(Q,\Sigma,\delta,q_{0},F)$, we define its language $L_{\mathcal{M}}$ as:

The languages recognisable by FSMs are the ”regular” languages, i.e. those that can be described by a regular expression [11]. Each regular language is recognised by a set of FSMs which are equivalent in that for any string, each of them produces the same result of acceptance or rejection. The lowest number of states of any FSM recognising a regular language is termed the ”state complexity” of the language, as explained by Yu [9]. For an algorithm to compute the state complexity from any equivalent FSM, see [12].

To be able to run experiments with a range of language complexities, we looked for a family of languages that differed primarily in their complexity only, and preferably only included one member language for each state complexity value. Both or these criteria are met by the ”universal witness” languages described by Brzozowski [13], which we use here. This is a family (or ”stream”) of languages $U_{n}$, which has one member for any $n<=3$, which are examples (”witnesses”) of the upper bounds of state complexity in a number of theorems concerning the complexity of FSMs. In particular, it has the property that $U_{n}$ cannot be recognised by an FSM of less than $n$ states.

Each of the $U_{n}$ languages has a corresponding FSM $\mathcal{U}_{n}$ that accepts it. The general structure of these FSMs is shown in Figure 1. The formal definition is as follows:

The two objectives we combine in the selection applied in this study are:

1. 1.

   ”linguistic fitness” - maximising the correct classification by FSMs of strings as being in or out of a language; and

2. 2.

   minimising the number of states of the FSMs.

The first objective favours more states, as more states can embody more complex information about the target language. The second objective selects for fewer states. In this way, the two objectives counteract each other.

To quantify the fitness of an FSM as an acceptor of a language, we use its performance in accepting or rejecting strings in two sample sets, positive (strings in the language) and negative (strings not in the language).

In this study, the ”linguistic fitness” $F_{A,R}(\mathcal{M})$ of an FSM $\mathcal{M}$ against a set $A$ of strings to be accepted and a set $R$ of strings to be rejected, is the total of correctly accepted and correctly rejected examples:

The maximum value of $F_{A,R}$ for an FSM is the total size of the positive and negative reference sets $A$ and $R$. The fitness gains we study are specifically the increases of this linguistic fitness over time.

A genetic algorithm selecting for multiple objectives needs to decide which of a set of candidates to favour in the reproductive pool, based on how well they satisfy each of the objectives. As described by Neumann [14], this can be expressed in a ”dominance” relationship combining the two objectives.

In this study, we combine the objectives of maximisation of fitness and minimisation of states. The former is measured by a function $F_{A,R}$ ($A$ and $R$ being the positive and negative sample sets), the latter by the number of states, $C$.

This paper uses the two relations ”weakly dominates” (denoted by the symbol $\succcurlyeq$) and ”dominates” (denoted by $\succ$) between FSMs X and Y:

Informally, X weakly dominates Y if it is no worse than Y on either fitness or complexity, and X dominates Y if it is no worse on either fitness or number of states, but better on at least one of the two.

We use two methods of generating sample sets of positive and negative examples. In both methods, the positive and negative sets contain 500 strings each, for a total of 1,000 strings. The two methods labelled $Bss$ and $Rle_{n}$, are defined below.

The reason for equal numbers of positive and negative examples (regardless of the percentage of strings of a given length that are in versus out of the language) is technical. An FSM of a single state can either accept all strings or rejects all strings. Its fitness score therefore would be the number of positive and negative samples respectively, but its complexity is the same in either case. Using the same number of positive and negative examples provides a common baseline of performance for minimal complexity.

The study of complexity in multi-objective genetic programming by Neumann [14] describes the SMO-GP algorithm (Simple Multi-Objective Genetic Programming). It starts with a population of one individual. In each iteration, SMO-GP selects one member of the population, applies a mutation operation, and then either replaces all dominated individuals with the (single) new mutant, or drops the mutant if it does not dominate any existing members.

For this study, we adapted this algorithm is adapted to evolve FSMs starting with the simplest possible FSM, which we call $\mathcal{N}$, see Algorithm 3. $\mathcal{N}$ is an FSM of a single non-accepting state, with the transition function mapping all inputs back to that state. This is in a sense the simplest possible FSM, and corresponds to the empty language, as it rejects all strings. (An FSM accepting all strings, i.e. accepting $\ast{\Sigma}$, would be equally simple.) The formal definition of such an FSM for a ternary alphabet is:

Note that half the 1,000 sample strings will not be elements of the language, so the FSM $\mathcal{N}$ by rejecting them will achieve a linguistic fitness score of 500. The only way for a new mutant to enter the population is to weakly dominate an existing FSM in the population. This can come about by having higher fitness or fewer states, but no FSM can have less states than $\mathcal{N}$. Therefore, all other FSMs that will become part of the population will score at least 500.

In some preliminary work, we also experimented with starting evolution towards $U_{n}$ not with $\mathcal{N}$, but instead with the result of evoluition over a set number of generations toward $U_{n-1}$. This approach did not produce any notable patterns correlating the starting point with improved speed of adaptation to higher fitness, and we did not pursue it further.

The mutation operation used on FSMs selects one random state for the source of an arc, and a random input symbol from the alphabet for the label of the arc. A target state is then selected; half the time, this is an existing state of the FSM, otherwise it is a new state which has all outgoing arcs leading back to itself.

The FSM is then modified so that the arc from the source state, labelled with the chosen input symbol, is set to lead to the chosen target state.

Lastly, a random state is chosen and changed from accepting to non-accepting and vice versa. For details, see Algorithm 4.