Changes between Version 6 and Version 7 of Documentation/Howto/DefineCustomProblems
- Timestamp:
- 10/18/15 22:26:28 (9 years ago)
Legend:
- Unmodified
- Added
- Removed
- Modified
-
Documentation/Howto/DefineCustomProblems
v6 v7 1 = Documentation not up-to-date =2 {{{3 #!html4 <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 9 1 = How to ... define custom problems in the GUI = 10 2 … … 13 5 == Problem Definition == 14 6 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".7 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. 16 8 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)]] 18 10 19 [[Image(2-Initial-Problem-View.png)]] 11 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. 20 12 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 associated23 2. The size of the knapsack in terms of how much weight it can hold13 We 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 24 16 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.17 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. 26 18 27 [[Image( 3-Add-Parameters.png)]]19 [[Image(2-Add-Variables.png)]] 28 20 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". 21 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: 30 22 31 [[Image( 4-Create-Parameter.png)]]23 [[Image(3-Knapsack-Problem-Instance.png)]] 32 24 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 25 Next we choose the problem's encoding. In this case replace the contents of the Initialize() method with 71 26 72 27 {{{#!csharp 73 DoubleArray weights = Weights.ActualValue; 74 DoubleArray values = Values.ActualValue; 75 double size = Size.ActualValue.Value; 76 BinaryVector solution = BinaryVector.ActualValue; 28 Encoding = new BinaryVectorEncoding("kp", length: ((DoubleArray)vars.weights).Length); 29 }}} 30 31 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. 32 33 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: 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"); 77 41 78 42 double v = 0.0; … … 85 49 } 86 50 87 if (w > size) v = 0.0; 88 89 Quality.ActualValue = new DoubleValue(v); 51 if (w > size) v = size - w; 52 return v; 90 53 }}} 91 54 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.55 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. 93 56 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.57 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. 95 58 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. 59 At this point your problem definition should look as follows: 97 60 98 == Optimization == 61 [[Image(4-Programmable-Problem-Definition.png)]] 99 62 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.63 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. 101 64 102 [[Image(9-Optimize.png)]] 65 Save the problem to a file "Custom Knapsack.hl". 103 66 104 You can also download the pre-built file I created in the attachments to this page. 67 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. 68 69 [[Image(5-Optimize-It.png)]] 70 71 You can also download the pre-configured file I created in the attachments to this page "GA solves custom Knapsack.hl".
