Difference between revisions of "Evoptool: Evolutionary Optimization Tool"

Revision as of 17:57, 21 October 2011 (view source) LuigiMalago (Talk | contribs) (→‎Project profile) ← Older edit		Latest revision as of 18:02, 14 April 2012 (view source) DavideCucci (Talk | contribs) (→‎PPSN 2012)
(118 intermediate revisions by 3 users not shown)
Line 1:		Line 1:
−	== '''Project profile''' ==	+	== Description ==
−	{| style="color:black; background-color:#F9F9F9;" cellpadding="3" cellspacing="0" border="1"	+
−	|-	+
−	||'''Name:'''	+
−	||Evoptool: Evolutionary Optimization Tool.	+
−	|-	+
−	||'''Field:'''	+
−	||Evolutionary Computation (EC).	+
−	|-	+
−	||'''People involved:'''	+
−	||[[User:MatteoMatteucci| Matteo Matteucci]] - matteucci@elet.polimi.it	+
−	[[User:LuigiMalago| Luigi Malagò]] - malago@elet.polimi.it	+
−	[[User:GabrieleValentini| Gabriele Valentini]] - gabriele.valentini@mail.polimi.it	+
−	Cucci Davide - cucci@elet.polimi.it	+
−	|-	+
−	||'''Formerly involved:'''	+
−	|| Emanuele Corsano	+
−	|}	+
−	== Tool 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.
−	Evolutionary Optimization Tool (Evoptool) is an open source optimization tool, distributed under GNU General Public License, implementing meta-heuristics based on the Evolutionary Algorithms paradigm, that 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 ==
−	=== Algorithms ===	+	*[[User:MatteoMatteucci| Matteo Matteucci]] - matteucci [AT] elet.polimi.it
−	Evoptool offers a set of algorithm implementations coming from several paradigms within Evolutionary Computation, in the context of black-box optimization of boolean functions.	+	*[http://www.dei.polimi.it/personale/dettaglio.php?id_persona=829&id_sezione=&lettera=M&idlang=ita| Luigi Malagò] - malago [AT] elet.polimi.it
−	* Genetic Algorithms (GAs)	+	*[http://iridia.ulb.ac.be/~gvalentini/ Gabriele Valentini] - gvalentini [AT] iridia.ulb.ac.be
−	** ''Simple Genetic Algorithm (SGA)''. It is the original genetic algorithm with truncation selection, bitflip mutation, and single-point crossover.	+
−	** ''SGA with binary tournament selection.'' It is a variation of the SGA, and it differs for the selection operator that implements a binary tournament selection. Two individuals are picked up randomly from the population, and their fitness compared: the fittest individual is selected for the new population.	+
−	** ''SGA with uniform bitwise crossover''. Another variation of SGA, it maintains the truncation selection and bitflip mutation, but implements a uniform bitwise crossover. This variation operator looks each bit of the two individuals string and swap them with a fixed crossover probability.	+
−	[[Image:Evoptool_algo.jpg|750px|thumb|Algorithm hierarchy.]]	+	*[[User:DavideCucci| Davide Cucci]] - cucci [AT] elet.polimi.it
−	* Estimation of Distributions Algorithms (EDAs)	+	'''Formerly involved'''
−	** Univariate EDAs:	+	*Emanuele Corsano
−	*** ''Population Based Incremental Learning (PBIL)''. It maintains a vector of marginal probabilities which is used to sample a new population at each generation. Then, after a selection of the population is performed, the marginal probabilities are computed again and the vector is updated according to a learning rule.	+
−	*** ''Univariate Marginal Distribution Algorithm (UMDA)''. It differs from PBIL in having no learning rule. It simply generate new individuals using marginal probabilities computed as marginal frequencies of the previous population.	+
−	*** ''Compact Genetic Algorithm (cGA)''. It is a space-efficient variation of PBIL that maintains a probability vector, but rather than generating a whole population, only two individuals are generated, from it and then are subjected to tournament. The probability vector is then updated according to a learning rule which considers both individuals.	+
−	*** U''nivariate Distribution of Estimation Using Markov Random Field (Univariate DEUM)''. It uses an univariate Markov Random Field (MRF) to model the relationship between individuals and their fitness. MRF parameters are estimated through maximum likelihood, then the model is used to sample a new population by employing a Gibbs or Metropolis sampler.	+
−	** Bivariate EDAs:	+
−	*** ''Mutual Information Maximizing Input Clustering (MIMIC)''. It adopts a directed conditional chain model for the distribution structure, learned by a greedy heuristic employing Shannon's Information Entropy, in order to minimize the Kullback-Leibler Divergence between the model and the true distribution.	+
−	*** ''Combining Optimizers with Mutual Information Trees (COMIT)''. It is similar to MIMIC, but with a tree-structured Bayesian network rather than a single chain. A maximum weight spanning tree is used to learn the structure, guided by the entropy information principle. Once the structure is defined, it samples the individuals according to defined model, and then it exploits fast search algorithms to further improve the generated individuals. Inside Evoptool there are two implementation: one with an hill-climber fast search, and one with a PBIL based fast search.	+
−	*** ''Bivariate Chain DEUM (Bivariate DEUM)''. It differs from the univariate version only for the structure of the underlying probabilistic model, that takes the form of a bivariate undirected chain.	+
−	*** ''Ising Model DEUM (Ising DEUM)''. It is a DEUM like algorithm specifically designed to solve the Ising Spin Glass problem, by employing a bivariate lattice structure.	+
−	** Multivariate EDAs:	+
−	*** ''Simple Bayesian Optimization Algorithm (sBOA)''. It uses a Bayesian network to represent the fitness structure, it employs the Bayesian-Dirichlet metric to measure the network quality, and a greedy algorithm to search the space of possible networks. At each generation, it computes and stores in the network the marginal and conditional probabilities of a selection of the original individuals, and than uses the Bayesian network to generate the new population.	+
−	=== Benchmarks ===	+	== PPSN 2012 ==
−	Evoptool is designed to support the study of black-box optimization for boolean functions. The fitness function of each benchmark accepts as argument a string of boolean variables and returns a real value. Being performance comparison the main purpose of Evoptool, it already includes several optimization problems with different properties, varying from classical toy problems to more complex ones.	+
−	A first set of benchmarks is composed of simple toy problems without any variable dependency, therefore with an underlying univariate structure.	+	In this section we report the details of the experiments presented in the paper "Variable Transformations in Estimation of Distribution Algorithms", submitted to PPSN 2012.
−	* ''One Max''. A simple problem where the returned value is represented by the count of alleles of the individual taking value one. It has a unique optimal solution and every allele has the same relevance in the individual.	+	The experiments were run using the unstable version of evoptool, which is available trought SVN at
−	* ''One-Zero Max''. It is a variation of One Max, where the fitness of an individual is represented by the maximum between the count of zeros and the count of ones. The relevant property of this problem is the existence of two optimal solutions: one with all alleles taking value one, and one with all zeros.	+
−	* ''Sum Value''. In this toy problem the optimal solution is represented by a string of all ones. The fitness value is computed as the sum of the products between alleles and coefficients equal to the allele position inside the string. Also in this case there are no variable dependencies, but in contrast to the previous benchmarks the relevance of each allele is different and it grows linearly.	+
−	* ''Binary Value''. Very similar to the Sum Value benchmark, it gives an increasing quadratic relevance at each alleles.	+
−	Another group of functions is constituted by deceptive problems, designed to mislead classical Genetic Algorithms. Their structure defines dependencies among variables with different orders (bivariate, trivariate, multivariate).	+	https://svn.ws.dei.polimi.it/evoptool/branches/unstable
−	* ''Alternated Bits''. Also called 1D Checkerboard, it introduces dependencies between couples of adjacent variables defining a chain structure. The problem takes into account the value of a variable relative to that of its immediate neighbours in the chain, in particular, higher fitness is achieved when neighbourring variables take opposite values.	+	For each problem, Alternated Bits, Trap3, Trap3 Overlapping and Trep5, a python script is used to generate the Evoptool configuration files. For a given problm size ''n'', we chose a population size, run 24 instances of the test algorithm and check the success ratio. If it below 95%, we increase the population, otherwise we compute from these runs the average number of fitness function evaluations performed before the global optimum appears in the population. We increase the population exponentially with ''n'', so that ''N=n^k'' and each time the success ratio is below the chosen we set k=k+0.1.
−	* ''F3-Deceptive, Overlapping and Bipolar''. This deceptive function is composed of separable building blocks of order three which has one global optimum for all ones and a deceptive local optimum to all zeros. The final fitness value is composed by the sum of the contributions of each deceptive pattern defined on three consecutive bits. The Bipolar variant is based on blocks of six bits, where there are two global optimum (all ones and all zeros) and a deceptive local optimum(three ones and three zeros). Overlapping version introduces overlaps among building blocks.	+
−	* ''Trap-5''. This benchmark is similar to previous deceptive functions, and differs for the length of building blocks. As the previous functions, it has a global optimum for all alleles taking value one, and a deceptive local optimum for all zeros.	+
−	* ''Four Peaks and Six Peaks''.	+
−	* ''Quadratic''.	+
−	* ''Liepins Vose Fully Deceptive''	+
−	Last but not least, there are implementation of real-like applications as:	+	Each time an experiment is performed using Evoptool, a .tar file is produced which contain statistics and plots for each instance of the algorithms run and also aggregated averages. The python scripts we used name this tar files with the following convention:
−	* ''MAXSAT''. The task in this benchmark is to find a set of values which maximizes the number of satisfied clauses of a fixed predicate logic formula expressed in conjunctive normal form. Many real-world problems can be reduced to MAXSAT, besides it is known to be NP-complete in its general form.	+	algorithm-n-N-selection_rate-maps_number.tar
−	* ''Ising Spin Glass''. The general Ising Spin Glass problem can be described as an energy function ''H'' defined over a set of spin variables, and a set of coupling constants. Each spin variable can be either ''+1'' or ''-1'', and they are organized in a lattice of ''n'' sites. Given a set of coupling constants, the task in the Ising Spin Glass problem is to find the value for each spin that minimizes the energy, ''H''.	+
−	* ''Texture Restoration''.	+
−	=== Statistics ===	+	All the .tar files used to compute the result presented in the paper, along with the python scripts and everything else needed to reproduce the experiments are available trought SVN at
−	== Tool Usage ==	+	https://svn.ws.dei.polimi.it/evoptool/branches/papers/PPSN-2012-FCA/experiments/
−	Evoptool is distributed under GNU General Public License and, so far, available for GNU/Linux platforms. Evoptool exploits several open source libraries and software, and it allows to wrap external algorithm implementations, as for Simple Bayesian Agorithm, reducing the efforts for the development. In this section, are described in the details the procedures to install the tool on your system.	+	== Mailing List ==
		+	http://groups.google.com/group/evoptool
−	=== Download ===	+	== Features ==
−	As metioned above, Evoptool implements several optimization algorithms, and it can also wrap external algorithm implementations through patches. This characteristic of the tool need to be correctly considered: if you plan to write an new algorithm then it is prefered to write it directly into Evoptool packages, if you just have the source code of an algorithm, and you want to save the time to implement it again, you can modify your code in order to work within Evoptool.	+	====Algorithms implemented====
		+	* Genetic Algorithms
		+	** SGA
		+	*Estimation of Distribution Algorithms
		+	**PBIL, UMDA, cGA, COMIT, BOA, FCA
		+	* DEUM framework
		+	**DEUMd, IsingDEUM, DEUM-Chain, DEUM-LDA, DEUM-CE, DEUM-X2, DEUM-JEMP, DEUM-l1, sDEUM
		+	* Stochastic Gradient Descent
		+	**SGD, SNGD
		+	* Other Meta-heuristics
		+	**Simulated Annealing
−	<blockquote>	+	References to original papers will be added soon.
−	{| border="1" cellspacing="0" cellpadding="5"	+
−	! Description	+
−	! Version	+
−	! Date	+
−	! Link	+
−	|-	+
−	| Evoptool with sBOA support.	+
−	| 1.1	+
−	| 11/03/2010	+
−	| [[Media:evoptool1.1.zip | Evoptool1.1]]	+
−	|-	+
−	| Evoptool without sBOA support.	+
−	| 1.0	+
−	| 24/02/2010	+
−	| [[Media:evoptool.zip | Evoptool1.0]]	+
−	|-	+
−	|}	+
−	</blockquote>	+
−	External algorithm implementations cannot be directly distributed within Evoptool, but need to be downloaded from their original position, and, to be adjusted to work with Evoptool by applying a patch. Here you can find reference to wrapped algorithms and their patches to work within Evoptool.	+	====Benchmark functions implemented====
		+	* OneMax
		+	* AltBit
		+	* Trap3
		+	* Trap5
		+	* IsingSpinGlass2D (*)
		+	* IsingSpinGlass3D (*)
		+	* Max Cut
−	<blockquote>	+	(*) instances generated and solved with Spin Glass Server. This service is provided by COPhy and M. Jünger's group.
−	{| border="1" cellspacing="0" cellpadding="5"	+	http://www.informatik.uni-koeln.de/spinglass/
−	! Description !! External link !! Patch	+
−	|-	+
−	| Simple Bayesian Algorithm || [http://www.cs.umsl.edu/~pelikan/software.html sBOA] || [[Media:SBOA.patch.zip | sBOA.patch]]	+
−	|}	+
−	</blockquote>	+
−	=== Requirements ===	+	== Download ==
−	In order to compile Evoptool, you need to install on your system some open source software and libraries, needed by the tool.	+	svn checkout https://svn.ws.dei.polimi.it/evoptool/trunk --username usrevoptool --password evoptoolpsw
−	* Libraries:	+	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 <code>l1_logreg-0.8.2</code> 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
		+	<code>README.evoptool</code> in the <code>l1_logreg-0.8.2</code> directory
		+
		+	Next, compile <code><id_dist/code> following the instructions in <code>README.evoptool</code> in the <code><id_dist</code> 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 <code>common</code>
		+
		+	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 <code>core</code>  module and type
		+
		+	make exe
		+
		+	Binary files will be copied in the <code>bin</code> directory in the root as well as the <code>bin</code> directory of the <code>core</code> module
		+
		+	'''Required packages'''
		+	* Libraries
	** ''gtkmm-2.4''		** ''gtkmm-2.4''
	** ''glademm-2.4''		** ''glademm-2.4''
	** ''gthread-2.0''		** ''gthread-2.0''
	** ''sigc++-2.0''		** ''sigc++-2.0''
−	** ''cv''	+	** ''opencv'' (see for instance http://www.samontab.com/web/2011/06/installing-opencv-2-2-in-ubuntu-11-04/)
−	** ''highgui''	+
−	** ''cvaux''	+
	** ''gsl''		** ''gsl''
	** ''gslcblas''		** ''gslcblas''
	** ''libxml++-2.6''		** ''libxml++-2.6''
		+	** ''f2c''
−	* Software:	+	* Software
	** ''gnuplot''		** ''gnuplot''
		+	**  ''R (lars package)''
		+
		+	== Running  ==
		+
		+	Right now <code>evoptool</code> only runs as a script. GUI is not maintained in the latest version.
		+	The <code>evoptool</code> binary file is supposed to be run in the <code>bin</code> 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 <code>evoptool-file</code> directory that you find in the <code>bin</code> 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 <code>evoptool-file/example</code> directory contains a set of xml files for different benchmarks and different algorithms.
		+	Take a loot at the <code>example.xml</code> file for the documentation on hoe to set the parameters for an each execution of <code>evoptool</code>
		+
		+	Each execution of <code>evoptool</code> produces a set of files as output. You can find all files in <code>evoptool-file/temp</code> directory. Plus a tar.gz file containing such files can be produced at the end of the execution of <code>evoptool</code>. 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 <code>function</code> module. A benchmark is the maximization problem of a real valued function defined over a vector of n binary variables. Functions are maximized in <code>evoptool</code>. In order to implement a new benchmark function you have to create a new <code>class</code> that inherits from <code>ObjectiveFunction</code> in the <code>common</code> module. Take a look at the <code>OneMax</code> benchmark function.
		+
		+	Among the arguments of the constructor of the <code>ObjectiveFunction</code> 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 <code>f</code> method, which takes the <code>BinaryString</code> x and return f(x). For instance, for <code>OneMax</code> you have
		+
		+	double OneMax::f(BinaryString *bi) {
		+	&nbsp;if (bi != NULL) {
		+	&nbsp;&nbsp;if(!(bi->validCache())) {
		+	&nbsp;&nbsp;&nbsp;/* Fitness cache value not valid */
		+	&nbsp;&nbsp;&nbsp;int sum = 0;
		+	&nbsp;&nbsp;&nbsp;for (int j = 0; j < _size; j++) {
		+	&nbsp;&nbsp;&nbsp;&nbsp;sum = sum + bi->get(j);
		+	&nbsp;&nbsp;&nbsp;}
		+	&nbsp;&nbsp;&nbsp;bi->setFitnessCache(sum);
		+	&nbsp;&nbsp;&nbsp;return sum;
		+	&nbsp;&nbsp;} else {
		+	&nbsp;&nbsp;&nbsp;return bi->getFitnessCache();
		+	&nbsp;&nbsp;}
		+	&nbsp;} else {
		+	&nbsp;&nbsp;cerr << "[OneMax::f] binary instance cannot be null" << endl;
		+	&nbsp;&nbsp;return 0;
		+	&nbsp;}
		+	}
		+
		+	In order to avoid multiple evaluations of the same <code>BinaryString</code> x, a caching mechanism has been implemented.
		+
		+	Moreover, you are asked to implement the <code>exportInteration</code> function, which return an <code>HyperGraph</code> 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 <code>OneMax</code> function, such representation corresponds to the independence graph, since such function is linear.
		+
		+	HyperGraph* OneMax::exportInteractions() {
		+	&nbsp;HyperGraph *interactions = new HyperGraph();
		+	&nbsp;interactions->createIndependenceGraph(_size);
		+	&nbsp;return interactions;
		+	}
		+
		+	In <code>Evoptool.h</code> add an entry in the <code>Tasks</code> enum.
		+
		+	/* This enumeration defines an identifier for each task function. */
		+	typedef enum {
		+	&nbsp;ONE_MAX = 7,
		+	} Tasks;
		+
		+	This value will identify uniquely the benchmark in the xml file. In the <code>XMLParser.cpp</code> file, add an entry for the new function.
		+
		+	bool XMLParser::parseTask(xmlpp::TextReader &reader, Evoptool::TestParameters *params) {
		+	&nbsp;..
		+	&nbsp;switch (task) {
		+	&nbsp;&nbsp;case Evoptool::ONE_MAX: params->task = new OneMax(size);
		+	&nbsp;&nbsp;break;
		+	&nbsp;&nbsp;..
		+	&nbsp;&nbsp;default: return false;
		+	&nbsp;}
		+	&nbsp;..
		+	}
		+
		+	Additional parameters can be obtained using the xml TextReader object, as for the <code>ForPeaks</code> function.
		+
		+	case Evoptool::FOUR_PEAKS:
		+	&nbsp;value = readNodeContent(reader, "peaks", &errorFlag);
		+	&nbsp;if (errorFlag) return false;
		+	&nbsp;int peaks = toInt(value);
		+	&nbsp;params->task = new FourPeaks(size, peaks);
		+	&nbsp;break;
		+
		+	Finally in the xml file, a function can set with the <code>task</code> tag, together with all parameters.
		+
		+	<task>
		+	&nbsp;<name>7</name>
		+	&nbsp;<size>64</size>
		+	</task>
		+
		+	==== To create a new algorithm ====
−	=== Compilation ===	+	1. Implement a new algorithm
−	Evoptool source files and external algorithm implementations need to be compiled separately. In this section are described, step by step, all you need to compile the tool.	+	All algorithms must inherit from the Algorithm class. First override the Algorithm::initAlgorithm as follows:
−	==== Evoptool package ====	+	void DEUM::initAlgorithm(ObjectiveFunction* of) {
		+	Algorithm::initAlgorithm(of);
		+
		+	/* Initialization tasks */
		+	...
		+	}
−	If you want to compile the entire package, including the whole set of Evoptool libraries, you need to:	+	Then implement a run() method which performs al the required task for '''one''' iteration of your algorithm.
−	# In the main folder ''../evoptool/trunk/'' give a ''make cleanall'' command in order to remove all the binary files and library dependencies, and be sure to compile the entire project in the right way.	+	There are some classes which contain useful methods such as samplers and estimators from which your algorithm can inherit. The most useful are:
−	# In the main folder ''../evoptool/trunk/'' give a ''make all'' command in order to compile all the libraries and build the executable file.	+
−	If you need only to compile a single library, you need to:	+	PopulationBasedAlgorithm
		+	ModelBasedAlgorithm
		+	ExponentialFamilyAlgorithm
		+	BayesianNetworkBasedAlgorithm
−	# In the folder ''../evoptool/trunk/mylib/src/'' give a ''make lib'' command in order to compile and build library associated with that module. Repeat this operation for each library you want to compile.	+	2. Append entry in the <tt>Algorithms</tt> enum in Evoptool.h.
−	# In the folder ''../evoptool/trunk/gui/src'' give a ''make exe'' command in order to build the executable file.	+
−	==== Wrapped Algorithms ====	+	typedef enum {
		+	...
		+	DEUM    // 5
		+	} Algorithms;
−	Evoptool is able to wrap external algorithm implementations thanks to patch mechanism. Actually, it is possible to wrap the original implementation of the Simple Bayesian Algorithm, so, we are going to explain how to add external algorithm implementations using sBOA as an example. All you need to do is to perform the following steps:	+	In the xml configuration file, your algorithm will be characterized by the int value associated with the position in this enum declaration.
−	# In the folder ''../trunk/evoptool-file/wrapped/'' create the directory ''sBOA''.	+	3. modify the file
−	# Extract the original implementation of sBOA to the just created directory.	+	core/src/XMLParser.cpp. Search for the method <tt>bool XMLParser::parseAlgorithms</tt> and insert an new entry for your algorithm in the <tt>algorithmParameters</tt> array, for example
−	# Applay the patch with the command ''patch -p1 <PATCH_FILE'', where PATCH_FILE is the sBOA patch file provided by us complete of the correct path.	+
−	# Compile the sBOA source code by the command ''make all''.	+
−	# Compile Evoptool following the previous instruction.	+
−	=== Execution ===	+	AlgorithmParameters algorithmParameters[] = {
		+	...
		+	{ Evoptool::DEUM, 5, (char*) "IDDDI" }, // Pop, percElitism, percSelec, CoolRate, GibbsIterations
		+	...
		+	};
−	Evoptool is available as command line software, providing a configuration file, or with a graphic user interface. In order to run Evoptool in GUI mode you need only to:	+	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.
−	# Go to folder ''../evoptool/trunk/gui/bin''.	+	4. add a case in the switch that follows in <tt>bool XMLParser::parseAlgorithms</tt>, for instance:
−	# Run Evoptool by ''./evoptool'' command.	+
−	If you want to run Evoptool as a command line tool you need to:	+	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;
−	# Go to folder ''../evoptool/trunk/gui/bin''.	+	Note that your algorithm can employ the random number generator provided by the Evoptool core, <tt>params->rng</tt>.
−	# Run Evoptool by ''./evoptool --nogui PATH1'', where the argument PATH1 is a complete path for a configuration file.	+
−	Within Evoptool is provided a simple configuration file in the folder  ../evoptool/trunk/evoptool-file/configuration-file/''.	+	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
−	== How to Extend Evoptool ==	+	Algorithm  Id    Types    Parameters
		+	=====================================================================================================
		+	...
		+	FCA      26    "IDDII"  (Pop, PercSelection, LearningRate, MaxCompositionLenght, MaxMonomialOrder)
		+	...
−	=== Create an Algorithm ===	+	7. Add an instantiation example for your algorithm in evoptool-file/exec-scripts/example.xml
−	=== Add an Algorithm to GUI ===	+	<algo id="26" instanceName="FCA">
−	In  folder ''../trunk/gui/src/'':	+	<int>1000</int>
−	* Create the new decorator files ''ExampleDecorator.h'' and ''ExampleDecorator.cpp''. You can simply copy another decorator structure and modify it where necessary.	+	<double>0.5</double>
−	* Add Decorator header file to ''AlgorithmsDecorator.h'' main header.	+	<double>1</double>
−	* Add decorator to GUI by modifying the ''initializeResolutorsPanel'' function of the ''EvoptoolGUI.cpp'' file.	+	<int>64</int>
		+	<int>2</int>
		+	</algo>
−	=== Add an Algorithm to Command Line Parser ===	+	==== Run an algorithm in a C++ program ====
−	In folder ''..trunk/gui/src/'':	+
−	* Add the header file of the new algorithm to the main header ''Algorithms.h''.	+
−	* Add a new entry for the algorithm into the algorithms enumeration in ''Evoptool.h'' file.	+
−	* Modify the ''parseResolutor'' function of ''XMLParser.cpp'' file:	+
−	** Add a new entry in the ''AlgorithmParameters'' structure list.	+
−	** Treat the new case in the main switch as for other algorithms.	+
−	* Take care about update the example configuration file with instructions for the parametrization of your algorithm (''../evoptool-file/configuration-examples/testConf.xml).	+
−	=== Create a Benchmark ===	+	The simplest way to do this is to create a new submodule in <code>core</code>, i.e., a new source directory within the source directory of a module
		+	For instance, the steps to create a new submodule named <code>myexample</code> are
−	If you want to implement a new benchmark within Evoptool, you need to follow the next steps:	+	1. copy the example submodule <code>exampleRunAlgorithm</code> in a new folder named <code>myexample</code> in
−	* In the folder ''../opt-pbl/src'' create a new benchmark class, e.g, ''NewBenchmark.cpp'' and ''NewBenchmark.h''.	+	evoptool/core/src
−	* The ''NewBenchmark'' must inherits from ''ObjectiveFunction.h'' and must implement the function ''f'' (call to the fitness).	+	2. modify the <code>Makefile</code> in the <code>myexample</code> directory, see comments in the makefile for more details.
−	* Configure headers. Add the ''NewBenchmark.h'' to ''ObjectiveFunctions.h'' (look the 's'!) that is placed in the ''../gui/src/'' folder. This will avoid to include a long list of headers to the main GUI class.	+	3. edit the <code>main</code> function in the source file, if you need you can create other C++ and .h files in the same folder.
−	=== Add a Benchmark to GUI ===	+	4. from <code>evoptool/core/src/myexample</code> run
−	In order to add the ''NewBenchmark'' to the Evoptool GUI you need to:	+
−	* Add a new entry in the ''Evoptool::Tasks'' enumeration, let say NEW_BENCHMARK.	+	make bin
−	* In the ''EvoptoolGUI::initializeTaskBar'' function within the ''../gui/src/Evoptool.cpp'' file, add the newly created benchmark to the list of objective functions showed by the GUI.	+	The bin file is create in <code>evoptool/core/bin</code> and copied in <code>evoptool/bin</code>
−	* In the ''EvoptoolGUI::taskBoxHandler'' function within the ''../gui/src/Evoptool.cpp'' file, treat the new case in order to correctly load the benchmark parameters within the task bar.	+	NOTICE that <code>evoptool/core/bin</code> may be deleted after a <code>make cleanall</code>
−	* In the ''EvoptoolGUI::initializeTask'' function within the ''../gui/src/Evoptool.cpp'' file, treat the new case in order to correctly create the benchmark object when the test is executed.	+	5. from <code>evoptool/bin</code> run
−	=== Add a Benchmark to Command Line Parser ===	+	./myexample
−	In order to add the ''NewBenchmark'' to the Evoptool XMLParser you need to:	+	==== Available statistics  ====
−	* Add a new entry in the ''Evoptool::Tasks'' enumeration, let say NEW_BENCHMARK.	+	In the configuration xml file you can enable the evaluation of three set of statistics:
−	* In the ''XMLParser::parseTask'' function within the ''../gui/src/XMLParser.cpp'' file, add the newly created benchmark to the list of objective functions that can be parsed by the parser.	+	<statisticsConfiguration>
		+	<evalPopulationStatistics>yes</evalPopulationStatistics>
		+	<evalModelStatistics>yes</evalModelStatistics>
		+	<evalExecutionStatistics>No</evalExecutionStatistics>
		+	...
		+	</statisticsConfiguration>
−	* Update the example configuration file within ''../evoptool-file/configuration-examples/testConf.xml'', by adding a new entry to the list of avaiable benchmark (This simplify the use of configuration file).	+	See the headers file in evoptool/common/src for details.

---

Latest revision as of 18:02, 14 April 2012

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

• Matteo Matteucci - matteucci [AT] elet.polimi.it

• Luigi Malagò - malago [AT] elet.polimi.it

• Gabriele Valentini - gvalentini [AT] iridia.ulb.ac.be

• Davide Cucci - cucci [AT] elet.polimi.it

Formerly involved

• Emanuele Corsano

PPSN 2012

In this section we report the details of the experiments presented in the paper "Variable Transformations in Estimation of Distribution Algorithms", submitted to PPSN 2012.

The experiments were run using the unstable version of evoptool, which is available trought SVN at

https://svn.ws.dei.polimi.it/evoptool/branches/unstable

For each problem, Alternated Bits, Trap3, Trap3 Overlapping and Trep5, a python script is used to generate the Evoptool configuration files. For a given problm size n, we chose a population size, run 24 instances of the test algorithm and check the success ratio. If it below 95%, we increase the population, otherwise we compute from these runs the average number of fitness function evaluations performed before the global optimum appears in the population. We increase the population exponentially with n, so that N=n^k and each time the success ratio is below the chosen we set k=k+0.1.

Each time an experiment is performed using Evoptool, a .tar file is produced which contain statistics and plots for each instance of the algorithms run and also aggregated averages. The python scripts we used name this tar files with the following convention:

algorithm-n-N-selection_rate-maps_number.tar

All the .tar files used to compute the result presented in the paper, along with the python scripts and everything else needed to reproduce the experiments are available trought SVN at

https://svn.ws.dei.polimi.it/evoptool/branches/papers/PPSN-2012-FCA/experiments/

Mailing List

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

Features

Algorithms implemented

• Genetic Algorithms
  • SGA
• Estimation of Distribution Algorithms
  • PBIL, UMDA, cGA, COMIT, BOA, FCA
• DEUM framework
  • DEUMd, IsingDEUM, DEUM-Chain, DEUM-LDA, DEUM-CE, DEUM-X2, DEUM-JEMP, DEUM-l1, sDEUM
• Stochastic Gradient Descent
  • SGD, SNGD
• Other Meta-heuristics
  • Simulated Annealing

References to original papers will be added soon.

Benchmark functions implemented

• OneMax
• AltBit
• Trap3
• Trap5
• IsingSpinGlass2D (*)
• IsingSpinGlass3D (*)
• Max Cut

(*) instances generated and solved with Spin Glass Server. This service is provided by COPhy and M. Jünger's group. http://www.informatik.uni-koeln.de/spinglass/

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 in the <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
  • gtkmm-2.4
  • glademm-2.4
  • gthread-2.0
  • sigc++-2.0
  • opencv (see for instance http://www.samontab.com/web/2011/06/installing-opencv-2-2-in-ubuntu-11-04/)
  • gsl
  • gslcblas
  • libxml++-2.6
  • f2c

• Software
  • gnuplot
  • R (lars package)

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.

There are some classes which contain useful methods such as samplers and estimators from which your algorithm can inherit. The most useful are:

 PopulationBasedAlgorithm
 ModelBasedAlgorithm
 ExponentialFamilyAlgorithm
 BayesianNetworkBasedAlgorithm

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

Available statistics

In the configuration xml file you can enable the evaluation of three set of statistics:

 <statisticsConfiguration>
   <evalPopulationStatistics>yes</evalPopulationStatistics>
   <evalModelStatistics>yes</evalModelStatistics>
   <evalExecutionStatistics>No</evalExecutionStatistics>
   ...
 </statisticsConfiguration>

See the headers file in evoptool/common/src for details.