Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Potvin/Crossovers/PotvinInsertionBasedCrossover.cs @ 6491

Last change on this file since 6491 was 6491, checked in by svonolfe, 12 years ago

Fixed compiler warnings (#1561)

File size: 10.5 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2011 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using HeuristicLab.Common;
23using HeuristicLab.Core;
24using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
25using System.Collections.Generic;
26using HeuristicLab.Data;
27using System;
28using HeuristicLab.Parameters;
29
30namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
31  [Item("PotvinInsertionBasedCrossover", "The IBX crossover for VRP representations. It is implemented as described in Berger, J and Solois, M and Begin, R (1998). A hybrid genetic algorithm for the vehicle routing problem with time windows. LNCS 1418. Springer, London 114-127.")]
32  [StorableClass]
33  public sealed class PotvinInsertionBasedCrossover : PotvinCrossover {
34    public IValueParameter<IntValue> Length {
35      get { return (IValueParameter<IntValue>)Parameters["Length"]; }
36    }
37
38    [StorableConstructor]
39    private PotvinInsertionBasedCrossover(bool deserializing) : base(deserializing) { }
40    private PotvinInsertionBasedCrossover(PotvinInsertionBasedCrossover original, Cloner cloner)
41      : base(original, cloner) {
42    }
43    public override IDeepCloneable Clone(Cloner cloner) {
44      return new PotvinInsertionBasedCrossover(this, cloner);
45    }
46    public PotvinInsertionBasedCrossover()
47      : base() {
48      Parameters.Add(new ValueParameter<IntValue>("Length", "The maximum length of the replaced route.", new IntValue(1)));
49    }
50
51    private static int SelectRandomTourBiasedByLength(IRandom random, PotvinEncoding individual) {
52      int tourIndex = -1;
53
54      double sum = 0.0;
55      double[] probabilities = new double[individual.Tours.Count];
56      for (int i = 0; i < individual.Tours.Count; i++) {
57        probabilities[i] = 1.0 / ((double)individual.Tours[i].Cities.Count / (double)individual.Cities);
58        sum += probabilities[i];
59      }
60
61      for (int i = 0; i < probabilities.Length; i++)
62        probabilities[i] = probabilities[i] / sum;
63
64      double rand = random.NextDouble();
65      double cumulatedProbabilities = 0.0;
66      int index = 0;
67      while (tourIndex == -1 && index < probabilities.Length) {
68        if (cumulatedProbabilities <= rand && rand <= cumulatedProbabilities + probabilities[index])
69          tourIndex = index;
70
71        cumulatedProbabilities += probabilities[index];
72        index++;
73      }
74
75      return tourIndex;
76    }
77
78    private double CalculateCentroidDistance(Tour t1, Tour t2, DoubleMatrix coordinates) {
79      double xSum = 0;
80      double ySum = 0;
81      double c1X, c1Y, c2X, c2Y;
82
83      for (int i = 0; i < t1.Cities.Count; i++) {
84        xSum += coordinates[t1.Cities[i], 0];
85        ySum += coordinates[t1.Cities[i], 0];
86      }
87      c1X = xSum / t1.Cities.Count;
88      c1Y = ySum / t1.Cities.Count;
89
90      for (int i = 0; i < t2.Cities.Count; i++) {
91        xSum += coordinates[t2.Cities[i], 0];
92        ySum += coordinates[t2.Cities[i], 0];
93      }
94      c2X = xSum / t1.Cities.Count;
95      c2Y = ySum / t1.Cities.Count;
96
97      return Math.Sqrt(
98            Math.Pow(c1X - c2X, 2) +
99            Math.Pow(c1Y - c2Y, 2));
100    }
101
102    private double CalculateMeanCentroidDistance(Tour t1, IList<Tour> tours, DoubleMatrix coordinates) {
103      double sum = 0;
104
105      for (int i = 0; i < tours.Count; i++) {
106        sum += CalculateCentroidDistance(t1, tours[i], coordinates);
107      }
108
109      return sum / tours.Count;
110    }
111
112    private int SelectCityBiasedByNeighborDistance(IRandom random, Tour tour, DistanceMatrix distMatrix) {
113      int cityIndex = -1;
114
115      double sum = 0.0;
116      double[] probabilities = new double[tour.Cities.Count];
117      for (int i = 0; i < tour.Cities.Count; i++) {
118        int next = i + 1;
119        if (next >= tour.Cities.Count)
120          next = 0;
121        else
122          next = tour.Cities[next];
123        double distance = VRPUtilities.GetDistance(
124          tour.Cities[i], next, distMatrix);
125
126        int prev = i - 1;
127        if (prev < 0)
128          prev = 0;
129        else
130          prev = tour.Cities[prev];
131        distance += VRPUtilities.GetDistance(
132          tour.Cities[i], prev, distMatrix);
133
134        probabilities[i] = distance;
135        sum += probabilities[i];
136      }
137
138      for (int i = 0; i < probabilities.Length; i++)
139        probabilities[i] = probabilities[i] / sum;
140
141      double rand = random.NextDouble();
142      double cumulatedProbabilities = 0.0;
143      int index = 0;
144      while (cityIndex == -1 && index < probabilities.Length) {
145        if (cumulatedProbabilities <= rand && rand <= cumulatedProbabilities + probabilities[index])
146          cityIndex = index;
147
148        cumulatedProbabilities += probabilities[index];
149        index++;
150      }
151
152      return cityIndex;
153    }
154
155    private bool FindRouteInsertionPlace(
156      Tour tour,
157      DoubleArray dueTimeArray,
158      DoubleArray serviceTimeArray, DoubleArray readyTimeArray, DoubleArray demandArray, DoubleValue capacity,
159      DistanceMatrix distMatrix, int city, bool allowInfeasible, out int place) {
160      place = -1;
161      bool bestFeasible = false;
162      double minDetour = 0;
163
164      for (int i = 0; i <= tour.Cities.Count; i++) {
165        double length = tour.GetLength(distMatrix);
166
167        tour.Cities.Insert(i, city);
168
169        bool feasible = tour.Feasible(dueTimeArray, serviceTimeArray, readyTimeArray, demandArray,
170          capacity, distMatrix);
171
172        if ((!allowInfeasible && feasible) || (allowInfeasible && (!bestFeasible || feasible))) {
173          double newLength = tour.GetLength(distMatrix);
174          double detour = newLength - length;
175
176          if (place <= 0 || detour < minDetour ||
177                (allowInfeasible && ((!(bestFeasible && !feasible)) && detour < minDetour || (feasible && !bestFeasible)))) {
178            place = i;
179            minDetour = detour;
180
181            if (feasible)
182              bestFeasible = true;
183          }
184        }
185
186        tour.Cities.RemoveAt(i);
187      }
188
189      return place >= 0;
190    }
191
192    protected override PotvinEncoding Crossover(IRandom random, PotvinEncoding parent1, PotvinEncoding parent2) {
193      PotvinEncoding child = new PotvinEncoding();
194
195      BoolValue useDistanceMatrix = UseDistanceMatrixParameter.ActualValue;
196      DoubleMatrix coordinates = CoordinatesParameter.ActualValue;
197      DistanceMatrix distMatrix = VRPUtilities.GetDistanceMatrix(coordinates, DistanceMatrixParameter, useDistanceMatrix);
198      DoubleArray dueTime = DueTimeParameter.ActualValue;
199      DoubleArray readyTime = ReadyTimeParameter.ActualValue;
200      DoubleArray serviceTime = ServiceTimeParameter.ActualValue;
201      DoubleArray demand = DemandParameter.ActualValue;
202      DoubleValue capacity = CapacityParameter.ActualValue;
203
204      bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
205
206      List<Tour> R1 = new List<Tour>();
207      PotvinEncoding p1Clone = parent1.Clone() as PotvinEncoding;
208
209      int length = Math.Min(Length.Value.Value, parent1.Tours.Count) + 1;
210      int k = random.Next(1, length);
211      for (int i = 0; i < k; i++) {
212        int index = SelectRandomTourBiasedByLength(random, p1Clone);
213        R1.Add(p1Clone.Tours[index]);
214        p1Clone.Tours.RemoveAt(index);
215      }
216
217      foreach (Tour r1 in R1) {
218        List<int> R2 = new List<int>();
219
220        double r = CalculateMeanCentroidDistance(r1, parent2.Tours, coordinates);
221        foreach (Tour tour in parent2.Tours) {
222          if (CalculateCentroidDistance(r1, tour, coordinates) <= r) {
223            R2.AddRange(tour.Cities);
224          }
225        }
226
227        Tour childTour = new Tour();
228        childTour.Cities.AddRange(r1.Cities);
229
230        //DESTROY - remove cities from r1
231        int removed = random.Next(1, r1.Cities.Count + 1);
232        for (int i = 0; i < removed; i++) {
233          childTour.Cities.RemoveAt(SelectCityBiasedByNeighborDistance(random, childTour, distMatrix));
234        }
235
236        //REPAIR - add cities from R2
237        int maxCount = random.Next(1, Math.Min(5, R2.Count));
238        int count = 0;
239
240        while (count < maxCount && R2.Count != 0) {
241          PotvinEncoding newChild = child.Clone() as PotvinEncoding;
242          newChild.Tours.Add(childTour);
243
244          int index = random.Next(R2.Count);
245          int city = R2[index];
246          R2.RemoveAt(index);
247
248          int place = -1;
249          if (FindRouteInsertionPlace(childTour, dueTime, serviceTime, readyTime,
250            demand, capacity, distMatrix, city, allowInfeasible, out place)) {
251            childTour.Cities.Insert(place, city);
252
253            if (!Repair(random, child, childTour, distMatrix, dueTime, readyTime, serviceTime, demand, capacity, allowInfeasible)) {
254              childTour.Cities.RemoveAt(place);
255            } else {
256              count++;
257            }
258          }
259        }
260
261        child.Tours.Add(childTour);
262        Repair(random, child, childTour, distMatrix, dueTime, readyTime, serviceTime, demand, capacity, allowInfeasible);
263      }
264
265      for (int i = 0; i < p1Clone.Tours.Count; i++) {
266        Tour childTour = p1Clone.Tours[i].Clone() as Tour;
267        child.Tours.Add(childTour);
268        Repair(random, child, childTour, distMatrix, dueTime, readyTime, serviceTime, demand, capacity, allowInfeasible);
269      }
270
271      //route unrouted customers
272      for (int i = 1; i <= parent1.Cities; i++) {
273        if (FindRoute(child, i) == null)
274          child.Unrouted.Add(i);
275      }
276
277      bool success = true;
278      if (!RouteUnrouted(child, distMatrix, dueTime, readyTime, serviceTime, demand, capacity, allowInfeasible)) {
279        success = false;
280      }
281
282      if (success || allowInfeasible)
283        return child;
284      else {
285        if (random.NextDouble() < 0.5)
286          return parent1.Clone() as PotvinEncoding;
287        else
288          return parent2.Clone() as PotvinEncoding;
289      }
290    }
291  }
292}
Note: See TracBrowser for help on using the repository browser.