Free cookie consent management tool by TermsFeed Policy Generator

Changeset 8894 for trunk/sources


Ignore:
Timestamp:
11/12/12 13:32:46 (12 years ago)
Author:
jkarder
Message:

#1331:

  • improved path relinking and improvement operators for the VehicleRouting problem
  • recreated SS VRP sample
  • corrected SS VRP sample test
Location:
trunk/sources
Files:
1 added
6 edited

Legend:

Unmodified
Added
Removed

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

    r8649 r8894  
    141141    <Compile Include="Encodings\Potvin\Moves\TwoOptStar\PotvinTwoOptStarSingleMoveGenerator.cs" />
    142142    <Compile Include="Improver\VRPImprovementOperator.cs" />
     143    <Compile Include="Improver\VRPIntraRouteImprovementOperator.cs" />
    143144    <Compile Include="Interfaces\IVRPLocalSearchManipulator.cs" />
    144145    <Compile Include="Interpreters\MDCVRPInterpreter.cs" />
    … …  
    474475  -->
    475476  <PropertyGroup>
    476    <PreBuildEvent Condition=" '$(OS)' == 'Windows_NT' ">set Path=%25Path%25;$(ProjectDir);$(SolutionDir)
     477    <PreBuildEvent Condition=" '$(OS)' == 'Windows_NT' ">set Path=%25Path%25;$(ProjectDir);$(SolutionDir)
    477478set ProjectDir=$(ProjectDir)
    478479set SolutionDir=$(SolutionDir)
    … …  
    480481
    481482call PreBuildEvent.cmd</PreBuildEvent>
    482 <PreBuildEvent Condition=" '$(OS)' != 'Windows_NT' ">
     483    <PreBuildEvent Condition=" '$(OS)' != 'Windows_NT' ">
    483484export ProjectDir=$(ProjectDir)
    484485export SolutionDir=$(SolutionDir)

  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.4/Improver/VRPImprovementOperator.cs

    r8346 r8894  
    2828using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2929using HeuristicLab.Problems.VehicleRouting.Encodings;
    30 using HeuristicLab.Problems.VehicleRouting.Encodings.Alba;
    3130using HeuristicLab.Problems.VehicleRouting.Encodings.Potvin;
    3231using HeuristicLab.Problems.VehicleRouting.Interfaces;
    … …  
    3534namespace HeuristicLab.Problems.VehicleRouting {
    3635  /// <summary>
    37   /// An operator that improves vehicle routing solutions.
     36  /// A base class for operators which improve VRP solutions.
    3837  /// </summary>
    39   [Item("VRPImprovementOperator", "An operator that improves vehicle routing solutions.")]
     38  [Item("VRPImprovementOperator", "A base class for operators which improve VRP solutions.")]
    4039  [StorableClass]
    41   public sealed class VRPImprovementOperator : VRPOperator, IGeneralVRPOperator, ISingleObjectiveImprovementOperator {
     40  public abstract class VRPImprovementOperator : VRPOperator, IGeneralVRPOperator, ISingleObjectiveImprovementOperator {
    4241    #region Parameter properties
    4342    public ScopeParameter CurrentScopeParameter {
    … …  
    4746      get { return (IValueParameter<IntValue>)Parameters["ImprovementAttempts"]; }
    4847    }
    49     public IValueParameter<IntValue> LambdaParameter {
    50       get { return (IValueParameter<IntValue>)Parameters["Lambda"]; }
     48    public IValueLookupParameter<IntValue> LocalEvaluatedSolutions {
     49      get { return (IValueLookupParameter<IntValue>)Parameters["LocalEvaluatedSolutions"]; }
    5150    }
    5251    public ILookupParameter<IRandom> RandomParameter {
    … …  
    6261
    6362    [StorableConstructor]
    64     private VRPImprovementOperator(bool deserializing) : base(deserializing) { }
    65     private VRPImprovementOperator(VRPImprovementOperator original, Cloner cloner) : base(original, cloner) { }
    66     public VRPImprovementOperator()
     63    protected VRPImprovementOperator(bool deserializing) : base(deserializing) { }
     64    protected VRPImprovementOperator(VRPImprovementOperator original, Cloner cloner) : base(original, cloner) { }
     65    protected VRPImprovementOperator()
    6766      : base() {
    6867      #region Create parameters
    6968      Parameters.Add(new ScopeParameter("CurrentScope", "The current scope that contains the solution to be improved."));
    7069      Parameters.Add(new ValueParameter<IntValue>("ImprovementAttempts", "The number of improvement attempts the operator should perform.", new IntValue(100)));
    71       Parameters.Add(new ValueParameter<IntValue>("Lambda", "The number of neighbors that should be exchanged.", new IntValue(1)));
     70      Parameters.Add(new ValueLookupParameter<IntValue>("LocalEvaluatedSolutions", "The number of evaluated solutions."));
    7271      Parameters.Add(new LookupParameter<IRandom>("Random", "A pseudo random number generator."));
    73       Parameters.Add(new ValueParameter<IntValue>("SampleSize", "The number of moves that should be executed.", new IntValue(100)));
     72      Parameters.Add(new ValueParameter<IntValue>("SampleSize", "The number of moves that should be executed.", new IntValue(25)));
    7473      Parameters.Add(new ValueLookupParameter<IItem>("Solution", "The solution to be improved. This parameter is used for name translation only."));
    7574      #endregion
    7675    }
    7776
    78     public override IDeepCloneable Clone(Cloner cloner) {
    79       return new VRPImprovementOperator(this, cloner);
    80     }
    81 
    8277    public override IOperation Apply() {
    83       AlbaEncoding solution = SolutionParameter.ActualValue is AlbaEncoding
    84                                 ? SolutionParameter.ActualValue as AlbaEncoding
    85                                 : AlbaEncoding.ConvertFrom(SolutionParameter.ActualValue as IVRPEncoding, ProblemInstance);
     78      var solution = SolutionParameter.ActualValue as IVRPEncoding;
     79      var potvinSolution = solution is PotvinEncoding ? solution as PotvinEncoding : PotvinEncoding.ConvertFrom(solution, ProblemInstance);
    8680
    8781      if (solution == null)
    8882        throw new ArgumentException("Cannot improve solution because it has the wrong type.");
    8983
    90       double quality = -1;
    91       int evaluatedSolutions;
     84      int evaluatedSolutions = Improve(potvinSolution);
    9285
    93       AlbaLambdaInterchangeLocalImprovementOperator.Apply(solution, ImprovementAttemptsParameter.Value.Value,
    94                                                           LambdaParameter.Value.Value, SampleSizeParameter.Value.Value,
    95                                                           RandomParameter.ActualValue, ProblemInstance, ref quality,
    96                                                           out evaluatedSolutions);
    97 
    98       SolutionParameter.ActualValue = PotvinEncoding.ConvertFrom(solution, ProblemInstance);
    99       CurrentScopeParameter.ActualValue.Variables.Add(new Variable("LocalEvaluatedSolutions", new IntValue(evaluatedSolutions)));
     86      SolutionParameter.ActualValue = solution;
     87      LocalEvaluatedSolutions.ActualValue = new IntValue(evaluatedSolutions);
    10088
    10189      return base.Apply();
    10290    }
     91
     92    protected abstract int Improve(PotvinEncoding solution);
    10393  }
    10494}

  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.4/PathRelinkers/VRPPathRelinker.cs

    r8346 r8894  
    3737namespace HeuristicLab.Problems.VehicleRouting {
    3838  /// <summary>
    39   /// An operator that relinks paths between vehicle routing solutions.
     39  /// An operator which relinks paths between VRP solutions.
    4040  /// </summary>
    41   [Item("VRPPathRelinker", "An operator that relinks paths between vehicle routing solutions.")]
     41  [Item("VRPPathRelinker", "An operator which relinks paths between VRP solutions.")]
    4242  [StorableClass]
    4343  public sealed class VRPPathRelinker : SingleObjectivePathRelinker, IGeneralVRPOperator, IStochasticOperator {
    4444    #region Parameter properties
     45    public IValueParameter<IntValue> IterationsParameter {
     46      get { return (IValueParameter<IntValue>)Parameters["Iterations"]; }
     47    }
     48    public ILookupParameter<IVRPProblemInstance> ProblemInstanceParameter {
     49      get { return (ILookupParameter<IVRPProblemInstance>)Parameters["ProblemInstance"]; }
     50    }
    4551    public ILookupParameter<IRandom> RandomParameter {
    4652      get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
    4753    }
    48     public ILookupParameter<IVRPProblemInstance> ProblemInstanceParameter {
    49       get { return (ILookupParameter<IVRPProblemInstance>)Parameters["ProblemInstance"]; }
    50     }
    5154    public IValueParameter<IntValue> SampleSizeParameter {
    5255      get { return (IValueParameter<IntValue>)Parameters["SampleSize"]; }
    53     }
    54     public IValueParameter<IntValue> IterationsParameter {
    55       get { return (IValueParameter<IntValue>)Parameters["Iterations"]; }
    5656    }
    5757    #endregion
    … …  
    6262    public VRPPathRelinker()
    6363      : base() {
     64      Parameters.Add(new ValueParameter<IntValue>("Iterations", "The number of iterations the operator should perform.", new IntValue(50)));
     65      Parameters.Add(new LookupParameter<IVRPProblemInstance>("ProblemInstance", "The VRP problem instance"));
    6466      Parameters.Add(new LookupParameter<IRandom>("Random", "The pseudo random number generator which should be used for stochastic manipulation operators."));
    65       Parameters.Add(new LookupParameter<IVRPProblemInstance>("ProblemInstance", "The VRP problem instance"));
    6667      Parameters.Add(new ValueParameter<IntValue>("SampleSize", "The number of moves that should be executed.", new IntValue(10)));
    67       Parameters.Add(new ValueParameter<IntValue>("Iterations", "The number of iterations the operator should perform.", new IntValue(50)));
    6868    }
    6969
    … …  
    7272    }
    7373
     74    public static ItemArray<IItem> Apply(PotvinEncoding initiator, PotvinEncoding guide, PercentValue n, int sampleSize, int iterations, IRandom rand, IVRPProblemInstance problemInstance) {
     75      if (initiator == null || guide == null)
     76        throw new ArgumentException("Cannot relink path because one of the provided solutions or both are null.");
     77
     78      double sigma = 1.5;
     79      double minPenalty = 0.001;
     80      double maxPenalty = 1000000000;
     81
     82      var originalOverloadPenalty = new DoubleValue();
     83      if (problemInstance is IHomogenousCapacitatedProblemInstance)
     84        originalOverloadPenalty.Value = (problemInstance as IHomogenousCapacitatedProblemInstance).OverloadPenalty.Value;
     85      var originalTardinessPenalty = new DoubleValue();
     86      if (problemInstance is ITimeWindowedProblemInstance)
     87        originalTardinessPenalty.Value = (problemInstance as ITimeWindowedProblemInstance).TardinessPenalty.Value;
     88
     89      PotvinEncoding current = MatchTours(initiator, guide, problemInstance);
     90      double currentSimilarity = VRPSimilarityCalculator.CalculateSimilarity(current, guide);
     91
     92      IList<PotvinEncoding> solutions = new List<PotvinEncoding>();
     93      int i = 0;
     94      while (i < iterations && !currentSimilarity.IsAlmost(1.0)) {
     95        var currentEval = problemInstance.Evaluate(current);
     96        currentSimilarity = VRPSimilarityCalculator.CalculateSimilarity(current, guide);
     97
     98        if (currentSimilarity < 1.0) {
     99          for (int sample = 0; sample < sampleSize; sample++) {
     100            var next = current.Clone() as PotvinEncoding;
     101
     102            int neighborhood = rand.Next(3);
     103            switch (neighborhood) {
     104              case 0: next = RouteBasedXOver(next, guide, rand,
     105                problemInstance);
     106                break;
     107              case 1: next = SequenceBasedXOver(next, guide, rand,
     108                problemInstance);
     109                break;
     110              case 2: GuidedRelocateMove(next, guide, rand);
     111                break;
     112            }
     113
     114            next = MatchTours(next, guide, problemInstance);
     115
     116            var nextEval = problemInstance.Evaluate(next);
     117            if ((nextEval.Quality < currentEval.Quality)) {
     118              current = next;
     119              solutions.Add(current);
     120              break;
     121            }
     122          }
     123
     124          if (problemInstance is IHomogenousCapacitatedProblemInstance) {
     125            if (((CVRPEvaluation)currentEval).Overload > 0) {
     126              (problemInstance as IHomogenousCapacitatedProblemInstance).OverloadPenalty.Value =
     127                Math.Min(maxPenalty,
     128                (problemInstance as IHomogenousCapacitatedProblemInstance).OverloadPenalty.Value * sigma);
     129            } else {
     130              (problemInstance as IHomogenousCapacitatedProblemInstance).OverloadPenalty.Value =
     131                Math.Max(minPenalty,
     132                (problemInstance as IHomogenousCapacitatedProblemInstance).OverloadPenalty.Value * sigma);
     133            }
     134          }
     135
     136
     137          if (problemInstance is ITimeWindowedProblemInstance) {
     138            if (((CVRPTWEvaluation)currentEval).Tardiness > 0) {
     139              (problemInstance as ITimeWindowedProblemInstance).TardinessPenalty.Value =
     140                Math.Min(maxPenalty,
     141              (problemInstance as ITimeWindowedProblemInstance).TardinessPenalty.Value * sigma);
     142            } else {
     143              (problemInstance as ITimeWindowedProblemInstance).TardinessPenalty.Value =
     144                Math.Max(minPenalty,
     145                (problemInstance as ITimeWindowedProblemInstance).TardinessPenalty.Value / sigma);
     146            }
     147          }
     148
     149          i++;
     150        }
     151      }
     152
     153      if (problemInstance is IHomogenousCapacitatedProblemInstance)
     154        (problemInstance as IHomogenousCapacitatedProblemInstance).OverloadPenalty.Value = originalOverloadPenalty.Value;
     155      if (problemInstance is ITimeWindowedProblemInstance)
     156        (problemInstance as ITimeWindowedProblemInstance).TardinessPenalty.Value = originalTardinessPenalty.Value;
     157
     158      return new ItemArray<IItem>(ChooseSelection(solutions, n));
     159    }
     160
     161    private static IList<IItem> ChooseSelection(IList<PotvinEncoding> solutions, PercentValue n) {
     162      IList<IItem> selection = new List<IItem>();
     163      if (solutions.Count > 0) {
     164        int noSol = (int)(solutions.Count * n.Value);
     165        if (noSol <= 0) noSol++;
     166        double stepSize = (double)solutions.Count / (double)noSol;
     167        for (int i = 0; i < noSol; i++)
     168          selection.Add(solutions.ElementAt((int)((i + 1) * stepSize - stepSize * 0.5)));
     169      }
     170
     171      return selection;
     172    }
     173
     174    protected override ItemArray<IItem> Relink(ItemArray<IItem> parents, PercentValue n) {
     175      if (parents.Length != 2)
     176        throw new ArgumentException("The number of parents is not equal to 2.");
     177
     178      if (!(parents[0] is PotvinEncoding))
     179        parents[0] = PotvinEncoding.ConvertFrom(parents[0] as IVRPEncoding, ProblemInstanceParameter.ActualValue);
     180      if (!(parents[1] is PotvinEncoding))
     181        parents[1] = PotvinEncoding.ConvertFrom(parents[1] as IVRPEncoding, ProblemInstanceParameter.ActualValue);
     182
     183      return Apply(parents[0] as PotvinEncoding, parents[1] as PotvinEncoding, n,
     184        SampleSizeParameter.Value.Value, IterationsParameter.Value.Value, RandomParameter.ActualValue, ProblemInstanceParameter.ActualValue);
     185    }
     186
    74187    private static int MatchingCities(Tour tour1, Tour tour2) {
    75188      return tour1.Stops.Intersect(tour2.Stops).Count();
    … …  
    77190
    78191    private static PotvinEncoding MatchTours(PotvinEncoding initiator, PotvinEncoding guide, IVRPProblemInstance problemInstance) {
    79       PotvinEncoding result = new PotvinEncoding(problemInstance);
    80 
    81       List<bool> used = new List<bool>();
     192      var result = new PotvinEncoding(problemInstance);
     193
     194      var used = new List<bool>();
    82195      for (int i = 0; i < initiator.Tours.Count; i++) {
    83196        used.Add(false);
    … …  
    120233      return PotvinSequenceBasedCrossover.Apply(random, initiator, guide, problemInstance, false);
    121234    }
    122 
    123235
    124236    public static void GuidedRelocateMove(PotvinEncoding initiator, PotvinEncoding guide, IRandom random) {
    … …  
    208320      individual.Tours.RemoveAll(t => t.Stops.Count == 0);
    209321    }
    210 
    211     public static void ExchangeMove(PotvinEncoding individual, IRandom random) {
    212       if (individual.Tours.Count > 1) {
    213         int tour1Idx = random.Next(individual.Tours.Count);
    214         int tour2Idx = random.Next(individual.Tours.Count - 1);
    215         if (tour2Idx >= tour1Idx)
    216           tour2Idx++;
    217 
    218         Tour tour1 = individual.Tours[tour1Idx];
    219         Tour tour2 = individual.Tours[tour2Idx];
    220 
    221         int index1 = random.Next(tour1.Stops.Count);
    222         int city1 = tour1.Stops[index1];
    223 
    224         int index2 = random.Next(tour2.Stops.Count);
    225         int city2 = tour2.Stops[index2];
    226 
    227         tour1.Stops.RemoveAt(index1);
    228         tour1.Stops.Insert(index1, city2);
    229 
    230         tour2.Stops.RemoveAt(index2);
    231         tour2.Stops.Insert(index2, city1);
    232       }
    233     }
    234 
    235     public static void TwoOptMove(PotvinEncoding individual, IRandom random) {
    236       List<Tour> tours = individual.Tours.FindAll(t => t.Stops.Count >= 4);
    237 
    238       if (tours.Count > 0) {
    239         int tourIdx = random.Next(tours.Count);
    240         Tour tour = tours[tourIdx];
    241 
    242         int a;
    243         if (tour.Stops.Count == 4) {
    244           a = 0;
    245         } else if (tour.Stops.Count == 5) {
    246           int idx = random.Next(4);
    247           if (idx >= 2)
    248             idx++;
    249           a = idx;
    250         } else {
    251           a = random.Next(tour.Stops.Count);
    252         }
    253 
    254         int b;
    255         List<int> indices = new List<int>();
    256         for (int i = 0; i < tour.Stops.Count; i++) {
    257           if (Math.Abs(i - a) > 2) {
    258             indices.Add(i);
    259           }
    260         }
    261         b = indices[random.Next(indices.Count)];
    262 
    263         if (b < a) {
    264           int tmp = a;
    265           a = b;
    266           b = tmp;
    267         }
    268 
    269         int index = a + 1;
    270         int count = b - a - 1;
    271         List<int> segment = tour.Stops.GetRange(index, count);
    272         tour.Stops.RemoveRange(index, count);
    273         segment.Reverse();
    274         tour.Stops.InsertRange(index, segment);
    275       }
    276     }
    277 
    278     public static void TwoOptStarMove(PotvinEncoding individual, IRandom random) {
    279       //consider creating new tour
    280       individual.Tours.Add(new Tour());
    281 
    282       int route1Idx = random.Next(individual.Tours.Count);
    283       int route2Idx = random.Next(individual.Tours.Count - 1);
    284       if (route2Idx >= route1Idx)
    285         route2Idx++;
    286 
    287       Tour route1 = individual.Tours[route1Idx];
    288       Tour route2 = individual.Tours[route2Idx];
    289 
    290       int x1 = random.Next(route1.Stops.Count + 1);
    291       int x2 = random.Next(route2.Stops.Count + 1);
    292 
    293       int count = route1.Stops.Count - x1;
    294       List<int> segmentX1 = new List<int>();
    295       if (count > 0) {
    296         segmentX1 = route1.Stops.GetRange(x1, count);
    297         route1.Stops.RemoveRange(x1, count);
    298       }
    299 
    300       count = route2.Stops.Count - x2;
    301       List<int> segmentX2 = new List<int>();
    302       if (count > 0) {
    303         segmentX2 = route2.Stops.GetRange(x2, count);
    304         route2.Stops.RemoveRange(x2, count);
    305       }
    306 
    307       route1.Stops.AddRange(segmentX2);
    308       route2.Stops.AddRange(segmentX1);
    309 
    310       individual.Tours.RemoveAll(t => t.Stops.Count == 0);
    311     }
    312 
    313     public static void OrOptMove(PotvinEncoding individual, IRandom random) {
    314       List<Tour> tours = individual.Tours.FindAll(t => t.Stops.Count >= 2);
    315 
    316       if (tours.Count > 0) {
    317         int tourIdx = random.Next(tours.Count);
    318         Tour tour = tours[tourIdx];
    319 
    320         int segmentStart = random.Next(tour.Stops.Count);
    321         int segmentLength;
    322         if (segmentStart == 0) {
    323           segmentLength = 1 + random.Next(tour.Stops.Count - 1);
    324         } else {
    325           segmentLength = 1 + random.Next(tour.Stops.Count - segmentStart);
    326         }
    327 
    328         List<int> segment = tour.Stops.GetRange(segmentStart, segmentLength);
    329         tour.Stops.RemoveRange(segmentStart, segmentLength);
    330         int newPos;
    331         if (tour.Stops.Count == 1)
    332           newPos = 0;
    333         else
    334           newPos = random.Next(tour.Stops.Count - 1);
    335 
    336         if (newPos >= segmentStart)
    337           newPos++;
    338         tour.Stops.InsertRange(newPos, segment);
    339       }
    340     }
    341322    #endregion
    342 
    343     private static IList<IItem> ChooseSelection(IList<PotvinEncoding> solutions, PercentValue n) {
    344       IList<IItem> selection = new List<IItem>();
    345       if (solutions.Count > 0) {
    346         int noSol = (int)(solutions.Count * n.Value);
    347         if (noSol <= 0) noSol++;
    348         double stepSize = (double)solutions.Count / (double)noSol;
    349         for (int i = 0; i < noSol; i++)
    350           selection.Add(solutions.ElementAt((int)((i + 1) * stepSize - stepSize * 0.5)));
    351       }
    352 
    353       return selection;
    354     }
    355 
    356     public static ItemArray<IItem> Apply(PotvinEncoding initiator, PotvinEncoding guide, PercentValue n, int sampleSize, int iterations, IRandom rand, IVRPProblemInstance problemInstance) {
    357 
    358       if (initiator == null || guide == null)
    359         throw new ArgumentException("Cannot relink path because one of the provided solutions or both are null.");
    360 
    361       double sigma = 1.5;
    362 
    363       DoubleValue originalOverloadPenalty = new DoubleValue();
    364       if (problemInstance is IHomogenousCapacitatedProblemInstance)
    365         originalOverloadPenalty.Value = (problemInstance as IHomogenousCapacitatedProblemInstance).OverloadPenalty.Value;
    366       DoubleValue originalTardinessPenalty = new DoubleValue();
    367       if (problemInstance is ITimeWindowedProblemInstance)
    368         originalTardinessPenalty.Value = (problemInstance as ITimeWindowedProblemInstance).TardinessPenalty.Value;
    369 
    370       PotvinEncoding current = MatchTours(initiator, guide, problemInstance);
    371       double currentSimilarity = VRPSimilarityCalculator.CalculateSimilarity(current, guide);
    372 
    373       IList<PotvinEncoding> solutions = new List<PotvinEncoding>();
    374       int i = 0;
    375       while (i < iterations && currentSimilarity != 1.0) {
    376         VRPEvaluation currentEval = problemInstance.Evaluate(current);
    377         currentSimilarity = VRPSimilarityCalculator.CalculateSimilarity(current, guide);
    378 
    379         if (currentSimilarity < 1.0) {
    380           for (int sample = 0; sample < sampleSize; sample++) {
    381             PotvinEncoding next = current.Clone() as PotvinEncoding;
    382 
    383             int neighborhood = rand.Next(4);
    384             switch (neighborhood) {
    385               case 0: next = RouteBasedXOver(next, guide, rand,
    386                 problemInstance);
    387                 break;
    388               case 1: next = SequenceBasedXOver(next, guide, rand,
    389                 problemInstance);
    390                 break;
    391               case 2: TwoOptMove(next, rand);
    392                 break;
    393               case 3: GuidedRelocateMove(next, guide, rand);
    394                 break;
    395             }
    396 
    397             next = MatchTours(next, guide, problemInstance);
    398 
    399             VRPEvaluation nextEval = problemInstance.Evaluate(next);
    400             double nextSimilarity = VRPSimilarityCalculator.CalculateSimilarity(next, guide);
    401 
    402             if (nextSimilarity > currentSimilarity && nextEval.Quality <= currentEval.Quality) {
    403               current = next;
    404               solutions.Add(current);
    405               break;
    406             }
    407           }
    408 
    409           if (problemInstance is IHomogenousCapacitatedProblemInstance) {
    410             if (((CVRPEvaluation)currentEval).Overload > 0)
    411               (problemInstance as IHomogenousCapacitatedProblemInstance).OverloadPenalty.Value *= sigma;
    412             else
    413               (problemInstance as IHomogenousCapacitatedProblemInstance).OverloadPenalty.Value /= sigma;
    414           }
    415 
    416 
    417           if (problemInstance is ITimeWindowedProblemInstance) {
    418             if (((CVRPTWEvaluation)currentEval).Tardiness > 0)
    419               (problemInstance as ITimeWindowedProblemInstance).TardinessPenalty.Value *= sigma;
    420             else
    421               (problemInstance as ITimeWindowedProblemInstance).TardinessPenalty.Value /= sigma;
    422           }
    423 
    424           i++;
    425         }
    426       }
    427 
    428       if (problemInstance is IHomogenousCapacitatedProblemInstance)
    429         (problemInstance as IHomogenousCapacitatedProblemInstance).OverloadPenalty.Value = originalOverloadPenalty.Value;
    430       if (problemInstance is ITimeWindowedProblemInstance)
    431         (problemInstance as ITimeWindowedProblemInstance).TardinessPenalty.Value = originalTardinessPenalty.Value;
    432 
    433       return new ItemArray<IItem>(ChooseSelection(solutions, n));
    434     }
    435 
    436     protected override ItemArray<IItem> Relink(ItemArray<IItem> parents, PercentValue n) {
    437       if (parents.Length != 2)
    438         throw new ArgumentException("The number of parents is not equal to 2.");
    439 
    440       if (!(parents[0] is PotvinEncoding))
    441         parents[0] = PotvinEncoding.ConvertFrom(parents[0] as IVRPEncoding, ProblemInstanceParameter.ActualValue);
    442       if (!(parents[1] is PotvinEncoding))
    443         parents[1] = PotvinEncoding.ConvertFrom(parents[1] as IVRPEncoding, ProblemInstanceParameter.ActualValue);
    444 
    445       return Apply(parents[0] as PotvinEncoding, parents[1] as PotvinEncoding, n,
    446         SampleSizeParameter.Value.Value, IterationsParameter.Value.Value, RandomParameter.ActualValue, ProblemInstanceParameter.ActualValue);
    447     }
    448323  }
    449324}

  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.4/SimilarityCalculators/VRPSimilarityCalculator.cs

    r8720 r8894  
    3232namespace HeuristicLab.Problems.VehicleRouting {
    3333  /// <summary>
    34   /// An operator that performs similarity calculation between two vehicle routing solutions.
     34  /// An operator which performs similarity calculation between two VRP solutions.
    3535  /// </summary>
    3636  /// <remarks>
    3737  /// The operator calculates the similarity based on the number of edges the two solutions have in common.
    3838  /// </remarks>
    39   [Item("VRPSimilarityCalculator", "An operator that performs similarity calculation between two vehicle routing solutions.")]
     39  [Item("VRPSimilarityCalculator", "An operator which performs similarity calculation between two VRP solutions.")]
    4040  [StorableClass]
    4141  public sealed class VRPSimilarityCalculator : SingleObjectiveSolutionSimilarityCalculator {

  • trunk/sources/HeuristicLab.Tests/HeuristicLab-3.3/SamplesTest.cs

    r8891 r8894  
    968968      ss.SetSeedRandomly.Value = false;
    969969      RunAlgorithm(ss);
    970       Assert.AreEqual(749, GetDoubleResult(ss, "BestQuality"));
    971       Assert.AreEqual(766.95, GetDoubleResult(ss, "CurrentAverageQuality"));
    972       Assert.AreEqual(789, GetDoubleResult(ss, "CurrentWorstQuality"));
    973       Assert.AreEqual(27400, GetIntResult(ss, "EvaluatedSolutions"));
     970      Assert.AreEqual(828.93686694283383, GetDoubleResult(ss, "BestQuality"));
     971      Assert.AreEqual(868.63623986983077, GetDoubleResult(ss, "CurrentAverageQuality"));
     972      Assert.AreEqual(1048.8333559209832, GetDoubleResult(ss, "CurrentWorstQuality"));
     973      Assert.AreEqual(262622, GetIntResult(ss, "EvaluatedSolutions"));
    974974    }
    975975
    976976    private ScatterSearch CreateScatterSearchVRPSample() {
    977977      #region Problem Configuration
    978       var provider = new AugeratInstanceProvider();
    979       var instance = provider.GetDataDescriptors().Where(x => x.Name == "A-n38-k5").Single();
     978      var provider = new SolomonInstanceProvider();
     979      var instance = provider.GetDataDescriptors().Single(x => x.Name == "C101");
    980980      VehicleRoutingProblem vrpProblem = new VehicleRoutingProblem();
    981981      vrpProblem.Load(provider.LoadData(instance));
    … …  
    986986      ss.Engine = new SequentialEngine();
    987987      ss.Name = "Scatter Search - VRP";
    988       ss.Description = "A Scatter Search algorithm which solves the \"A-n38-k5\" vehicle routing problem (imported from Augerat)";
     988      ss.Description = "A scatter search algorithm which solves the \"C101\" vehicle routing problem (imported from Solomon)";
    989989      ss.Problem = vrpProblem;
    990990
    991       var improver = ss.Problem.Operators.OfType<VRPImprovementOperator>().First();
    992       improver.ImprovementAttemptsParameter.Value.Value = 5;
    993       improver.SampleSizeParameter.Value.Value = 5;
     991      var improver = ss.Problem.Operators.OfType<VRPIntraRouteImprovementOperator>().First();
     992      improver.ImprovementAttemptsParameter.Value.Value = 15;
     993      improver.SampleSizeParameter.Value.Value = 10;
    994994      ss.Improver = improver;
    995995
    996996      var pathRelinker = ss.Problem.Operators.OfType<VRPPathRelinker>().First();
    997       pathRelinker.IterationsParameter.Value.Value = 15;
     997      pathRelinker.IterationsParameter.Value.Value = 25;
    998998      ss.PathRelinker = pathRelinker;
    999999
    1000       var qualitySimCalc = ss.SimilarityCalculatorParameter.ValidValues.OfType<QualitySimilarityCalculator>().First();
    1001       ss.SimilarityCalculator = qualitySimCalc;
    1002 
    1003       ss.MaximumIterations.Value = 5;
     1000      var similarityCalculator = ss.SimilarityCalculatorParameter.ValidValues.OfType<VRPSimilarityCalculator>().First();
     1001      ss.SimilarityCalculator = similarityCalculator;
     1002
     1003      ss.MaximumIterations.Value = 2;
     1004      ss.PopulationSize.Value = 20;
     1005      ss.ReferenceSetSize.Value = 10;
    10041006      ss.Seed.Value = 0;
    10051007      return ss;
Note: See TracChangeset for help on using the changeset viewer.