Difference between revisions of "Evoptool: Evolutionary Optimization Tool"

From AIRWiki
Jump to: navigation, search
(To create a new algorithm (draft))
(To create a new algorithm (draft))
Line 199: Line 199:
 
   </task>
 
   </task>
  
==== To create a new algorithm (draft) ====
+
==== To create a new algorithm ====
  
 
1. Implement a new algorithm
 
1. Implement a new algorithm
Line 218: Line 218:
 
   typedef enum {
 
   typedef enum {
 
     ...
 
     ...
     DEUM
+
     DEUM   // 5
 
   } Algorithms;
 
   } Algorithms;
  
Line 234: Line 234:
 
In each entry, the first field is the name of the entry in the <tt>Algorithms</tt> enum just modified in <tt>Evoptool.h</tt>, the second is the number of parameters to be parsed in the xml configuration file and the third is a string specifying their type: <tt>I</tt> for integer and <tt>D</tt> for double.
 
In each entry, the first field is the name of the entry in the <tt>Algorithms</tt> enum just modified in <tt>Evoptool.h</tt>, the second is the number of parameters to be parsed in the xml configuration file and the third is a string specifying their type: <tt>I</tt> for integer and <tt>D</tt> for double.
  
4. add a case in the switch that follows in  
+
4. add a case in the switch that follows in <tt>bool XMLParser::parseAlgorithms</tt>, for instance:
bool XMLParser::parseAlgorithms
+
  
for instance
+
  case Evoptool::DEUM:  
case Evoptool::EXTENDEDFCA:  
+
    algos[i] = new extendedFCA(intVal[0], doubleVal[0], doubleVal[1], intVal[1], intVal[2], params->rng);
  algos[i] = new extendedFCA(intVal[0], doubleVal[0], doubleVal[1], intVal[1], intVal[2], params->rng);
+
    algos[i]->initAlgorithm(params->task);
  algos[i]->initAlgorithm(params->task);
+
    break;
  break;
+
  
where the algorithm is instantiated
+
Note that your algorithm can employ the random number generator provided by the Evoptool core, <tt>params->rng</tt>.
  
5. Add an entry for your algorithm in  
+
5. Include your headers in core/src/Algorithms.h
core/src/Algorithms.h
+
  
 +
6. Document how your algorithm is instantiated in the comments appearing in evoptool-file/exec-scripts/example.xml
  
 +
  Algorithm  Id    Types    Parameters
 +
  =====================================================================================================
 +
    ...
 +
    FCA      26    "IDDII"  (Pop, PercSelection, LearningRate, MaxCompositionLenght, MaxMonomialOrder)
 +
    ...
 +
 +
7. Add an instantiation example for your algorithm in evoptool-file/exec-scripts/example.xml
  
6. Add a line in
+
  <!algo id="26" instanceName="FCA"> 
evoptool-file/exec-scripts/example.xml
+
    <int>1000</int>
as a documenation for the parameters of your algorithm.
+
    <double>0.5</double>
Choose a new Id for your algorithm
+
    <double>1</double>
Types indicates then type of the parameters (the order is important) that will must be specified
+
    <int>64</int>
in the xml file (see <algo>) and are passed to the constructor of the algorithm when the object is instantiated
+
    <int>2</int>
I = integer
+
  </algo>
D = double
+
B = bool
+
  
 
==== Run an algorithm in a C++ program ====
 
==== Run an algorithm in a C++ program ====

Revision as of 11:35, 24 October 2011

Description

Evolutionary Optimization Tool (Evoptool) is an open source optimization tool writte in C++, distributed under GNU General Public License. Evoptool implements meta-heuristics based on the Evolutionary Computation paradigm and aims to provide a common platform for the development and test of new algorithms, in order to facilitate the performance comparison activity. Evoptool offers a wide set of benchmark problems, from classical toy samples to more complex tasks, and a collection of algorithm implementations from Genetic Algorithms and Estimation of Distribution Algorithms paradigms. Evoptool is flexible, easy to extend, also with algorithms based on other approaches other from EAs.

The Evoptool Team

Formerly involved

  • Emanuele Corsano

Mailing List

http://groups.google.com/group/evoptool

Download

 svn checkout https://svn.ws.dei.polimi.it/evoptool/trunk --username usrevoptool --password evoptoolpsw

Developers may also access unstable branch. Contact the evoptool team for more details.

Installation

Follow these steps in order to compile evoptool

1. Download source code from svn

 svn checkout https://svn.ws.dei.polimi.it/evoptool/trunk --username usrevoptool --password evoptoolpsw

Refer to trunk for the lastest (stable?) version of evoptool

2. First you need to manually compile the l1_logreg-0.8.2 package, http://www.stanford.edu/~boyd/l1_logreg/ whose source are already included in the evoptool repository. In order to do that follow the instrunctions in README.evoptool in the l1_logreg-0.8.2 directory

Next, compile <id_dist/code> following the instructions in <code>README.evoptool<code> in the <code><id_dist folder

3. Then you need to compile a module at a time. Each module is included in a different folder. To compile a module, from go to the module source folder and do make lib. For instance, for the module named common

 cd common/src
 make lib
 cd ..

Compile modules in the following orderm due to dependencies

 common
 functions
 ga
 stochastic
 eda

To clean a module, do

 make clean

from the module source directory

4. Go to core module and type

 make exe

Binary files will be copied in the bin directory in the root as well as the bin directory of the core module

Required packages

  • Libraries
  • Software
    • gnuplot

Running

Right now evoptool only runs as a script. GUI is not maintained in the latest version. The evoptool binary file is supposed to be run in the bin directory in the root, this is because right now the script looks for some configuration files, for the instances of the problems, and temp directories. If you want to run the script from other directories, you just need to copy in that directory the evoptool-file directory that you find in the bin directory. Link such directory instead of copying it is not safe if you run multiple scripts at the same time, since output files will be shared.

To run the algorithm you need to enter as input an xml file. For instance you can run

 ./evoptool evoptool-file/examples/unitTestOneMax.xml

The evoptool-file/example directory contains a set of xml files for different benchmarks and different algorithms. Take a loot at the example.xml file for the documentation on hoe to set the parameters for an each execution of evoptool

Each execution of evoptool produces a set of files as output. You can find all files in evoptool-file/temp directory. Plus a tar.gz file containing such files can be produced at the end of the execution of evoptool. See the xml file for details.

 evoptool-file/temp/data

contains the raw data of the statistics according to the xml file

 evoptool-file/temp/gnuplot

contains the gnuplot files to produce images of the statistics

 evoptool-file/temp/image

contains images of the statistics produced according to the xml file

 evoptool-file/temp/support

contains logs

Documentation

Implement a new benchmark function

Benchmarks are defined in the function module. A benchmark is the maximization problem of a real valued function defined over a vector of n binary variables. Functions are maximized in evoptool. In order to implement a new benchmark function you have to create a new class that inherits from ObjectiveFunction in the common module. Take a look at the OneMax benchmark function.

Among the arguments of the constructor of the ObjectiveFunction class there must be the size of the benchmark, which may or may not be a parameter of the new benchmark.

 OneMax::OneMax(int size) : ObjectiveFunction(size)

In the constructor you have whether the maximum of the function is known or not

  _knownSolution = true;

And in case this is known, set the minimum value and maximum value for the function

_minFitness = 0; 
_maxFitness = size; //the maximum value of the OneMax function is defined as the sum of the bits of x set to one.

Besides, such values are used in the normalization of the functions in the plots of the statistics.

Each benchmark must implement the f method, which takes the BinaryString x and return f(x). For instance, for OneMax you have

 double OneMax::f(BinaryString *bi) {
  if (bi != NULL) {
   if(!(bi->validCache())) { 
    /* Fitness cache value not valid */
    int sum = 0;
    for (int j = 0; j < _size; j++) {
     sum = sum + bi->get(j);
    }
    bi->setFitnessCache(sum);
    return sum;
   } else {
    return bi->getFitnessCache();
   }
  } else {
   cerr << "[OneMax::f] binary instance cannot be null" << endl;
   return 0;
  }
}

In order to avoid multiple evaluations of the same BinaryString x, a caching mechanism has been implemented.

Moreover, you are asked to implement the exportInteration function, which return an HyperGraph which represents the interactions present in the function. In order to determine such hypergraph, start from the polinomial representation of the function, and for each monomial introduce a new hyperedge in the hypergraph.

For the OneMax function, such representation corresponds to the independence graph, since such function is linear.

 HyperGraph* OneMax::exportInteractions() {
  HyperGraph *interactions = new HyperGraph();
  interactions->createIndependenceGraph(_size);
  return interactions;
 }

In Evoptool.h add an entry in the Tasks enum.

 /* This enumeration defines an identifier for each task function. */
 typedef enum {
  ONE_MAX = 7,
 } Tasks;

This value will identify uniquely the benchmark in the xml file. In the XMLParser.cpp file, add an entry for the new function.

 bool XMLParser::parseTask(xmlpp::TextReader &reader, Evoptool::TestParameters *params) {
  .. 
  switch (task) {
   case Evoptool::ONE_MAX: params->task = new OneMax(size);
   break;
   ..
   default: return false; 
  }
  ..
 }

Additional parameters can be obtained using the xml TextReader object, as for the ForPeaks function.

 case Evoptool::FOUR_PEAKS: 
  value = readNodeContent(reader, "peaks", &errorFlag);
  if (errorFlag) return false;
  int peaks = toInt(value);
  params->task = new FourPeaks(size, peaks);
  break; 

Finally in the xml file, a function can set with the task tag, together with all parameters.

 <task>
  <name>7</name>
  <size>64</size>
 </task>

To create a new algorithm

1. Implement a new algorithm

All algorithms must inherit from the Algorithm class. First override the Algorithm::initAlgorithm as follows:

 void DEUM::initAlgorithm(ObjectiveFunction* of) {
   Algorithm::initAlgorithm(of);
 
   /* Initialization tasks */
   ...
 }

Then implement a run() method which performs al the required task for one iteration of your algorithm.

2. Append entry in the Algorithms enum in Evoptool.h.

 typedef enum {
   ...
   DEUM    // 5
 } Algorithms;

In the xml configuration file, your algorithm will be characterized by the int value associated with the position in this enum declaration.

3. modify the file core/src/XMLParser.cpp. Search for the method bool XMLParser::parseAlgorithms and insert an new entry for your algorithm in the algorithmParameters array, for example

 AlgorithmParameters algorithmParameters[] = {
   ...
   { Evoptool::DEUM, 5, (char*) "IDDDI" }, // Pop, percElitism, percSelec, CoolRate, GibbsIterations
   ...
 };

In each entry, the first field is the name of the entry in the Algorithms enum just modified in Evoptool.h, the second is the number of parameters to be parsed in the xml configuration file and the third is a string specifying their type: I for integer and D for double.

4. add a case in the switch that follows in bool XMLParser::parseAlgorithms, for instance:

 case Evoptool::DEUM: 
   algos[i] = new extendedFCA(intVal[0], doubleVal[0], doubleVal[1], intVal[1], intVal[2], params->rng);
   algos[i]->initAlgorithm(params->task);
   break;

Note that your algorithm can employ the random number generator provided by the Evoptool core, params->rng.

5. Include your headers in core/src/Algorithms.h

6. Document how your algorithm is instantiated in the comments appearing in evoptool-file/exec-scripts/example.xml

  Algorithm  Id    Types    Parameters
 =====================================================================================================
   ...
   FCA       26    "IDDII"  (Pop, PercSelection, LearningRate, MaxCompositionLenght, MaxMonomialOrder)
   ...

7. Add an instantiation example for your algorithm in evoptool-file/exec-scripts/example.xml

 <!algo id="26" instanceName="FCA">  
   <int>1000</int>
   <double>0.5</double>
   <double>1</double>
   <int>64</int>
   <int>2</int>
 </algo>

Run an algorithm in a C++ program

The simplest way to do this is to create a new submodule in core, i.e., a new source directory within the source directory of a module For instance, the steps to create a new submodule named myexample are

1. copy the example submodule exampleRunAlgorithm in a new folder named myexample in

 evoptool/core/src

2. modify the Makefile in the myexample directory, see comments in the makefile for more details.

3. edit the main function in the source file, if you need you can create other C++ and .h files in the same folder.

4. from evoptool/core/src/myexample run

 make bin

The bin file is create in evoptool/core/bin and copied in evoptool/bin

NOTICE that evoptool/core/bin may be deleted after a make cleanall

5. from evoptool/bin run

 ./myexample