Changes between Version 2 and Version 3 of Documentation/Howto/ImplementANewVRPEncoding

Timestamp:

02/20/14 11:11:47 (12 years ago)

Author:

pfleck

Comment:

--

Documentation/Howto/ImplementANewVRPEncoding

@@ -412 +412 @@
 
 = Implementing new Operators =
+
 == Foundations ==
+
+HeuristicLab defines different operators for different situations and algorithms. In this tutorial we will use the following operators:
+
+ - ''SolutionCreator'': Operator responsible for creating a new solution (instancing a specific encoding)
+ - ''Crossover'': Combines two solutions
+ - ''Manipulator'': Mutates a solution
+
 == Link Encoding/Operators to VRP variants ==
+
+Because different encodings store different information, encodings are able to handle different VRP variants. Each variant specify a '''marker interface''' to indicate its "variant type" (e.g. TimeWindowedOperator). A VRP variant compatible encoding can implement this variant type (e.g. {{{GVROperator}}} implements the {{{TimeWindowedOperator}}}). This way, each encoding can specify compatible variants and implements the operators based on the encodings abilities. 
+
+In order to link the compatible operators to a VRP variant, the {{{ProblemInstance}}} have to provide a list of compatible {{{Operators}}}. Because a {{{ProblemInstance}}} usually derives from a base {{{ProblemInstance}}}, it uses the operators from the base implementation and selects only the compatible ones. For instance, the {{{CVRPTWProblemInstance}}} uses the operators from the {{{CVRPProblemInstance}}} and only uses those operators which implement the {{{TimeWindowedOperator}}}.
+
+The following figure shows a small sample and overview:
+
+[[Image(1_MTVRP_operator_featuremodel.png, 600px)]]
+
+The {{{SingleDepotOperator}}}, {{{CapcaitatedOperator}}} and {{{TimeWindowedOperator}}} represent '''VRP variants''' or '''parts of VRP variants'''. The {{{AlbaOperator}}} implements all three of them and therefore can be used for all of them. In comparison, the {{{GVROperator}}} (not show in the diagram) does not implement {{{MultiDepotOperator}}}(also not shown) and therefore is not compatible with variants that use multiple depots.
+
+Specific and {{{VRPProblemInstances}}} then specifies which operators are compatible. For instance the {{{CVRPProblemInstance}}} filters the operators by {{{CapacitatedOperator}}}. The {{{CVRPTWProblemInstance}}}, which derives from {{{CVRPProblemInstances}}} used the prefiltered operators and filters by {{{TimeWindowedOperator}}}: 
+
+{{{
+#!cs
+protected override IEnumerable<IOperator> GetOperators() {
+  return base.GetOperators().Where(o => o is ITimeWindowedOperator).Cast<IOperator>();
+}
+}}}
+
 == Implementing new MultiTripOperator ==
+
+The first step in implementing new operators is to create the marker interface for the VRP variant.
+
+{{{
+#!cs
+public interface IMultiTripOperator : IVRPOperator { }
+}}}
+
+After that, we need to link all our {{{MultiTripOperators}}} implementations to the {{{MultiTripProblemInstance}}}. This is done by overriding the {{{GetOperators}}} method. If you implement a complete new {{{Encoding}}} the method would look like this:
+
+{{{
+#!cs
+protected override IEnumerable<IOperator> GetOperators() {
+  return base.GetOperators().Where(o => o is IMultiTripOperator).Cast<IOperator>();
+}
+}}}
+
+In the case of this tutorial we are extending the {{{PotvinEncoding}}}, which defines multiple {{{Operators}}} already. Therefore we want to reuse the existing {{{Operators}}} for our {{{MultiTripEncoding}}} (e.g. the {{{Manipulators}}} and {{{Crossovers}}}). Because we will derive our {{{MultiTripOperators}}} from the {{{PotvinOperators}}} we could simply use all the {{{Operators}}} specified in the base {{{ProblemInstance}}}.
+
+However, we cannot use all {{{PotvinOperators}}}, we need to rule out the {{{PotvinCreators}}}. If someone accidently configures a {{{PotvinCreator}}}, plain {{{PotvinEncoding}}} instances are created and our own {{{MultiTripOperators}}}, which rely on the additional data, will not work. Therefore if an {{{Operator}}} is a {{{VRPCreator}}} it implies that it is a {{{MultiTripOperator}}}. 
+
+For a similar reason we cannot reuse {{{Operators}}} from other {{{Encodings}}}, which is usually possible due to conversion between them. If we convert our {{{MultiTripEncoding}}} to a different {{{Encoding}}} we lose the information about the delimiters. Therefore we can only reuse the {{{PotvinOperators}}} because no conversion is required this way.
+
+{{{
+#!cs
+protected override IEnumerable<IOperator> GetOperators() {
+  return base.GetOperators()
+    .Where(o => o is IPotvinOperator)
+    // is IVRPCreator  implicates  is IMultiTripOperator 
+    .Where(o => !(o is IVRPCreator) || (o is IMultiTripOperator)).Cast<IOperator>();
+}
+}}}
+
+
 == Implementing new Creator ==
 == Implementing new Manipulator ==