Free cookie consent management tool by TermsFeed Policy Generator

source: branches/PersistenceOverhaul/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Crossovers/PotvinInsertionBasedCrossover.cs @ 13368

Last change on this file since 13368 was 13368, checked in by ascheibe, 8 years ago

#2520 added guids to storable classes

File size: 9.7 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2015 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;
29using HeuristicLab.Problems.VehicleRouting.ProblemInstances;
30using HeuristicLab.Problems.VehicleRouting.Interfaces;
31
32namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
33  [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.")]
34  [StorableClass("F07D6203-DDB0-401E-A6E5-C2850EB8B5A6")]
35  public sealed class PotvinInsertionBasedCrossover : PotvinCrossover {
36    public IValueParameter<IntValue> Length {
37      get { return (IValueParameter<IntValue>)Parameters["Length"]; }
38    }
39
40    [StorableConstructor]
41    private PotvinInsertionBasedCrossover(bool deserializing) : base(deserializing) { }
42    private PotvinInsertionBasedCrossover(PotvinInsertionBasedCrossover original, Cloner cloner)
43      : base(original, cloner) {
44    }
45    public override IDeepCloneable Clone(Cloner cloner) {
46      return new PotvinInsertionBasedCrossover(this, cloner);
47    }
48    public PotvinInsertionBasedCrossover()
49      : base() {
50      Parameters.Add(new ValueParameter<IntValue>("Length", "The maximum length of the replaced route.", new IntValue(1)));
51    }
52
53    private static int SelectRandomTourBiasedByLength(IRandom random, PotvinEncoding individual) {
54      int tourIndex = -1;
55
56      double sum = 0.0;
57      double[] probabilities = new double[individual.Tours.Count];
58      for (int i = 0; i < individual.Tours.Count; i++) {
59        probabilities[i] = 1.0 / ((double)individual.Tours[i].Stops.Count / (double)individual.Cities);
60        sum += probabilities[i];
61      }
62
63      double rand = random.NextDouble() * sum;
64      double cumulatedProbabilities = 0.0;
65      int index = 0;
66      while (tourIndex == -1 && index < probabilities.Length) {
67        if (cumulatedProbabilities <= rand && rand <= cumulatedProbabilities + probabilities[index])
68          tourIndex = index;
69
70        cumulatedProbabilities += probabilities[index];
71        index++;
72      }
73
74      return tourIndex;
75    }
76
77    private double CalculateCentroidDistance(Tour t1, Tour t2, IVRPProblemInstance instance) {
78      double xSum = 0;
79      double ySum = 0;
80      double c1X, c1Y, c2X, c2Y;
81
82      for (int i = 0; i < t1.Stops.Count; i++) {
83        xSum += instance.GetCoordinates(t1.Stops[i])[0];
84        ySum += instance.GetCoordinates(t1.Stops[i])[1];
85      }
86      c1X = xSum / t1.Stops.Count;
87      c1Y = ySum / t1.Stops.Count;
88
89      for (int i = 0; i < t2.Stops.Count; i++) {
90        xSum += instance.GetCoordinates(t2.Stops[i])[0];
91        ySum += instance.GetCoordinates(t2.Stops[i])[1];
92      }
93      c2X = xSum / t1.Stops.Count;
94      c2Y = ySum / t1.Stops.Count;
95
96      return Math.Sqrt(
97           (c1X - c2X) * (c1X - c2X) +
98           (c1Y - c2Y) * (c1Y - c2Y));
99    }
100
101    private double CalculateMeanCentroidDistance(Tour t1, IList<Tour> tours, IVRPProblemInstance instance) {
102      double sum = 0;
103
104      for (int i = 0; i < tours.Count; i++) {
105        sum += CalculateCentroidDistance(t1, tours[i], instance);
106      }
107
108      return sum / tours.Count;
109    }
110
111    private int SelectCityBiasedByNeighborDistance(IRandom random, Tour tour, IVRPEncoding solution) {
112      int cityIndex = -1;
113
114      double sum = 0.0;
115      double[] probabilities = new double[tour.Stops.Count];
116      for (int i = 0; i < tour.Stops.Count; i++) {
117        int next;
118        if (i + 1 >= tour.Stops.Count)
119          next = 0;
120        else
121          next = tour.Stops[i + 1];
122        double distance = ProblemInstance.GetDistance(
123          tour.Stops[i], next, solution);
124
125        int prev;
126        if (i - 1 < 0)
127          prev = 0;
128        else
129          prev = tour.Stops[i - 1];
130        distance += ProblemInstance.GetDistance(
131          tour.Stops[i], prev, solution);
132
133        probabilities[i] = distance;
134        sum += probabilities[i];
135      }
136
137      double rand = random.NextDouble() * sum;
138      double cumulatedProbabilities = 0.0;
139      int index = 0;
140      while (cityIndex == -1 && index < probabilities.Length) {
141        if (cumulatedProbabilities <= rand && rand <= cumulatedProbabilities + probabilities[index])
142          cityIndex = index;
143
144        cumulatedProbabilities += probabilities[index];
145        index++;
146      }
147
148      return cityIndex;
149    }
150
151    private bool FindRouteInsertionPlace(
152      PotvinEncoding individual,
153      Tour tour,
154      int city, bool allowInfeasible, out int place) {
155      place = -1;
156
157      if (tour.Stops.Contains(city))
158        return false;
159
160      if (tour.Stops.Count == 0) {
161        place = 0;
162        return true;
163      }
164
165      double minDetour = 0;
166      VRPEvaluation eval = ProblemInstance.EvaluateTour(tour, individual);
167      bool originalFeasible = ProblemInstance.Feasible(eval);
168
169      for (int i = 0; i <= tour.Stops.Count; i++) {
170        bool feasible;
171        double detour = ProblemInstance.GetInsertionCosts(eval, individual, city, 0, i, out feasible);
172        if (feasible || allowInfeasible) {
173          if (place < 0 || detour < minDetour) {
174            place = i;
175            minDetour = detour;
176          }
177        }
178      }
179
180      return place >= 0;
181    }
182
183    private ICollection<int> GetUnrouted(PotvinEncoding solution, int cities) {
184      HashSet<int> undiscovered = new HashSet<int>();
185      for (int i = 1; i <= cities; i++) {
186        undiscovered.Add(i);
187      }
188
189      foreach (Tour tour in solution.Tours) {
190        foreach (int city in tour.Stops)
191          undiscovered.Remove(city);
192      }
193
194      return undiscovered;
195    }
196
197    protected override PotvinEncoding Crossover(IRandom random, PotvinEncoding parent1, PotvinEncoding parent2) {
198      PotvinEncoding child = parent1.Clone() as PotvinEncoding;
199      child.Tours.Clear();
200
201      bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
202
203      List<Tour> R1 = new List<Tour>();
204      PotvinEncoding p1Clone = parent1.Clone() as PotvinEncoding;
205
206      int length = Math.Min(Length.Value.Value, parent1.Tours.Count) + 1;
207      int k = 1;
208      if(length > 1)
209        k = random.Next(1, length);
210      for (int i = 0; i < k; i++) {
211        int index = SelectRandomTourBiasedByLength(random, p1Clone);
212        R1.Add(p1Clone.Tours[index]);
213        p1Clone.Tours.RemoveAt(index);
214      }
215
216      foreach (Tour r1 in R1) {
217        List<int> R2 = new List<int>();
218
219        double r = CalculateMeanCentroidDistance(r1, parent2.Tours, ProblemInstance);
220        foreach (Tour tour in parent2.Tours) {
221          if (CalculateCentroidDistance(r1, tour, ProblemInstance) <= r) {
222            R2.AddRange(tour.Stops);
223          }
224        }
225
226        Tour childTour = new Tour();
227        child.Tours.Add(childTour);
228        childTour.Stops.AddRange(r1.Stops);
229
230        //DESTROY - remove cities from r1
231        int removed = 1;
232        if(r1.Stops.Count > 1)
233          removed = random.Next(1, r1.Stops.Count + 1);
234        for (int i = 0; i < removed; i++) {
235          childTour.Stops.RemoveAt(SelectCityBiasedByNeighborDistance(random, childTour, child));
236        }
237
238        //REPAIR - add cities from R2
239        int maxCount = 1;
240        if(R2.Count > 1)
241          maxCount = random.Next(1, Math.Min(5, R2.Count));
242        int count = 0;
243
244        while (count < maxCount && R2.Count != 0) {
245          int index = random.Next(R2.Count);
246          int city = R2[index];
247          R2.RemoveAt(index);
248
249          int place = -1;
250          bool found = FindRouteInsertionPlace(child, childTour, city, allowInfeasible, out place);
251          if (found) {
252            childTour.Stops.Insert(place, city);
253
254            if (!Repair(random, child, childTour, ProblemInstance, allowInfeasible)) {
255              childTour.Stops.RemoveAt(place);
256            } else {
257              count++;
258            }
259          }
260        }
261
262        Repair(random, child, childTour, ProblemInstance, 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, ProblemInstance, allowInfeasible);
269      }
270
271      //route unrouted customers
272      child.Unrouted.AddRange(GetUnrouted(child, ProblemInstance.Cities.Value));
273      bool success = RouteUnrouted(child, allowInfeasible);
274
275      if (success || allowInfeasible)
276        return child;
277      else {
278        if (random.NextDouble() < 0.5)
279          return parent1.Clone() as PotvinEncoding;
280        else
281          return parent2.Clone() as PotvinEncoding;
282      }
283    }
284  }
285}
Note: See TracBrowser for help on using the repository browser.