Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
07/25/13 09:21:45 (11 years ago)
Author:
gkronber
Message:

#1591: adapted FLA branch to reference most recent version of ALGLIB (3.7.0) and VRP (3.4). Several major changes were necessary to port the implementation to the new VRP problem.

Location:
branches/FitnessLandscapeAnalysis/HeuristicLab.Analysis.FitnessLandscape.VRP/Manipulators
Files:
5 edited

Legend:

Unmodified
Added
Removed

  • branches/FitnessLandscapeAnalysis/HeuristicLab.Analysis.FitnessLandscape.VRP/Manipulators/ExchangeManipulator.cs

    r7159 r9750  
    2929using HeuristicLab.Problems.VehicleRouting.Encodings;
    3030using HeuristicLab.Problems.VehicleRouting;
     31using HeuristicLab.Problems.VehicleRouting.Interfaces;
    3132
    3233namespace HeuristicLab.Analysis.FitnessLandscape.VRP {
    … …  
    4647    }
    4748
    48     private static bool RouteFeasible(Tour tour, DoubleArray demand, DoubleValue capacity) {
    49       double routeLoad = 0;
    50       for (int i = 0; i < tour.Cities.Count; i++) {
    51         routeLoad += demand[tour.Cities[i]];
    52       }
    53 
    54       return routeLoad <= capacity.Value;
    55     }
    56 
    57     public static void Apply(IRandom random, PotvinEncoding individual, DoubleArray demand, DoubleValue capacity, bool allowInfeasible) {
     49    public static void Apply(IRandom random, PotvinEncoding individual, IVRPProblemInstance problemInstance, bool allowInfeasible) {
    5850      bool feasible;
    5951
    … …  
    7062          Tour tour2 = individual.Tours[tour2Idx];
    7163
    72           int index1 = random.Next(tour1.Cities.Count);
    73           int city1 = tour1.Cities[index1];
     64          int index1 = random.Next(tour1.Stops.Count);
     65          int city1 = tour1.Stops[index1];
    7466
    75           int index2 = random.Next(tour2.Cities.Count);
    76           int city2 = tour2.Cities[index2];
     67          int index2 = random.Next(tour2.Stops.Count);
     68          int city2 = tour2.Stops[index2];
    7769
    7870          if (!allowInfeasible) {
    79             bool originalFeasible =
    80               RouteFeasible(tour1, demand, capacity) &&
    81               RouteFeasible(tour2, demand, capacity);
     71            bool originalFeasible = problemInstance.TourFeasible(tour1, individual) &&
     72                                    problemInstance.TourFeasible(tour2, individual);
    8273
    8374            if (originalFeasible) {
    84               double routeLoad = 0;
    85               for (int i = 0; i < tour1.Cities.Count; i++) {
    86                 if (i != index1)
    87                   routeLoad += demand[tour1.Cities[i]];
     75              var tmpCity1 = tour1.Stops[index1];
     76              tour1.Stops.RemoveAt(index1);
     77              tour1.Stops.Insert(index1, city2);
     78
     79              if (problemInstance.TourFeasible(tour1, individual)) {
     80                var tmpCity2 = tour2.Stops[index2];
     81                tour2.Stops.RemoveAt(index2);
     82                tour2.Stops.Insert(index2, city1);
     83
     84                feasible = problemInstance.TourFeasible(tour2, individual);
     85
     86                if (!feasible) {
     87                  // undo tour1 and tour2 changes
     88                  tour2.Stops.RemoveAt(index2);
     89                  tour2.Stops.Insert(index2, tmpCity2);
     90
     91                  tour1.Stops.RemoveAt(index1);
     92                  tour1.Stops.Insert(index1, tmpCity1);
     93                }
     94              } else {
     95                feasible = false;
     96                // undo tour1 change
     97                tour1.Stops.RemoveAt(index1);
     98                tour1.Stops.Insert(index1, tmpCity1);
    8899              }
    89               routeLoad += demand[city2];
    90 
    91               if (routeLoad > capacity.Value) {
    92                 feasible = false;
    93               } else {
    94                 routeLoad = 0;
    95                 for (int i = 0; i < tour2.Cities.Count; i++) {
    96                   if (i != index2)
    97                     routeLoad += demand[tour2.Cities[i]];
    98                 }
    99                 routeLoad += demand[city1];
    100 
    101                 if (routeLoad > capacity.Value) {
    102                   feasible = false;
    103                 }
    104               }
    105 
    106             }
    107           }
    108 
    109           if (feasible) {
    110             tour1.Cities.RemoveAt(index1);
    111             tour1.Cities.Insert(index1, city2);
    112 
    113             tour2.Cities.RemoveAt(index2);
    114             tour2.Cities.Insert(index2, city1);
     100            } else feasible = false;
    115101          }
    116102        }
    … …  
    119105
    120106    protected override void Manipulate(IRandom random, PotvinEncoding individual) {
    121       BoolValue useDistanceMatrix = UseDistanceMatrixParameter.ActualValue;
    122       DoubleMatrix coordinates = CoordinatesParameter.ActualValue;
    123       DistanceMatrix distMatrix = VRPUtilities.GetDistanceMatrix(coordinates, DistanceMatrixParameter, useDistanceMatrix);
    124       DoubleArray demand = DemandParameter.ActualValue;
    125       DoubleValue capacity = CapacityParameter.ActualValue;
    126 
    127107      bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
    128       Apply(random, individual, demand, capacity, allowInfeasible);
     108      Apply(random, individual, ProblemInstance, allowInfeasible);
    129109    }
    130110  }

  • branches/FitnessLandscapeAnalysis/HeuristicLab.Analysis.FitnessLandscape.VRP/Manipulators/OrOptManipulator.cs

    r7159 r9750  
    4848
    4949    public static void Apply(IRandom random, PotvinEncoding individual) {
    50       List<Tour> tours = individual.Tours.FindAll(t => t.Cities.Count >= 2);
     50      List<Tour> tours = individual.Tours.FindAll(t => t.Stops.Count >= 2);
    5151
    5252      if (tours.Count > 0) {
    … …  
    5454        Tour tour = tours[tourIdx];
    5555
    56         int segmentStart = random.Next(tour.Cities.Count);
     56        int segmentStart = random.Next(tour.Stops.Count);
    5757        int segmentLength;
    5858        if (segmentStart == 0) {
    59           segmentLength = 1 + random.Next(tour.Cities.Count - 1);
     59          segmentLength = 1 + random.Next(tour.Stops.Count - 1);
    6060        } else {
    61           segmentLength = 1 + random.Next(tour.Cities.Count - segmentStart);
     61          segmentLength = 1 + random.Next(tour.Stops.Count - segmentStart);
    6262        }
    6363
    64         List<int> segment = tour.Cities.GetRange(segmentStart, segmentLength);
    65         tour.Cities.RemoveRange(segmentStart, segmentLength);
     64        List<int> segment = tour.Stops.GetRange(segmentStart, segmentLength);
     65        tour.Stops.RemoveRange(segmentStart, segmentLength);
    6666        int newPos;
    67         if(tour.Cities.Count == 1)
     67        if (tour.Stops.Count == 1)
    6868          newPos = 0;
    6969        else
    70           newPos = random.Next(tour.Cities.Count - 1);
     70          newPos = random.Next(tour.Stops.Count - 1);
    7171
    7272        if (newPos >= segmentStart)
    7373          newPos++;
    74         tour.Cities.InsertRange(newPos, segment);
     74        tour.Stops.InsertRange(newPos, segment);
    7575      }
    7676    }

  • branches/FitnessLandscapeAnalysis/HeuristicLab.Analysis.FitnessLandscape.VRP/Manipulators/RelocateManipulator.cs

    r7159 r9750  
    2929using HeuristicLab.Problems.VehicleRouting.Encodings;
    3030using HeuristicLab.Problems.VehicleRouting;
     31using HeuristicLab.Problems.VehicleRouting.Interfaces;
    3132
    3233namespace HeuristicLab.Analysis.FitnessLandscape.VRP {
    … …  
    4647    }
    4748
    48     private static bool RouteFeasible(Tour tour, DoubleArray demand, DoubleValue capacity) {
    49       double routeLoad = 0;
    50       for (int i = 0; i < tour.Cities.Count; i++) {
    51         routeLoad += demand[tour.Cities[i]];
    52       }
    53 
    54       return routeLoad <= capacity.Value;
    55     }
    56 
    57     public static void Apply(IRandom random, PotvinEncoding individual, DoubleArray demand, DoubleValue capacity, bool allowInfeasible) {
     49    public static void Apply(IRandom random, PotvinEncoding individual, IVRPProblemInstance problemInstance, bool allowInfeasible) {
    5850      bool feasible;
    5951
    … …  
    6355        int cities = individual.Cities;
    6456        int city = 1 + random.Next(cities);
    65         Tour originalTour = individual.Tours.Find(t => t.Cities.Contains(city));
     57        Tour originalTour = individual.Tours.Find(t => t.Stops.Contains(city));
    6658        //consider creating new route
    6759        individual.Tours.Add(new Tour());
    … …  
    7264        }
    7365
    74         int originalPosition = originalTour.Cities.IndexOf(city);
    75         originalTour.Cities.RemoveAt(originalPosition);
     66        int originalPosition = originalTour.Stops.IndexOf(city);
     67        originalTour.Stops.RemoveAt(originalPosition);
    7668
    7769        Tour insertionTour;
    7870        int insertionPosition;
    7971        if (position <= cities) {
    80           insertionTour = individual.Tours.Find(t => t.Cities.Contains(position));
    81           insertionPosition = insertionTour.Cities.IndexOf(position) + 1;
     72          insertionTour = individual.Tours.Find(t => t.Stops.Contains(position));
     73          insertionPosition = insertionTour.Stops.IndexOf(position) + 1;
    8274        } else {
    8375          insertionTour = individual.Tours[position - cities - 1];
    … …  
    8678
    8779        if (!allowInfeasible && insertionTour != originalTour) {
    88           bool originalFeasible = RouteFeasible(insertionTour, demand, capacity);
     80          bool originalFeasible = problemInstance.TourFeasible(insertionTour, individual);
    8981
    9082          if (originalFeasible) {
    91             double routeLoad = 0;
    92             for (int i = 0; i < insertionTour.Cities.Count; i++) {
    93               routeLoad += demand[insertionTour.Cities[i]];
     83            // try insert into insertionTour
     84            insertionTour.Stops.Insert(insertionPosition, city);
     85            feasible = problemInstance.TourFeasible(insertionTour, individual);
     86
     87            if (!feasible) {
     88              // when insertionTour is not feasible we undo the change and add to the original tour instead
     89              insertionTour.Stops.RemoveAt(insertionPosition);
     90              originalTour.Stops.Insert(originalPosition, city);
    9491            }
    95             routeLoad += demand[city];
    96 
    97             feasible = routeLoad <= capacity.Value;
    98           }
     92          } else feasible = false;
    9993        }
    100 
    101         if (feasible) {
    102           insertionTour.Cities.Insert(insertionPosition, city);
    103         } else {
    104           originalTour.Cities.Insert(originalPosition, city);
    105         }
    106 
    107         individual.Tours.RemoveAll(t => t.Cities.Count == 0);
     94        individual.Tours.RemoveAll(t => t.Stops.Count == 0);
    10895      } while (!feasible);
    10996    }
    11097
    11198    protected override void Manipulate(IRandom random, PotvinEncoding individual) {
    112       BoolValue useDistanceMatrix = UseDistanceMatrixParameter.ActualValue;
    113       DoubleMatrix coordinates = CoordinatesParameter.ActualValue;
    114       DistanceMatrix distMatrix = VRPUtilities.GetDistanceMatrix(coordinates, DistanceMatrixParameter, useDistanceMatrix);
    115       DoubleArray demand = DemandParameter.ActualValue;
    116       DoubleValue capacity = CapacityParameter.ActualValue;
    117 
    11899      bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
    119       Apply(random, individual, demand, capacity, allowInfeasible);
     100      Apply(random, individual, ProblemInstance, allowInfeasible);
    120101    }
    121102  }

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

    r7159 r9750  
    4848
    4949    public static void Apply(IRandom random, PotvinEncoding individual) {
    50       List<Tour> tours = individual.Tours.FindAll(t => t.Cities.Count >= 4);
     50      List<Tour> tours = individual.Tours.FindAll(t => t.Stops.Count >= 4);
    5151
    5252      if (tours.Count > 0) {
    … …  
    5555
    5656        int a;
    57         if (tour.Cities.Count == 4) {
     57        if (tour.Stops.Count == 4) {
    5858            a = 0;
    59         } else if (tour.Cities.Count == 5) {
     59        } else if (tour.Stops.Count == 5) {
    6060          int idx = random.Next(4);
    6161          if (idx >= 2)
    … …  
    6363          a = idx;
    6464        } else {
    65           a = random.Next(tour.Cities.Count);
     65          a = random.Next(tour.Stops.Count);
    6666        }
    6767
    6868        int b;
    6969        List<int> indices = new List<int>();
    70         for (int i = 0; i < tour.Cities.Count; i++) {
     70        for (int i = 0; i < tour.Stops.Count; i++) {
    7171          if (Math.Abs(i - a) > 2) {
    7272            indices.Add(i);
    … …  
    8383        int index = a + 1;
    8484        int count = b - a - 1;
    85         List<int> segment = tour.Cities.GetRange(index, count);
    86         tour.Cities.RemoveRange(index, count);
     85        List<int> segment = tour.Stops.GetRange(index, count);
     86        tour.Stops.RemoveRange(index, count);
    8787        segment.Reverse();
    88         tour.Cities.InsertRange(index, segment);
     88        tour.Stops.InsertRange(index, segment);
    8989      }
    9090    }

  • branches/FitnessLandscapeAnalysis/HeuristicLab.Analysis.FitnessLandscape.VRP/Manipulators/TwoOptStarManipulator.cs

    r7159 r9750  
    2929using HeuristicLab.Problems.VehicleRouting.Encodings;
    3030using HeuristicLab.Problems.VehicleRouting;
     31using HeuristicLab.Problems.VehicleRouting.Interfaces;
    3132
    3233namespace HeuristicLab.Analysis.FitnessLandscape.VRP {
    … …  
    4647    }
    4748
    48     private static bool RouteFeasible(Tour tour, DoubleArray demand, DoubleValue capacity) {
    49       double routeLoad = 0;
    50       for (int i = 0; i < tour.Cities.Count; i++) {
    51         routeLoad += demand[tour.Cities[i]];
    52       }
    53 
    54       return routeLoad <= capacity.Value;
    55     }
    56 
    57     public static void Apply(IRandom random, PotvinEncoding individual, DoubleArray demand, DoubleValue capacity, bool allowInfeasible) {
     49    public static void Apply(IRandom random, PotvinEncoding individual, IVRPProblemInstance problemInstance, bool allowInfeasible) {
    5850      bool feasible;
    5951
    … …  
    7264        Tour route2 = individual.Tours[route2Idx];
    7365
    74         int x1 = random.Next(route1.Cities.Count + 1);
    75         int x2 = random.Next(route2.Cities.Count + 1);
     66        int x1 = random.Next(route1.Stops.Count + 1);
     67        int x2 = random.Next(route2.Stops.Count + 1);
    7668
    7769        if (!allowInfeasible) {
    78           bool originalFeasible =
    79             RouteFeasible(route1, demand, capacity) &&
    80             RouteFeasible(route2, demand, capacity);
     70          bool originalFeasible = problemInstance.TourFeasible(route1, individual) &&
     71                                  problemInstance.TourFeasible(route2, individual);
    8172
    8273          if (originalFeasible) {
    83             double routeLoad = 0;
    84             for (int i = 0; i < x1; i++)
    85               routeLoad += demand[route1.Cities[i]];
    86             for (int i = x2; i < route2.Cities.Count; i++)
    87               routeLoad += demand[route2.Cities[i]];
     74            int count = route1.Stops.Count - x1;
     75            List<int> segmentX1 = new List<int>();
     76            if (count > 0) {
     77              segmentX1 = route1.Stops.GetRange(x1, count);
     78              route1.Stops.RemoveRange(x1, count);
     79            }
    8880
    89             if (routeLoad > capacity.Value) {
    90               feasible = false;
     81            count = route2.Stops.Count - x2;
     82            List<int> segmentX2 = new List<int>();
     83            if (count > 0) {
     84              segmentX2 = route2.Stops.GetRange(x2, count);
     85              route2.Stops.RemoveRange(x2, count);
     86            }
     87
     88            route1.Stops.AddRange(segmentX2);
     89            feasible = problemInstance.TourFeasible(route1, individual);
     90            if (feasible) {
     91              route2.Stops.AddRange(segmentX1);
     92              feasible = problemInstance.TourFeasible(route2, individual);
     93              if (!feasible) {
     94                // undo all changes
     95                route1.Stops.RemoveRange(x1, segmentX2.Count);
     96                route1.Stops.AddRange(segmentX1);
     97                route2.Stops.RemoveRange(x2, segmentX1.Count);
     98                route2.Stops.AddRange(segmentX2);
     99              }
    91100            } else {
    92               routeLoad = 0;
    93               for (int i = 0; i < x2; i++)
    94                 routeLoad += demand[route2.Cities[i]];
    95               for (int i = x1; i < route1.Cities.Count; i++)
    96                 routeLoad += demand[route1.Cities[i]];
     101              // undo changes
     102              route1.Stops.RemoveRange(x1, segmentX2.Count);
     103              route1.Stops.AddRange(segmentX1);
     104              route2.Stops.AddRange(segmentX2);
     105            }
    97106
    98               if (routeLoad > capacity.Value) {
    99                 feasible = false;
    100               }
    101             }
     107          } else {
     108            feasible = false;
    102109          }
    103         }
    104 
    105         if (feasible) {
    106           int count = route1.Cities.Count - x1;
    107           List<int> segmentX1 = new List<int>();
    108           if (count > 0) {
    109             segmentX1 = route1.Cities.GetRange(x1, count);
    110             route1.Cities.RemoveRange(x1, count);
    111           }
    112 
    113           count = route2.Cities.Count - x2;
    114           List<int> segmentX2 = new List<int>();
    115           if (count > 0) {
    116             segmentX2 = route2.Cities.GetRange(x2, count);
    117             route2.Cities.RemoveRange(x2, count);
    118           }
    119 
    120           route1.Cities.AddRange(segmentX2);
    121           route2.Cities.AddRange(segmentX1);
    122110        }
    123111      } while (!feasible);
    124112
    125       individual.Tours.RemoveAll(t => t.Cities.Count == 0);
     113      individual.Tours.RemoveAll(t => t.Stops.Count == 0);
    126114    }
    127115
    128116    protected override void Manipulate(IRandom random, PotvinEncoding individual) {
    129       BoolValue useDistanceMatrix = UseDistanceMatrixParameter.ActualValue;
    130       DoubleMatrix coordinates = CoordinatesParameter.ActualValue;
    131       DistanceMatrix distMatrix = VRPUtilities.GetDistanceMatrix(coordinates, DistanceMatrixParameter, useDistanceMatrix);
    132       DoubleArray demand = DemandParameter.ActualValue;
    133       DoubleValue capacity = CapacityParameter.ActualValue;
    134 
    135117      bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
    136       Apply(random, individual, demand, capacity, allowInfeasible);
     118      Apply(random, individual, ProblemInstance, allowInfeasible);
    137119    }
    138120  }
Note: See TracChangeset for help on using the changeset viewer.