Changeset 9836 for branches/FitnessLandscapeAnalysis/HeuristicLab.Analysis.FitnessLandscape.VRP/Manipulators/TwoOptManipulator.cs

Timestamp:

08/01/13 13:55:01 (11 years ago)

Author:

epitzer

Message:

Fix VRP FLA manipulators and adapt to VRP-3.4 (#1703)

File:

• branches/FitnessLandscapeAnalysis/HeuristicLab.Analysis.FitnessLandscape.VRP/Manipulators/TwoOptManipulator.cs (modified) (2 diffs)

branches/FitnessLandscapeAnalysis/HeuristicLab.Analysis.FitnessLandscape.VRP/Manipulators/TwoOptManipulator.cs

@@ -30 +30 @@
 using HeuristicLab.Problems.VehicleRouting;
 using System;
+using HeuristicLab.Problems.VehicleRouting.Interfaces;
 
 namespace HeuristicLab.Analysis.FitnessLandscape.VRP {
@@ -47 +48 @@
     }
 
-    public static void Apply(IRandom random, PotvinEncoding individual) {
-      List<Tour> tours = individual.Tours.FindAll(t => t.Stops.Count >= 4);
+    public static void Apply(IRandom random, PotvinEncoding individual, IVRPProblemInstance instance, bool allowInfeasible) {
+      List<Tour> tours = individual.Tours.FindAll(t => t.Stops.Count >= 2);
+      if (tours.Count == 0) return;
 
-      if (tours.Count > 0) {
+      bool feasible;
+      int count = 0;
+
+      do {
+        feasible = true;
         int tourIdx = random.Next(tours.Count);
         Tour tour = tours[tourIdx];
 
-        int a;
-        if (tour.Stops.Count == 4) {
-            a = 0;
-        } else if (tour.Stops.Count == 5) {
-          int idx = random.Next(4);
-          if (idx >= 2)
-            idx++;
-          a = idx;
+        int first;
+        int length;
+        if (tour.Stops.Count == 2) {
+          first = 0;
+          length = 2;
         } else {
-          a = random.Next(tour.Stops.Count);
+          first = random.Next(tour.Stops.Count - 1);
+          if (first == tour.Stops.Count - 2) {
+            length = tour.Stops.Count - first;
+          } else {
+            length = random.Next(tour.Stops.Count - first - 1) + 2;
+          }
         }
 
-        int b;
-        List<int> indices = new List<int>();
-        for (int i = 0; i < tour.Stops.Count; i++) {
-          if (Math.Abs(i - a) > 2) {
-            indices.Add(i);
+        var originalFeasible = instance.TourFeasible(tour, individual);
+
+        var segment = tour.Stops.GetRange(first, length);
+        tour.Stops.RemoveRange(first, length);
+        segment.Reverse();
+        tour.Stops.InsertRange(first, segment);
+
+        if (!allowInfeasible && originalFeasible) {
+          feasible = instance.TourFeasible(tour, individual);
+          if (!feasible) {
+            tour.Stops.RemoveRange(first, length);
+            segment.Reverse();
+            tour.Stops.InsertRange(first, segment);
           }
         }
-        b = indices[random.Next(indices.Count)];
 
-        if (b < a) {
-          int tmp = a;
-          a = b;
-          b = tmp;
-        }
-
-        int index = a + 1;
-        int count = b - a - 1;
-        List<int> segment = tour.Stops.GetRange(index, count);
-        tour.Stops.RemoveRange(index, count);
-        segment.Reverse();
-        tour.Stops.InsertRange(index, segment);
-      }
+      } while(!feasible && count++ < 100);
     }
 
     protected override void Manipulate(IRandom random, PotvinEncoding individual) {
-      Apply(random, individual);
+      bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
+      Apply(random, individual, ProblemInstance, allowInfeasible);
     }
   }