New parameter types

Adding new parameter types

While ugp3 offers a wide range of parameters and Genetic operators, the need might arise to modify the evolutionary core to add new type of parameters and/or operators for specific projects. In this tutorial, we will follow the necessary steps to add a new type of parameter (permutation); in the following, we will add two new operators (inverOverCrossover and swapMutation) that work on the new parameter.

New parameter type: Permutation

The first step in adding a new type of parameter in ugp3 is design: it is important to understand what is the purpose of the parameter and if the parameter itself could be expressed through the existing ones.

In this case, the idea behind the new parameter is to tackle permutation problems (e.g. the famous Traveling Salesman Problem), where a solution is a certain ordering of a given set of elements. There are of course several ways to express an ordering of elements without resorting to a new parameter: for example, we could associate a floating point weight between 0 and 1 to each variable, and subsequently sort them in ascending order of weight. Another individual representation might be a set of operations done on the initial vector (e.g. a set of swaps).

Nevertheless, both the aforementioned representations lack a sufficient "closeness" between related individual: for example, a mutation in a single floating point weight might abruptly disrupt the previous ordering, moving the children individual very far from the parent in the genotype space; and a crossover between two set of operations might create children individual that do not have common parts with their parents.

The best way to obtain such "closeness" is therefore to create a new type of parameter, to specifically represent permutation problems.

Making it compile

The first step is to try and recycle as much code as possible. In our case, there is another type of parameter (Constant, see Macro) that has several possible values. The main difference is that Constant parameters only assume one value among the possible ones: but a lot of code related to Constant might be re-used.

So, first of all I copied the ConstantParameter.h ConstantParameter.cc ConstantParameter.xml.cc files found in Libs/Constraints directory of ugp3, renaming them into PermutationParameter.h PermutationParameter.cc PermutationParameter.xml.cc respectively.

I changed all the references to the ConstantParameter class inside the files as well. Since we are starting from code cut and pasted, it is important to change the two lines in the initial #ifdef of the class, to avoid problems of inclusion. The two lines in my new file look like:

#ifndef HEADER_UGP3_CONSTRAINTS_PERMUTATIONPARAMETER
#define HEADER_UGP3_CONSTRAINTS_PERMUTATIONPARAMETER

Now, to make our PermutationParameter actually used inside ugp3, we need to include PermutationParameter.h inside all classes that use it. Fortunately, there is only one file, that collects all headers in the Constraints library: Constraints.h.

One final modification in the CMakeLists.txt file in the Libs/Constraints to add the two PermutationParameter.cc PermutationParameter.xml.cc file names in the list of file that will be compiled, and we can try to compile.

If everything is correct, ugp3 will compile without problems. Still, at the moment our PermutationParameter is just an alias for the ConstantParameter, and it is not really used anywhere. In the next sections, we will fix that!

Preparing the field

It is important to notice that the structure of an individual in ugp3 is a constrained tagged graph: each node in the graph can contain several type of parameters, whose current value is stored inside tags, in std::string format. The static class Convert is used to convert different type of values from and to strings.

Since a parameter of type Permutation represents a specific sorting of a set of elements, as an implementation choice I decided to make it equivalent to a vector of strings in a certain order. For example, if the values of our Permutation parameter are "red,blue,green,white,gold" then a specific value could be "green,red,white,blue,gold". A nice addition for our Permutation parameter would be a "delimiter" to be used when the internal representation of the sorting will be written to file.

To add another option to be inserted in the XML, we have to modify PermutationParameter.xml.cc. First of all, let's define the XML tag for the delimiter, that I chose to call "delimiter".

const string PermutationParameter::XML_CHILD_ELEMENT_DELIMITER = "delimiter";

The existence of the const string must also be reported in PermutationParameter.h, along with a new variable to store the delimiter (that I simply called "delimiter" again).

std::string delimiter;
static const std::string XML_CHILD_ELEMENT_DELIMITER; 

Then, the readXml and writeXml methods will be modified accordingly, to take into account the new parameter.

void PermutationParameter::writeXml(ostream& output) const throw()
{
       _STACK;
       LOG_DEBUG << "Serializing object ugp3::constraints::PermutationParameter" << ends;
       if(this->typeDefinition == NULL)
       {
               output << "<" << this->getXmlName() << " xsi:type=\"permutation\" "
               << XML_ATTRIBUTE_NAME << "=\"" << xml::Utility::transformXmlEscChar(this->getName()) << "\">" << endl;
               for(unsigned int i = 0; i < this->constants.size(); i++)
               {
                       output
                       << "<" << XML_CHILD_ELEMENT_VALUE << ">"
                       << xml::Utility::transformXmlEscChar(this->constants[i])
                       << "</" << XML_CHILD_ELEMENT_VALUE << ">" << endl;
               }
               output  << "<" << XML_CHILD_ELEMENT_DELIMITER << ">"
                       << xml::Utility::transformXmlEscChar(this->delimiter)
                       << "</" << XML_CHILD_ELEMENT_DELIMITER << ">" << endl;
               output << "</" << this->getXmlName() << ">" << endl;
       }
       else output << this->writeXmlAsTypeDefinition();
}
void PermutationParameter::readXml(const xml::Element& element) throw(exception)
{
   _STACK;
   Parameter::readXml(element);
   const xml::Element* childElement = element.FirstChildElement();
   while(childElement != NULL)
   {
       if(childElement->ValueStr() == XML_CHILD_ELEMENT_VALUE)
       {
               string constant = xml::Utility::elementText(*childElement);
               this->constants.push_back(constant);
       }
       else if(childElement->ValueStr() == XML_CHILD_ELEMENT_DELIMITER)
       {
               this->delimiter = xml::Utility::elementText(*childElement);
       }
       else
       {
               throw xml::SchemaException("expected elements \"value\" or \"delimiter\" for parameter of type \"permutation\"", LOCATION);
       }
       childElement = childElement->NextSiblingElement();
   }
   if(constants.size() == 0 || this->delimiter.length() == 0)
   {
       throw xml::SchemaException("expected elements \"value\" and \"delimiter\" for parameter of type \"permutation\"", LOCATION);
   }
}

And a getter method is added to return the value of the new attribute.

        inline const std::string& PermutationParameter::getDelimiter() const throw()
        {
           return this->delimiter;
        }

A method will then be added to the Convert class, to convert a string to a vector of strings (given a certain delimiter):

vector<string> Convert::toStringVector(const string& value, const string& delimiters) throw(std::exception)
{
   _STACK;
   vector<string> result;
   // Skip delimiters at beginning.
   string::size_type lastPos = value.find_first_not_of(delimiters, 0);
   // Find first "non-delimiter".
   string::size_type pos     = value.find_first_of(delimiters, lastPos);
   while (string::npos != pos || string::npos != lastPos)
   {
       // Found a token, add it to the vector.
       result.push_back(value.substr(lastPos, pos - lastPos));
       // Skip delimiters.  Note the "not_of"
       lastPos = value.find_first_not_of(delimiters, pos);
       // Find next "non-delimiter"
       pos = value.find_first_of(delimiters, lastPos);
   }
   return result;
}

To let ugp3 know that we have a new type of parameter, we also have to modify Libs/Constraints/ConstrainingElement.xml.cc, where we have the code that reads the XML parameters and converts them into the internal ugp3 representation. In particular, we have to add the new type to the method ConstrainingElement::parseParameter(). There is a consistent "if" block; before the "else" statement, we will add

   ...
   else if(type == "permutation")
   {
       parameter = new PermutationParameter();
   }
   ...

Now everything is ready for our permutation parameter! The only thing left is to actually implement its behavior.

Permutational behavior

A parameter type is defined by several methods: the ones that must be included are the constructors, randomize (returns a random value for the parameter), validate (assures that a specific value for the parameter is valid), clone (creates a clone of the value). We might still need to add further methods to ease some operations.

The constructors will be identical to ConstantParameter ones, with an additional parameter this->delimiter, to separate the constant values in an instance of PermutationParameter.

PermutationParameter::PermutationParameter(const string name, const vector<string>* constants, const string delimiter) throw(exception) : DataParameter(name)
{
       _STACK;
       if(constants == NULL)
       {
               throw ArgumentNullException("constants", LOCATION);
       }
       this->constants = *constants;
       this->delimiter = delimiter;
}

The clone method will also be updated with the new definition of the constructor.

void PermutationParameter::clone(Parameter*& outParameter, const string name)
{
       _STACK;
       PermutationParameter* parameter = new PermutationParameter(name, &this->constants, this->delimiter);
       parameter->typeDefinition = (this->typeDefinition != NULL? this->typeDefinition : this);
       outParameter = parameter;
}

For randomize, we basically want to return a random order of the constants. We will shuffle the vector and return the values, separated by the delimiter string. In order to do so, we will exploit the std::random_shuffle function, found in the <algorithm> library. It is interesting to notice that std::random_shuffle also accepts a pointer to a function that generates random numbers. For more information, see std::random_shuffle on cplusplus.com</algorithm>

const string PermutationParameter::randomize() const throw()
{
       _STACK;
       Assert(this->constants.size() > 0);
       // the vector is shuffled using std::random_shuffle; TODO: pass pointer to random number generator function
       vector<string> temp = this->constants;
       random_shuffle( temp.begin(), temp.end() );
       // the value is the vector in a random order, with the delimiter separating each value
       ostringstream ss;
       ss << temp[0];
       for(unsigned int i = 1; i < temp.size(); i++)
       {
               ss << this->delimiter << temp[i];
       }
       return ss.str();
}