Documentation:Manual:User Manual
From Beagle
This section is a extensive presentation of what an application programmer, which is called the user from now, needs to know to develop EC process with Open BEAGLE. Some important aspects of C++ programming using Open BEAGLE are presented here. The discussion starts with what the user should and should not do (the guidelines). Following this is presented a simple pattern of what is needed to build a system for an evolution. Thereafter the different ways to modify the parameters of the system are exposed. Finally is presented the different approaches to customize the evolutionary process and a specific manual for the different standard EC algorithms implemented in Open BEAGLE.
Contents |
Guidelines
Open BEAGLE is a powerful framework for EC. It is based on different elaborated mechanisms that make it both a flexible and programmer-friendly environment. But, these mechanisms require that to the user follows some general guidelines. A little adaptation effort is necessary to make the experience with Open BEAGLE as pleasant as possible. There is these general guidelines, accompanied by a deeper discussion on each of them.
Any instance (i.e. C++ objects) used in combination of Open BEAGLE must inherit, directly or indirectly, from the abstract Object class
As explained in previous sections of the document, every Open BEAGLE classes are derived from the Object abstract class, with as exception the class Pointer and derived. The Open BEAGLE class architecture can be see as a tree with the Object class as root. The internal mechanisms of Open BEAGLE usually manipulate data types by using the common Object interface. It is then necessary for the user to integrate his application classes to the basic architecture. This is often done implicitly by sub-classing some Open BEAGLE entities. But, in some circumstances, a user may need to define a new class that do not have any relation with other existing Open BEAGLE classes. To do so, it is advised to use the WrapperT template to encapsulate these custom types.
Any Open BEAGLE objects that are smart pointed must be allocated on the heap and memory-managed by object handles.
The smart pointer, also called handle, is a very useful mechanism that both simplify the task of the user and add global functionality and flexibility to the Open BEAGLE environment. But, users have to be cautious when they use smart pointers. They must be sure to allocate smart pointed objects on the heap, by a call to the new operator. This is fundamental because the smart pointed objects are automatically destructed, with a call to the delete operator, when their reference counter reach 0. This is incompatible with stack-allocated instances.
The nested types Handle, Alloc, and Bag must be defined in any object classes.
In every classes of the Open BEAGLE framework, the types Handle, Alloc, Bag are defined. The handle type is a smart pointer to the type associated (i.e. a Double::Handle is a smart pointer of Double). An allocator is a type that can allocate, clone and copy the associated type. A bag is an Open BEAGLE container of the given type. Both these types are used extensively by the Open BEAGLE mechanisms. These three types can be easily defined by a synonym declaration to the associated template classes, as in the following listing.
class MyClass : public SuperClass {
public:
typedef PointerT<MyClass,SuperClass::Handle> Handle;
typedef AllocatorT<MyClass,SuperClass::Alloc> Alloc;
typedef ContainerT<MyClass,SuperClass::Bag> Bag;
...
};
The templates take as first parametrized value the type of the associated object. In this case, the associated object is the type MyClass. The second parametrized value is the equivalent nested type of the direct superclass. In this case, the class MyClass inherits from the class Object so the equivalent nested type to a MyClass::Handle is a Object::Handle.
Any upcast of Open BEAGLE objects must be done by a call to the Open BEAGLE castObjectT operator for references and C-pointers, and by call to the Open BEAGLE castHandleT operator for smart pointers.
With the ANSI/ISO C++ standard, it is highly recommended to use the new style cast operators instead of the old C-style one. This new style cast operators, such the operators static_cast and const_cast, are more specialized cast operations. The use of different cast operators prevent some unwanted casting operations that could lead to nasty hidden bugs. In the Beagle namespace, two new cast operator is defined, castObjectT and castHandleT. These operators must be used to cast any Open BEAGLE object type into another object type. The usage of this casting operator is identical to the usage of new style cast operators.
Any call to Open BEAGLE methods must be into a try-catch block to handle properly any thrown Open BEAGLE exceptions.
Open BEAGLE defines his own exceptions in spirit of the modern C++ exception handling mechanisms. In fact, an hierarchy of classes are defined to cover different cases of error, with at the top the class Beagle::Exception. When programming an application, the user should be aware to catch any Open BEAGLE exceptions and treat them accordingly. At least, the user should catch them and call the exception aborting method. The following code is an example of an internal structure of Open BEAGLE that detects an irregular situation and throws an appropriate exception.
if(n > size()) throw Beagle_RunTimeExceptionM("Out of bound!");
The macro Beagle_RunTimeExceptionM is a wrapper to create an exception object of the type Beagle::RunTimeException, with the message given and the good file name and line number. For almost all the exception classes of Open BEAGLE there is a wrapper macro associated to construct exception with the appropriate file name and line number. A Beagle_AssertM macro is also provided to check some condition as with the useful standard C assert macro.
A simple way to achieve the current guideline is to try-catch all the main routine of the user application, to intercept any Open BEAGLE exceptions. Using the following code, the exceptions not previously caught is displayed at the standard error output, just before the program exit.
int main(int argc, char** argv) {
try {
...
}
catch(Beagle::Exception& inException) {
inException.terminate();
}
return 0;
}
Building a System for an Evolution
To build an EC application with Open BEAGLE, some components need to be configured. Depending the type of evolutionary algorithm and the application, the configuration step is more or less demanding. Conceptually, the components to be configured are divided in three classes, the system, the population and the operator and evolver.
The system
The Open BEAGLE system of EC contains handles to some central entities used all over the evolution, such the register, the randomizer, the logger, and the context. Depending of the evolutionary algorithm used, the system can handles other specialized entities.
The population
In Open BEAGLE, the representation of the individual is not restricted. The application developer can use different standard population representation or implement his own. However the way to instantiate a population for an evolution follows the same bottom-up pattern:
- Instantiate an allocator of the fitness type used;
- Instantiate an allocator of the genotype type used;
- Instantiate an allocator of the individual type used with the genotype and fitness allocators;
- Instantiate an allocator of statistics type used;
- Instantiate an allocator of the deme type used with the individual and statistics allocators;
- Instantiate the vivarium with the deme and statistics allocators.
As example, for multiobjective real-valued GA, the above pattern is translated into the following code.
FitnessMultiObj::Alloc::Handle lFitsAlloc = new FitnessMultiObj::Alloc;
GA::FloatVector::Alloc::Handle lGenoAlloc = new GA::FloatVector::Alloc;
Individual::Alloc::Handle lIndivAlloc =
new Individual::Alloc(lGenoAlloc,lFitsAlloc);
Stats::Alloc::Handle lStatsAlloc = new Stats::Alloc;
Deme::Alloc::Handle lDemeAlloc = new Deme::Alloc(lIndivAlloc,
lStatsAlloc);
Vivarium::Handle lVivarium = new Vivarium(lDemeAlloc,
lStatsAlloc);
For the other EC flavors the pattern is the same, only the types used must be changed. There is several other vivarium constructors, which can take directly, for example, allocators to genotypes and fitness values. You can use these instead of the previously exposed long pattern, if you only wanted to use a specific genotype of fitness type.
The operators and the evolver
As explained in section Operators and Evolver, the evolver applies iteratively, at each generation, the operators on each deme. The operators are packed in the evolver into the bootstrap and the main-loop sets. For usual application, the user can instantiate the default evolvers. If the user want to customize the evolutionary algorithm, he can build his exotic evolver, using the configuration file. This is the topic of section Customizing the Evolutionary Algorithm. In all case, once the operator sets is built, the whole EC system is initialized with a call to the evolver initialize method. The method takes as arguments an handle to the system and the command-line arguments. Once the EC system initialized, the evolution can then be launch with a call to the method evolve of the evolver, taking the vivarium to evolve as argument.
All the EC applications are built following the previously presented scheme. To get more details on how to develop an application for a specific EC flavor, take a look in the chapter GP Tutorial and GP User Manual and GA User Manual. The section Customizing the Evolutionary Algorithm gives also good insight on configuring a custom evolution.
Using the Register
The register is a central repository of all Open BEAGLE modifiable parameters. All these parameters must be registered when the EC system is initialized. The parameters are held in the register as a pair of tag and smart pointer. The tag is the unique identifier of a parameter associated to a smart pointer which is an indirection to the instance of the parameter.
Registering Parameters
When the EC system is initialized, the different parameters must be registered by the appropriate holding objects. As example, a probability of crossover is registered at the initialization time by a crossover operator. Usually, the parameters are registered when the initialize methods are called. The register is referred in the system object. The parameters are added in the register with a call to the method addEntry. The method take as arguments the tag of the parameter, the smart pointer the value of the parameter, and the description of the parameter. The following example add the parameters ec.cx.indpb with a reference to the floating point attribute mMatingProba of the crossover operator.
class CrossoverOp : public BreederOp {
public:
CrossoverOp() { }
virtual void initialize(System& ioSystem) {
BreederOp::initialize(ioSystem);
if(ioSystem.getRegister().isRegistered("ec.cx.indpb")) {
mMatingProba =
castHandleT<Float>(ioSystem.getRegister().getEntry("ec.cx.indpb"));
} else {
mMatingProba = new Float(0.5);
Register::Description lDescription(
"Individual crossover probability",
"Float",
"0.5",
"Single individual crossover probability for a generation."
);
ioSystem.getRegister().addEntry("ec.cx.indpb", mMatingProba, lDescription);
}
}
...
protected:
Float::Handle mMatingProba;
};
In this example, a test is first done to check if the parameter is already registered. If it is registered, a reference is taken on it. If the parameter is not registered, the parameter is instantiated on on the heap and is then registered. When a parameter is registered, a short description must be given. This description is used by the usage of an application and to explain the meaning of the parameter. Note that the parameter referenced by the smart pointer attribute mMatingProba is a Float Open BEAGLE object instead of a C++ float. The type Float is a wrapper of float. All the parameters registered must be smart pointed, which mean that they must be Open BEAGLE objects.
Interaction with the Register
The application programmer can fetch parameters from the register with a call to the method getEntry (or the operator operator[]) of the class Register. This method takes as argument a tag and returns an handle to the parameter associated. The handle returned is a smart pointer of Object. The developer must upcast the handle referred into a exact derived type, if needed. If the named parameter is not registered, the method getEntry (or the operator operator[]) returns a null handle.
void MyClass::MyMethod(System::Handle ioSystem) {
Object::Handle lParameter = ioSystem->getRegister()["ec.cx.indpb"];
if(lParameter == NULL) {
std::cout << "No crossover probability registered" << std::endl;
}
else {
try {
Float::Handle lCastedParameter = castHandleT<Float>(lParameter);
std::cout << "The crossover probability is "
<< *lCastedParameter << std::endl;
}
catch(Beagle::BadCastException&) {
std::cout << "Object registered is not of the Float type" << std::endl;
}
}
}
The exception handling of the object casting is to intercept some abnormal cases, that is when the parameter fetched is not of the desired Float type.
Modifying Parameters
The parameters recorded in the register can be modified in three different ways: by directly modifying the value in the program, by passing specials arguments on the command-line and by using configuration files. The initialization sequence is the following:
- Initialize the parameters to their default value (before the registration);
- Read the default configuration file;
- Parse the command-line, the parameters being modified in the order they are expressed (left to right);
- Read the configuration files given on the command-line, if any. The files are read at the time the configuration file argument is parsed.
Modifying Parameters on the Command-Line
It is possible to modify the parameters registered with arguments on the command-line. When an evolver is initialized in the method initialize, it takes the command-line value (i.e the variables argc and argv) as method argument. This is done to parse the command-line and extract Open BEAGLE specific arguments. All the Open BEAGLE specific arguments start with the prefix -OB, followed by the tag, an equal sign and the values of the parameter. As example, if our executable is named maxfct and the crossover probability must be changed to 0.75, the command-line would be:
./maxfct -OBga.cx.indpb=0.75
If more than a parameter must be changed on the command-line, the user can specify numerous arguments starting with a -OB, or enumerate all of them following a single -OB, separated by comas:
./maxfct -OBga.cx.indpb=0.75,ec.term.maxgen=100
Note that all the command-line arguments starting with the -OB prefix are erased from the structure argc/argv once they are parsed.
There is four special parameters that can be given on the command-line. First, there is the special argument usage, that made the application to display the tag with a short description of the available parameters and exit normally without evolving.
./maxfct -OBusage
The second special argument, help, is very similar to the first one except that it display the tags with everything you want to know on the parameters and exit normally without evolving.
./maxfct -OBhelp
The third special argument, ec.conf.file, can be assigned to the configuration file to use to set the parameters of the evolution. This argument take as value a string that contains the name of the configuration file.
./maxfct -OBec.conf.file=maxfct.conf
And finally, the fourth special command-line argument, ec.conf.dump, can be used to generate configuration file with the default parameters value for a given application. This argument takes the name of the configuration file to generate as value.
./maxfct -OBec.conf.dump=mymaxfct.conf
Modifying Parameters Using a Configuration File
Another interesting way to modify parameters is to use a configuration file. This file, formatted in XML, contains the new value of some or all of the parameters registered. The file format is quite straightforward in the XML style, the logical sequence being preserved. The following is a presentation of a short, but valid, Open BEAGLE XML configuration file.
<?xml version="1.0" encoding="ISO-8859-1"?>
<Beagle version="2.1.1">
<Register>
<Entry key="ec.hof.demesize">0</Entry>
<Entry key="ec.hof.vivasize">1</Entry>
<Entry key="ec.mig.interval">1</Entry>
<Entry key="ec.mig.size">5</Entry>
<Entry key="ec.pop.size">100</Entry>
<Entry key="ec.sel.tournsize">2</Entry>
<Entry key="ec.term.maxgen">50</Entry>
<Entry key="ga.cx1p.prob">0.3</Entry>
<Entry key="ga.init.bitpb">0.5</Entry>
<Entry key="ga.init.bitstrsize">125</Entry>
<Entry key="ga.mutflip.bitpb">0.01</Entry>
<Entry key="ga.mutflip.indpb">1</Entry>
<Entry key="lg.console.enabled">1</Entry>
<Entry key="lg.file.name">beagle.log</Entry>
<Entry key="lg.log.level">3</Entry>
<Entry key="lg.show.class">0</Entry>
<Entry key="lg.show.level">0</Entry>
<Entry key="lg.show.type">0</Entry>
<Entry key="ms.write.interval">0</Entry>
<Entry key="ms.write.over">1</Entry>
<Entry key="ms.write.perdeme">0</Entry>
<Entry key="ms.write.prefix">beagle</Entry>
</Register>
</Beagle>
Customizing the Evolutionary Algorithm
The present section thread of important aspect of Open BEAGLE: how to customize an existing evolutionary algorithm (EA). This can be as simple as to modify a genetic operator of a standard EA to the more complex task of implementing a brand new EA. In any cases, this is an advanced topics that a newcomer can skip in the first time. This section presents the important concepts that is related to the customizing of the EA. It is advised to consult the reference manual for the implementation details.
Building a Custom Evolver
The evolver is a high level entity that apply the iterative evolution process on a population. An evolver is composed of two operator sets, the bootstrap and the main-loop. The bootstrap operators are applied once on the population, at the beginning of an evolution (at generation 0). The main-loop operators are then applied iteratively, until the termination state is reached. These iterations can be seen as generations in a generational evolution model or as certain amount of individual processing in the steady-state evolution model. In all case the basic algorithm is independent of the underlying evolution operations.
Evolvers can be dynamically configured directly by the configuration file. The set-up of the evolver is stated between two Evolver tag, with the list of the operators to used listed in the BootStrapSet and the MainLoopSet tags. The following XML snippet presents the default evolver of GA for the maxfct example.
<?xml version="1.0" encoding="ISO-8859-1"?>
<Beagle version="2.1.0">
<Evolver>
<BootStrapSet>
<IfThenElseOp parameter="ms.restart.file" value="">
<PositiveOpSet>
<GA-InitBitStrOp/>
<MaxFctEvalOp/>
<StatsCalcFitnessSimpleOp/>
</PositiveOpSet>
<NegativeOpSet>
<MilestoneReadOp/>
</NegativeOpSet>
</IfThenElseOp>
<TermMaxGenOp/>
<MilestoneWriteOp/>
</BootStrapSet>
<MainLoopSet>
<SelectTournamentOp/>
<GA-CrossoverOnePointBitStrOp/>
<GA-MutationFlipBitStrOp/>
<MaxFctEvalOp/>
<MigrationRandomRingOp/>
<StatsCalcFitnessSimpleOp/>
<TermMaxGenOp/>
<MilestoneWriteOp/>
</MainLoopSet>
</Evolver>
</Beagle>
When an user want to change the evolutionary algorithm by changing the order of operations, or using other standard operators, he only needs to modify the configuration file accordingly. If the user wants to use custom operators, he must first implement them, as explained at the following section, and then add an instance of them to the evolver, using the method addOperator, before initializing the evolver. Several typical configuration files are given with the examples to illustrate how these can be used to modify the EA used.
Custom Evolver with a Breeder Tree
The breeder model allows the implementation of sophisticated EA. For example, the steady-state formulation of GA, you can use a specialized configuration file using the steady-state replacement strategy operator, with crossover, mutation, and selection operators structured under it as a breeder tree. The configuration file of a steady-state version of maxfct example, using a breeder tree would be the following.
<?xml version="1.0" encoding="ISO-8859-1"?>
<Beagle version="2.1.0">
<Evolver>
<BootStrapSet>
<IfThenElseOp parameter="ms.restart.file" value="">
<PositiveOpSet>
<GA-InitBitStrOp/>
<MaxFctEvalOp/>
<StatsCalcFitnessSimpleOp/>
</PositiveOpSet>
<NegativeOpSet>
<MilestoneReadOp/>
</NegativeOpSet>
</IfThenElseOp>
<TermMaxGenOp/>
<MilestoneWriteOp/>
</BootStrapSet>
<MainLoopSet>
<SteadyStateOp>
<MaxFctEvalOp>
<GA-CrossoverOnePointBitStrOp>
<SelectTournamentOp/>
<SelectTournamentOp/>
</GA-CrossoverOnePointBitStrOp>
</MaxFctEvalOp>
<MaxFctEvalOp>
<GA-MutationFlipBitStrOp>
<SelectTournamentOp/>
</GA-MutationFlipBitStrOp>
</MaxFctEvalOp>
<SelectTournamentOp/>
</SteadyStateOp>
<MigrationRandomRingOp/>
<StatsCalcFitnessSimpleOp/>
<TermMaxGenOp/>
<MilestoneWriteOp/>
</MainLoopSet>
</Evolver>
</Beagle>
The important thing to understand is that the steady-state operator (SteadyStateOp) is a replacement strategy and that the XML tree under it (between the <SteadyStateOp> and </SteadyStateOp> tags)) is its breeding tree. The three sub-trees under it are called randomly following a uniform probability density function parametrized by their respective breeding probability. For the first breeding sub-tree to the steady-state replacement strategy, the breeding probability is given by parameter ga.cx1p.indpb, while for the second sub-tree the breeding probability is given by parameter ga.mutflip.indpb, and the last sub-tree breeding probability is given by parameter ec.repro.prob. The steady-state replacement strategy generates n individuals with its breeder tree at each generation, where n is the size of the population. Each newly generated individual replaces a randomly chosen individual existing in the actual population in a steady-state fashion. Once the configuration file set-up correctly, an evolution using the given EA structure can be launched by given the good configuration file to use on the command-line. See previous section Modifying Parameters on the Command-Line for more details.
Defining New Operators
An operator is a specialized agent that apply an operation to an EC system. It is generally a genetic or utility operations such applying the crossover operation on a deme or calculating the fitness statistics for the actual generation. The operators are generally applied on one deme at the time for each generation, or sometime once a generation on all the population.
The definition of a new operator is not that complicated, usually the developer only needs to subclass the Operator class and over-define the method operate. The method received as argument a Context object. All the important contextual data are in the context object: smart pointers to the actual population, deme and system, the actual generation, etc. Furthermore, some EA use an extended context that haves some more specific informations in it. Several general pre-defined operators are already defined for most common operations such crossover, mutation, and selection. For these operators, the operate is usually already defined, and another operator-specific method need to be coded. This operator-specific method is usually the piece of coded very specific to the operation and representation used. Take a look into the code of existing operator to figure out the specificities of each case.
An usual operator also holds some evolution parameters, probabilities, and such. These parameters must be registered in the register of the evolutions system. This is done by redefining the initialize method by calling the appropriation registration method of the class Register. The method initialize is called once an evolution, before any the operator is applied to any population.
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 a configuration file. The rule is that the initialize method must be used only to add elements to the evolution system. If the user defines a new operator derived from an existing one, he must also call the initialize method from the super-class operator, as illustrated here.
class DerivedClassOp: public SuperClassOp {
virtual void initialize(System& ioSystem) {
SuperClassOp::initialize(ioSystem);
// DerivedClassOp initialization code follow ...
}
};
This is necessary as the super-class operator might do some specific operation such as registering its parameter.
The postInit operator method is the a companion method of initialize. The postInit method is called once for each operator, just after the whole system is initialized and the parameters are set. This method is best to do some parameters value checking and to setup operators internal structures. As with method initialize, if the postInit method is over-defined in a given operator, the parent's postInit must be called in the implementation before executing the actual operator post-initialization code.
There is a important hierarchy of standard defined operators in Open BEAGLE. The user is advised to interface his operators classes to already defined operator, using inheritance. This is in the spirit of OO programming and code reusing.
GA User Manual
NOTE: More explanations are necessary here on the integer-valued vector, real-valued vector, non-isotropic SA-ES and CMA-ES. Only the GA bit string representation is properly explained.
The Genetic Algorithm (GA) framework has been re-engineered in version 2.1.0 to extend its support over the basic binary representation to real-valued GA and simple Evolution Strategy (ES) representations. In fact, ES is not considered as a GA representation, but rather as a completely different EC flavor. But in Open BEAGLE, it is implemented as another EC linear representation in the existing GA framework. The accommodate the purists, we should in fact consider the GA framework a generic vector-based EC framework. The three standard representations of the GA framework share the namespace GA and a similar organization. Each representation has a genotype class that implement the linear structure which are derived from a std::vector. There is several crossover operators generic (1-point, 2-points, uniform) for vector-based representation implemented as class template, where the templated parameter must respect the STL sequence conceptual interface (the std::vector template respects this interface). A representation-specific type for each generic crossover operator is defined for each standard GA representation. There is also a representation-specific mutation operator defined for each standard representation, along with a per representation evolver. Every representation-specific evolver set the bootstrap and main-loop operators set with the default structures as presented in section Standard Open BEAGLE Operators Library.
To implement an application using a GA representation, we should follow the steps explained in section Building a System for an Evolution by taking attention to specify the genotype used and the appropriate evolver. The following code snippet is extracted for the onemax example and illustrates this for a bit-string GA representation.
// 1. Build the system. System::Handle lSystem = new System; // 2. Build evaluation operator. OneMaxEvalOp::Handle lEvalOp = new OneMaxEvalOp; // 3. Instanciate the evolver. const unsigned int lNumberOfBitsPerGenotype = 50; IntegerVector lEncoding(1, lNumberOfBitsPerGenotype); GA::EvolverBitString::Handle lEvolver = new GA::EvolverBitString(lEvalOp, lEncoding); // 4. Initialize the vivarium for bit string GA population. GA::BitString::Alloc::Handle lBSAlloc = new GA::BitString::Alloc; Vivarium::Handle lVivarium = new Vivarium(lBSAlloc); // 5. Initialize the evolver and evolve the vivarium. lEvolver->initialize(lSystem, argc, argv); lEvolver->evolve(lVivarium);
Each of three GA standard evolvers have a constructor that take as argument an integer vector. The size of this vector states the number of genotypes in each individual, while the integer value of it specify the number of elements of each linear genotype, that is the number of bits for binary GA, the number of floating-point values for real-valued GA, or the number of (x,sigma) pairs for ES vectors. So in the previous example, the integer vector passed to the evolver at step 3 configures the evolve to initialize the individuals with one bit-string of 50 random bits. The vivarium is initialized at step 4 with a bit string allocator to generate the population. For the two other representation, we would have used a GA::FloatVector::Alloc for real-valued GA or a GA::ESVector::Alloc for ES.
In the bit-string GA representation, the bits can be used as is (for example in the OneMax problem), or transformed into floating-point value in a given interval and a given precision, depending the number of bits used (for example in the function maximization problem). When the bits are converted to floating-point values, these are used as parameters to solve the problem, the fitness value is deduced from these parameters. The representation of a binary GA genotype is implemented in the class GA::BitString, which both inherits from the class Genotype and std::vector<bool>.
namespace GA {
class BitString : public Beagle::Genotype, public std::vector<bool> {
public:
struct DecodingKey {
double mLowerBound;
double mUpperBound;
unsigned int mEncoding;
};
void decode(const std::vector<DecodingKey>& inKeys,
std::vector<double>& outVector) const;
void decodeGray(const std::vector<DecodingKey>& inKeys,
std::vector<double>& outVector) const;
...
};
}
The method decode is used to decode binary-encoded bit strings, to translate it into a real-valued vector using a decoding key. The method decodeGray is similar to the decode method, except that it supposes Gray-encoded bit strings. If the application needs to work directly on the bits, the interface of the class std::vector<bool> can be used.
GP User Manual
This section goes more deeply into the GP specific aspect of Open BEAGLE. This concern mainly the declaration of primitives by the user and the use of strongly typed GP.
Getting the Most of the Primitives
NOTE: The Primitive interface has slightly evolved since the writting of this section. New methods and changes to modified methods should be given here.
The declaration of the primitives are a central aspect of the implementation of GP in Open BEAGLE. An abstract class Primitive is declared with a standardized interface presented in the following listing.
namespace GP {
class Primitive : public Object {
public:
typedef AllocatorT<Primitive,Object::Alloc> Alloc;
typedef PointerT<Primitive,Object::Handle> Handle;
typedef ContainerT<Primitive,Object::Bag> Bag;
explicit Primitive(unsigned int inNumberArguments=0,std::string inName="");
virtual ~Primitive();
virtual void execute(GP::Datum& outDatum,GP::Context& ioContext) =0;
virtual std::string getArgType(unsigned int inN) const;
virtual std::string getAttribute() const;
unsigned int getChildrenNodeIndex(unsigned int,GP::Context&) const;
std::string getName() const;
unsigned int getNumberArguments() const;
virtual std::string getReturnType() const;
virtual void getValue(Object& outValue);
virtual Handle giveReference(GP::Context& ioContext);
virtual bool isEqual(const Object& inRightObj) const;
virtual void initialize(GP::System& ioSystem);
virtual void read(InputStream& ioIS);
virtual void setAttribute(std::string inAttribute);
virtual void setValue(const Object& inValue);
virtual bool validate(GP::Context& ioContext) const;
virtual void write(OutputStream& ioOS) const;
protected:
void setName(std::string inName);
void setNumberArguments(unsigned int inNumberArguments);
void getArgument(unsigned int inN,GP::Datum& outResult,GP::Context& ioContext);
void getArguments(GP::Datum outResults[],size_t inSizeTDatum,
GP::Context& ioContext);
void get1stArgument(GP::Datum& outResult,GP::Context& ioContext);
void get2ndArgument(GP::Datum& outResult,GP::Context& ioContext);
void get3rdArgument(GP::Datum& outResult,GP::Context& ioContext);
private:
std::string mName; //!< Name of the primitive.
unsigned int mNumberArguments; //!< Number of arguments of the primitive.
};
}
As explained in previous sections, the primitive represent the operation to be done by nodes of the GP trees. This operation is implemented the method execute, in classes derived from GP::Primitive. In this method, the user can get the value of the child subtrees to the node and apply the characteristic operation. The result must be returned in the datum given as argument. A primitive has a fixed number of arguments, the child subtrees, and a unique name. This attribute are generally given by the constructor of the derived subclass to the constructor of GP::Primitive, as in the following declaration.
class Add : public Beagle::GP::Primitive {
public:
Add() : Beagle::GP::Primitive(2,"+") { }
};
The number of arguments and the name of the primitive can also be stated by a call to the methods setNumberArguments and setName.
The primitives are put into sets of usable primitives before creating any GP trees. In the process of trees creation, for every node, an associated primitive is chosen. Usually, the association is made by a call to the method giveReference, affecting the node's primitive smart pointer to the chosen primitives. But, for some special case, such when using ephemeral constants, the operation done must be different. In this case the method giveReference can be over-defined to desired behavior. By default, the method return an handle to the primitive instance, which is then put into the primitive smart pointer of the node. By over-defining the method, the user can return any other kind of primitive instance that will be put into the node's primitive smart pointer.
NOTE: Give explanations here on primitives with variable number of arguments and primitive with variable selection weight in primitive set.
NOTE: GP trees are no more written as Lisp-like string but rather as complete XML trees. The following paragraph should be completely rewritten.
The way the GP trees are inserted and extracted from a Open BEAGLE XML stream is standard. For each trees, the composing nodes are written into a Lisp-like string. By default, for each node, only the name of the primitive associated is written in the Lisp-like string. If appropriate when the primitive is written, some information can be added to the name of the primitive. This is called the attribute of the primitive. The attribute of the primitive is given by a call to the method getAttribute and the attribute can be changed by a call to the method setAttribute. When an attribute different from the null string is used, the value is put between braces just after the name of the primitive, in the Lisp-like string.
A primitive can have a value that is modified at the runtime by a call to the method setValue. A similar method exist in class GP::Primitive, taking a second argument that is the name of the primitive to modify the value. Actually, the method of GP::EvaluationOp only call the equivalent setValue of the variable primitive, with the GP::Datum given as argument. For the abstract class GP::Primitive, the method setValue does nothing. This method can be over-defined in the more specific subclasses to do what is needed to set the value of the primitive.
Three of the remaining primitive methods getArgType, getReturnType, and validate are related to the usage of strongly typed GP. This is the topic of the next section.
Strongly Typed GP
NOTE: Typing verification in STGP has been changed to compare references to type_info object instead of strings. The whole subsection on STGP should be updated accordingly.
Strongly typed GP (STGP) is a standard Open BEAGLE GP feature. In every standard operators that modify the structure of the GP individuals, a dual operator supporting constraints is defined. These operator apply their operation while checking whether the typing of the nodes is respected when a GP genome is altered. Following table presents the list standard constrained GP operators actually implemented in the framework.
| GP Operator | Constrained Dual Operator |
|---|---|
| GP::InitFullOp | GP::InitFullConstrainedOp |
| GP::InitGrowOp | GP::InitGrowConstrainedOp |
| GP::InitHalfOp | GP::InitHalfConstrainedOp |
| GP::CrossoverOp | GP::CrossoverConstrainedOp |
| GP::MutationSwapOp | GP::MutationSwapConstrainedOp |
| GP::MutationShrinkOp | GP::MutationShrinkConstrainedOp |
| GP::MutationStandardOp | GP::MutationStandardConstrainedOp |
| GP::MutationSwapSubtreeOp | GP::MutationSwapSubtreeConstrainedOp |
When an user want to take advantage of STGP, he first needs to use an evolver made of the constrained operators (instead of the simple unconstrained ones). The example spambase included in the distribution contains configuration files where evolver composed of operators that support constraints. Section Building a Custom Evolver also explain how to change the set-up of evolvers.
The second point needed to do STGP is to set the typing in the primitives used. The typing is made by associating a char string to a type, generally the RTTI name of the datum type. To implement the typing of the individuals, two methods must be over-defined in the concrete primitives classes, getArgType and getReturnType. The method getReturnType gives the type of the datum that is returned by the primitives. The method getArgType give the string type of the ith argument of the nodes associated to the primitive.
To illustrate this, suppose an application where two different datum types are used, Double and Bool. STGP is usually implemented by using the RTTI naming of the types used. Supposing a if-then-else primitive implemented in the class IfThenElse. The primitive received a Boolean as first argument and return a floating-point number, that is the second argument of the primitive if the Boolean is true and the third if not.
using namespace Beagle;
class IfThenElse : public GP::Primitive {
public:
IfThenElse() : GP::Primitive(3,"if-then-else") { }
virtual void execute(GP::Datum& outResult,
GP::Context& ioContext) {
Bool lTest;
get1stArguments(lTest,ioContext);
if(lTest == true) get2ndtArgument(outResult,ioContext);
else get3rdArgument(outResult,ioContext);
}
virtual std::string getArgType(unsigned int inN) const {
if(inN == 0) return typeid(Bool).name();
return typeid(Double).name();
}
virtual std::string getReturnType() const {
return typeid(Double).name();
}
};
The type of the root of a given tree is stated in the primitive set associated to the given GP tree. The constructor of the class GP::PrimitiveSet is defined in such way that you only need to pass the name of the type returned from the root of the tree when constructing the set.
This implementation of STGP is usually sophisticated enough to allow quite constrained tree structures. But, the use of STGP does not allow all kind of structural constraints, and the user may want to apply to the GP individuals more elaborated constraints. The method validate of GP::Primitive is called to do the typing validation. As defined in GP::Primitive, this method implements STGP by checking the types returned by the methods getArgType and getReturnType. The user can over-define the method to do his custom structural checking. The method returns true if the structure imposed is respected, and false if not.
NOTE: More explanations should be given on general constraints that can be applied on GP trees. The use of constrained operator for dynamic ADFs should also be detailed.
Multiobjective EA User Manual
Multiobjective Evolutionary Algorithms (MOEA) are now supported in Open BEAGLE. To make use of it in your application, you must do the three following things:
- Return a multiobjective fitness measure (class FitnessMultiObj or derived) in your evaluation operator;
- Set the population allocators for the used multiobjective fitness measure allocators in the main routine;
- Set-up a configuration file with the appropriate evolver structure, that is a multiobjective selection operator and a statistics calculation operator compatible with the fitness measure used.
The basic MOEA fitness measure is implemented in class FitnessMultiObj, which maximize all the objectives. A derived fitness measure is also defined in class FitnessMultiObjMin and consists to minimize the objectives. You should either use one of the two preceding standard MOEA fitness measure, or use a custom one derived from these as fitness measure. The class FitnessMultiObj is derived from a std::vector<float> and thus the user should use the STL vector interface to set the different objectives value.
Once the type of fitness measure used is stated in the evaluation operator, the population allocators must be set up to use it. This can be done by following the explanations given in Section Building a System for an Evolution, at the item population. This is necessary to clone/copy fitness value between individuals and to read a milestone from uninitialized population.
Finally, the evolutionary algorithm must be set-up for the use of MOEA. This first imply that a multiobjective selection operation must be used. There is actually two of these in Open BEAGLE, NSGA-II implemented as replacement strategy operator NSGA2Op, and NPGA 2 implemented as a more classical selection operator NPGA2Op. The following presents how the NSGA-II configuration file of the multiobjective bit string GA example knapsack.
<?xml version="1.0" encoding="ISO-8859-1"?>
<Beagle version="2.1.0">
<Evolver>
<BootStrapSet>
<IfThenElseOp parameter="ms.restart.file" value="">
<PositiveOpSet>
<GA-InitBitStrOp/>
<KnapsackEvalOp/>
<StatsCalcFitnessMultiObjOp/>
</PositiveOpSet>
<NegativeOpSet>
<MilestoneReadOp/>
</NegativeOpSet>
</IfThenElseOp>
<TermMaxGenOp/>
<MilestoneWriteOp/>
</BootStrapSet>
<MainLoopSet>
<NSGA2Op>
<KnapsackEvalOp>
<GA-CrossoverOnePointBitStrOp>
<SelectRandomOp/>
<SelectRandomOp/>
</GA-CrossoverOnePointBitStrOp>
</KnapsackEvalOp>
<KnapsackEvalOp>
<GA-MutationFlipBitStrOp>
<SelectRandomOp/>
</GA-MutationFlipBitStrOp>
</KnapsackEvalOp>
</NSGA2Op>
<MigrationRandomRingOp/>
<StatsCalcFitnessMultiObjOp/>
<TermMaxGenOp/>
<ParetoFrontCalculateOp/>
<MilestoneWriteOp/>
</MainLoopSet>
</Evolver>
</Beagle>
The NSGA-II algorithm proceed first by generating a population of n children from a population of n parents. This is actually done here by calling the breeder tree of the NSGA2Op replacement strategy n times. The breeder tree generates the children one at the time by either applying one point crossover or bit mutation on randomly chosen individuals from the parent individuals, and then evaluating fitness of the newly generated individuals. When the n children are generated, the parents and children populations are merged and a non-dominated sort is done to keep the n best, which constitutes the new population. Note in the previous configuration file, the use of operator StatsCalcFitnessMultiObjOp, which is the appropriate statistics calculation operator for fitness measures FitnessMultiObj and FitnessMultiObjMin.
The NPGA 2 MOEA selection operator can be more simply used as a replacement of a usual mono-objective selection operators. The following configuration file shows the use of NPGA 2 in the knapsack MOEA example.
<?xml version="1.0" encoding="ISO-8859-1"?>
<Beagle version="2.0.0">
<Evolver>
<BootStrapSet>
<IfThenElseOp parameter="ms.restart.file" value="">
<PositiveOpSet>
<GA-InitBitStrOp/>
<KnapsackEvalOp/>
<StatsCalcFitnessMultiObjOp/>
</PositiveOpSet>
<NegativeOpSet>
<MilestoneReadOp/>
</NegativeOpSet>
</IfThenElseOp>
<TermMaxGenOp/>
<MilestoneWriteOp/>
</BootStrapSet>
<MainLoopSet>
<NPGA2Op/>
<GA-CrossoverOnePointBitStrOp/>
<GA-MutationFlipBitStrOp/>
<KnapsackEvalOp/>
<MigrationRandomRingOp/>
<StatsCalcFitnessMultiObjOp/>
<TermMaxGenOp/>
<ParetoFrontCalculateOp/>
<MilestoneWriteOp/>
</MainLoopSet>
</Evolver>
</Beagle>
This time the formulation of the evolver structure is more straight-forward, without the use of a breeder tree. Note that once again the multiobjective fitness measure statistics calculation operator StatsCalcFitnessMultiObjOp is used.
Attentive reader may note the use of an operator named ParetoFrontCalculateOp in the evolver's main-loop operator set. This operator is used to compute the Pareto front of the population into the hall-of-fame, just before exiting. This operator must be put in the main-loop operator set after the termination operator (in this case operator TermMaxGenOp), to intercept the moment that the evolution must stop, but before the milestone writing operator to get the Pareto front written into the milestone. It is not compulsory to use this operator in your evolver, although it may be very useful for result analysis.
NOTE: A section on co-evolution would be appreciated here.
NOTE: A detailed section on Open BEAGLE file format is necessary here.
Next chapter: Conclusion.
