[wiki.beagle] push by cgagne@gmail.com - Split the specific sections on GP, BitStr, EMO and Coev in their respe... on 2012-08-01 11:36 GMT

5 views
Skip to first unread message

bea...@googlecode.com

unread,
Aug 1, 2012, 7:37:08 AM8/1/12
to openbeagle...@googlegroups.com
Revision: 7ae7b582e684
Author: Christian Gagne <christi...@gel.ulaval.ca>
Date: Wed Aug 1 04:36:53 2012
Log: Split the specific sections on GP, BitStr, EMO and Coev in their
respective manuals.
http://code.google.com/p/beagle/source/detail?r=7ae7b582e684&repo=wiki

Modified:
/Architecture.wiki
/BitStrManual.wiki
/CoevManual.wiki
/EMOManual.wiki
/GPManual.wiki
/STGPManual.wiki
/UserGuide.wiki

=======================================
--- /Architecture.wiki Wed Aug 1 04:25:18 2012
+++ /Architecture.wiki Wed Aug 1 04:36:53 2012
@@ -457,100 +457,3 @@
}}}

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`.
-
-
-=== 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
[http://www.iitk.ac.in/kangal/Deb_NSGA-II.pdf NSGA-II], implemented as a
replacement strategy of a breeder model, and the
[http://dl.acm.org/citation.cfm?id=739267 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
[UserGuide#Building_a_System_for_an_Evolution Building a System for an
Evolution] of the User Guide (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.
-
-=== GP Genotypes ===
-
-For the GP specific individual implementation, the abstract interface
`Individual` is sub-classed in the concrete class `GP::Individual`. An
standard GP genotype, `GP::Tree`, is also defined. This class is declared
as genotype and a vector of nodes. The nodes are declared by the struct
`GP::Node`, that comprises a smart pointer to a GP primitive and the size
of the sub-tree.
-{{{
-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. Section
[UserGuide#Getting_the_Most_of_the_Primitives Getting the Most of the
Primitives] of the User Guide is a detailled 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 figure below.
-
-[http://wiki.beagle.googlecode.com/hg/images/primit-set.png]
-
-*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.
Following table presents and describe of all these Primitives.
-
-|| *Primitive* || *Datum* || *Description* ||
-|| `TokenT` || Any || Terminal that contain a value, the token. ||
-|| `AdfT` || Any || Call to an associated ADF. ||
-|| `EphemeralT` || Any || Generate and represent randomly generated
constants. ||
-|| `EphemeralDouble` || `Double` || Generate and represent randomly
generated floating-point constants in _[-1,1]_. ||
-|| `AddT` || Any (must have `operator+` defined) || Add two floating-point
numbers (_x,,1,, + x,,2,,_). ||
-|| `Add` || `Double` || Synonym of `AddT<Double>`. ||
-|| `SubtractT` || Any (must have `operator-` defined) || Subtract two
floating-point numbers (_x,,1,, - x,,2,,_). ||
-|| `Subtract` || `Double` || Synonym of `SubtractT<Double>`. ||
-|| `MultiplyT` || Any (must have `operator*` defined) || Multiply two
floating-point numbers (_x,,1,, * x,,2,,_). ||
-|| `Multiply` || `Double` || Synonym of `MultiplyT<Double>`. ||
-|| `DivideT` || Any (must have `operator/` defined be built from a
`float`) || Protected division of two floating-point numbers, return
(_x,,1,, / x,,2,,_) when _|x,,2,,| ≥ 0.001_, return _1.0_ otherwise. ||
-|| `Divide` || `Double` || Synonym of `DivideT<Double>`. ||
-|| `Sin` || `Double` || Sinus of a floating-point number in radians
(_sin(x,,1,,)_). ||
-|| `Cos` || `Double` || Cosine of a floating-point number in radians
(_cos(x,,1,,)_). ||
-|| `Log` || `Double` || Natural logarithm of a floating-point number
(_ln(x,,1,,)_). ||
-|| `Exp` || `Double` || Exponentiation of a floating-point number
(_exp(x,,1,,)_). ||
-|| `And` || `Bool` || And logical operator. ||
-|| `Or` || `Bool` || Or logical operator. ||
-|| `Not` || `Bool` || Not logical operator. ||
-|| `Nand` || `Bool` || Nand logical operator. ||
-|| `Nor` || `Bool` || Nor logical operator. ||
-|| `Xor` || `Bool` || Xor logical operator. ||
=======================================
--- /BitStrManual.wiki Wed Aug 1 04:08:51 2012
+++ /BitStrManual.wiki Wed Aug 1 04:36:53 2012
@@ -1,6 +1,47 @@
#summary Bit String Representation Manual
-#labels TODO
+#labels RequireUpdate

= Bit String Representation Manual =

-* TODO *
+* TODO: This page must be revised completely. *
+
+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. 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.
+
+To implement an application using a GA representation, we should follow
the steps explained in Section
[UserGuide#Building_a_System_for_an_Evolution 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. 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.
=======================================
--- /CoevManual.wiki Wed Aug 1 04:21:39 2012
+++ /CoevManual.wiki Wed Aug 1 04:36:53 2012
@@ -3,4 +3,10 @@

= Co-evolution Manual =

-* TODO *
+*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
[UserGuide#Building_a_System_for_an_Evolution Building a System for an
Evolution] of the User Guide (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.
=======================================
--- /EMOManual.wiki Wed Aug 1 04:21:25 2012
+++ /EMOManual.wiki Wed Aug 1 04:36:53 2012
@@ -3,4 +3,98 @@

= Evolutionary Multiobjective Optimization Manual =

-* TODO *
+* TODO: An important update is require here *
+
+Since version 2.1.0, Open BEAGLE includes support for Evolutionary
Multiobjective Optimization (EMO). 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 EMO support in Open BEAGLE is the multiobjective
selection operator. There is currently two of these implemented, that is
[http://www.iitk.ac.in/kangal/Deb_NSGA-II.pdf NSGA-II], implemented as a
replacement strategy of a breeder model, and the
[http://dl.acm.org/citation.cfm?id=739267 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.
+
+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 EMO 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 EMO
fitness measure, or use a custom one derived from these as fitness measure.
The class `FitnessMultiObj` is derived from a `std::vector<double>` 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
[UserGuide#Building_a_System_for_an_Evolution 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 EMO.
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 EMO 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` EMO 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.
=======================================
--- /GPManual.wiki Wed Aug 1 04:12:09 2012
+++ /GPManual.wiki Wed Aug 1 04:36:53 2012
@@ -3,4 +3,152 @@

= Genetic Programming Manual =

-* TODO *
+== Getting the Most of the Primitives ==
+
+* TODO: 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 the following standardized interface.
+{{{
+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.
+
+* TODO: Give explanations here on primitives with variable number of
arguments and primitive with variable selection weight in primitive set. *
+
+* TODO: 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.
+
+== GP Genotypes ==
+
+For the GP specific individual implementation, the abstract interface
`Individual` is sub-classed in the concrete class `GP::Individual`. An
standard GP genotype, `GP::Tree`, is also defined. This class is declared
as genotype and a vector of nodes. The nodes are declared by the struct
`GP::Node`, that comprises a smart pointer to a GP primitive and the size
of the sub-tree.
+{{{
+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.
+
+*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 figure below.
+
+[http://wiki.beagle.googlecode.com/hg/images/primit-set.png]
+
+*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.
Following table presents and describe of all these Primitives.
+
+|| *Primitive* || *Datum* || *Description* ||
+|| `TokenT` || Any || Terminal that contain a value, the token. ||
+|| `AdfT` || Any || Call to an associated ADF. ||
+|| `EphemeralT` || Any || Generate and represent randomly generated
constants. ||
+|| `EphemeralDouble` || `Double` || Generate and represent randomly
generated floating-point constants in _[-1,1]_. ||
+|| `AddT` || Any (must have `operator+` defined) || Add two floating-point
numbers (_x,,1,, + x,,2,,_). ||
+|| `Add` || `Double` || Synonym of `AddT<Double>`. ||
+|| `SubtractT` || Any (must have `operator-` defined) || Subtract two
floating-point numbers (_x,,1,, - x,,2,,_). ||
+|| `Subtract` || `Double` || Synonym of `SubtractT<Double>`. ||
+|| `MultiplyT` || Any (must have `operator*` defined) || Multiply two
floating-point numbers (_x,,1,, * x,,2,,_). ||
+|| `Multiply` || `Double` || Synonym of `MultiplyT<Double>`. ||
+|| `DivideT` || Any (must have `operator/` defined be built from a
`float`) || Protected division of two floating-point numbers, return
(_x,,1,, / x,,2,,_) when _|x,,2,,| ≥ 0.001_, return _1.0_ otherwise. ||
+|| `Divide` || `Double` || Synonym of `DivideT<Double>`. ||
+|| `Sin` || `Double` || Sinus of a floating-point number in radians
(_sin(x,,1,,)_). ||
+|| `Cos` || `Double` || Cosine of a floating-point number in radians
(_cos(x,,1,,)_). ||
+|| `Log` || `Double` || Natural logarithm of a floating-point number
(_ln(x,,1,,)_). ||
+|| `Exp` || `Double` || Exponentiation of a floating-point number
(_exp(x,,1,,)_). ||
+|| `And` || `Bool` || And logical operator. ||
+|| `Or` || `Bool` || Or logical operator. ||
+|| `Not` || `Bool` || Not logical operator. ||
+|| `Nand` || `Bool` || Nand logical operator. ||
+|| `Nor` || `Bool` || Nor logical operator. ||
+|| `Xor` || `Bool` || Xor logical operator. ||
=======================================
--- /STGPManual.wiki Wed Aug 1 04:20:49 2012
+++ /STGPManual.wiki Wed Aug 1 04:36:53 2012
@@ -1,6 +1,50 @@
#summary Strongly Typed Genetic Programming Manual
-#labels TODO
+#labels RequireUpdate

= Strongly Typed Genetic Programming Manual =

-* TODO *
+* TODO: 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 [UserGuide#Building_a_Custom_Evolver 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.
+
+* TODO: 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. *
=======================================
--- /UserGuide.wiki Wed Aug 1 04:25:18 2012
+++ /UserGuide.wiki Wed Aug 1 04:36:53 2012
@@ -1,7 +1,7 @@
#summary User Guide on Open BEAGLE
#labels RequireUpdate

-This page 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.
+This page 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 with Open BEAGLE.

<wiki:toc max_depth="3"/>

@@ -90,7 +90,7 @@

As explained in Section [Architecture#Operators_and_Evolver Operators and
Evolver] of the Architecture page, 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
[UserGuide#Customizing_the_Evolutionary_Algorithm 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 [GPTutoral GP Tutorial] and
[UserGuide#GP_User_Manual GP User Manual] section for GP and Section
[UserGuide#GA_User_Manual GA User Manual] for GA. Section
[UserGuide#Customizing_the_Evolutionary_Algorithm Customizing the
Evolutionary Algorithm] gives also good insight on configuring a custom
evolution.
+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 [GPTutoral GP Tutorial] and [GPManual GP
Manual] section for GP and [BitStrManual Bit String Representation Manual]
for bit string GA. Section
[UserGuide#Customizing_the_Evolutionary_Algorithm Customizing the
Evolutionary Algorithm] gives also good insight on configuring a custom
evolution.

= Using the Register =

@@ -326,271 +326,3 @@
The `init` operator method is the a companion method of `registerParams`.
The `initialize` method is called once for each operator, just after the
parameters are registered and the whole system is initialized. This method
is best to do some parameters value checking and to setup operators
internal structures. As with method `registerParams`, if the `init` method
is over-defined in a given operator, the parent's `init` 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 =
-
-* TODO: This section must be revised completely. *
-
-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. 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.
-
-To implement an application using a GA representation, we should follow
the steps explained in Section
[UserGuide#Building_a_System_for_an_Evolution 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. 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 ==
-
-* TODO: 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 the following standardized interface.
-{{{
-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.
-
-* TODO: Give explanations here on primitives with variable number of
arguments and primitive with variable selection weight in primitive set. *
-
-* TODO: 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 ==
-
-* TODO: 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 [UserGuide#Building_a_Custom_Evolver 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.
-
-* TODO: 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<double>` 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
[UserGuide#Building_a_System_for_an_Evolution 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.
-
-
-= Co-evolution =
-
-* TODO: A section on co-evolution need to be added here.*
Reply all
Reply to author
Forward
0 new messages