Symbiosis as a metaphor for Hierarchical Policy Search in Genetic Programming:

One of the early developments in (biological) evolution resulted in the transition from prokaryotes to eukaryotes. At the centre of symbiosis lies the ability of organisms (bacteria) to inherit material from different species of organism. Thus, for symbiosis to actually take place, the context of the inherited material -- candidate symbiont -- w.r.t. that of the `host' organism must be clearly established. Models of symbiosis therefore pay considerable attention to how host `compartments' control symbiont content.

A set of five factors appear to play a significant role in establishing frameworks for symbiosis: Spatial relation between potential symbionts; Temporal relationships between host `compartment' and candidate symbionts; Metabolic or the mechanism for communication between symbionts; Genetic or the process by which alignment of genetic material is established; and the nature of the Coevolutionary relationship, where a mutualistic relation is often assumed, but this might actually have began as an openly adversarial relation and over time became mutualistic.

Framework for Symbiotic Evolution in Genetic Programming

In order to get to this point, however, there are several general evolutionary systems concepts that need to be available to successfully support the scaling of Evolutionary Computation paradigms to real-world problem domains. Specifically, a major contributing factor to supporting diversity in (biological) evolution is the environment in which evolution takes place. Thus, as the wider `ecosystem' changes, different traits are favoured in the population of organisms. This concept also implies that the organisms are competing with each other to establish their respective niches. Natural selection will then select the appropriate survivors. From a learning system perspective this means that we have a `point' population that defines the cases against which evaluation of the candidate (host) population of organisms takes place. The interaction between point and host populations is that of a competition a.k.a competitive coevolution. From the perspective of a biological ecosystem this represents a major mechanism for speciation (in the host population) as in the definition of geographic barriers (dichopatric speciation) or the isolation of founder populations (peripatric speciation) to name but two. From a machine learning perspective, without speciation, we curtail our ability to support (automatic) problem decomposition. Without a point population we will need to evolve the host organisms over the some `complete' set of training instances -- where this is generally infeasible in practice or at least very in efficient.

From an Evolutionary Computation perspective the mechanism governing the interaction between point and host population might be as simple as stochastic sampling of states defining the world, or as complex as a pair-wise Pareto optimal policy of replacement (the later unfortunately being rather expensive computationally). The principle factor in distinguishing which policy for competitive coevolution to adopt appears to be the informativeness of the cost function expressing the relative performance of hosts relative to the test conditions defined by the point population. The more (less) informative the cost function the more (less) appropriate stochastic sampling becomes. Symbiosis operates within this general framework -- as would any model of inheritance -- with the general architecture for a single host--symbiont population as summarized by the following architecture for the case of Symbiotic-Bid Based (SBB) Genetic Programming:


In essence, symbionts are initialized with a single `atomic' action, defined a priori relative to the problem domain. Thus, under a classification contact symbiont actions are sampled from the set of class labels. This implies that a host must consist of at least two symbionts with dissimilar actions in order to provide a non-degenerate behaviour. Moreover, the symbiont actions are NOT evolved. Instead, the goal of symbionts is to evolve a program representing a bidding policy. The bidding policy establishes the context under which the symbionts' action is employed. This naturally assumes a model of coevolution between symbionts based on cooperation. At the host level, the goal is to evolve the combination of symbionts which identify a `fit' host relative to others in the host population. Given a training scenario defined by the point population -- say, exemplar for classification -- symbionts from the same host run their respective bidding algorithms. Only the host symbiont with largest bid gets to suggest their action. It is relative to this action that the cost function is evaluated.

From the perspective of the representation assumed at host and symbiont populations, individuals of the host population are merely indexing subsets of symbionts from the symbiont population under a variable length chromosome. As such the host population takes the form of a `Genetic Algorithm' that is adapted under a `breeder' style generational framework. There is no particular magic to this decision. That said, given that we are making use of fitness sharing to explicitly maintain diversity at the host population, the initial work utilized crossover as well as mutation by way of the search operators. This turned out to result in premature convergence, particularly in reinforcement style problem domains. Moreover, there is a hidden assumption in the use of crossover -- at least from the perspective of Evolutionary Computation -- whereby parents exchanging material under the crossover metaphor are assumed to be members of the same species. This is relatively easy to establish under biology. However, species identification when competitive models of coevolution such as fitness sharing are employed is a nontrivial problem. Indeed Genetic Algorithms have frequently relied on references to spatial locality to facilitate species identification or diversity (through the application of appropriate distance functions and radii). However, no such concept of distance exists here. Thus, since 2010 we have concentrated on asexual reproduction, thus replying on several forms of mutation as our search operator.

In the case of the symbiont population, the population itself is not of a fixed size. Specifically, symbionts `die' when they are no longer indexed by individuals from the host population. Variation in the symbiont population is achieved through the action of the mutation operator at the host, care of the breeding cycle. Thus, each generation will result in a fixed number of hosts being replaced by new hosts. The hierarchical relationship between host and symbiont populations results in a variable number of symbionts dying/ being borne.

Under classification domains the host-symbiont metaphor appears to be particularly effective at providing simple solutions that decompose the overall problem with very low attribute support/ program complexity.