anatomy - morinim/vita GitHub Wiki

Please note that this document is a Work-in-Progress

Abstract. This paper presents an extended specification for Vita evolutionary framework. Architectural choices will be detailed and their conceptual significance underlined. Implementation detail issues will be discussed.

Introduction

Architecture

Vita implements an object oriented layered architecture, built on the base of five classes:

  • problem;
  • search and evolution;
  • population and individual.

High level class diagram

The goal of a layered architecture is to neatly divide base concepts, such as the internal structure of individuals, from higher level concepts, more directly relating to the evolutionary method.

Here is the skeleton of a program using the Vita framework:

vita::src_search s(problem_instance);
s.run();

The vita::problem class holds the objectives, functions and data necessary to define and solve a particular task. A developer can:

  • use the basic implementation (e.g. that's enough for vita::ga_search);
  • specify his own implementation (via inheritance);
  • use a predefined specialized class (e.g. vita::src_problem for symbolic regression and classification problems).

The search of a solution is driven entirely by a specialization of the master vita::search class, that uses problem to access data and specific parameters/constraints.

Since Vita is a genetic programming framework, vita::search performs its task with the help of the vita::evolution and vita::population classes.

Evolution

Evolution flow

This diagram really simplifies the evolution process. The goal is to evolve successively better individuals with every generation.

We begin our run by generating the initial population (vita::population).

Then we enter the genetic programming loop, choosing a genetic operation and the individual(s) to participate in the genetic operation (vita::selection::strategy and vita::recombination::strategy).

The offspring can eventually replace (vita::replacement::strategy) other individual(s) of the population (steady state population).

Evolution class diagram

We repeat this process of selecting, copying and modifying until the termination criteria is satisfied.

With any luck, this process will produce an individual that solves the problem at hand.

Population

The population is organized in a 1-dimensional spatial structure, a circle, where the first and last locations are considered adjacent (see "Trivial Geography in Genetic" - Spector L., Klein J. - 2005).

Population layer

Population

Individual

Genome

Symbol

GP assembles variable length program structures from basic units called functions and terminals. Functions perform operations on their inputs, which are either terminals or output from other functions. Together functions and terminals are referred to as symbols.

In Vita symbol is an abstract class, leaving to terminal and function classes the specification of many details.

If you take a look at the implementation you'll see many pure virtual methods like arity():

virtual unsigned arity() const = 0

We could avoid the virtual interface storing additional information inside symbol, e.g.:

unsigned arity() const { return arity_; }

where the arity_ variable is an example of such additional information.

In theory the current approach should be:

  • slower (virtual methods), but we cannot measure performance differences;
  • more memory efficient, but this isn't important considering that we manage not so much symbols.

So the key point in favour of the virtual interface is that it enforces correctness (for some insight about the virtual interface choice see c++ Storing type of the object, what choice is better?).

The class only partially adheres to the NVI pattern (i.e.. penalty function) since the added flexibility wouldn't compensate the additional complexity.

Other readings