Evolution of control with learning classifier systems

Abstract

In this paper we describe the application of a learning classifier system (LCS) variant known as the eXtended classifier system (XCS) to evolve a set of 'control rules' for a number of Boolean network instances. We show that (1) it is possible to take the system to an attractor, from any given state, by applying a set of 'control rules' consisting of ternary conditions strings (i.e. each condition component in the rule has three possible states; 0, 1 or #) with associated bit-flip actions, and (2) that it is possible to discover such rules using an evolutionary approach via the application of a learning classifier system. The proposed approach builds on learning (reinforcement learning) and discovery (a genetic algorithm) and therefore the series of interventions for controlling the network are determined but are not fixed. System control rules evolve in such a way that they mirror both the structure and dynamics of the system, without having 'direct' access to either.

Keywords: Boolean network; Complex systems; Controllability; Discovery; Intervention; LCS; Learning; XCS.

Fig. 1

A simple example of rule matching with two rules with ternary (three state) condition components and one binary environmental state. Adapted from (Matthew R Karlsen and Sotiris Moschoyiannis: Learning condition action rules for personalised journey recommendations, forthcoming)

Fig. 2

A simple Boolean network

Fig. 3

State space of the simple Boolean network with all nodes using the AND logic function

Fig. 4

State space of the simple Boolean network with all nodes using the XOR logic function

Fig. 5

Structure of an XCS classifier system. Based on (Wilson 1998) and originally shown in (Matthew R Karlsen and Sotiris Moschoyiannis: Learning condition action rules for personalised journey recommendations, forthcoming)

Fig. 6

A chart showing the relationship between a classifier’s error and its accuracy for the XCS classifier accuracy function. Accuracy is defined as: α(ε_j/ε₀)^−ν where ε_j is the error of classifier j. This chart is based on that presented by Butz et al. Fig. 1 (Butz et al. 2001)

Fig. 7

NK Boolean network, instantiation 1 (N=5,K=2)

Fig. 8

NK Boolean network, instantiation 2 (N=5,K=2)

Fig. 9

NK Boolean network, instantiation 3 (N=5,K=2)

Fig. 10

NK Boolean network, instantiation 4 (N=5,K=2)

Fig. 11

An example control graph for NK Boolean Network 4 using an evolved rule set

Fig. 12

NK Boolean network, instantiation 6 (N=5,K=2)