wiki:Documentation/Howto/DefineCustomProblems

How to ... 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

The preferred way of prototyping new problems is by using the Programmable Problem in HeuristicLab. You can either go for single-objective or multi-objective problem definitions. In this case we want to create a new "Programmable Problem (single-objective)" from the new item dialog.

The programmable problem allows you to code the problem definition directly in C# without using complex build tools. In the code editor we choose the appropriate encoding, and define the fitness function.

We also need to think about the problem's data. The knapsack problem is defined by:

  1. A set of items each with a certain weight and value
  2. The size of the knapsack as a value representing total weight

For simplicity we can simply hard-code these parameters in the code by defining appropriate data structures as private variables. A more elegant way is to add them to the variable store so that we can use the GUI for manipulating the data.

In the variable store on the right add 2 variables of type DoubleArray and one of type DoubleValue, name these weights, values, and maxWeight respectively. Then double-click to open them and enter the values of your problem instance. Similar to the following:

Next we choose the problem's encoding. In this case replace the contents of the Initialize() method with

Encoding = new BinaryVectorEncoding("kp", length: ((DoubleArray)vars.weights).Length);

This will indicate that the problem uses binary encoded solutions named "kp". The length is automatically initialized to the length of the weights array that you have added in the variables store.

Next we want to specify the evaluation function. Take a look at the Evaluate method. It requires us to return the fitness value as a double. The argument individual holds the actual solution. We can ignore the random argument as our problem is deterministic. The evaluation function for the knapsack may look as follows:

    var weights = (DoubleArray)vars.weights;
    var values = (DoubleArray)vars.values;
    var size = ((DoubleValue)vars.maxWeight).Value;
    var solution = individual.BinaryVector("kp");
    
    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 = size - w;
    return v;

This means we're penalizing overweight solutions by assigning them negative fitness values where higher means less overweight and feasible solutions are assigned the value of the knapsack. Note: we're assuming only positive item values.

The evaluation function is defined such that larger values are better which means we need to change the Maximization property to return true instead of false.

At this point your problem definition should look as follows:

You can now press the "Compile" button right above the upper right corner of the code-editor. It should read "Compilation succeeded" in green. Otherwise try to identify and fix compile errors by looking at the "Error List" tab below the code-editor pane.

Save the problem to a file "Custom Knapsack.hl".

Next use the "New Item" dialog to create a new "Genetic Algorithm". In its "Problem" tab load the file. Configure the algorithm's parameters (select SinglePointCrossover as Crossover and SinglePositionBitflipManipulator as Mutator). Then press the green "Play" button at the bottom and look at the "Results" tab to see the solution being optimized.

You can also download the pre-configured file I created in the attachments to this page "GA solves custom Knapsack.hl".

Last modified 20 months ago Last modified on 10/18/15 22:26:28

Attachments (6)

Download all attachments as: .zip