LibGEP - A library dedicated to Gene Expression Programming

0.4

Gene Expression Programming GEP is a new evolutionary algorithm that evolves computer programs. LibGEP is a free implementation of this heuristic based on the following material:

[1] Candida Ferreira. Gene expression programming: A new adaptive algorithm for solving problems. Complex Systems, 13(2):87-129, 2001.

[2] Candida Ferreira. Gene Expression Programming: Mathematical Modeling by an Artificial Intelligence. 2nd Edition, Springer-Verlag, Germany, 2006.

For more info, please consult the Project Homepage

Design

LibGEP is fully templated to permit the maximum flexibility and efficiency. The design of the library is based on the Chromosome object. A Chromosome objet is used to store the tree structure and is translated into it when calculateValue() command is invoked. An Individual object encloses a Chromosome. The main methods used by an Individual are evaluate(param), calculateFitness() and reset(). See respective descriptions in the header file. A Population object stores a set of Individuals and manages them. The management includes invoking selection, recombination and mutation operators as well as updating the elite and copying it to newly created population. A GEPAlg object is managing the Population by executing the loops of generations and loops of independent runs. The GEPAlg object stores training and testing sets (if any), records the best individuals, statistics and population contents.

See also:: GEP::Chromosome GEP::Individual GEP::Population GEP::GEPAlg

Customization

User customization of GEP functionality can be performed on four levels:

Function level - a basic customization, involves writing a CustomOneArg or CustomTwoArg functions, that inherit from oneArg or twoArg, respectively and implement operator() and name() functions.
Individual level - a basic customization, involves writing a separate CustomIndividual class that inherits from Individual and implements evaluate(), calculateFitness() and reset() methods. The design of an Individual class is problem-dependent (see examples for implementation of minimum square approximation method).
Population level - more advanced one, involves writing a separate CustomPopulation class that inherits from Population and implements population generation, modification and management methods. The design should be reimplemented only if you want to use a specific population model (see GEP::CellPopulation and GEP::MergePopulation).
GEPAlg level - more advanced one, involves writing a separate CustomGEPAlg class that inherits from GEPAlg and implements global population management methods, learning set modification methods and custom statistics. It is done mostly in four functions: runStart() - a preamble of an independent run, runEnd() a postamble of an independent run, genStart() a preamble of a generation and genEnd() a postamble of a generation.

Configuration

The configuration of a whole setup of GEP algorithm is handled mostly via config file, that should contain three sections, for Chromosome, Population and GEPAlg. For a customized design one should implement their own readConfig() functions that invoke the readConfig of the mother class and read their parameters own parameters afterwards. Consult readConfig() function of GEP::MergePopulation.

Configuration file contains two types of lines - active (parsed during readConfig() invocation) and commented (starting with "#" symbol). The separators of active line fields are spacebar or tabulation. The first element of an active line is a configuration argument nam, the rest are its values. The order of active lines is unimportant. The following configuration arguments are considered:

Chromosome section:
This the only case of explicit invocation of readConfig() function (see examples). The following arguments are considered:

HeadLength - followed by one argument, defines the head length
NumGenes - followed by one argument, defines the number of genes
Terminals - followed by multiple arguments, the syntax as follows:
--- argument 1 defines the number of terminal inputs.
--- arguments 2 to n define the initial contents of the terminal input, they can be proided separately or using (:) notation, where (a:b) means repeating the value 'a' 'b' times. RandomConstants - followed by one argument, defines the number of random constant variables
LinkingFunctions - followed by multiple arguments, describing symbols of gene linking functions
OneArgFunctions - followed by multiple arguments, describing symbols of one argument functions
TwoArgFunctions - followed by multiple arguments, describing symbols of two argument functions

Population section:
This readConfig() invocation is handled by the constructor (see GEP::Population). The following arguments are considered: PopSize - followed by one argument, defines the population size
EliteSize - followed by one argument, defines the elite size
InversionLength - followed by one argument, defines the inversion length
TransposonLength - followed by one argument, defines the transposon length
MutationProbability - followed by one argument, defines the mutation probability
LinkMutationProbability - followed by one argument, defines the link mutation probability
InversionProbability - followed by one argument, defines the inversion probability
TranspositionISProbability - followed by one argument, defines the transposition probability
TranspositionRISProbability - followed by one argument, defines the root transposition probability
TranspositionGeneProbability - followed by one argument, defines the gene transposition probability
OnePointCrossoverProbability - followed by one argument, defines the one point crossover probability
TwoPointCrossoverProbability - followed by one argument, defines the two point crossover probability
GenePointCrossoverProbability - followed by one argument, defines the gene crossover probability
RcEvolution - followed by one argument, defines the Random Constants evolution model (currently only one supported)

-- Optional -- GEP::MergePopulation
MergeSize - followed by one argument, defines the number of individuals modified each generation (for MergeSize 2 this model becomes a SteadyState population model)
-- Optional -- GEP::CellPopulation
DimensionX - followed by one argument, defines the width of the cellular grid
DimensionY - followed by one argument, defines the height of the cellular grid
Neighborhood - followed by mutliple arguments, defines the neighbohood. Elements have the syntax (a,b), where a is the distance from central cell in X dimension, and b is the distance from central cell in Y dimension. See DataStructures.h for details.

GEPAlg section:
This readConfig() invocation is handled by the constructor (see GEP::GEPAlg). The following arguments are considered: Generations - followed by one argument, defines the number of generations
Runs - followed by one argument, defines the number of independent runs
EliteMode - followed by one argument, defines the elite model (0 for simple, 1 for smart)
VerboseOutput - followed by one argument, defines the generation interval for verbose output to be displayed
VerboseGeneration - followed by one argument, defines the generation interval for population statistics to be displayed
VerboseRun - followed by one argument, defines if the run statistics to be displayed
VerboseTotal - followed by one argument, defines if the sumary statistics to be displayed
BreakOnOptimum - followed by multiple arguments, defines if there is a known optimum (multiple optima for MO GEP)
LogInterval - followed by one arguments, defines the generation interval for recording statistics
RecordInterval - followed by one argument, defines the generation interval for the population data
InitializationPath - followed by one argument, defines the path from which an initial population is loaded
HallOfFamePath - followed by one argument, defines the path to which the best individuals will be recorded

Example

Here is a small example (a part of the gep_example.cpp file in examples directory):

#include <boost/assign/std/vector.hpp>
using namespace boost::assign;
#include <libgep>
#include "TrainingSetExample.h"
#include "IndividualExample.h" 

typedef GEP::MinSqrFunctionIndividual IndividualType;
typedef IndividualType::data_type     DataType;
typedef DataType::InType              InputType;


int main(int argc, char * argv[]){
    //Default file
    std::string cfg_file = "GEP.cfg";
    
    //Explicit Chromosome configuration\n
    GEP::Chromosome<InputType>::readConfig(cfg_file);
    
    //Training set generation
    std::vector<InputType> v;
    v += 2.81, 6, 7.043, 8, 10, 11.38, 12, 14, 15, 20;
    std::vector<DataType> trainingSet;
    constructTrainingSet<BenchmarkPolynome<InputType>, DataType>(v, trainingSet);

    //Apply your custom IndividualType/Population/GEPAlg here
    GEP::GEPAlg<GEP::Population<IndividualType,GEP::IndividualLT> > gep_alg(cfg_file,trainingSet);
    
    //The algorithm
    gep_alg.runGEPAlg();
    
    //Graceful end to the function pointers in Chromosome
    GEP::Chromosome<InputType>::clearFunctionPointers();
    
    return 0;
}

License

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.

Marek Ostaszewski <Marek.Ostaszewski@uni.lu>
Sebastien Varrette <Sebastien.Varrette@uni.lu>
University of Luxembourg
6 rue Richard Coudenhove-Kalergi
L-1359 Luxembourg, LUXEMBOURG