|
|
latest version v1.9 - last update 10 Apr 2010 |
|
Pareto Front computation with PESA. More...
#include <ltiParetoFront.h>
Classes | |
| class | individual |
| Structure characterizing an individual. More... | |
| class | parameters |
| The parameters for the class paretoFront. More... | |
Public Types | |
| typedef std::vector< bool > | chromosome |
Public Member Functions | |
| paretoFront () | |
| paretoFront (const parameters &par) | |
| paretoFront (const paretoFront &other) | |
| virtual | ~paretoFront () |
| virtual const char * | getTypeName () const |
| virtual bool | apply (matrix< double > &front) |
| virtual bool | apply (matrix< double > &front, std::vector< functor::parameters * > &phenotypes) |
| virtual bool | resume (matrix< double > &front, std::vector< functor::parameters * > &phenotypes) |
| paretoFront & | copy (const paretoFront &other) |
| paretoFront & | operator= (const paretoFront &other) |
| virtual functor * | clone () const =0 |
| const parameters & | getParameters () const |
| bool | trash (std::vector< functor::parameters * > phenotypes) const |
Additional Information | |
| void | getAnalyzedBox (matrix< double > &bbox) const |
| void | getDominatedIndividuals (matrix< double > &dindiv) const |
| bool | getDataFromLog (const std::string &logFile, matrix< double > &front, std::vector< functor::parameters * > &phenotypes) |
Progress Info | |
| void | setProgressObject (const progressInfo &progBox) |
| void | removeProgressObject () |
| bool | validProgressObject () const |
| bool | validProgressObject (const int detailLevel) const |
| progressInfo & | getProgressObject () |
| const progressInfo & | getProgressObject () const |
Public methods to be reimplemented | |
| virtual bool | chromosomeToPhenotype (const chromosome &genotype, functor::parameters &phenotype) const =0 |
| virtual functor::parameters * | chromosomeToPhenotype (const chromosome &genotype) const =0 |
| virtual bool | phenotypeToChromosome (const functor::parameters &phenotype, chromosome &genotype) const =0 |
| virtual int | getChromosomeSize () const =0 |
| virtual bool | evaluateChromosome (const chromosome &individual, dvector &fitness)=0 |
Conversion Tools | |
| int | binToInt (const chromosome &chain, const int startBit, const int bitLength, int32 &result) const |
| int | binToInt (const chromosome &chain, const int startBit, const int bitLength, const int lowLimit, const int highLimit, int32 &result) const |
| int | binToUInt (const chromosome &chain, const int startBit, const int bitLength, uint32 &result) const |
| int | binToDouble (const chromosome &chain, const int startBit, const int bitLength, const double &lowLimit, const double &highLimit, double &result) const |
| int | intToBin (const int value, const int startBit, const int bitLength, chromosome &chain) const |
| int | intToBin (const int value, const int startBit, const int bitLength, const int lowLimit, const int highLimit, chromosome &chain) const |
| int | uintToBin (const uint32 value, const int startBit, const int bitLength, chromosome &chain) const |
| int | doubleToBin (const double &value, const int startBit, const int bitLength, const double &lowLimit, const double &highLimit, chromosome &chain) const |
Protected Member Functions | |
| parameters & | getRWParameters () |
| virtual bool | initInternalPopulation (std::vector< individual > &data) |
| double | rand () const |
Methods to be reimplemented | |
| virtual bool | randomIndividual (chromosome &genotype) |
| virtual bool | mutate (const chromosome &parent, chromosome &mutant) |
| virtual bool | crossover (const chromosome &parent1, const chromosome &parent2, chromosome &child) |
Pareto Front computation with PESA.
The Pareto Front functor provides an evaluation mechanism for algorithms, in which the qualitiy of the algorithm cannot be restricted to one single scalar measure. It is adecuate to compare different parameterizations for one or several algorithms, which are supposed to solve the same task.
This class generates a "front" in a multidimensional fitness space, which represents a trade-off between several fitness values, that each derived class explicitelly implements.
The algorithm used here to generate the front is called PESA (Pareto Envelope-based Selection Algorithm), and it is described in:
David. W. Corne, Joshua D. Knowles and Martin J. Oates The Pareto Envelope-based Selection Algorithm for Multiobjective Optimization. In: Proceedings of the International Conference on Parallel Problem Solving from Nature (PPSN VI). (2000) 839-848
A good introduction to the application of this problem for the evaluation of image processing algorithms, specifically to the evaluation of segmentation is given in:
Mark Everingham, Henk Muller and Barry Thomas, Evaluating Image Segmentation Algorithms using the Pareto Front. In Proceedings of the 7th European Conference on Computer Vision (ECCV2002), Part IV (LNCS 2353), pages 34-48. Springer, June 2002.
http://www.cs.bris.ac.uk/Tools/Reports/Abstracts/2002-everingham-1.html
This is the parent class for all evaluation algorithms using PESA. Its kern administrates the evolutionary part of the algorithm and the derived classes provide the adaptions necessary for each application in particular, which include the conversion between functor parameters and a binary chain chromosome representation, the computation of the fitness measures, etc.
The current class also provides some simple tools that simplify the construction of evaluation functors.
There is a deviation from the original paper which is more suitable for the evaluation of algorithms used here. The original algorithms separates the fitness space into regular hyperboxes and computes the density of individuals in each hyperbox to decide which elements will be used for crossover or mutation (those boxes with the smallest density) and which elements need to be removed (those with the highest density). The computation of the density is in the present functor much more computationally expensive, but its computation is nevertheless negligible in comparison to the computation of the fitness measures for an algorithm:
The current algorithm keeps track of the bounding box of the fitness space for which individuals have been created. This bounding box is used to determine the size of a Gaussian kernel, which will be used on each individual to compute the influence of all other individuals in the front. This way, the selection is not strongly bounded to the selection of a partitioning of the fitness space.
For an example of an evaluation class see lti::locationSearchEvaluation.
To monitor the progress of the evolutionary process this functor makes use of classes derived from lti::progressInfo, where the detail level of the substeps can be used to show the information required.
| typedef std::vector<bool> lti::paretoFront::chromosome |
Type used to represent chromosomes.
| lti::paretoFront::paretoFront | ( | ) |
Default constructor.
| lti::paretoFront::paretoFront | ( | const parameters & | par | ) |
Construct a functor using the given parameters.
| lti::paretoFront::paretoFront | ( | const paretoFront & | other | ) |
Copy constructor.
| other | the object to be copied |
| virtual lti::paretoFront::~paretoFront | ( | ) | [virtual] |
Destructor.
| virtual bool lti::paretoFront::apply | ( | matrix< double > & | front, | |
| std::vector< functor::parameters * > & | phenotypes | |||
| ) | [virtual] |
Compute the Pareto Front and the corresponding parameter objects for each non-dominated point.
Since the evaluation function can get as input any kind of information, it is left to the derived classes to provide alternative ways of doing this: other apply methods or use() methods to indicate the data set to be used in the algorithm evaluation.
The Pareto Front will be represented by a matrix of size m x n with m parameters::externalPopulationSize and n fitnessSpaceDimensionality.
For each row in this matrix (an individual), the corresponding parameter setting (a phenotype) is returned. Since different algorithms usually use different parameters, this can only be done with dynamically allocated objects. You need to take care of them, but this class provides an utility trash() method, which deletes them for you if you want to.
| front | matrix containing for each row the multidimensional fitness value. | |
| phenotypes | the parameters for each fitness value. |
| virtual bool lti::paretoFront::apply | ( | matrix< double > & | front | ) | [virtual] |
Compute the Pareto Front.
Since the evaluation function can get as input any kind of information, it is left to the derived classes to provide alternative way of doing this: other apply methods or use() methods to indicate the set of data to be used.
The Pareto Front will be represent by a matrix of size m x n with m parameters::externalPopulationSize and n fitnessSpaceDimensionality.
| front | matrix containing for each row the multidimensional fitness value. |
| int lti::paretoFront::binToDouble | ( | const chromosome & | chain, | |
| const int | startBit, | |||
| const int | bitLength, | |||
| const double & | lowLimit, | |||
| const double & | highLimit, | |||
| double & | result | |||
| ) | const |
Convert binary chain into an double floating point representation.
The binarization of floating point values for "genetic" manipulation can easily result in non-sense values. Therefore here a specified value range is quantized in the desired number of bits between 0 and 31.
| chain | the binary chain representing a chromosome | |
| startBit | index of the bit, at which the integer begins. | |
| bitLength | number of bits used for this double number (never greater or equal than 32). | |
| lowLimit | lowest value (inclusive) that the stored variable can take. | |
| highLimit | highest value (inclusive) that the stored variable can take. | |
| result | double value read from the chain |
| int lti::paretoFront::binToInt | ( | const chromosome & | chain, | |
| const int | startBit, | |||
| const int | bitLength, | |||
| const int | lowLimit, | |||
| const int | highLimit, | |||
| int32 & | result | |||
| ) | const |
Convert binary chain into an integer representation.
The lower indices in the chain represent the MSB of the number.
If the given value range is higher than the range representable with the given number of bits, only the lowLimit will be considered. If the read number has a higher range than the high-low one, then the modulo operation will be applied to keep the values in range.
| chain | the binary chain representing a chromosome | |
| startBit | index of the bit, at which the integer begins | |
| bitLength | number of bits used for this integer (never greater than 32). | |
| lowLimit | lowest value (inclusive) that the stored variable can take. | |
| highLimit | highest value (inclusive) that the stored variable can take. | |
| result | integer value read from the chain |
| int lti::paretoFront::binToInt | ( | const chromosome & | chain, | |
| const int | startBit, | |||
| const int | bitLength, | |||
| int32 & | result | |||
| ) | const |
Convert binary chain into an integer representation.
The lower indices in the chain represent the MSB of the number.
| chain | the binary chain representing a chromosome | |
| startBit | index of the bit, at which the integer begins | |
| bitLength | number of bits used for this integer (never greater than 32). | |
| result | integer value read from the chain |
| int lti::paretoFront::binToUInt | ( | const chromosome & | chain, | |
| const int | startBit, | |||
| const int | bitLength, | |||
| uint32 & | result | |||
| ) | const |
Convert binary chain into an unsigned integer representation.
The lower indices in the chain represent the MSB of the number.
| chain | the binary chain representing a chromosome | |
| startBit | index of the bit, at which the integer begins | |
| bitLength | number of bits used for this integer (never greater than 32). | |
| result | integer value read from the chain |
| virtual functor::parameters* lti::paretoFront::chromosomeToPhenotype | ( | const chromosome & | genotype | ) | const [pure virtual] |
Return a fresh allocated parameters for the evaluated functor, which is equivalent to the given genotype.
There are some tools to convert binary chains into standard types:
Implemented in lti::locationSearchEvaluation, lti::paretoFrontTester, and lti::segmentationEvaluation.
| virtual bool lti::paretoFront::chromosomeToPhenotype | ( | const chromosome & | genotype, | |
| functor::parameters & | phenotype | |||
| ) | const [pure virtual] |
Convert a binary-chain representation of a chromosome to a valid parameter object.
There are some tools to convert standard types into some binary chains, which can be used by all derived classes:
Implemented in lti::locationSearchEvaluation, lti::paretoFrontTester, and lti::segmentationEvaluation.
| virtual functor* lti::paretoFront::clone | ( | ) | const [pure virtual] |
Returns a pointer to a clone of this functor.
Implements lti::functor.
Implemented in lti::locationSearchEvaluation, and lti::paretoFrontTester.
| paretoFront& lti::paretoFront::copy | ( | const paretoFront & | other | ) |
Copy data of "other" functor.
| other | the functor to be copied |
Reimplemented from lti::functor.
| virtual bool lti::paretoFront::crossover | ( | const chromosome & | parent1, | |
| const chromosome & | parent2, | |||
| chromosome & | child | |||
| ) | [protected, virtual] |
Crossover between two chromosomes.
This should be reimplemented to ensure that the crossover produces a valid phenotype.
The default implementation does a so called uniform crossover, in which each pair of corresponding bits are exchanged with a probability of 0.5, followed by the mutation indicated in the original PESA paper.
Reimplemented in lti::paretoFrontTester.
| int lti::paretoFront::doubleToBin | ( | const double & | value, | |
| const int | startBit, | |||
| const int | bitLength, | |||
| const double & | lowLimit, | |||
| const double & | highLimit, | |||
| chromosome & | chain | |||
| ) | const |
Convert double value in a binary change.
| value | value to be quantized. | |
| startBit | starting index in the chain, where the representation has to be stored. | |
| bitLength | number of bits used to represent the number. If it is not possible, then -1 will be returned. | |
| lowLimit | lowest value (inclusive) that the stored variable can take. | |
| highLimit | highest value (inclusive) that the stored variable can take. | |
| chain | binary change with the resulting representation. |
| virtual bool lti::paretoFront::evaluateChromosome | ( | const chromosome & | individual, | |
| dvector & | fitness | |||
| ) | [pure virtual] |
Evaluate Chromosome.
This method is one of the most important ones for the pareto evaluation. Its task is to produce a multidimensional fitness measure for a given chromosome.
It returns true if the evaluation was successful, of false if the phenotype represents some invalid parameterization. It is highly recomended that the mutation and crossover methods are reimplemented to avoid invalid parameterizations.
There are mainly two types of fitness measures that can be analyzed with a functor of this kind: empirical goodness and empirical discrepancy (Zhang). The empirical goodness computes some measure using exclusively the test data, without requiring any ground truth. The empirical discrepancy assumes the existency of ground truth and provides as measure some distance between the result of an algorithm and the ground truth. Each class derived from paretoFront should specify clearly which kind of fitness measures it provides.
Implemented in lti::locationSearchEvaluation, lti::paretoFrontTester, and lti::segmentationEvaluation.
| void lti::paretoFront::getAnalyzedBox | ( | matrix< double > & | bbox | ) | const |
Fitness space bounding box.
After determining the Pareto Front, you usually want to know the bounding box of the fitness space that was analyzed. This for visualization purposes among others.
After the apply() methods you can get the bounding box calling this one.
This will always be a matrix 2 x parameters::fitnessSpaceDimensionality, where the first row contains the minima for each dimension and the second row the maxima.
| virtual int lti::paretoFront::getChromosomeSize | ( | ) | const [pure virtual] |
Return the length in bits for a chromosome.
This method needs to be reimplemented, in order to get some default implementations to work.
Implemented in lti::locationSearchEvaluation, and lti::paretoFrontTester.
| bool lti::paretoFront::getDataFromLog | ( | const std::string & | logFile, | |
| matrix< double > & | front, | |||
| std::vector< functor::parameters * > & | phenotypes | |||
| ) |
Get data from log.
If a log file is generated, usually you cannot read the used parameterization. With this method you will get from the log file the list of parameters and their corresponding fitness values, as if you had used the corresponding apply method.
The parameters of the current functor will change without invalidating the reference. Therefore this method is not constant.
| void lti::paretoFront::getDominatedIndividuals | ( | matrix< double > & | dindiv | ) | const |
Dominated individuals.
This method returns all points in the fitness space that were analyzed while constructing the feature space. For this method to return something meaningful, you need to set in the parameters the attribute logAllEvaluations to true.
The resulting matrix will have the size n x parameters::fitnessSpaceDimensionality, where n is the number of dominated individuals analyzed in the process.
| const parameters& lti::paretoFront::getParameters | ( | ) | const |
Returns used parameters.
Reimplemented from lti::functor.
Reimplemented in lti::locationSearchEvaluation, and lti::segmentationEvaluation.
| const progressInfo& lti::paretoFront::getProgressObject | ( | ) | const |
get progress object
| progressInfo& lti::paretoFront::getProgressObject | ( | ) |
get progress object
| parameters& lti::paretoFront::getRWParameters | ( | ) | [protected] |
Returns used parameters.
| virtual const char* lti::paretoFront::getTypeName | ( | ) | const [virtual] |
Returns the name of this type ("paretoFront").
Reimplemented from lti::functor.
Reimplemented in lti::locationSearchEvaluation, lti::paretoFrontTester, and lti::segmentationEvaluation.
| virtual bool lti::paretoFront::initInternalPopulation | ( | std::vector< individual > & | data | ) | [protected, virtual] |
Initialize the internal population.
You usually don't want to reimplement this method, but randomIndividual(). However, you can reimplemented it if you need more that the standard generation of parameters::internalPopulationSize random individuals.
| int lti::paretoFront::intToBin | ( | const int | value, | |
| const int | startBit, | |||
| const int | bitLength, | |||
| const int | lowLimit, | |||
| const int | highLimit, | |||
| chromosome & | chain | |||
| ) | const |
Convert integer value in a binary change.
| value | the value to be stored. | |
| startBit | starting index in the chain, where the representation has to be stored. | |
| bitLength | number of bits used to represent the number. If it is not possible, then -1 will be returned. | |
| chain | binary change with the resulting representation. | |
| lowLimit | lowest value (inclusive) that the stored variable can take. | |
| highLimit | highest value (inclusive) that the stored variable can take. |
| int lti::paretoFront::intToBin | ( | const int | value, | |
| const int | startBit, | |||
| const int | bitLength, | |||
| chromosome & | chain | |||
| ) | const |
Convert integer value in a binary change.
| value | the value to be stored. | |
| startBit | starting index in the chain, where the representation has to be stored. | |
| bitLength | number of bits used to represent the number. If it is not possible, then -1 will be returned. | |
| chain | binary change with the resulting representation. |
| virtual bool lti::paretoFront::mutate | ( | const chromosome & | parent, | |
| chromosome & | mutant | |||
| ) | [protected, virtual] |
Mutate the given chromosome.
This should be reimplemented to ensure that the mutation is a valid phenotype.
The default implementation flips the bits with the probability given in the parameters.
Reimplemented in lti::paretoFrontTester.
| paretoFront& lti::paretoFront::operator= | ( | const paretoFront & | other | ) |
| virtual bool lti::paretoFront::phenotypeToChromosome | ( | const functor::parameters & | phenotype, | |
| chromosome & | genotype | |||
| ) | const [pure virtual] |
Convert a valid parameters object (phenotype) into binary-chain representation of a chromosome.
Implemented in lti::locationSearchEvaluation, and lti::paretoFrontTester.
| double lti::paretoFront::rand | ( | ) | const [inline, protected] |
Get a random value between 0 and 1.
References lti::continuousRandomDistribution::draw().
| virtual bool lti::paretoFront::randomIndividual | ( | chromosome & | genotype | ) | [protected, virtual] |
Generate a random individual.
You usually will need to reimplement this method to ensure that the generated random individuals have a valid phenotype, i.e. that the chromosome binary representation in "genotype" has an equivalent parameter object for the class you are using.
Return true if successful, false otherwise.
Reimplemented in lti::paretoFrontTester.
| void lti::paretoFront::removeProgressObject | ( | ) |
remove the active progress object
| virtual bool lti::paretoFront::resume | ( | matrix< double > & | front, | |
| std::vector< functor::parameters * > & | phenotypes | |||
| ) | [virtual] |
Compute the Pareto Front and the corresponding parameter objects for each non-dominated point.
This is a special method which reassumes a broken analysis, gaining the lost information from a previously generated file. That file can be generated activating in the parameters the option logFront and indicating there the name for the file.
This method will work only if the parameters logFront and logFilename are properly set (logFront in true and logFilename with the proper filename). It is not named "apply" for the simple reason that the parameters will be changed to those stored in the log-file itself.
Since the evaluation function can get as input any kind of information, it is left to the derived classes to provide alternative ways of doing this: other apply()-methods or use()-methods to indicate the data set to be used in the algorithm evaluation.
The Pareto Front will be represented by a matrix of size m x n with m parameters::externalPopulationSize and n fitnessSpaceDimensionality.
For each row in this matrix (an individual), the corresponding parameter setting (a phenotype) is returned. Since different algorithms usually use different parameters, this can only be done with dynamically allocated objects. You need to take care of them, but this class provides an handy trash() method, which deletes them for you if you want to. If you don't remove them properly you will have a huge memory-leak! Therefore, we recomend the use of trash().
| front | matrix containing for each row the multidimensional fitness value. | |
| phenotypes | the parameters for each fitness value. |
| void lti::paretoFront::setProgressObject | ( | const progressInfo & | progBox | ) |
set a progress object
A clone of the given object will be generated.
| bool lti::paretoFront::trash | ( | std::vector< functor::parameters * > | phenotypes | ) | const |
Delete all parameter objects in the given vector.
| int lti::paretoFront::uintToBin | ( | const uint32 | value, | |
| const int | startBit, | |||
| const int | bitLength, | |||
| chromosome & | chain | |||
| ) | const |
Convert integer value in a binary change.
| value | the value to be stored. | |
| startBit | starting index in the chain, where the representation has to be stored. | |
| bitLength | number of bits used to represent the number. If it is not possible, then -1 will be returned. | |
| chain | binary change with the resulting representation. |
| bool lti::paretoFront::validProgressObject | ( | const int | detailLevel | ) | const |
Return true if a valid progressInfo object has already been set and its detail level is greater or equal the given value.
| bool lti::paretoFront::validProgressObject | ( | ) | const |
return true if a valid progressInfo object has already been set