Talk:Evoptool: Evolutionary Optimization Tool - Revision history

LuigiMalago: Blanked the page

2011-10-22T15:37:13Z

Blanked the page

Show changes

GabrieleValentini: /* Add an Objective Function */

2010-11-17T22:09:05Z

‎Add an Objective Function

GabrieleValentini: /* Add an Objective Function */

2010-11-17T22:03:05Z

‎Add an Objective Function

GabrieleValentini: /* ToDo List (only for developers) */

2010-08-19T10:02:28Z

‎ToDo List (only for developers)

GabrieleValentini: /* ToDo List (only for developers) */

2010-07-16T15:20:15Z

‎ToDo List (only for developers)

GabrieleValentini: /* Old Page */

2010-07-16T15:17:46Z

‎Old Page

GabrieleValentini: /* New Page */

2010-05-30T18:43:48Z

‎New Page

GabrieleValentini: /* ToDo List (only for developers) */

2010-05-30T18:43:26Z

‎ToDo List (only for developers)

GabrieleValentini: /* Benchmarks */

2010-02-21T21:35:26Z

‎Benchmarks

GabrieleValentini: /* Benchmarks */

2010-02-21T21:32:07Z

‎Benchmarks

@@ Line 134: / Line 134: @@
 # ''Fill files.'' Every objective function must inherits from the abstract class ''ObjectiveFunction'', or from one of its concrete implementation. It must implements or overwrites the abstract function ''f'' (fitness) inherited from its superclass.
 # ''Configure headers.'' Add the ''SomeObjFun.h'' to ''ObjectiveFunctions.h'' (note the 's'!) that is placed in the ''../evoptool/trunk/opt-pbl/src/'' folder. This will avoid to include a long list of headers within the libraries ''core'' and ''gui''.
-# ''Update Enumeration.'' Add a new value for the enum ''GUI::ObjFunctions'' defined in the GUI header file. The header ''GUI.h'' can be found in the ''../evoptool/trunk/gui/src/'' folder.
+# ''Update Enumeration.'' Add a new value for the enum ''Evoptool::Task'' defined in the ''Evoptool.h'' header file. The header ''Evoptool.h'' can be found in the ''../evoptool/trunk/core/src/'' folder.
-# ''Update GUI''. In order to link the just created fitness function with the grafic user interface it is needed to modify the ''GUI.cpp'' file.
+# ''Update GUI''. In order to link the just created fitness function with the grafic user interface it is needed to modify the ''EvoptoolGUI.cpp'' file.
 #* ''getSelectedObjectiveFunction function''. Add the new component to the ''switch/case'' block.
 #* ''initObjList function.'' Add the new componet to the ''Gtk::TreeModel'' object, so it will be showed in the proper selection menu.
-# ''Update Configuration Parser.'' This is a quite simple task to do, just look to the code!
+# ''Update Configuration Parser.''
 == '''Usefull Links''' ==

@@ Line 133: / Line 133: @@
 # ''Create files.'' Create the files ''SomeObjFun.h'' and ''SomeObjFun.cpp'' inside the ''../evoptool/trunk/opt-pbl/src/'' folder.
 # ''Fill files.'' Every objective function must inherits from the abstract class ''ObjectiveFunction'', or from one of its concrete implementation. It must implements or overwrites the abstract function ''f'' (fitness) inherited from its superclass.
-# ''Configure headers.'' Add the ''SomeObjFun.h'' to ''ObjectiveFunctions.h'' (note the 's'!) that is placed in the ''../evoptool/trunk/gui/src/'' folder. This will avoid to include a long list of headers to the main GUI class.
+# ''Configure headers.'' Add the ''SomeObjFun.h'' to ''ObjectiveFunctions.h'' (note the 's'!) that is placed in the ''../evoptool/trunk/opt-pbl/src/'' folder. This will avoid to include a long list of headers within the libraries ''core'' and ''gui''.
 # ''Update Enumeration.'' Add a new value for the enum ''GUI::ObjFunctions'' defined in the GUI header file. The header ''GUI.h'' can be found in the ''../evoptool/trunk/gui/src/'' folder.
 # ''Update GUI''. In order to link the just created fitness function with the grafic user interface it is needed to modify the ''GUI.cpp'' file.

@@ Line 5: / Line 5: @@
 * '''TODO''' DEUM: svd resolutor causes problems durign execution.
 * '''TODO''' export data in tgz not in tar
-* '''TODO''' modalità averageOver sfruttare parallelismo con 1 thread x algoritmo, classe solver
+* '''TODO''' BugFix, convertire XMLParser e tutti i decorator ad usare Algorithm->getName() invece che stringhe defini manualmente (inconsistenze).
 = Old Page =

@@ Line 5: / Line 5: @@
 * '''TODO''' DEUM: svd resolutor causes problems durign execution.
 * '''TODO''' export data in tgz not in tar
 = Old Page =

@@ Line 1: / Line 1: @@
 = Old Page =
 === '''Graphic User Interface'''===
 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.
@@ Line 208: / Line 146: @@
 * [http://www.gnuplot.info/ Gnuplot Utility]
 * [http://www.cplusplus.com/reference/ C++ Library reference]

← Older revision		Revision as of 18:43, 30 May 2010
Line 1:		Line 1:
−	~~= New Page =~~
−	~~== Evoptool Description ==~~
−	~~=== Algorithms ===~~
−	~~Evoptool offers a set of algorithm implementations coming from several paradigms within Evolutionary Computation, in the context of black-box optimization of boolean functions.~~

−	* Genetic Algorithms (GAs)
−	** ''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.
−
−	* Estimation of Distributions Algorithms (EDAs)
−	** Univariate EDAs:
−	*** ''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 ===~~
−	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.~~
−
−	* ''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.
−	* ''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).
−
−	* ''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.
−	* ''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''.
−	~~Last but not least, there are implementation of real-like applications as:~~
−
−	~~=== Statistics ===~~
−	~~== Compile the Source ==~~
−	~~=== Entire Tool ===~~
−	~~=== Individual Library ===~~
−	~~== Run the Tool ==~~
−	~~=== GUI ===~~
−	~~=== Command Line ===~~
−	~~== Source Documentation ==~~
−	~~== Download Evoptool ==~~

	= Old Page =		= Old Page =

@@ Line 260: / Line 260: @@
 == ''ToDo List (only for developers)''==
-* '''TOSO:''' UMDA check algorithm.
+* '''TODO:''' XMLParser incorrect propagation of erroFlag, does not discovers errors
-* '''TODO:''' sBOA integration.
-** Adjust normalization of value computed by FourPeaks and SixPeaks fitness functions, must be between [0,100].
-** Add to sBOA unsupported objective problem (SatLib, SpinGlass, TextureRestoration).
 * '''TODO''' DEUM: svd resolutor causes problems durign execution.
 * '''TODO''' export data in tgz not in tar

← Older revision		Revision as of 21:35, 21 February 2010
Line 35:		Line 35:
	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).		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).

		+	* ''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.
		+	* ''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''.
	Last but not least, there are implementation of real-like applications as:		Last but not least, there are implementation of real-like applications as:

@@ Line 28: / Line 28: @@
 A first set of benchmarks is composed of simple toy problems without any variable dependency, therefore with an underlying univariate structure.
-** ''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.
+* ''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.
-<math>f(x) = \sum_{i = 1}^{n} x_{i}</math> $$  $$
+* ''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.
 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).