Difference between revisions of "Evoptool: Evolutionary Optimization Tool"

Revision as of 21:02, 28 May 2009 (view source) GabrieleValentini (Talk | contribs) (→‎Software Modules) ← Older edit		Latest revision as of 19:02, 14 April 2012 (view source) DavideCucci (Talk | contribs) (→‎PPSN 2012)
(241 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: Evolutive Optimization Tool.	+
−	|-	+
−	||'''Field:'''	+
−	||Combining Estimation of Distribution Algorithms and other Evolutionary techniques	+
−	for combinatorial optimization.	+
−	|-	+
−	||'''Project's head:'''	+
−	||M. Matteucci - [[User:MatteoMatteucci]]	+
−	L. Malagò - [[User:LuigiMalago]]	+
−	|-	+
−	||'''People involved:'''	+
−	||G. Valentini - [[User:GabrieleValentini]]	+
−	|}	+
−	=== Short 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 project focus on the study, implementation, comparison and analysis of different algorithms for combinatorial optimization using techniques and algorithms proposed in Evolutionary Computation. In particular we are interested in the study of Estimation of Distribution Algorithms, a recent meta-heuristic, often presented as an evolution of Genetic Algorithms, where classical crossover and mutation operators, used in genetic algorithms, are replaced with operators that come from statistics, such as sampling and estimation.	+
−	The focus will be on the implementation of new hybrid algorithms able to combine estimation of distribution algorithms with different approaches available in the evolutionary computation literature, such as genetic algorithms and evolutionary strategies, together with other local search techniques.	+
−	== '''User Manual''' ==	+	== The Evoptool Team ==
−	=== '''Algorthms''' ===	+
−	This section have the purpose to show the set of algorithms implemented inside evoptool. These algorithms belong to different classes, and they perfom different operations. In the following lines are presented the theoretical bases for better undestand the use of evoptool.	+
−	* '' '''Genetic Algorithm (GA). ''' ''Is a search technique used in computing to find exact or approximate solutions to optimization and search problems. They grow a population of abstract representations (''chromosomes'' or ''genotype'') of candidate solutions (''individuals'' or ''phenotypes'') to an optimization problem evolves toward better solutions. In this tool, solutions are represented as binary strings of 0s and 1s, but other encodings are also possible. The evolution usually starts from a population of randomly generated individuals and happens in several generations (selection, crossover, mutation). The new population is then used in the next iteration of the algorithm. Commonly, the algorithm terminates when either a maximum number of generations has been produced, or a satisfactory fitness level has been reached for the population. Nowaday, there are the following GA implemented inside evoptool:	+	*[[User:MatteoMatteucci| Matteo Matteucci]] - matteucci [AT] elet.polimi.it
−	** ''SGA (Simple Genetic Algorithm). ''A selection operator is applied to the population and two random recombinator operators called crossover and mutation are applied to the selected population in order to improve the population. SGA uses a truncation selection with a fixed percentage. The variation operators used are Uniform crossover and Bit-Flip mutation.	+
−	*** ''SGA with Binary Tournment.''	+
−	*** ''SGA with Population Wise Uniform Crossover.''	+
−	* '''''Estimation Distribution Algorithm (EDA). '''''Is powerful population-based searcher where the variation operations traditionally implemented via crossover and mutation in EAs are replaced by the process of random sampling from a probability distribution. The distribution is modified generation after generation, using information obtained from the fitter individuals in the population (estimation). The objective of these changes in the distribution is to increase the probability of generating individuals with high fitness. In our tool there are several EDA implemented such:	+	*[http://www.dei.polimi.it/personale/dettaglio.php?id_persona=829&id_sezione=&lettera=M&idlang=ita| Luigi Malagò] - malago [AT] elet.polimi.it
−	** ''cGA (Compact Genetic Algorithm).'' It initialize a vector of probabilities where each component follows a Bernoulli distribution with parameter 0.5. Next, two individuals are generated randomly from this vector of probabilities. After the individuals are evaluated, a competion between then is carried out. The competion is held at level of each of the unidimensional variables, in such a way that if for the i''th'' position the conquiring individual take a value different from the loser, the i''th'' component of the vector of probabilities increases its value.	+
−	** ''PBIL (Population Based Incremental Learning).'' It maintains unconditional probabilities and no interparameter dependencies are modeled. A vector, P, specifies the probability of generating a 1 in each bit position. Initially, all values in P are set to 0.5. A number of solution vectors are generated by stochastically sampling P; each bitis sampled independently of all the others. The probability vector is then moved towards the generated solution vector with the highest evaluation.	+
−	** ''UMDA (Univariate Marginal Distribution Algorithm).'' At each generation, it estimate the joint probability distribution model of the selected individual by factorize it as product of indipendent univariate marginal distributions. Each univariate marginal distribution is estimated from marginal frequency.	+
−	** ''MIMIC (Mutual Information Maximizing Input Clustering)''. It attempts to communicate information about the cost function obtained from one iteration of the search to later iterations of the search directly. There are two main components of MIMIC: first, a randomized optimization algorithm that samples from those regions of the input space most likely to contain the maximum; second, an effective density estimator that can be used to capture a wide variety of structure on the input space, and that build a Markov Chain in order to represents the bivariate structure.	+
−	** ''COMIT (Combining Optimizers with Mutual Information Trees).'' It gains most of the benefits of modeling the dependencies in the search space at a significantly reduced computational cost. COMIT starts by estimating a probabilistic model of the population, than uses the model to stochastically generate new solutions, it selects the fittest solutions and perfom a local fast-search initialized with these solutions.	+
−	*** ''COMIT with HillClimbing as fast-search.''	+
−	*** ''COMIT with PBIL as fast-search.''	+
−	** ''DEUM (Distribution Estimation Using Markov Random Field).'' DEUM uses MRF approach to estimate and sample the probability distribution using a fitness modelling approach to estimate the MRF parameters. This version of DEUM is an univariate model of probability distribution. This allows to completely eliminate the structure learning task.	+
−	*** ''DEUM with probability vector.'' It uses the estimated parameters of MRF for update the probability vector, generation by generation.	+
−	*** ''DEUM with direct sampling from Gibbs distribution.'' It uses the estimated parameters of MFR for directly calcutate the probability of each bit to be 1 or 0.	+
−	** ''Is-DEUM (Ising model DEUM). ''It is an evolution from the univariate DEUM to a bivariate version. This algorithm has been defined for solve the Ising Sping Glass problem, and therefore it use a grid structure to model the interactions between each variables of a solution.	+
−	*** ''Is-DEUM with a Metropolis sampler.''	+
−	*** ''Is-DEUM with a Gibbs sampler.''	+
−	** ''sBOA (Simple Bayesian Optimization Algorithm). ''It is a multivariate EDA that uses the Bayesian Dirichlet equivalence metric to measure the goodness of each structure. The search used is a greedy search and it starts in each generation from scratch. In order to reduce the cardinality of the search space the constraint that each node in the Bayesian network as at most ''k'' parents is assumed.	+
−	* '''''Genetic Estimation Distribution Algorithm (GEDA). '''''This class of Evolute Algorithms is a new proposal class, where genetic variation operations such mutation and crossover are applied to a probabilistic model of the population, rather than directly to an individual of the population. Each generation of a GEDA is composed by estimation of population distribution, variation of the probabilistic model, and sampling from the variated model.	+	*[http://iridia.ulb.ac.be/~gvalentini/ Gabriele Valentini] - gvalentini [AT] iridia.ulb.ac.be
−	** ''gcGA.''	+
−	* '''''Operative Reaserch classical algorithms (OR). '''''It is distinguished by its frequent use to examine an entire management information system, rather than concentrating only on specific elements. An operations researcher faced with a new problem is expected to determine which techniques are most appropriate given the nature of the system, the goals for improvement, and constraints on time and computing power. For this and other reasons, the human element of OR is vital. Like any other tools, OR techniques cannot solve problems by themselves.	+	*[[User:DavideCucci| Davide Cucci]] - cucci [AT] elet.polimi.it
−	** ''Pseudo Boolean Linear Programming.''	+
−	=== '''Optimization Problems''' ===	+	'''Formerly involved'''
−	An optimization problem is defined by a specified problem space ''X'', an objective functions ''F'' , a search	+	*Emanuele Corsano
−	space ''G'', a set of search operations ''A''. Specifying the elements of this tuple is the most important prerequisite for any experiment. The problem space ''X'' is the space of all possible solutions canditates, in our case is defined by every combinations of a fixed lengh bit string. The objective functions ''F'' (''fitness'') measure the utility of a solution. As convention, we decide that every objective function return a real number between in the [0,100] set, and if nothing else is stated, maximization is assumed. The search space ''G'' is the space of elements where the search operations are applied. For evoptool is defined by the individual lenght (''size''). The search operations ''A'' are all the operations used for perform the search, and such we compare several algorthms a time, they are defined by the particular algorthm used.	+
−	----	+	== PPSN 2012 ==
−	Inside evoptool, is possible to choose between several different Objective Functions and customize a proper Optimization Problem setting the individual size and choosing a set of Algorithms to compare. The following list contains the Objective Functions implemented for the moment.	+	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.
−	* ''AltBits.''	+
−	* ''One Max and One Zero Max. ''The task in the OneMax problem is to find a binary string of length ''n'' consisting of all ones. The search and problem space are both the fixed-length bit strings ''G = X = Bn''. Each gene (bit) has two alleles 0 and 1 which also contribute exactly this value to the total fitness.	+
−	* ''BinVal. ''It is something like a perverted version of the OneMax problem, with the objective function defined as the real value of the binary string. Since the bit at index i has a higher contribution to the fitness than all other bit at higher indices together, the comparison between two solution candidates x1 and x2 is won by the	+
−	lexicographically bigger one. We can expect that the bits with high contribution (high salience) will converge quickly whereas the other genes with lower salience are only pressured by selection when all others have already been fully converged.	+
−	* ''F3d Deceptive.''	+
−	** ''F3d Deceptive Bipolar.''	+
−	** ''F3d Deceptive Ovelapping.''	+
−	* ''Four and Six Peaks.'' This Objective Function have some global optima wich are isolated, and therefore are difficult to find. It also have some local optima which are easy to get and therefore the search algorithms tend to converge on local optima.	+
−	* ''Trap5.  ''Subjected to maximization based on the Hamming distance to a pre-defined global optimum X' . They build a second, local optimum in form of a hill with a gradient pointing away from the global optimum. This trap is specified with two values, b and r, where b corresponds to the width of the attractive basins (in our case b = 5)and r to their relative importance.	+
−	* ''Quadratic.''	+
−	* ''Sat Lib.''	+
−	* ''SumVal.''	+
−	* ''Royal Road.''	+
−	* ''Liepins Vose Fully Deceptive.''	+
−	=== '''Graphic User Interface'''===	+	The experiments were run using the unstable version of evoptool, which is available trought SVN at
−	The graphic user interface of evoptool is quite intuitive. The user can easily customize his own experiment, and visualize the results graph. In the next rows there are shortly described the GUI componets and their use.	+
−	[[Image:Evo2.png|600px|thumb|center|Evoptool running on Ubuntu 9.04.]]	+
−	# ''Control Buttons.'' There are three control buttons which can be used to start or stop the execution of an experitment, and to force the update of the graphs.	+
−	# ''Objective Function Settings.'' This part of the toolbar allows the customization of the Objective Problem. It is possible to select an objective function type and fix the individual size as number of bits.	+
−	# ''Average Mode Setting.'' Pushing this toggled button it is possible to enable ''Average Test Mode''. In this mode, evoptool will run a difined number of algortihms for each selected one in the ''Algorithm Panel'', and it will perform the average of the different executions of the same algorithm. This option is usefull to show the average behavior of searchers.	+
−	# ''Algorithms Panel.'' This panel allows to select a set of algorithms to compare in a particular execution. It is subdivided in four parts, in order to classify algorithms for belonging kind. Next, is possible to customize the parameters of each selected algorithm.	+
−	# ''Result Tabs. ''This tabs show the result graphics of the a test execution in real time mode. At this time, only the average fitness graph is implemented in evoptool, but new graphs can be easily added in future.	+
−	# ''Log Monitor. ''This monitor keep the user informed about the execution status and several others information such warnings or errors.	+
−	==== '''Video Example of Use'''====	+
−	In this short video is briefly presented an example of use of evoptool. It starts by configuring the Optimization Problem to solve, next select a set of algortihms to compare and finally is showed the execution of a test.	+
−	:::::{{#ev:youtube|I6NNRWtFptk|550}}	+	https://svn.ws.dei.polimi.it/evoptool/branches/unstable
−	=== '''Command Line'''===	+	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.
−	Evoptool is also powered by a ''command line'' interface, so when the GUI is not needed and can be an unusefull weight, it is possible to escape it and run the software just typing a command inside a terminal such ''bash or dash''.	+
−	==== '''Commands''' ====	+	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:
−	* ''--help (-h). ''This command print at video usefull information about evoptool commands and their use.	+
−	* ''--version (-v). ''This command print at video information about currently version of the software and others informations such ''Copyright'' or link to the evoptool web page.	+
−	* ''--nogui [CONF_FILE] (-n). ''This is the more usefull command, such it allows to run evoptool from command line and to achieve the results as an image graph or, for more complex purposes, as data files. This command need only of one parameter that specify the ''CONFIGURATION FILE'' for the execution. The configuration file parameter need to be specified with a proper ''PATH'' if, and only if, its position differs from the program executable folder. In the next image is possible to view the output generated from an execution of a test from command line.	+
−	[[Image:Evo3.png|600px|thumb|center|Evoptool running from command line]]	+
−	==== '''Configuration File''' ====	+	algorithm-n-N-selection_rate-maps_number.tar
−	In order to run evoptool from command line, is needed a proper ''configuration file'' that define all the contraints and settings for that particulat test execution. A default configuration file can be found in the folder ''../evoptool/trunk/gui/bin/confi.evoptool'', and the user is free to customize it or to create a different file in a different position and specify the entire ''PATH'' before run evoptool.	+
−	The configuration file is quite intuitive, and the default file presents several usuful information about the contents and how to modify it. It is subdivided in three main section, each of them define the behavior of a particular component.	+
−	* ''General Settings.'' Allows to specify if the execution of a test have to be a normal one (''Single Run Mode''), or an average execution (''Multi Run Mode''). In the last case, the parameter ''N_ALGO'' define the number of execution of an algorithm on that perform the average.	+	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
−	* ''Objective Function.''Allows to specify which is the Objective Function for this test execution and to define the needed parameters as the individual size or others.	+
−	* ''Algorithms.'' Allows to define a set of algorithms to run, and to specify their parameters individually.	+
−	Some usefull information on how to customize the configuration file are listed in the next rows:	+	https://svn.ws.dei.polimi.it/evoptool/branches/papers/PPSN-2012-FCA/experiments/
−	* Comment or uncomment lines with a simbol '#' for customize the configuration.	+
−	* Mandatory sections are signaled with a simbol '*', other sections can be deleted.	+
−	* Uneeded parameters must be commented!	+
−	* Values must be between square braces.	+
−	* Order of parameters inside sections is mandatory!	+
−	* There must be the end of file delimiter at last line.	+
−	== '''Documentation''' ==	+	== Mailing List ==
		+	http://groups.google.com/group/evoptool
−	Evoptool is a software with the purpose to compare the performance of several different algorithms from the Evolutive family and, for obvious reasons, with some algorithms from the classical Operation Research family.	+	== Features ==
−	Evoptool is written in C++ for the GNU/Linux platform and it exploit the Gtk libraries (in this case gtkmm libraries) and GNUplot utility. Inside this tool there are several implemented algorithms and some wrapped ones from already existing applications.	+
−	[[Image:Schermata.png|600px|thumb|center|Evoptool running on Ubuntu 9.04.]]	+	====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
−	==='''Software Modules''' ===	+	References to original papers will be added soon.
−	Evoptool is made up of several different modules (or libraries). This architecture make easy to organize files and better understanding how the application work.	+
−	* ''common - '' It contains commons classes and ancestors for the algorithm modules and for the optimization function module.	+	====Benchmark functions implemented====
−	* ''ga - '' It contains the implementation of several Genetic Algorithms.	+	* OneMax
−	* ''eda - '' It contains the implementation of several Estimation Distribution Algorithms.	+	* AltBit
−	* ''geda - '' It contains the implementation of several gEDAs.	+	* Trap3
−	* ''or - '' It contains the implementation of some algorithms from the classical Operation Research.	+	* Trap5
−	* ''opt-pbl - '' It contains the implementation of several objective functions (fitness), that represents different problem instances.	+	* IsingSpinGlass2D (*)
−	* ''gui - '' This module is the main one, it contains all the classes for manage GUI (algorithm decorators). From the other side it implements the multithread mechanism under the GUI, and last but not list it contains the wrapped applications and take care about wrapping.	+	* IsingSpinGlass3D (*)
−	* ''misc - '' It contains general utility classes such rondom seed geerator.	+	* Max Cut
−	=== '''Hierarchies''' ===	+	(*) 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/
−	==== '''Algorithms Hierarchy''' ====	+	== Download ==
−	==== '''Decorators Hierarchy''' ====	+
−	==== '''Objective Functions Hierarchy''' ====	+
−	=== '''Usefull Links'''===	+
−	* [https://svn.ws.dei.polimi.it/evoptool/ Evoptool Repository] (Need authentication!)	+
−	* [http://www.gnu.org/software/gsl/ GNU Scientific Library]	+
−	* [http://www.gtkmm.org/ GUI Library Gtkmm]	+
−	* [http://www.boost.org/ Boost Library]	+
−	* [http://www.gnuplot.info/ Gnuplot Utility]	+
−	* [http://www.cplusplus.com/reference/ C++ Library reference]	+
−	== '''How To Add New Features''' ==	+	svn checkout https://svn.ws.dei.polimi.it/evoptool/trunk --username usrevoptool --password evoptoolpsw
−	=== '''Add an Algorithm ''' ===	+
−	=== '''Add a Decorator ''' ===	+	Developers may also access unstable branch. Contact the evoptool team for more details.
−	=== '''Add an Objective Function ''' ===	+
−	=== '''Update Configuration Parser ''' ===	+	== 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''
		+	** ''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 <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 ====
		+
		+	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 <tt>Algorithms</tt> 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 <tt>bool XMLParser::parseAlgorithms</tt> and insert an new entry for your algorithm in the <tt>algorithmParameters</tt> 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 <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 <tt>bool XMLParser::parseAlgorithms</tt>, 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, <tt>params->rng</tt>.
		+
		+	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 <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
		+
		+	1. copy the example submodule <code>exampleRunAlgorithm</code> in a new folder named <code>myexample</code> in
		+
		+	evoptool/core/src
		+
		+	2. modify the <code>Makefile</code> in the <code>myexample</code> directory, see comments in the makefile for more details.
		+
		+	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.
		+
		+	4. from <code>evoptool/core/src/myexample</code> run
		+
		+	make bin
		+
		+	The bin file is create in <code>evoptool/core/bin</code> and copied in <code>evoptool/bin</code>
		+
		+	NOTICE that <code>evoptool/core/bin</code> may be deleted after a <code>make cleanall</code>
		+
		+	5. from <code>evoptool/bin</code> 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.

---

Latest revision as of 19: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.