Define custom problems in the GUI

In HeuristicLab 3.3 you don't always need to use Visual Studio or other developing and build tools to optimize your problem. Most of the tasks can be performed in the GUI. Here we'll show how to recreate the ​knapsack problem in the GUI and use a genetic algorithm for optimizing it. After reading through this tutorial, you should be comfortable to define your own, probably more complex, problem.

Problem Definition

First we start by creating a new genetic algorithm and on the problem tab we click on the "New Problem" button and create a new "User-Defined Problem".

Let's name this problem "My Knapsack Problem" and it should look like in the following screenshot.

Next, we'll need to define the parameters that are important to this problem. The knapsack problem is defined by:

1. A set of items where with each item there is a weight and a value associated
2. The size of the knapsack in terms of how much weight it can hold

We can represent the items as two vectors of double values that denote the items' weights and values and the size as a double value. So we add these as ValueParameters to our problem by clicking on the yellow plus icon as shown in the following screenshot.

The "Create Parameter" dialog pops up and asks for the kind of parameters to create. We'll choose ValueParameter<T> (1), name it "Weights" (4), add a description and when we click on the T (2) and on the button to select a type (3). We choose DoubleArray in the Type Selector dialog that pops up. The dialog window should look as follows before we click "OK".

Now we can see that the parameter has been added to the problem's parameter list. Any operator with a LookupParameter<DoubleArray> that also has Weights as its ActualName is now able to find this parameter and obtain its value. In a similar fashion we add another parameter called "Values", and another one called "Size" which however is just a single real value so this time create a ValueParameter<DoubleValue>. Our problem now looks as in the following screenshot.

Now it's time to fill the parameters, so to say to define an instance of our problem. You can choose your own values, I chose to make a knapsack problem with 5 items, so I put 5 as the length of my DoubleArrays and then choose [ 1; 1; 3; 2; 2 ] for the weights and [ 3; 1; 5; 4; 1 ] for the values. For the size of the knapsack I chose 4. The problem is small and usually not worth to optimize, but it is suited in a tutorial like this. As you may have already calculated, there are two best solutions and the quality is 8. We could enter this information in the problem's BestKnownQuality and BestKnownSolution parameters, but let's have the algorithm find that out.

The problem definition is done, but we still need to define the encoding and finally write the evaluation function before we can start the optimization.

Encoding

The knapsack problem can be represented as a 0-1 decision problem, which means for every item we can either choose not to take it (0) or to include it (1). Such kind of problems can be represented by using a Boolean vector that is as large as the number of items. Our solution thus consists of a BoolArray.

Select the SolutionCreator parameter in the problem and set it to a "RandomBinaryVectorCreator" which can be found under HeuristicLab.Encodings.BinaryVectorEncoding. You'll see that it has a parameter called "Length" which we set to a new IntValue that has the value 5 or whatever you choose to be the length of the Weights and Values parameters. There are some other parameters, probably hidden, which you can see by clicking on the "Show Hidden Parameters" button. We'll notice that it has a parameter called "BinaryVector" which is the name of the solution. Now we're able to create random solutions to our problem. The RandomBinaryVectorCreator will do that for us in that it creates Boolean vectors of our specified length.

To optimize problems with a genetic algorithm however we also need a crossover operator and often also a mutation operator. We add them to the ItemList of Operators. Click the "Operators" parameter and add the SinglePointCrossover and the SinglePositionBitflipManipulator from the HeuristicLab.Encodings.BinaryVectorEncoding namespace. Finally also add an analyzer so that we can track the best found solution, click the yellow plus icon on the Operators list once again and add the BestScopeSolutionAnalyzer from the HeuristicLab.Analysis namespace. Our Operators list looks as follows.

Now we have defined the encoding in that we chose a SolutionCreator and operators for manipulating it.

Evaluation Function

First we change our Evaluator parameter to be a "User-Defined Evaluator" as shown in the following screenshot.

This operator has an ItemList of operators that are executed one after another on each solution. Let's add a ProgrammableOperator from HeuristicLab.Operators.Programmable to this list and double-click on it so that we get to view it in a new window.

The parameters tab of our programmable operator is already open. Here we add the parameters that are necessary for performing the evaluation. We need: The Weights, the Values, the Size of the knapsack, the BinaryVector solution and a parameter Quality which we will return into the scope of the solution. So we add the following parameters:

1. A LookupParameter<DoubleArray> called Weights
2. A LookupParameter<DoubleArray> called Values
3. A LookupParameter<DoubleValue> called Size
4. A LookupParameter<BinaryVector> called BinaryVector
5. A LookupParameter<DoubleValue> called Quality

Next we switch to the Code tab and write the evaluation code. Notice that all parameters are available in the method signature. We can write C# code in the text box. Let's write

    DoubleArray weights = Weights.ActualValue;
    DoubleArray values = Values.ActualValue;
    double size = Size.ActualValue.Value;
    BinaryVector solution = BinaryVector.ActualValue;
    
    double v = 0.0;
    double w = 0.0;
    for (int i = 0; i < solution.Length; i++) {
      if (solution[i]) {
        w += weights[i];
        v += values[i];
      }
    }
    
    if (w > size) v = 0.0;
    
    Quality.ActualValue = new DoubleValue(v);

In this function we count the values whenever the item in the binary vector is marked for inclusion. We also added a simply penalty in that we set the value to 0 should the knapsack be too heavy and tear. This may not be the best way to handle so called infeasible solutions as it creates a plateau in the fitness landscape which may not direct the optimizer into the feasible region. I'll leave it as an exercise to the reader to think of, define, test and experiment with better penalty functions.

If we click on the "Compile" button in the upper left we'll notice an error. We need to tell the programmable operator which plugins we want to utilize. It will come preloaded with only a basic set of plugins. We're missing the plugin for BinaryVector so in the list of assemblies search and select HeuristicLab.Encodings.BinaryVectorEncoding and in the namespaces list also check that namespace. Now compilation works and we can close the window of the programmable operator.

With the fitness function defined, we want to actually maximize it. Look for the parameter Maximization in the problem's parameters and set it to True. This tells the algorithm that higher Quality values are better.

Optimization

Now it's time to review the parameters of our genetic algorithm. For this simple problem I reduced the PopulationSize to 10, set the MaximumGenerations to 5 and selected the SinglePositionBitflipManipulator as the mutation operator. All other parameters are left unchanged. Save the algorithm and run it. You'll see how it performs in the Results tab.

You can also download the pre-built file I created in the attachments to this page.