Documentation:Manual:Architecture

From Beagle

This section presents the global class architecture of Open BEAGLE. The framework has a three levels architecture, as illustrated in the following Figure.

The foundations are located at the bottom, as an OO extension of the C++ language and STL. The EC generic framework is built on these foundations and is composed of features that are common to all Evolutionary Algorithms (EA). Over this generic framework, Open BEAGLE comprises different independent modules specialize this generic framework, each module implementing a specific EA. Since version 3.0.0, Open BEAGLE also integrates PACC, a collection of utilitary C++ classes. PACC also acts as a portability layer over the operating system calls for multi-threading, TCP/IP socket communications.

The discussion is divided in four parts: the naming convention, the generic object oriented framework, the generic EC framework, and the specialized frameworks.

Open BEAGLE C++ Naming Convention

All the Open BEAGLE framework has been implemented following a simple, but precise, naming convention. This naming convention is stated by the following rules.

MyIdentifier

namespace   MyNamespace;
class       MyClass;
struct      MyStruct;
typedef int MyInt;

template<class T> MyTemplateT;

enum MyEnum {eValue1, eValue2};

void MyClass::setValue(...);

class MyClass {
  int mAttribute;
};

class MyClass {
  static int smStaticAttribute;
};

void simpleMethod(int inParam1, 
                  double &ioParam2, 
                  char *outParam3);

void MyClass::simpleMethod2(...) {
  ...
  int lLocalVariable;
  ...
}

#define MyMacroM(X) (...)

namespace MyNamespace {
#define MyNamespace_MyMacroM(X) (...)
}

Portable Agile C++ Classes

NOTE: A detailed section on PACC is necessary here.

Generic OO Foundation

This section presents the generic object oriented (OO) mechanisms used in Open BEAGLE. Although these mechanisms were designed to be the foundation of Open BEAGLE, they could have been implemented in most OO frameworks. Some of our design choices are inspired from design patterns. Some concepts are also took from well-known OO environments such the C++ Standard Template Library (STL), the Java Library and CORBA.

Objects

In Open BEAGLE, most classes are derived from an abstract class called Object. An Open BEAGLE object comprises some general methods that are characteristic of a complete C++ object.

namespace Beagle {
class Object {
public:
  unsigned int getRefCounter() const; 
  virtual bool isEqual(const Object& inRightObj) const;
  virtual bool isLess(const Object& inRightObj) const;
  virtual void read(PACC::XML::ConstIterator inIter);
  Object*      refer();
  void         unrefer();
  virtual void write(PACC::XML::Streamer& ioStreamer, bool inIndent=false) const;
private:
  unsigned int mRefCounter;
};
}

The usual C++ objects comparison operators are defined, receiving arguments of the Object type and calling the appropriate comparison method (isEqual or isLess). The method read and write are used to read and write objects in the XML format. Section XML Input/Output gives more details about the Open BEAGLE I/O in XML.

An Open BEAGLE object also implements a reference counter that remembers the number of references that point to it. The C++ language defines two ways of allocating an object instance. First, the instance can be allocated on the stack, it will then be destructed at the end of the scope. Second, the instance can be allocated on the heap with a call to the new operator, which means that it is necessary to apply a symmetrical delete at the end of the instance lifetime. With Open BEAGLE, there is a variation on the second way to allocate objects: an Open BEAGLE object can be allocated on the heap and affected to Open BEAGLE smart pointers that interact with the object reference counter. The destruction of the object is then the responsibility of the smart pointers. This is the topic of the following section.

Smart Pointers

An Open BEAGLE smart pointer acts like a standard C++ pointer that manage the memory used by the pointed objects. It is implemented in class Pointer, which is tightly linked to the reference counter of class Object. The implementation of the Pointer class guarantees that the pointed object exists since there is a smart pointer that refer to it. It also guarantees that the object will be destroyed when its last reference will vanish. This emulates the appreciated garbage collection mechanism of some programming languages. In fact, the Open BEAGLE smart pointers are coherent with the creation and the garbage collecting of objects of the Java language. The two things that the user should remember are to allocate objects on the heap (with a new) and never interfere with object destruction after assigning them to smart pointers. Once an object is referred by smart pointer, the memory management responsibility is held by the smart pointer.

Exceptionally, the Pointer class and its subclasses do not inherit from superclass Object. Like a C++ pointer, an Open BEAGLE pointer can be assigned to a null pointer. The class also provides the two usual dereferencing operators, operator* and operator-><TT>, which return a reference to the pointed object. There is also two comparison operators (<TT>operator== and operator!=) between two Pointer, between a Pointer and an Object* and the null pointer testing operator (operator!). The relation between the objects and the smart pointers is presented in next Figure.

Since any instance are concrete objects and smart pointers give references to the abstract Object type, each access to methods or attributes that are not declared in the object interface needs a cast of the reference given by the smart pointer to the desired derived type. This could lead to inelegant code, or even type inconsistencies if old C-style casts were used. To avoid these problems, there is a templated class, PointerT, that defines the pointer unreferencing operators to the desired type.

template <class T, class BaseType>
class PointerT : public BaseType {
public:
  inline T& operator*();
  inline T* operator->();
};

The PointerT template also emulates the mechanism of automatic pointer type binding for inheritance-related classes. This allows a compile-time binding of T-type smart pointers that inherit from the BaseType, when a BaseType object is needed. For example, suppose a method taking an argument of the type Base::Handle, which is a smart pointer to an object instance of the class Base. With the automatic type binding of smart pointer, the method can get as argument a smart pointer to the type Derived::Handle, supposing that the class Derived inherits from the class Base. This can be done without any explicit cast of the smart pointers. PointerT has two templated parameters: the type of object handled, the T-type, and the parent type of the smart pointer, the BaseType. The BaseType is useful for the automatic type binding emulation by inheritance.

For each class of Open BEAGLE, the nested type Handle is declared. This is the type of handle to the class, that is, a smart pointer that gives exact reference type. Usually, this type is simply declared as a synonym of a parametrized PointerT.

class AnyClass : public SuperClass {
public:
  typedef PointerT<AnyClass,SuperClass::Handle> Handle;
  ...
};

Doing so, a smart pointer can be used to return reference to the right type, the type AnyClass, simply by working with the right handle type, AnyClass::Handle. It is a good practice to define the nested Handle type for every class that inherits directly or indirectly from an Object.

Allocators

Open BEAGLE is characterized by great versatility. This is achieved by different features and design choices, the first being an abstract object superclass that gives some essential generic mechanisms and from which almost every other Open BEAGLE class is derived. Another important design choice that gives flexibility to Open BEAGLE is the allocators, a kind of object factory that generates objects in an abstract fashion. An abstract allocator class named Allocator is implemented to define the methods to create objects on the heap.

class Allocator : public Object {
public:
  virtual Object* allocate() const =0;
  virtual Object* clone(const Object&) const =0;
  virtual void    copy(Object&, const Object&) const =0;
};

The purpose of the allocators is to provide factory methods to create and clone new types of objects derived from Open BEAGLE constituents. With such mechanism, any user could create new type of objects that redefine the default one and use associated allocators that return pointers to this new type of objects. This mechanism is similar and coherent with the Factory Method design pattern.

Usually, an allocator is used to allocate objects through their default constructor and clones the objects by calling their copy constructor. An allocator can also copy an existing object of a given type into an other. To simplify the task, a simple standard parametrized allocator named AllocatorT is defined to override the virtual method of the abstract class Allocator. Like the smart pointers Handle type, each component of Open BEAGLE has a nested allocator type called Alloc. The users are encouraged to define it in their classes.

class AnyClass : public SuperClass {
public:
  typedef PointerT<AnyClass,SuperClass::Handle>  Handle;
  typedef AllocatorT<AnyClass,SuperClass::Alloc> Alloc;
};

However, the template AllocatorT cannot be used to define an Alloc type for an abstract type. The reason is that the method allocate and clone cannot be implemented to instantiate object of the abstract allocated type. To solve this problem, another templated allocator type is implemented, AbstractAllocT. This allocator does not define the methods allocate and clone, but is usable in the same way than AllocatorT as an allocator type for abstract types.

Data Structures

It is natural to design data structures that take advantage of all the mechanisms exposed in the current section. Working with the new features of the C++, it is essential to exploit the Standard Template Library (STL) which provides common, well known and portable data structures and algorithms. An Open BEAGLE specific, but STL compliant, data structures is extensively used: the container.

The Open BEAGLE container is a random access table of heterogeneous objects. It is implemented as a dynamic array of specified smart pointers. Any objects that is a specialization of the contained type could be put in a container. The constraints are the same as those of the smart pointers: the objects must be allocated on the heap (via the new operator) and these objects must not be unallocated explicitly (i.e. delete of the objects are forbidden). Our container is implemented as a Beagle object that is also a STL vector of object handles.

 class Container : public Object, public std::vector<Object::Handle> { ... };

Built this way, our container could be manipulated by the STL generic algorithms. It is also possible to make container of containers, since a container is an object that can be smart pointed.

A drawback of this data structure is that every contained objects must have been allocated (on the heap) and thereafter inserted into the container. Knowing so, we add an allocator handle member attribute to the class Container. This member automatically allocates instance of objects when resizing. If no allocator are given to a container (the member value of the allocator handle is null), resizing will simply resizes the vector of smart pointer and the newly added pointers are initialized to the null value. It is then possible to dynamically type containers by giving them allocator instances of the desired type.

As with the smart pointers and allocators, every Open BEAGLE type has a nested type that define a container of the specified type, the nested type named Bag. For example, the type that is a container of floating-point values, Float, is the type Float::Bag. The nested type is declared in classes as usual for the nested types Handle and Alloc, using a typedef to a template, in this case to template class ContainerT.

class MyClass : public SuperClass {
public:
  typedef AllocatorT<MyClass,SuperClass::Alloc> Alloc;
  typedef PointerT<MyClass,SuperClass::Handle>  Handle;
  typedef ContainerT<MyClass,SuperClass::Bag>   Bag;
};

The use of dynamically typed containers raises a problem when it is necessary to allocate containers of objects not from the basic usual associated type. Supposing a container of genotype, namely a Genotype::Bag. It may be possible for the container to contain a different type of genotype, for example genotypes of the type SpecializedGenotype, which is derived from the type Genotype. Then, the type allocator member of Genotype::Bag should be an instance of the type SpecializedGenotype::Alloc. This can be easily done by giving as argument an SpecializedGenotype::Alloc to the constructor of Genotype::Bag. But supposing now that a Genotype::Bag::Bag is created and that it should contain these containers dynamically typed, it is necessary to defined a new allocator of Genotype::Bag that instantiate the allocator of Genotype as instances of allocator of SpecializedGenotype. This can be very tricky to implement for a novice user.

This issue is solved by designing a new template of allocators specific to the Open BEAGLE containers. This specialized allocator has an attribute that is an object allocator handle compatible with the type contained in the associated bag. This allocator is implemented in the basic class ContainerAllocator.

class ContainerAllocator : public Object::Alloc {
public:
  ContainerAllocator(Object::Alloc::Handle);
protected:
  Object::Alloc::Handle mContainerTypeAlloc;
};

The type Alloc of ContainerT is declared as typedef of a templated allocator of container (ContainerAllocatorT). This template takes a third type, the type of the member allocator type of the container, in addition to the two first usual types.

template <class T, class BaseType>
class ContainerT : public BaseType {
public:
  typedef ContainerAllocatorT<ContainerT<T,BaseType>,BaseType,T::Alloc> Alloc;
  ...
};

Doing so, allocators of bags that are dynamically typed can be instantiated. A second template for the case of abstract bag type has also been declared, AbstractContainerAllocT. This is coherent with the discussion about the type AbstractAllocT, which is presented in Section Allocators.

XML Input/Output

Reading and writing files containing evolutionary data, such the population, the parameters, the algorithm, the results of the evolution, is an important aspect of an EC framework. The C++ already provides an interesting streaming mechanism to read and write objects into a file, the memory or the standard input/output. Although, there is also a very interesting technology that is more and more used as a file format, the eXtensible Markup Language (XML).

The XML format was first intended to be an improved generic replacement to HTML, but it appears to be so generic, and so well accepted by the industry, that it's now a central technology for domains such data modeling (as in the modern word processors), lightweight distributed computing (SOAP and XML-RPC), databases interactions and Web integration in general. Although the XML is a human understandable format, it is also a flexible and powerful file format, ideal for a to be used in conjunction of a framework such Open BEAGLE. A XML document can also be interpreted to screen by most modern Web browsers such Mozilla and Microsoft Internet Explorer.

Since version 3.0.0, Open BEAGLE uses the XML facilities provided by PACC. These consist of a DOM-like XML parser and an XML streamer. The XML parser reads a file by constructing a tree from the XML file it reads. The XML parser uses a standard C++ input stream as input. The XML output streamer is a simple API class that can generate XML output to a standard C++ output stream. Please note that PACC's XML code only supports basic extended ASCII; it does not support utf-16 or any other encodings.

For every Open BEAGLE objects that can read and written, the methods read and write must be over-defined consequently. For the read, this is done by a exploring the tree build by the XML parser. For the write method, the object must be serialized using the XML streamer API.

To illustrate this, the following example presents the listing of the method read and write of the hypothetical class DataValue.

class DataValue : public Beagle::Object {

private:
  std::string mName;
  double      mValue;

public:
  virtual void read(PACC::XML::ConstIterator inIter) {
   if((inIter->getType()!=PACC::XML::eData) && (inIter->getValue()!="Data"))
     throw Beagle_IOExceptionNodeM(*inIter, "tag <Data> expected");
   mName = inIter()->getAttribute("name");
   if(!inIter->getFirstChild())
     throw Beagle_IOExceptionNodeM(*inIter, "no value for tag <Data> found");
   mValue = uint2str(inIter->getFirstChild()->getValue());
 }

 virtual void write(PACC::XML::Streamer& ioStreamer, bool inIndent) const {
   ioStreamer.openTag("Data", inIndent);
   if(mName != "") ioStreamer.insertAttribute("name", mName);
   ioStreamer.insertFloat(mValue);
   ioStreamer.closeTag();
 }

};

The XML output produced of an instance of a DataValue object that have as name mydata and as value 1.5 would be the following.

<Data name="mydata">1.5</Data> 

In conjunction of the XML file format used in Open BEAGLE, there is a Web interface called BEAGLE Visualizer, which allow the analysis of files containing the populations or evolution statistics, into a standard Web browser. There is also some plans to develop scripted interfaces to visualise on-the-go the progress of evolutions.

NOTE: A short overview (1-2 sentences) of Open BEAGLE file format is necessary here.

Object Wrappers

Given all this functionalities, the predominance of the object abstraction in Open BEAGLE's design is evident. But, if a user has some elaborated classes, or if a user wants to use other libraries in conjunction of Open BEAGLE, it might be restrictive that everything must inherit from the superclass Object. The user might not want to redefine everything or to use multiple inheritance to created hybrid classes. To enhance the user experience, a class template that would keep the use of Open BEAGLE simple is defined: the object wrapper. The wrapper is a simple adapter of any type to the Open BEAGLE Object interface. The concept of object wrapper is based upon the Adapter design pattern.

The wrapper is defined in the C++ template WrapperT. The template maps the Object interface to the usual methods of the wrapped type. The template got some casting operators to indifferently use the wrapper as the wrapped type. Furthermore, some types that are wrappers of the C++ fundamental types are defined as standard types of Open BEAGLE. The following Table presents all the standard wrapped type defined in Open BEAGLE.

NOTE: Some explanations on the ArrayT template is also necessary here.

Exceptions

Open BEAGLE integrates the C++ exceptions mechanism. Keeping it OO, an hierarchy of exceptions are defined. At the top there is the abstract exception superclass, Exception, from which every other Open BEAGLE exception classes inherit. This class inherit from the standard std::exception class, which allow catch of Open BEAGLE exceptions in a simple catch(std::exception&) expression.

class Exception : public Object, public std::exception {
public:
  explicit Exception(std::string inMessage="");
  void terminate(std::ostream& ioES=std::cerr) throw();
  virtual const char* what() const throw();
protected:
  std::string  mMessage;
};

Some other exceptions classes are defined into Open BEAGLE for different type of problem encountered. For most concrete standard Open BEAGLE exceptions, there is an associated macro that simplify the throwing of an exception. Following Table presents the list of exceptions defined in Open BEAGLE, with a short description of the context they are used.

NOTE: New exceptions have been added to the GP framework, to interrupt the interpretation of an individual. They should be added to the table.

Summary

Open BEAGLE's foundation is made of different entities that compose the generic part of the framework. The most important of them is the class Object, the basic class from which most others Open BEAGLE class inherits. Any object subtype could be smart pointed by a Open BEAGLE pointer, which managed the deallocation of the object when it is appropriate. The allocators are objects that allocate, clone, and copy Open BEAGLE objects. The container is a flexible data structures tightly related with the objects, smart pointers and allocators. There is also mechanisms that allow a transparent reading and writing of Open BEAGLE object into the powerful XML file format. There is some templates related to these entities that exploit great concepts of generic programming and make the programmer's life easier. Error handling mechanism are also deployed to facilitate developments and debugging.

Generic EC Framework

The generic EC framework is the extension of OO foundations. It offers a solid basis for implementing Evolutionary Algorithms (EA). It is composed of a generic structure for populations, an evolution system and a set of operators packed in an evolver. All components of the generic EC framework are integrated together as modules that can be replaced or specialized independently. This modular design gives much versatility to the framework and simplifies the implementation of any EA. The following Figure presents the generic EC framework.

The following discussion explains this generic framework and is divided into three sections: the populations and statistics, the internal system, and the operators and evolvers.

Populations and Statistics

The statistics of the fitness measurements of a population is held in the following structure.

struct Measure {
  std::string mId;
  float       mAvg;
  float       mStd;
  float       mMax;
  float       mMin;
};

class Stats : public Object, public std::vector<Measure> { 
public:
  void          addItem(std::string inTag, double inValue);
  void          clearItems();
  double        deleteItem(std::string inTag);
  double&       getItem(std::string inTag);
  const double& getItem(std::string inTag) const;
...
protected:
  std::map<std::string,double>  mItemMap; 
  std::string                   mId;
  unsigned int                  mGeneration;
  unsigned int                  mPopSize;
};

For the usual EC algorithm, statistics for a population are calculated every generation. Two important elements compose the statistics: the measures and the items. A measure provides the statistical analysis of the distribution (average, standard deviation, maximum, and minimum) of a given value of interest taken on the population. On the other hand, an item is a single value represented by a floating-point number associated to a tag name. Items and measures are dynamically added to the statistics, and are generally computed by a statistics computation operators. These operators are specific to the fitness object and inherit from the abstract class StatsCalculationOp.

class StatsCalculateOp : public Operator {
public:
  virtual void calculateStatsDeme(Stats& outStats, Deme& ioDeme, 
                                  Context& ioContext) const =0;
};

When a non-standard fitness object is used, a companion statistics computation operator must defined by inheriting from StatsCalculationOp class and over-defining the pure virtual method calculateStatsDeme.

The fitness holder of an individual is represented in an object derived of the type Fitness. When the user implements a concrete evaluation class, the method evaluate must returns a fitness object appropriate to the application. There is some of the predefined standard fitness measures, such FitnessSimple, FitnessSimpleMin, FitnessMultiObj, FitnessMultiObjMin or GP::FitnessKoza, which defined respectively a fitness made of a single float, the minimization equivalent of single float, multiobjective maximization fitness measures, multiobjective minimization fitness measures or a more elaborated fitness traditionnally used for GP. A specialized fitness type could also be defined for more sophisticated evolution.

In Open BEAGLE, the population is structured into four layers: a vivarium, the demes, the individuals and the genotypes. The first layer, the vivarium, comprises the whole population of a specific evolution, that is, an aggregate of one or more demes. A deme is a population that evolves in an independent environment. Generally, at each generation, there are some individuals that migrate between the demes that compose a vivarium. A deme is implemented in class Deme. The class provides and implements an interface of standard methods necessary to evolve its own population. The class Vivarium describes a bag of demes, which is itself a bag of individuals. Every single vivarium and deme also has an hall-of-fame (a HallOfFame object), where the best-of-run individuals are conserved, and its statistics (a Stats object).

The next underlying layer, the individual, is defined in class Individual. It is a bag of genotypes, the parts that compose a genome. The genotypes are tightly related to the representation of the individuals for a given EC algorithm. The genotype interface is declared in the abstract class Genotype. This hierarchical organization of the population is illustrated in the following Figure.

Internal System

This section presents the internal system of Open BEAGLE, which is the structure that holds and gives access to the state of the genetic engine. These structures are fundamental, because they are used as entry points to the data of the evolution.

During the evolutionary processes, a context gives the current state of the evolution. A basic, general context is implemented in class Context. It provides some essential contextual informations such as the current deme, individual, genotype and generation. For a specific EC algorithm, a specific context could be used. For example, a GP specific context is defined, GP::Context, which contains the call stack with some other GP specific informations. An Open BEAGLE context is similar to the execution context of a computer that contains the different registers, counters and pointers to the actual state of the machine.

Given that the parameters of Open BEAGLE are distributed in the appropriate objects, an agent is implemented to take into account these parameter: the register. All the variables that are considered as parameters should be registered by giving the reference (object handle) of the parameter with the associated namespace and tag. The class Register can be seen as a centralized database from which any entity could dynamically add, delete, access or modify parameters. The register is also responsible of interpreting the parameters part of the configuration file.

All the output messages given to the user pass by the logger. It consists of an interface with the user, that receives all messages, associated with a type, a class name, and an output level, and output them in a given device if the used log level allow it. This is very interesting if a user want, for example, to use Open BEAGLE into a broader system using a graphical user interface. In such case, the user only need to define his own specialized logger that will intercept the messages and log them into the desired device, for example a specific graphical windows. There is actually one specialized logger, LoggerXML, that log messages to a file and/or the console (the STDOUT device) in a XML format. The other very interesting aspect of the logger is the possibility to choose the log level desired. The messages outputted are classified into eight categories, as depicted in the following Table.

The registered parameters lg.console.level and lg.file.level allows the user to select the desired log level. For example, if the user choose the log level info (3), all messages classified in categories basic (1), stats (2), and info (3) will be outputted. Log levels basic (1) to detailed (4) are appropriate for monitoring evolutions, log levels detailed (4) and trace (5) are good to get familiar with the internal functioning of Open BEAGLE, while log levels trace (5) to debug (7) may be useful to debug an user application, or the framework.

Class Randomizer provides a common pseudo-random numbers generator. The randomizer comprises two parameters that are registered (in the register): the internal state and the seed. The internal state is an integer that give the actual state of the randomizer. This value change at every generation of a random number. This value is useful mainly to restart an evolution from a milestone. The seed is the value of the first state of the randomizer. By default, the seed is initiated to the timer value. The seed can be set by the user to reproduce an evolution. Starting with version 2.0.0, the default random number generator used in the framework is based on the Mersenne Twister of Matsumoto and Nishimura.

NOTE: There have been several changes in the organisation of the randomizer, although it is still the Mersenne twister. 
All the previous paragraph should be updated accordingly.

The entry point to these resources is given by an extensible central repository: the system. This is simply an entry point that possessed some vital resources of the EC engine: a context allocator, a reference to the register, a reference to the logger, and a reference to the randomizer. This general system is implemented in the class System. The system is accessible by any context of a given evolution. The relations between the different constituents of the internal system is presented in following Figure.

NOTE: A paragraph is necessary here in the concept of system components, new with version 3.0.0.

Operators and Evolver

The operator is a central concept of Open BEAGLE as an EC framework. The main-loop of operations executed on populations is dynamically defined. The operators are specified at runtime and the user is free to define them for his evolution. This give the opportunity to easily and rapidly experiment numerous variants of EC. The operator and evolver model is based on the Strategy design pattern, which is applied to the evolutionary algorithms. The operator interface is declared in the abstract class Operator.

class Operator : public Object {
public:
  Operator() { }
  virtual void initialize(System& ioSystem) { }
  virtual void postInit(System& ioSystem) { }
  virtual void operate(Deme& ioDeme,Context& ioContext) =0;
};

Before the characteristic method is applied to demes, method initialize is invocated. In this method, the operator usually registers its own parameters, probabilities or anything else, used by the characteristic operation. The characteristic operation is defined in the virtual method operate. There is a bunch of predefined operators in Open BEAGLE. To name a few of them, the tournament selection operator (SelectTournamentOp), the GP tree crossover operator (GP::CrossoverOp) and the milestone writing operator (MilestoneWriteOp).

The user that define his own operators must be aware that the system is not fully set-up when the initialize method is called. For example, the random number generator must not be used, as the seed can be modified thereafter on the command-line or in the configuration file. The rule is that the initialize method must be used only to add elements to the evolution system. There is also a second hook called postInit, which is also called once, just after the whole system is set-up. The postInit method can be use, for example, to configure some data using the random number generator, which is now fully configured.

The operators of a specific evolution are inserted into the evolver that supervises the evolution process. This object, implemented in class Evolver, comprises two major attributes: the bootstrap operator set and the main-loop operator set. The bootstrap operators set contains an ordered list of operators to apply on each deme, for the initial generation. The main-loop operators set is an ordered list of operators to apply iteratively, at each generation, on each deme. The user could launch an evolution, by calling the method evolve with the vivarium to evolve as argument.

class Evolver : public Object {
public:
  virtual void initialize(System::Handle ioSystem,int& ioArgc,char** ioArgv);
  virtual void evolve(Vivarium::Handle ioVivarium);
protected:
  Operator::Bag mBootStrapSet;
  Operator::Bag mMainLoopSet;
};

For common EC algorithms, the user usually needs not to create custom sequences of operators. In fact, some classes inheriting of Evolver can be used to create evolvers with predefined operator sets. If a special EC algorithm is needed, a custom building method can be invocated and the evolver should be configured properly. Section Standard Open BEAGLE Operators Library presents the standard operator library with the methods that can be used to build standard EC algorithm.

Breeder Model

NOTE: The explanations on the breeder model are somewhat fuzzy. It is not easy to understand this thing, although this is an central mechanism of Open BEAGLE. 
More explanations are necessary in order to make it clear.

A conceptual layer is added over the operator/evolver model: the breeder model. This allow the manipulation of the population at the individual level, in comparison to manipulations at the deme level by the standard operators. Note that the use of the breeder model over the standard operator/evolver model is optional; users don't have to use it if they don't need it.

The breeder model includes a set of operators structured into a tree: the breeder tree. At the root of the breeder tree, there is a replacement strategy, which act as an interface between the operator/evolver mechanism and the breeder model. The function of a replacement strategy is to generate, by applying the breeder tree on a deme, the next generation deme. The direct children in the breeder tree to the replacement strategy are called alternatively following their respective breeding probability. The operators that compose the nodes of the breeding tree process the bred individual, while the leaves of the breeder tree are generally used to select individuals. The following snippet presents the XML configuration of a breeder tree for the maxfct example, using a steady-state replacement strategy.

...
<SteadyStateOp>
  <MaxFctEvalOp>
    <GA-CrossoverOp>
      <SelectTournamentOp/>
      <SelectTournamentOp/>
    </GA-CrossoverOp>
  </MaxFctEvalOp>
  <MaxFctEvalOp>
    <GA-MutationOp>
      <SelectTournamentOp/>
    </GA-MutationOp>
  </MaxFctEvalOp>
  <SelectTournamentOp/>
</SteadyStateOp>
...

Three new classes are added to the framework to support the new breeder model: BreederOp, BreederNode, and ReplacementStrategyOp. Class BreederOp designates operators that can, in addition to the facilities of the operators, process a pool of individuals to return one bred individual. The interface of the class BreederOp is the following.

class BreederOp : public Operator {
public:
  virtual Individual::Handle breed(Individual::Bag& inBreedingPool,
                                   BreederNode::Handle inChild,
                                   Context& ioContext) = 0;
  virtual float getBreedingProba(BreederNode::Handle inChild) = 0;
};

The pure virtual method breed is used to apply the characteristic breeder operation. It takes as first argument a pool of individual from which the breeding operation is done, as second argument a breeder node giving the position of the first child to the actual operator in the breeder tree, and as last argument the evolutionary context. The method getBreedingProba returns the breeding probability, which is used by the replacement strategy to decide which of its subtrees is called to generate a bred individual. The BreederNode class defines the breeder tree structure. It is made of three smart pointers, one to its first child, another to its next sibling, and one last to the associated breeder operator. Finally, the class ReplacementStrategyOp defines an item of the evolver's operator set that can be used as the root of the breeding tree, to generate a new generation of individuals. Five replacement strategies operator are actually implemented in Open BEAGLE: GenerationalOp, which defines a generational replacement operator using a breeder tree, SteadyStateOp, which defines a steady-state replacement operator, NSGA2Op, which defines the NSGA-II multiobjective evolutionary algorithm, and finally the MuCommaLambdaOp and MuPlusLambdaOp replacement operators, which define the (μ,λ) and (μ+λ) approaches commonly used with the evolution strategy EC paradigm.

Summary

This section had presented three important components of the EC architecture of Open BEAGLE. The first component is the structure of the population of the framework, that includes elements such the vivarium, the demes, the individuals, and the genotypes. The following is the internal system, where the parameters and some other entities are held. The third component is a central aspect of Open BEAGLE as EC framework, the operators and the evolver. An operator is simple operation, such writing a population to the disk or GP tree crossover operation, which is applied sequentially and iteratively in conjunction of others operators to evolve a population. An evolver is an agglomerate of operators to apply on the population. An applications developers can use an evolver pre-packed with usual operators or instantiate his own custom evolver composed of more exotic operators. And finally, the breeder model represents a set of specific operators that allow the manipulation of population with a finer granularity.

Miscellaneous Architecture Elements

This section presents of different miscellaneous architecture elements more specific certain EC flavors or applications. It presents of some common application-specific elements such the evaluation and termination operators, and some other more EC flavor-specific elements such the GP primitives. It also discuss of a more general elements such the different standard operators defined in the Open BEAGLE framework.

Evaluation Operator

In most EC algorithms, modified individuals are evaluated at each generation. To do so, there is a common operator to evaluate individuals, the evaluation operator. This operator is implemented in class EvaluationOp, which is a standard abstract interface for the evaluation of an individual.

class EvaluationOp : public Operator {
public:
  virtual Fitness::Handle evaluate(Individual& inIndividual,
                                   Context& ioContext) =0;
  virtual void operate(Deme& ioDeme,Context& ioContext);
};

Usually, for a specific problem, the user must implements a concrete class that specialize EvaluationOp. In this concrete class, he must declare a definition of the method evaluate. This method provides the way an individual is evaluated.

It is also possible to evaluate more than one individual at a time. This is especially useful if there is no known absolute fitness score, but it is possible to produce a fitness value when two individuals compete. For such a scenario, the user should derive a concrete evaluation class from EvaluationMultipleOp.

Termination Operator

As explained in previous sections, the basic Open BEAGLE algorithm is an infinite loop over the main operator set. But, there is a standard Open BEAGLE operator, the termination criterion, that determine whether to stop or not the evolution process. In Open BEAGLE, the termination criterion is implemented in operator TerminationOp.

class TerminationOp : public Operator {
public:
  virtual bool terminate(const Deme& inDeme,const Context& inContext) = 0;
  virtual void operate(Deme& ioDeme,Context& ioContext);
};

The default termination criteria is the number of generations the algorithm iterates for an evolution. This criterion is defined in the operator class TermMaxGenOp. There is also several other termination operators such TermMaxFitnessOp (maximum fitness value), TermMinFitnessOp (minimum fitness value), TermMaxEvalsOp (maximum number of fitness evaluations), and GP::TermMaxHitsOp (maximum number of hits for GP Koza's fitness measure). The user could change or add termination criteria for his evolutionary application by redefining the method terminate.

History Storage Mechanism

The history mechanism stores the operations that occurred during evolution (e.g. crossover, mutation, evaluation). It allows the user to produce a genealogy tree for each individual in the population. A graphical example of the data that is collected by the history mechanism can be seen here

All that is required for the storage of History data is for the History component to be installed into the System. To do this, create an instance of Beagle::System and then call the Beagle::System::addComponent() method passing a handle to an instance of a Beagle::History component:

Beagle::System::Handle lSystem = new System;
lSystem->addComponent(new Beagle::History());

The history data can then be found in the milestone files that Beagle produces (see Beagle::MilestoneWriteOp). When a History component is installed, individuals will be allocated identification numbers; these can be seen when an individual is written out. Along with identification numbers, revision numbers are also stored; these state how many times an individual has been modified.

Even if a System has a History component installed, the output of data can be switched off with the use of the hs.record.activated register variable. The use of this flag will reduce memory consumption, and history data will still appear in the log file if the log level is set to 'trace' (level 5) or higher.

If memory consumption becomes an issue, the Beagle::HistoryFlushOp operator will clear the memory used once the data had been written to a milestone file. As a result, 'link' operations will be included in the history data to allow the connection of history entries.

If, for example, you have created a new genetic operator and would like to add the storage of your operation to the history mechanism, then the Beagle::History::trace() method should be used. You can find examples of its use in the Beagle::CrossoverOp::operate() and Beagle::MutationOp::operate() methods. If you are modifying an individual with your operator then you should also increment the individual's variation number with a call to the Beagle::Individual::incrementHistoryVar() method.

Multiobjective Evolutionary Algorithms

Since version 2.1.0, Open BEAGLE includes support for Multiobjective Evolutionary Algorithms (MOEA). For this purpose, two fitness measure types have been defined in the framework, that is a maximization one named FitnessMultiObj, and its minimization equivalent FitnessMultiObjMin. In both these two fitness measures, a Pareto domination test has been added in method isDominated. If the user want to use a different multiobjective measure, for example a fitness measure comprising a mix of minimizing and maximizing objectives, the method isDominated of the new fitness measure class must be over-defined accordingly.

The other element of MOEA support in Open BEAGLE is the multiobjective selection operator. There is currently two of these implemented, that is NSGA-II, implemented as a replacement strategy of a breeder model, and the NPGA 2, implemented as a classical selection operator. There is also a multiobjective-specific hall-of-fame class called ParetoFrontHOF, that contains the population's Pareto front.

Co-evolution

NOTE: This subsection on co-evolution is far to short. It should be rewritten with more explanations and use examples.
Maybe a complete section in next chapter would be necessary. 

Co-evolution framework is based on multi-threading programming, where each thread is associated to a population. The execution sequence of each thread is the same than what usually done in the main function of standard evolutions, as described in Section Building a System for an Evolution (i.e. build system, evaluation operator, vivarium, evolver, initialize evolver, and start evolution). The population in each thread evolves independently, with inter-thread synchronization only in co-evolutionary fitness evaluation operator. This operator behaves quite differently than usual mono-population evaluation operator. The co-evolution evaluation procedure starts by calling Coev::EvaluationOp::makeSets, which makes evaluation sets of the evolving population and add them into shared storage structure, using method Coev::EvaluationOp::addSet. When the desired number of evaluation sets is added (the trigger value) the co-evolutionary fitness evaluation method defined in Coev::EvaluationOp::evaluateSets is called. Pure virtual methods Coev::EvaluationOp::makeSets and Coev::EvaluationOp::evaluateSets are problem-specific and must be defined by the user in its co-evolutionary fitness evaluation operators.

A trigger value is used to specify the number of evaluation sets needed to start a co-evolutionary evaluation. This value is usually equal to the number of threads/populations used, as usually each thread/population add one evaluation set before doing the co-evolutionary evaluation operation. But different trigger value can be used depending on the context.

Marc Parizeau's portable C++ classes for multi-threading (defined in namespace Threading) are also provided with co-evolutionary framework. These are used internally by the co-evolution framework. Users are advised to use them for their co-evolutionary applications.

Standard Open BEAGLE Operators Library

NOTE: Lot of new operators has been added to Open BEAGLE. They should be added to the different Tables of the actual subsection. 

An important advantage of OO programming is the reuse of standard components with few or no modifications. Up to now, a bunch of generic and specific (to GP and GA) operators are integrated to Open BEAGLE. There is plans to integrate some more for doing other EC algorithms.

The following tables present the standard operators of Open BEAGLE and the bootstrap and main loops of the bit string GA, interger vector GA, float vector GA, ES, and GP default evolvers.

GA::EvolverBitString default operator sets:

<Evolver>
  <BootStrapSet>
    <IfThenElseOp parameter="ms.restart.file" value="">
      <PositiveOpSet>
        <GA-InitBitStrOp/>
        <MyEvaluationOp/>
        <StatsCalcFitnessSimpleOp/>
      </PositiveOpSet>
      <NegativeOpSet>
        <MilestoneReadOp/>
      </NegativeOpSet>
    </IfThenElseOp>
    <TermMaxGenOp/>
    <MilestoneWriteOp/>
  </BootStrapSet>
  <MainLoopSet>
    <SelectTournamentOp/>
    <GA-CrossoverOnePointBitStrOp/>
    <GA-MutationFlipBitStrOp/>
    <MyEvaluationOp/>
    <MigrationRandomRingOp/>
    <StatsCalcFitnessSimpleOp/>
    <TermMaxGenOp/>
    <MilestoneWriteOp/>
  </MainLoopSet>
</Evolver>

GA::EvolverIntegerVector default operator sets:

<Evolver>
  <BootStrapSet>
    <IfThenElseOp parameter="ms.restart.file" value="">
      <PositiveOpSet>
        <GA-InitIntVecOp/>
        <MyEvaluationOp/>
        <StatsCalcFitnessSimpleOp/>
      </PositiveOpSet>
      <NegativeOpSet>
        <MilestoneReadOp/>
      </NegativeOpSet>
    </IfThenElseOp>
    <TermMaxGenOp/>
    <MilestoneWriteOp/>
  </BootStrapSet>
  <MainLoopSet>
    <SelectTournamentOp/>
    <GA-CrossoverUniformIntVecOp/>
    <GA-MutationUniformIntVecOp/>
    <MyEvaluationOp/>
    <StatsCalcFitnessSimpleOp/>
    <TermMaxGenOp/>
    <MilestoneWriteOp/>
  </MainLoopSet>
</Evolver>

GA::EvolverFloatVector default operator sets:

<Evolver>
  <BootStrapSet>
    <IfThenElseOp parameter="ms.restart.file" value="">
      <PositiveOpSet>
        <GA-InitFltVecOp/>
        <MyEvaluationOp/>
        <StatsCalcFitnessSimpleOp/>
      </PositiveOpSet>
      <NegativeOpSet>
        <MilestoneReadOp/>
      </NegativeOpSet>
    </IfThenElseOp>
    <TermMaxGenOp/>
    <MilestoneWriteOp/>
  </BootStrapSet>
  <MainLoopSet>
    <SelectTournamentOp/>
    <GA-CrossoverBlendFltVecOp/>
    <GA-MutationGaussianFltVecOp/>
    <MyEvaluationOp/>
    <StatsCalcFitnessSimpleOp/>
    <TermMaxGenOp/>
    <MilestoneWriteOp/>
  </MainLoopSet>
</Evolver>

GA::EvolverES default operator sets:

<Evolver>
  <BootStrapSet>
    <IfThenElseOp parameter="ms.restart.file" value="">
      <PositiveOpSet>
        <GA-InitESVecOp/>
        <MaxFctESEvalOp/>
        <StatsCalcFitnessSimpleOp/>
      </PositiveOpSet>
      <NegativeOpSet>
        <MilestoneReadOp/>
      </NegativeOpSet>
    </IfThenElseOp>
    <TermMaxGenOp/>
    <MilestoneWriteOp/>
  </BootStrapSet>
  <MainLoopSet>
    <MuCommaLambdaOp>
      <MaxFctESEvalOp>
        <GA-MutationESVecOp>
          <SelectRandomOp/>
        </GA-MutationESVecOp>
      </MaxFctESEvalOp>
    </MuCommaLambdaOp>
    <StatsCalcFitnessSimpleOp/>
    <TermMaxGenOp/>
    <MilestoneWriteOp/>
  </MainLoopSet>
</Evolver>

GP::Evolver default operator sets:

<Evolver>
  <BootStrapSet>
    <IfThenElseOp parameter="ms.restart.file" value="">
      <PositiveOpSet>
        <GP-InitHalfOp/>
        <MyEvaluationOp/>
        <GP-StatsCalcFitnessSimpleOp/>
      </PositiveOpSet>
      <NegativeOpSet>
        <MilestoneReadOp/>
      </NegativeOpSet>
    </IfThenElseOp>
    <TermMaxGenOp/>
    <MilestoneWriteOp/>
  </BootStrapSet>
  <MainLoopSet>
    <SelectTournamentOp/>
    <GP-CrossoverOp/>
    <GP-MutationStandardOp/>
    <GP-MutationShrinkOp/>
    <GP-MutationSwapOp/>
    <GP-MutationSwapSubtreeOp/>
    <MyEvaluationOp/>
    <GP-StatsCalcFitnessSimpleOp/>
    <TermMaxGenOp/>
    <MilestoneWriteOp/>
  </MainLoopSet>
</Evolver>

GP Genotypes

namespace GP {
struct Node {
  Primitive::Handle mPrimitive;
  unsigned int      mSubTreeSize;
};
class Tree : public Genotype, public std::vector<Node> { ... };
}

One of the most notable points with Open BEAGLE is the possibility to redefine and modify almost everything. This is easily done by giving the appropriate allocator of a subclass to the upper layer class constructor. As example, when a GP::Vivarium is created, it creates by default GP::Individual by passing to its constructor an allocator of GP::FitnessKoza for the fitness value and an allocator of GP::Tree to allocate its genotypes.

namespace GP {
class Individual : public Beagle::Individual {
public:
  Individual(Fitness::Alloc::Handle inFitnessAlloc,
             GP::Tree::Alloc::Handle inTreeAlloc);
  ...
};
}

But, if the user want to use a different genotype, suppose a user defined custom genotype implemented in the class MyGenotype, he only needs to pass an allocator of his custom genotype to the allocator of GP::Individual:

Fitness::Alloc::Handle        lFitsAlloc     = new GP::FitnessKoza::Alloc;
MyGenotype::Alloc::Handle     lGenotypeAlloc = new MyGenotype::Alloc;
GP::Individual::Alloc::Handle lIndivAlloc    = 
  new GP::Individual::Alloc(lFitsAlloc,lGenotypeAlloc);

The allocator of individual will then create individuals that are bags of MyGenotype. Furthermore, if the GP::Individual is copied into another GP::Individual, the reference to the allocator of custom genotype is copied and the genotypes of the bag are cloned.

GP Primitives and Sets

Open BEAGLE uses a real OO approach to implement the primitives that compose GP genotypes. The genotypes are composed of nodes that have one attribute, that is a smart pointer to an abstract primitive. Using this abstract interface, it is easy to implement primitives that have specific behavior without loosing any generality.

To make a concrete primitive that is usable to compose GP trees, the user needs to declare a concrete class derived from the abstract superclass GP::Primitive. Given that, existing primitives can be reused or specialized. These are some fundamental principles of OO programming. These also give us powerful mechanisms to defined atypical primitives without tweaking the internal structure. The section Getting the Most of the Primitives is a deep discussion on how to define GP primitives.

NOTE: The following explanations on association between the number of primitive sets in the super set and the number of trees in the GP individuals is no more true. This implicit link is broken and it is now possible to have GP individuals with several trees while having one primitive set. An index to the associated primitive set has been added to the GP trees. The following paragraph should be rewritten.

Once the primitives used for a genetic evolution of programs are determined, they must be packed into sets that are given to the GP system. In Open BEAGLE, the process is straightforward: the user directly creates the set of primitives by inserting references to primitives. The primitives set is implemented in the class GP::PrimitiveSet, a bag of GP::Primitive. When the primitives sets are made, they are put into the super set of primitives, implemented in the class GP::PrimitiveSuperSet. A GP::PrimitiveSuperSet is a bag of GP::PrimitiveSet. Finally, this super set of primitives is given to the system of GP. When only one set of primitives is used, which is usual when there is no use of automatically defined structures, the user could directly pass the simple primitive set as reference to the system. Then, the system build a super set of primitives that wraps the simple set. Each set is associated with corresponding trees of each individual, as presented in following Figure.

NOTE: Lot of improvements have been made to the GP framework concerning the individuals. For example, primitives with variable number of arguments, variable selection weight of primitives in primitive set, dynamic ADFs, and evolutionary module acquisition should be detailed.

GP Primitives Library

NOTE: The ADFs mechanisms has been completely changed.

Some common primitives are defined from the abstract interface GP::Primitive. As with the operators, there is some common GP primitives into Open BEAGLE. At this moment, there is three different series of standard primitives: the generic, the arithmetics and the Boolean functions. The generic series comprise a simple terminal containing a token, TokenT, a primitives to program automatically subroutines, AdfT, and a primitive for randomly generated constants, EphemeralT. The second bunch comprises usual arithmetics operators. The third bunch comprises some common logical operators that work on the Open BEAGLE Bool type. The following table presents and describe of all these primitives.

Next chapter: User Manual.