Changes between Version 6 and Version 7 of Documentation/Howto/DefineCustomProblems


Ignore:
Timestamp:
10/18/15 22:26:28 (4 years ago)
Author:
abeham
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Documentation/Howto/DefineCustomProblems

    v6 v7  
    1 = Documentation not up-to-date =
    2 {{{
    3 #!html
    4 <p style="color: darkred; font-weight: bold">
    5 As of HeuristicLab 3.3.11 the preferred way of creating custom problems in the GUI is by using the Programmable Problem. The documentation is still valid, but the new way is considerably simpler.
    6 </p>
    7 }}}
    8 
    91= How to ... define custom problems in the GUI =
    102
     
    135== Problem Definition ==
    146
    15 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".
     7The 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.
    168
    17 Let's name this problem "My Knapsack Problem" and it should look like in the following screenshot.
     9[[Image(1-Create-Programmable-Problem.png)]]
    1810
    19 [[Image(2-Initial-Problem-View.png)]]
     11The 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.
    2012
    21 Next, we'll need to define the parameters that are important to this problem. The knapsack problem is defined by:
    22  1. A set of items where with each item there is a weight and a value associated
    23  2. The size of the knapsack in terms of how much weight it can hold
     13We also need to think about the problem's data. The knapsack problem is defined by:
     14 1. A set of items each with a certain weight and value
     15 2. The size of the knapsack as a value representing total weight
    2416
    25 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.
     17For 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.
    2618
    27 [[Image(3-Add-Parameters.png)]]
     19[[Image(2-Add-Variables.png)]]
    2820
    29 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".
     21In 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:
    3022
    31 [[Image(4-Create-Parameter.png)]]
     23[[Image(3-Knapsack-Problem-Instance.png)]]
    3224
    33 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.
    34 
    35 [[Image(5-Problem-View-With-Parameters.png)]]
    36 
    37 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.
    38 
    39 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.
    40 
    41 == Encoding ==
    42 
    43 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.
    44 
    45 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.
    46 
    47 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.
    48 
    49 [[Image(6-Operators-ItemList.png)]]
    50 
    51 Now we have defined the encoding in that we chose a !SolutionCreator and operators for manipulating it.
    52 
    53 == Evaluation Function ==
    54 
    55 First we change our Evaluator parameter to be a "User-Defined Evaluator" as shown in the following screenshot.
    56 
    57 [[Image(7-Set-Evaluator.png)]]
    58 
    59 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.
    60 
    61 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:
    62  1. A `LookupParameter<DoubleArray>` called Weights
    63  2. A `LookupParameter<DoubleArray>` called Values
    64  3. A `LookupParameter<DoubleValue>` called Size
    65  4. A `LookupParameter<BinaryVector>` called !BinaryVector
    66  5. A `LookupParameter<DoubleValue>` called Quality
    67 
    68 [[Image(8-Evaluator-Parameters.png)]]
    69 
    70 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
     25Next we choose the problem's encoding. In this case replace the contents of the Initialize() method with
    7126
    7227{{{#!csharp
    73     DoubleArray weights = Weights.ActualValue;
    74     DoubleArray values = Values.ActualValue;
    75     double size = Size.ActualValue.Value;
    76     BinaryVector solution = BinaryVector.ActualValue;
     28Encoding = new BinaryVectorEncoding("kp", length: ((DoubleArray)vars.weights).Length);
     29}}}
     30
     31This 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.
     32
     33Next 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:
     34
     35
     36{{{#!csharp
     37    var weights = (DoubleArray)vars.weights;
     38    var values = (DoubleArray)vars.values;
     39    var size = ((DoubleValue)vars.maxWeight).Value;
     40    var solution = individual.BinaryVector("kp");
    7741   
    7842    double v = 0.0;
     
    8549    }
    8650   
    87     if (w > size) v = 0.0;
    88    
    89     Quality.ActualValue = new DoubleValue(v);
     51    if (w > size) v = size - w;
     52    return v;
    9053}}}
    9154
    92 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.
     55This 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.
    9356
    94 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.
     57The 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.
    9558
    96 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.
     59At this point your problem definition should look as follows:
    9760
    98 == Optimization ==
     61[[Image(4-Programmable-Problem-Definition.png)]]
    9962
    100 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.
     63You 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.
    10164
    102 [[Image(9-Optimize.png)]]
     65Save the problem to a file "Custom Knapsack.hl".
    10366
    104 You can also download the pre-built file I created in the attachments to this page.
     67Next 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.
     68
     69[[Image(5-Optimize-It.png)]]
     70
     71You can also download the pre-configured file I created in the attachments to this page "GA solves custom Knapsack.hl".