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


Ignore:
Timestamp:
02/20/14 11:11:47 (6 years ago)
Author:
pfleck
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Documentation/Howto/ImplementANewVRPEncoding

    v2 v3  
    412412
    413413= Implementing new Operators =
     414
    414415== Foundations ==
     416
     417HeuristicLab defines different operators for different situations and algorithms. In this tutorial we will use the following operators:
     418
     419 - ''SolutionCreator'': Operator responsible for creating a new solution (instancing a specific encoding)
     420 - ''Crossover'': Combines two solutions
     421 - ''Manipulator'': Mutates a solution
     422
    415423== Link Encoding/Operators to VRP variants ==
     424
     425Because 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.
     426
     427In 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}}}.
     428
     429The following figure shows a small sample and overview:
     430
     431[[Image(1_MTVRP_operator_featuremodel.png, 600px)]]
     432
     433The {{{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.
     434
     435Specific 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}}}:
     436
     437{{{
     438#!cs
     439protected override IEnumerable<IOperator> GetOperators() {
     440  return base.GetOperators().Where(o => o is ITimeWindowedOperator).Cast<IOperator>();
     441}
     442}}}
     443
    416444== Implementing new MultiTripOperator ==
     445
     446The first step in implementing new operators is to create the marker interface for the VRP variant.
     447
     448{{{
     449#!cs
     450public interface IMultiTripOperator : IVRPOperator { }
     451}}}
     452
     453After 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:
     454
     455{{{
     456#!cs
     457protected override IEnumerable<IOperator> GetOperators() {
     458  return base.GetOperators().Where(o => o is IMultiTripOperator).Cast<IOperator>();
     459}
     460}}}
     461
     462In 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}}}.
     463
     464However, 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}}}.
     465
     466For 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.
     467
     468{{{
     469#!cs
     470protected override IEnumerable<IOperator> GetOperators() {
     471  return base.GetOperators()
     472    .Where(o => o is IPotvinOperator)
     473    // is IVRPCreator  implicates  is IMultiTripOperator
     474    .Where(o => !(o is IVRPCreator) || (o is IMultiTripOperator)).Cast<IOperator>();
     475}
     476}}}
     477
     478
    417479== Implementing new Creator ==
    418480== Implementing new Manipulator ==