Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
08/01/13 13:55:01 (11 years ago)
Author:
epitzer
Message:

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

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

Legend:

Unmodified
Added
Removed

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

    r9750 r9836  
    4949    public static void Apply(IRandom random, PotvinEncoding individual, IVRPProblemInstance problemInstance, bool allowInfeasible) {
    5050      bool feasible;
     51      int count = 0;
    5152
    5253      do {
    5354        feasible = true;
    54 
    5555        if (individual.Tours.Count > 1) {
    5656          int tour1Idx = random.Next(individual.Tours.Count);
    … …  
    6868          int city2 = tour2.Stops[index2];
    6969
    70           if (!allowInfeasible) {
    71             bool originalFeasible = problemInstance.TourFeasible(tour1, individual) &&
    72                                     problemInstance.TourFeasible(tour2, individual);
     70          bool originalFeasible = problemInstance.TourFeasible(tour1, individual) &&
     71                                  problemInstance.TourFeasible(tour2, individual);
    7372
    74             if (originalFeasible) {
    75               var tmpCity1 = tour1.Stops[index1];
    76               tour1.Stops.RemoveAt(index1);
    77               tour1.Stops.Insert(index1, city2);
     73          tour1.Stops[index1] = city2;
     74          tour2.Stops[index2] = city1;
    7875
    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);
    99               }
    100             } else feasible = false;
     76          if (!allowInfeasible && originalFeasible) {
     77            feasible = problemInstance.TourFeasible(tour1, individual) &&
     78                       problemInstance.TourFeasible(tour2, individual);
     79            if (!feasible) {
     80              tour1.Stops[index1] = city1;
     81              tour2.Stops[index2] = city2;
     82            }
    10183          }
    10284        }
    103       } while (!feasible);
     85      } while (!feasible && count++ < 100);
    10486    }
    10587

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

    r9750 r9836  
    3030using HeuristicLab.Problems.VehicleRouting;
    3131using System;
     32using HeuristicLab.Problems.VehicleRouting.Interfaces;
    3233
    3334namespace HeuristicLab.Analysis.FitnessLandscape.VRP {
    … …  
    4748    }
    4849
    49     public static void Apply(IRandom random, PotvinEncoding individual) {
     50    public static void Apply(IRandom random, PotvinEncoding individual, IVRPProblemInstance instance, bool allowInfeasible) {
    5051      List<Tour> tours = individual.Tours.FindAll(t => t.Stops.Count >= 2);
     52      if (tours.Count == 0) return;
     53      bool feasible;
     54      int count = 0;
    5155
    52       if (tours.Count > 0) {
     56      do {
     57        feasible = true;
    5358        int tourIdx = random.Next(tours.Count);
    5459        Tour tour = tours[tourIdx];
    … …  
    5863        if (segmentStart == 0) {
    5964          segmentLength = 1 + random.Next(tour.Stops.Count - 1);
    60         } else {
     65        }
     66        else {
    6167          segmentLength = 1 + random.Next(tour.Stops.Count - segmentStart);
    6268        }
     69
     70        bool originalFeasible = instance.TourFeasible(tour, individual);
    6371
    6472        List<int> segment = tour.Stops.GetRange(segmentStart, segmentLength);
    … …  
    7381          newPos++;
    7482        tour.Stops.InsertRange(newPos, segment);
    75       }
     83
     84        if (!allowInfeasible && originalFeasible) {
     85          feasible = instance.TourFeasible(tour, individual);
     86          if (!feasible) {
     87            tour.Stops.RemoveRange(newPos, segment.Count);
     88            tour.Stops.InsertRange(segmentStart, segment);
     89          }
     90        }
     91      } while (!feasible && count++ < 100);
    7692    }
    7793
    7894    protected override void Manipulate(IRandom random, PotvinEncoding individual) {
    79       Apply(random, individual);
     95      bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
     96      Apply(random, individual, ProblemInstance, allowInfeasible);
    8097    }
    8198  }

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

    r9750 r9836  
    4949    public static void Apply(IRandom random, PotvinEncoding individual, IVRPProblemInstance problemInstance, bool allowInfeasible) {
    5050      bool feasible;
     51      int count = 0;
    5152
    5253      do {
    … …  
    6465        }
    6566
     67        var originalFeasible = problemInstance.TourFeasible(originalTour, individual);
     68
    6669        int originalPosition = originalTour.Stops.IndexOf(city);
    6770        originalTour.Stops.RemoveAt(originalPosition);
    … …  
    7275          insertionTour = individual.Tours.Find(t => t.Stops.Contains(position));
    7376          insertionPosition = insertionTour.Stops.IndexOf(position) + 1;
    74         } else {
     77        } else { // additional insertion positions at beginning of tours
    7578          insertionTour = individual.Tours[position - cities - 1];
    7679          insertionPosition = 0;
    7780        }
     81        originalFeasible &= problemInstance.TourFeasible(insertionTour, individual);
     82        insertionTour.Stops.Insert(insertionPosition, city);
    7883
    79         if (!allowInfeasible && insertionTour != originalTour) {
    80           bool originalFeasible = problemInstance.TourFeasible(insertionTour, individual);
    81 
    82           if (originalFeasible) {
    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);
    91             }
    92           } else feasible = false;
     84        if (!allowInfeasible && originalFeasible) {
     85          feasible = problemInstance.TourFeasible(insertionTour, individual) &&
     86                     problemInstance.TourFeasible(originalTour, individual);
     87          if (!feasible) {
     88            insertionTour.Stops.RemoveAt(insertionPosition);
     89            originalTour.Stops.Insert(originalPosition, city);
     90          }
    9391        }
    9492        individual.Tours.RemoveAll(t => t.Stops.Count == 0);
    95       } while (!feasible);
     93      } while (!feasible && count++ < 100);
    9694    }
    9795

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

    r9750 r9836  
    3030using HeuristicLab.Problems.VehicleRouting;
    3131using System;
     32using HeuristicLab.Problems.VehicleRouting.Interfaces;
    3233
    3334namespace HeuristicLab.Analysis.FitnessLandscape.VRP {
    … …  
    4748    }
    4849
    49     public static void Apply(IRandom random, PotvinEncoding individual) {
    50       List<Tour> tours = individual.Tours.FindAll(t => t.Stops.Count >= 4);
     50    public static void Apply(IRandom random, PotvinEncoding individual, IVRPProblemInstance instance, bool allowInfeasible) {
     51      List<Tour> tours = individual.Tours.FindAll(t => t.Stops.Count >= 2);
     52      if (tours.Count == 0) return;
    5153
    52       if (tours.Count > 0) {
     54      bool feasible;
     55      int count = 0;
     56
     57      do {
     58        feasible = true;
    5359        int tourIdx = random.Next(tours.Count);
    5460        Tour tour = tours[tourIdx];
    5561
    56         int a;
    57         if (tour.Stops.Count == 4) {
    58             a = 0;
    59         } else if (tour.Stops.Count == 5) {
    60           int idx = random.Next(4);
    61           if (idx >= 2)
    62             idx++;
    63           a = idx;
     62        int first;
     63        int length;
     64        if (tour.Stops.Count == 2) {
     65          first = 0;
     66          length = 2;
    6467        } else {
    65           a = random.Next(tour.Stops.Count);
     68          first = random.Next(tour.Stops.Count - 1);
     69          if (first == tour.Stops.Count - 2) {
     70            length = tour.Stops.Count - first;
     71          } else {
     72            length = random.Next(tour.Stops.Count - first - 1) + 2;
     73          }
    6674        }
    6775
    68         int b;
    69         List<int> indices = new List<int>();
    70         for (int i = 0; i < tour.Stops.Count; i++) {
    71           if (Math.Abs(i - a) > 2) {
    72             indices.Add(i);
     76        var originalFeasible = instance.TourFeasible(tour, individual);
     77
     78        var segment = tour.Stops.GetRange(first, length);
     79        tour.Stops.RemoveRange(first, length);
     80        segment.Reverse();
     81        tour.Stops.InsertRange(first, segment);
     82
     83        if (!allowInfeasible && originalFeasible) {
     84          feasible = instance.TourFeasible(tour, individual);
     85          if (!feasible) {
     86            tour.Stops.RemoveRange(first, length);
     87            segment.Reverse();
     88            tour.Stops.InsertRange(first, segment);
    7389          }
    7490        }
    75         b = indices[random.Next(indices.Count)];
    7691
    77         if (b < a) {
    78           int tmp = a;
    79           a = b;
    80           b = tmp;
    81         }
    82 
    83         int index = a + 1;
    84         int count = b - a - 1;
    85         List<int> segment = tour.Stops.GetRange(index, count);
    86         tour.Stops.RemoveRange(index, count);
    87         segment.Reverse();
    88         tour.Stops.InsertRange(index, segment);
    89       }
     92      } while(!feasible && count++ < 100);
    9093    }
    9194
    9295    protected override void Manipulate(IRandom random, PotvinEncoding individual) {
    93       Apply(random, individual);
     96      bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
     97      Apply(random, individual, ProblemInstance, allowInfeasible);
    9498    }
    9599  }

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

    r9750 r9836  
    4949    public static void Apply(IRandom random, PotvinEncoding individual, IVRPProblemInstance problemInstance, bool allowInfeasible) {
    5050      bool feasible;
     51      int count = 0;
    5152
    5253      //consider creating new tour
    … …  
    6768        int x2 = random.Next(route2.Stops.Count + 1);
    6869
    69         if (!allowInfeasible) {
    70           bool originalFeasible = problemInstance.TourFeasible(route1, individual) &&
    71                                   problemInstance.TourFeasible(route2, individual);
     70        var originalFeasible =
     71          problemInstance.TourFeasible(route1, individual) &&
     72          problemInstance.TourFeasible(route2, individual);
    7273
    73           if (originalFeasible) {
    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             }
     74       SwapSegments(x1, route1, x2, route2);
    8075
    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               }
    100             } else {
    101               // undo changes
    102               route1.Stops.RemoveRange(x1, segmentX2.Count);
    103               route1.Stops.AddRange(segmentX1);
    104               route2.Stops.AddRange(segmentX2);
    105             }
    106 
    107           } else {
    108             feasible = false;
    109           }
    110         }
    111       } while (!feasible);
     76       if (!allowInfeasible && originalFeasible) {
     77         feasible = problemInstance.TourFeasible(route1, individual) &&
     78                    problemInstance.TourFeasible(route2, individual);
     79         if (!feasible) SwapSegments(x1, route1, x2, route2);
     80       }
     81      } while (!feasible && count++ < 100);
    11282
    11383      individual.Tours.RemoveAll(t => t.Stops.Count == 0);
     84    }
     85
     86    private static void SwapSegments(int x1, Tour route1, int x2, Tour route2) {
     87      int count = route1.Stops.Count - x1;
     88      List<int> segmentX1 = new List<int>();
     89      if (count > 0) {
     90        segmentX1 = route1.Stops.GetRange(x1, count);
     91        route1.Stops.RemoveRange(x1, count);
     92      }
     93      count = route2.Stops.Count - x2;
     94      List<int> segmentX2 = new List<int>();
     95      if (count > 0) {
     96        segmentX2 = route2.Stops.GetRange(x2, count);
     97        route2.Stops.RemoveRange(x2, count);
     98      }
     99      route1.Stops.AddRange(segmentX2);
     100      route2.Stops.AddRange(segmentX1);
    114101    }
    115102
Note: See TracChangeset for help on using the changeset viewer.