Free cookie consent management tool by TermsFeed Policy Generator

Changeset 4204


Ignore:
Timestamp:
08/12/10 14:36:13 (14 years ago)
Author:
svonolfe
Message:

Added operations for the Alba encoding (#1039)

Location:
trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3
Files:
27 added
1 deleted
11 edited
1 copied

Legend:

Unmodified
Added
Removed

  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Alba/AlbaEncoding.cs

    r4179 r4204  
    3030  [Item("AlbaEncoding", "Represents an Alba encoding of VRP solutions. It is implemented as described in Alba, E. and Dorronsoro, B. (2004). Solving the Vehicle Routing Problem by Using Cellular Genetic Algorithms.")]
    3131  [StorableClass]
    32   class AlbaEncoding : Permutation, IVRPEncoding {
     32  public class AlbaEncoding : Permutation, IVRPEncoding {
    3333    [Storable]
    3434    private int cities;

  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Alba/Crossovers/AlbaCrossover.cs

    r4179 r4204  
    2525using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2626using HeuristicLab.Data;
     27using HeuristicLab.Optimization;
    2728
    2829namespace HeuristicLab.Problems.VehicleRouting.Encodings.Alba {
    2930  [Item("AlbaCrossover", "An operator which crosses two Alba VRP representations.")]
    3031  [StorableClass]
    31   public sealed class AlbaCrossover : VRPCrossover {   
    32     public IValueLookupParameter<IPermutationCrossover> InnerCrossoverParameter {
    33       get { return (IValueLookupParameter<IPermutationCrossover>)Parameters["InnerCrossover"]; }
     32  public abstract class AlbaCrossover : VRPCrossover, IStochasticOperator {
     33    public ILookupParameter<IRandom> RandomParameter {
     34      get { return (LookupParameter<IRandom>)Parameters["Random"]; }
    3435    }
    35 
     36   
    3637    [StorableConstructor]
    37     private AlbaCrossover(bool deserializing) : base(deserializing) { }
     38    protected AlbaCrossover(bool deserializing) : base(deserializing) { }
    3839
    3940    public AlbaCrossover()
    4041      : base() {
    41       Parameters.Add(new ValueLookupParameter<IPermutationCrossover>("InnerCrossover", "The permutation crossover.", new EdgeRecombinationCrossover()));
    42     
     42      Parameters.Add(new LookupParameter<IRandom>("Random", "The pseudo random number generator which should be used for stochastic manipulation operators."));
     43   
    4344      AlbaEncoding.RemoveUnusedParameters(Parameters);
    4445    }
    4546
    46     private void Crossover() {
    47       //note - the inner crossover is called here and the result is converted to an alba representation
    48       //some refactoring should be done here in the future - the crossover operation should be called directly
    49 
    50       InnerCrossoverParameter.ActualValue.ParentsParameter.ActualName = ParentsParameter.ActualName;
    51       IAtomicOperation op = this.ExecutionContext.CreateOperation(
    52         InnerCrossoverParameter.ActualValue, this.ExecutionContext.Scope);
    53       op.Operator.Execute((IExecutionContext)op);
    54 
    55       string childName = InnerCrossoverParameter.ActualValue.ChildParameter.ActualName;
    56       if (ExecutionContext.Scope.Variables.ContainsKey(childName)) {
    57         Permutation permutation = ExecutionContext.Scope.Variables[childName].Value as Permutation;
    58         ExecutionContext.Scope.Variables.Remove(childName);
    59 
    60         ChildParameter.ActualValue = new AlbaEncoding(permutation, Cities);
    61       } else
    62         ChildParameter.ActualValue = null;
    63     }
     47    protected abstract AlbaEncoding Crossover(IRandom random, AlbaEncoding parent1, AlbaEncoding parent2);
    6448
    6549    public override IOperation Apply() {
    … …  
    7660      ParentsParameter.ActualValue = parents;
    7761
    78       Crossover();
     62      ChildParameter.ActualValue =
     63        Crossover(RandomParameter.ActualValue, parents[0] as AlbaEncoding, parents[1] as AlbaEncoding);
    7964
    8065      return base.Apply();

  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Alba/Manipulators/AlbaManipulator.cs

    r4179 r4204  
    2525using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2626using HeuristicLab.Data;
     27using HeuristicLab.Optimization;
    2728
    2829namespace HeuristicLab.Problems.VehicleRouting.Encodings.Alba {
    29   [Item("AlbaManipulator", "An operator which manipulates an alba VRP representation.")]
     30  [Item("AlbaManipulator", "An operator which manipulates an Alba VRP representation.")]
    3031  [StorableClass]
    31   public sealed class AlbaManipulator : VRPManipulator {
    32     public IValueLookupParameter<IPermutationManipulator> InnerManipulatorParameter {
    33       get { return (IValueLookupParameter<IPermutationManipulator>)Parameters["InnerManipulator"]; }
     32  public abstract class AlbaManipulator : VRPManipulator, IStochasticOperator {
     33    public ILookupParameter<IRandom> RandomParameter {
     34      get { return (LookupParameter<IRandom>)Parameters["Random"]; }
    3435    }
    3536
    3637    [StorableConstructor]
    37     private AlbaManipulator(bool deserializing) : base(deserializing) { }
     38    protected AlbaManipulator(bool deserializing) : base(deserializing) { }
    3839
    3940    public AlbaManipulator()
    4041      : base() {
    41         Parameters.Add(new ValueLookupParameter<IPermutationManipulator>("InnerManipulator", "The permutation manipulator.", new TranslocationManipulator()));
     42        Parameters.Add(new LookupParameter<IRandom>("Random", "The pseudo random number generator which should be used for stochastic manipulation operators."));
    4243
    4344        AlbaEncoding.RemoveUnusedParameters(Parameters);
     45    }
     46
     47    protected abstract void Manipulate(IRandom random, AlbaEncoding individual);
     48
     49    protected int FindCustomerLocation(int customer, AlbaEncoding individual) {
     50      int pos = -1;
     51      for (int i = 0; i < individual.Length; i++) {
     52        if (individual[i] == customer) {
     53          pos = i;
     54          break;
     55        }
     56      }
     57
     58      return pos;
    4459    }
    4560
    … …  
    4964        VRPToursParameter.ActualValue = AlbaEncoding.ConvertFrom(solution, VehiclesParameter.ActualValue.Value);
    5065      }
    51      
    52       OperationCollection next = new OperationCollection(base.Apply());
    5366
    54       IPermutationManipulator op = InnerManipulatorParameter.ActualValue;
    55       if (op != null) {
    56         op.PermutationParameter.ActualName = VRPToursParameter.ActualName;
    57         next.Insert(0, ExecutionContext.CreateOperation(op));
    58       }
     67      Manipulate(RandomParameter.ActualValue, VRPToursParameter.ActualValue as AlbaEncoding);
    5968
    60       return next;
     69      return base.Apply();
    6170    }
    6271  }

  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Alba/Moves/AlbaMoveOperator.cs

    r4179 r4204  
    3030  [StorableClass]
    3131  public abstract class AlbaMoveOperator : VRPMoveOperator {   
    32     [Storable]
    33     protected abstract IPermutationMoveOperator PermutationMoveOperatorParameter { get; set; }
    34 
    3532    [StorableConstructor]
    3633    protected AlbaMoveOperator(bool deserializing) : base(deserializing) { }
    … …  
    4744      }
    4845
    49       PermutationMoveOperatorParameter.PermutationParameter.ActualName = VRPToursParameter.ActualName;
    50       IAtomicOperation op = this.ExecutionContext.CreateChildOperation(PermutationMoveOperatorParameter);
    51       op.Operator.Execute((IExecutionContext)op);
    52 
    5346      return base.Apply();
    5447    }

  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Alba/Moves/Interfaces/IAlbaTranslocationMoveOperator.cs

    r4188 r4204  
    2525
    2626namespace HeuristicLab.Problems.VehicleRouting.Encodings.Alba {
    27   public interface IAlbaTranslocationMoveOperator : IMoveOperator {
     27  public interface IAlbaTranslocationMoveOperator : IVRPMoveOperator {
    2828    ILookupParameter<TranslocationMove> TranslocationMoveParameter { get; }
    2929  }

  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Alba/Moves/ThreeOpt/AlbaTranslocationMoveEvaluator.cs

    r4179 r4204  
    2929  [Item("AlbaTranslocationMoveEvaluator", "Evaluates a translocation or insertion move (3-opt) for the Alba representation.")]
    3030  [StorableClass]
    31   public sealed class AlbaTranslocationMoveEvaluator : VRPMoveEvaluator {
     31  public sealed class AlbaTranslocationMoveEvaluator : VRPMoveEvaluator, IAlbaTranslocationMoveOperator {
    3232    public ILookupParameter<TranslocationMove> TranslocationMoveParameter {
    3333      get { return (ILookupParameter<TranslocationMove>)Parameters["TranslocationMove"]; }

  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Alba/Moves/ThreeOpt/AlbaTranslocationMoveGenerator.cs

    r4179 r4204  
    3131  [Item("AlbaTranslocationMoveGenerator", "An operator which generates translocation moves for the Alba representation.")]
    3232  [StorableClass]
    33   public sealed class AlbaTranslocationMoveGenerator : AlbaMoveOperator, IAlbaTranslocationMoveOperator, IMultiMoveGenerator {
     33  public sealed class AlbaTranslocationMoveGenerator : PermutationMoveOperator, IAlbaTranslocationMoveOperator, IMultiMoveGenerator {
    3434    public IValueLookupParameter<TranslocationMoveGenerator> TranslocationMoveGeneratorParameter {
    3535      get { return (IValueLookupParameter<TranslocationMoveGenerator>)Parameters["TranslocationMoveGenerator"]; }
    … …  
    8686      string moveName = TranslocationMoveGeneratorParameter.ActualValue.TranslocationMoveParameter.Name;
    8787
    88       List<Scope> toBeDeleted = new List<Scope>();
    89       foreach (Scope scope in this.ExecutionContext.Scope.SubScopes) {
    90         if (scope.Variables.ContainsKey(moveName)) {
    91           TranslocationMove move = scope.Variables[moveName].Value as TranslocationMove;
    92 
    93           if (move != null) {
    94             bool criteria1 = true;
    95             if (move.Index1 - 1 >= 0 &&
    96               move.Index3 - 1 >= 0)
    97               criteria1 = (permutation[move.Index1] >= Cities &&
    98                 permutation[move.Index1 - 1] >= Cities &&
    99                 permutation[move.Index3 - 1] >= Cities);
    100 
    101             int index3 = move.Index3 + (move.Index2 - move.Index1) + 1;
    102             bool criteria2 = true;
    103             if (move.Index2 + 1 < permutation.Length &&
    104               index3 < permutation.Length)
    105               criteria2 = (permutation[move.Index2] >= Cities &&
    106                 permutation[move.Index2 + 1] >= Cities &&
    107                 permutation[index3] >= Cities);
    108 
    109             if (criteria1 && criteria2)
    110               toBeDeleted.Add(scope);
    111           }
    112         }
    113       }
    114 
    115       foreach (Scope scope in toBeDeleted) {
    116         this.ExecutionContext.Scope.SubScopes.Remove(scope);
    117       }
    118 
    11988      return successor;
    12089    }

  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Alba/Moves/ThreeOpt/AlbaTranslocationMoveHardTabuCriterion.cs

    r4179 r4204  
    2929  [Item("AlbaTranslocationMoveHardTabuCriterion", "An operator which checks if translocation moves are tabu using a hard criterion for the Alba representation.")]
    3030  [StorableClass]
    31   public sealed class AlbaTranslocationMoveHardTabuCriterion : AlbaMoveOperator, IAlbaTranslocationMoveOperator, ITabuChecker {
     31  public sealed class AlbaTranslocationMoveHardTabuCriterion : PermutationMoveOperator, IAlbaTranslocationMoveOperator, ITabuChecker {
    3232    private TranslocationMoveHardTabuCriterion tabuChecker;
    3333    protected override IPermutationMoveOperator PermutationMoveOperatorParameter {

  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Alba/Moves/ThreeOpt/AlbaTranslocationMoveMaker.cs

    r4179 r4204  
    3131  public sealed class AlbaTranslocationMoveMaker : AlbaMoveMaker, IAlbaTranslocationMoveOperator, IVRPMoveMaker {
    3232    private TranslocationMoveMaker moveMaker;
    33     protected override IPermutationMoveOperator PermutationMoveOperatorParameter {
    34       get { return moveMaker; }
    35       set { moveMaker = value as TranslocationMoveMaker; }
    36     }
    3733
    3834    public ILookupParameter<TranslocationMove> TranslocationMoveParameter {
    … …  
    5955      moveMaker = new TranslocationMoveMaker();
    6056    }
     57
     58    public override IOperation Apply() {
     59      IOperation next = base.Apply();
     60
     61      IVRPEncoding solution = VRPToursParameter.ActualValue;
     62
     63      moveMaker.PermutationParameter.ActualName = VRPToursParameter.ActualName;
     64      IAtomicOperation op = this.ExecutionContext.CreateChildOperation(moveMaker);
     65      op.Operator.Execute((IExecutionContext)op);
     66
     67      return next;
     68    }
    6169  }
    6270}

  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Alba/Moves/ThreeOpt/AlbaTranslocationMoveSoftTabuCriterion.cs

    r4179 r4204  
    2929  [Item("AlbaTranslocationMoveSoftTabuCriterion", "An operator which checks if translocation moves are tabu using a soft criterion for the Alba representation.")]
    3030  [StorableClass]
    31   public sealed class AlbaTranslocationMoveSoftTabuCriterion : AlbaMoveOperator, IAlbaTranslocationMoveOperator, ITabuChecker {
     31  public sealed class AlbaTranslocationMoveSoftTabuCriterion : PermutationMoveOperator, IAlbaTranslocationMoveOperator, ITabuChecker {
    3232    private TranslocationMoveSoftTabuCriterion tabuChecker;
    3333    protected override IPermutationMoveOperator PermutationMoveOperatorParameter {

  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Alba/Moves/ThreeOpt/AlbaTranslocationMoveTabuMaker.cs

    r4179 r4204  
    2929  [Item("AlbaTranslocationMoveTabuMaker", "An operator which makes translocation moves tabu for the Alba representation.")]
    3030  [StorableClass]
    31   public sealed class AlbaTranslocationMoveTabuMaker : AlbaMoveOperator, IAlbaTranslocationMoveOperator, ITabuMaker {
     31  public sealed class AlbaTranslocationMoveTabuMaker : PermutationMoveOperator, IAlbaTranslocationMoveOperator, ITabuMaker {
    3232    private TranslocationMoveTabuMaker moveTabuMaker;
    3333    protected override IPermutationMoveOperator PermutationMoveOperatorParameter {

  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/HeuristicLab.Problems.VehicleRouting-3.3.csproj

    r4186 r4204  
    107107  <ItemGroup>
    108108    <Compile Include="Analyzers\BestVRPSolutionAnalyzer.cs" />
     109    <Compile Include="Encodings\Alba\Crossovers\PermutationCrossover.cs" />
     110    <Compile Include="Encodings\Alba\Manipulators\SimpleLocalSearchManipulator.cs" />
     111    <Compile Include="Encodings\Alba\Manipulators\LambdaInterchangeManipulator.cs" />
     112    <Compile Include="Encodings\Alba\Moves\Interfaces\IAlbaLambdaInterchangeMoveOperator.cs" />
     113    <Compile Include="Encodings\Alba\Moves\Interfaces\IAlbaSimpleLocalSearchMoveOperator.cs" />
     114    <Compile Include="Encodings\Alba\Manipulators\CustomerInversionManipulator.cs" />
     115    <Compile Include="Encodings\Alba\Manipulators\CustomerSwapManipulator.cs" />
     116    <Compile Include="Encodings\Alba\Manipulators\CustomerInsertionManipulator.cs" />
     117    <Compile Include="Encodings\Alba\Manipulators\PermutationManipulator.cs" />
     118    <Compile Include="Encodings\Alba\Moves\LambdaInterchange\ExhaustiveLambdaInterchangeMoveGenerator.cs" />
     119    <Compile Include="Encodings\Alba\Moves\LambdaInterchange\LambdaInterchangeMove.cs" />
     120    <Compile Include="Encodings\Alba\Moves\LambdaInterchange\LambdaInterchangeMoveGenerator.cs" />
     121    <Compile Include="Encodings\Alba\Moves\LambdaInterchange\LambdaInterchangeMoveEvaluator.cs" />
     122    <Compile Include="Encodings\Alba\Moves\LambdaInterchange\LambdaInterchangeMoveMaker.cs" />
     123    <Compile Include="Encodings\Alba\Moves\LambdaInterchange\StochasticLambdaInterchangeSingleMoveGenerator.cs" />
     124    <Compile Include="Encodings\Alba\Moves\LambdaInterchange\StochasticLambdaInterchangeMutliMoveGenerator.cs" />
     125    <Compile Include="Encodings\Alba\Moves\PermutationMoveOperator.cs" />
     126    <Compile Include="Encodings\Alba\Moves\SimpleLocalSearch\StochasticSimpleLocalSearchMutliMoveGenerator.cs" />
     127    <Compile Include="Encodings\Alba\Moves\SimpleLocalSearch\StochasticSimpleLocalSearchSingleMoveGenerator.cs" />
     128    <Compile Include="Encodings\Alba\Moves\SimpleLocalSearch\SimpleLocalSearchMoveGenerator.cs" />
     129    <Compile Include="Encodings\Alba\Moves\SimpleLocalSearch\SimpleLocalSearchMoveEvaluator.cs" />
     130    <Compile Include="Encodings\Alba\Moves\SimpleLocalSearch\ExhaustiveSimpleLocalSearchMoveGenerator.cs" />
     131    <Compile Include="Encodings\Alba\Moves\SimpleLocalSearch\SimpleLocalSearchMoveMaker.cs" />
     132    <Compile Include="Encodings\Alba\Moves\SimpleLocalSearch\SimpleLocalSearchMove.cs" />
    109133    <Compile Include="Encodings\General\Crossovers\MultiVRPManipulator.cs" />
    110134    <Compile Include="Encodings\General\Crossovers\MultiVRPCrossover.cs" />
    … …  
    124148    <Compile Include="Encodings\General\Creators\DefaultRepresentationCreator.cs" />
    125149    <Compile Include="Encodings\Alba\Crossovers\AlbaCrossover.cs" />
    126     <Compile Include="Encodings\Alba\Interfaces\IAlbaTranslocationMoveOperator.cs" />
     150    <Compile Include="Encodings\Alba\Moves\Interfaces\IAlbaTranslocationMoveOperator.cs" />
    127151    <Compile Include="Encodings\Alba\Manipulators\AlbaManipulator.cs" />
    128152    <Compile Include="Encodings\Alba\Moves\AlbaMoveOperator.cs" />
Note: See TracChangeset for help on using the changeset viewer.