New evolutionary operators

Adding new evolutionary operators

While ugp3 offers a wide range of Genetic operators, the need might arise to modify the evolutionary core to add new type of operators for specific projects. In this tutorial, we will follow the necessary steps to add two new operators (inverOverCrossover and 'swapMutation), to work on the [new parameterpermutation`](New parameter types).

Permutation

Permutation is a type of parameter to represent problems whose solution is a particular ordering of a set of elements. The Traveling Salesman Problem is probably the most studied combinatorial problem to date. However, standard mutations and crossover cannot work on such problems, because they will likely create a huge number of non-valid individuals. Therefore, the need arises for new operators able to always create valid values for permutation elements.

SwapMutation

SwapMutation is a classical mutation operator for permutation problems. In practice, it randomly selects two elements of a parent sequence, and it swaps their places, generating a child sequence which is identical to the original one, except for the elements swapped.

Making it compile

The best way to proceed when creating a new genetic operator in ugp3, is probably to cut/paste and modify an existing one. In our case, we will start from singleParameterAlterationMutation, an operator that modifies a single parameter. So, first of all, we will copy the files SingleParameterAlterationMutation.cc SingleParameterAlterationMutation.h, found in Libs/EvolutionaryCore/Operators to SwapMutation.cc SwapMutation.h.

I then swapped (eh eh) all references to SingleParameterAlterationMutation with SwapMutation inside the class files, changing the string returned by methods SwapMutation::getName() and SwapMutation::getAcronym(), plus other details to match the new name. It is extremely important to replace the #ifdef at the beginning of the files. Mine now looks like:

#ifndef HEADER_UGP3_CORE_SWAPMUTATIONOPERATOR
#define HEADER_UGP3_CORE_SWAPMUTATIONOPERATOR

The line #include "SwapMutation.h" has to be added to the EvolutionaryCore.h file.
Operators/SwapMutation.cc is finally added to the list of files to be compiled inside Libs/EvolutionaryCore/CMakeLists.txt and compiled.

Preparing the field

Operators are used in several points of the code: when the evolution starts, the list of all available operators is loaded; the same happens when the companion program ugp3-extractor loads a population file to extract one or more individuals in text format.

In Frontends/ugp3/Program.Run.cc, we will add the line #include "SwapMutation.h". In the same file, in method Program::registerOperators(), we will add a line:

GeneticOperator::registration(new SwapMutationOperator());

The same line will be added to Contrib/ugp3-extractor/ugp3-extractor.cc in the function called registerOperators(). Now, our operator is actually usable and can be added to the Population's settings, but it will still behave as SingleParameterAlterationMutation. To change that, we will thus modify the method SwapMutation::generate().

SwapMutation Behavior

Now, the implementation of SwapMutation follows the subsequent steps. The first part of singleParameterAlterationMutation can be reused as it is: essentially, we take the current value of parameter sigma from the population, we clone the parent and we verify that everything is all right.

void SwapMutationOperator::generate( Parameters* parameters, std::vector<Individual*>& outChildren) const throw(std::exception)
{
       _STACK;
       double sigma = parameters->getSigma();
       std::vector<Individual*>parents = parameters->callSelector(this->getParentsCardinality());
       if(sigma <= 0 || sigma >= 1)
       {
               throw ArgumentException("sigma should be in (0, 1)", LOCATION);
       }
       if(parents.size() != this->getParentsCardinality())
       {
               throw ArgumentException("The number of input arguments (parents count) for the genetic operator " + this->toString() + " is incorrect.", LOCATION);
       }
       LOG_DEBUG << this << ": generating new mutant" << ends;
       Individual* parent = parents[0];
       Assert(parent->validate() == true);
       // create a copy of the parent
       auto_ptr<Individual> child = parent->clone();
       // set the lineage for the new individual
       child->setLineage( auto_ptr<Lineage>(new Lineage(this->getName(), parents)) )

Then, we collect all paremeters of type permutation in the child (that for the moment is an exact clone of the parent). This is the compulsory preliminary step to select one of the parameters to mutate. To avoid a deterministic choice, we will randomly select one graph (mapped as Section in the Population's Constraints), then one random subgraph (SubSection) from that Section, we will collect all the nodes and then all the parameters of type Permutation.

       // select the target (/graph/subGraph/macro/parameter)
       OperatorToolbox toolbox(child->getGraphContainer());

       // select a graph
       CGraph* graph =  toolbox.getRandomGraph();
       if(graph == NULL)
       {
               LOG_INFO << "No graph selected" << ends;
               return;
       }
       const string& sectionName = graph->getSection().getId();

       // select a subgraph
       CSubGraph* subGraph = toolbox.getRandomSubGraph(*graph);
       if(subGraph == NULL)
       {
               LOG_INFO << "No subGraph selected" << ends;
               return;
       }

       // select all the nodes that contain at least one combinatorial parameter
       vector<CNode*> candidates;
       CNode* node = &subGraph->getPrologue();
       do
       {
               candidates.push_back(node);
       }
       while((node = node->getNext()) != NULL);

       // collect all the parameters in a random node (until at least one parameter is found)
       vector<Parameter*> params;
       do
       {
               // choose random node
               unsigned long randomSample = Random::nextUInteger(0, (unsigned long)(candidates.size() - 1));
               Assert(randomSample >= 0 && randomSample <= candidates.size() - 1);
               node = candidates[randomSample];

               // remove node from candidates
               candidates.erase(candidates.begin() + randomSample);
               params.clear();

               // collect all the available parameters for the selected macro
               for(unsigned int i = 0; i < node->getGenericMacro().getParameterCount(); i++)
               {
                       // the only class of parameters usable is: 
                       // IntegerParameter
                       if( dynamic_cast<CombinatorialParameter*>(&node->getGenericMacro().getParameter(i)) != NULL )
                               params.push_back(&node->getGenericMacro().getParameter(i));
               }
       }
       while(params.size() == 0 && candidates.size() > 0);

       // if no parameters are found, return
       if( params.size() == 0 )
       {
               LOG_DEBUG << this << " : no appropriate parameters found. Failing..." << ends;
               return;
       }

At this point, we have a set of Permutation parameters in the vector params. We choose one at random, and finally operate the SwapMutation on it.

      // now, choose randomly the parameter to operate on and behave accordingly
       unsigned long randomSample = Random::nextUInteger(0, (unsigned long)(params.size() - 1));
       Assert(randomSample >= 0 && randomSample <= params.size() - 1);

       if( dynamic_cast<CombinatorialParameter*>(params[randomSample]) != NULL )
       {
               // combinatorial parameter
               CombinatorialParameter* parameter = dynamic_cast<CombinatorialParameter*>(params[randomSample]);

               // obtain the current value for the parameter
               Tag& tag = node->getTag(CNode::Escape + parameter->getName());
               vector<string> value = Convert::toStringVector( tag.getValue(), parameter->getDelimiter() );

               LOG_DEBUG << "Original value for parameter " << parameter->getName() << " is \"" << tag.getValue() << "\"." << ends;

               // mutate until random value is below sigma (at least once)
               do
               {
                       // select two random indexes in the vector
                       unsigned int index1 = Random::nextUInteger(0, (unsigned int)(value.size() - 1));
                       unsigned int index2 = Random::nextUInteger(0, (unsigned int)(value.size() - 1));

                       // swap the two values
                       string temp;
                       temp = value[index1];
                       value[index1] = value[index2];
                       value[index2] = temp;
               }
               while(sigma > Random::nextDouble());

               // convert value to string
               ostringstream ss;
               ss << value[0];
               for(unsigned int i = 1; i < value.size(); i++)
                       ss << parameter->getDelimiter() << value[i];

               LOG_DEBUG << "New value for parameter " << parameter->getName() << " is \"" << ss.str() << "\"." << ends;

               // assign value to child
               tag.setValue( ss.str() );

               // validate child
               if(child->getGraphContainer().attachFloatingEdges() == false || parameter->validate(ss.str()) == false ) return;

               LOG_DEBUG << "New value is \"" << node->getTag(CNode::Escape + parameter->getName()).getValue() << "\"." << ends;
       }

       Assert(child->validate() == true);

       LOG_VERBOSE << this << ": mutant " << child->toString() << " created" << ends;
       outChildren.push_back(child.release());
}

SwapMutation is now ready to work!