Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Prins/Manipulators/PrinsLSManipulator.cs @ 11246

Last change on this file since 11246 was 11171, checked in by ascheibe, 10 years ago

#2115 merged r11170 (copyright update) into trunk

File size: 13.0 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2014 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 System.Collections.Generic;
23using HeuristicLab.Common;
24using HeuristicLab.Core;
25using HeuristicLab.Data;
26using HeuristicLab.Parameters;
27using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
28using HeuristicLab.Problems.VehicleRouting.Interfaces;
29
30namespace HeuristicLab.Problems.VehicleRouting.Encodings.Prins {
31  [Item("PrinsLSManipulator", "An operator which manipulates a VRP representation by using the Prins local search.  It is implemented as described in Prins, C. (2004). A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & Operations Research, 12:1985-2002.")]
32  [StorableClass]
33  public abstract class PrinsLSManipulator : PrinsManipulator, IVRPLocalSearchManipulator {
34    public IValueParameter<IntValue> Iterations {
35      get { return (IValueParameter<IntValue>)Parameters["Iterations"]; }
36    }
37
38    [StorableConstructor]
39    protected PrinsLSManipulator(bool deserializing) : base(deserializing) { }
40
41    public PrinsLSManipulator()
42      : base() {
43      Parameters.Add(new ValueParameter<IntValue>("Iterations", "The number of max iterations.", new IntValue(5)));
44    }
45
46    protected PrinsLSManipulator(PrinsLSManipulator original, Cloner cloner)
47      : base(original, cloner) {
48    }
49
50    protected double GetQuality(PrinsEncoding individual) {
51      return ProblemInstance.Evaluate(individual).Quality;
52    }
53
54    private int FindCity(PrinsEncoding individual, int city) {
55      int index = -1;
56
57      int i = 0;
58      while (i < individual.Length && index == -1) {
59        if (individual[i] == city)
60          index = i;
61
62        i++;
63      }
64
65      return index;
66    }
67
68    protected const int depot = -1;
69
70    private Tour FindTour(PrinsEncoding individual, int city) {
71      Tour found = null;
72
73      List<Tour> tours = individual.GetTours();
74      int i = 0;
75
76      while (found == null && i < tours.Count) {
77        if (tours[i].Stops.Contains(city))
78          found = tours[i];
79
80        i++;
81      }
82
83      return found;
84    }
85
86    //inserts u after v in the child
87    private void InsertAfter(int u, int v, PrinsEncoding parent, PrinsEncoding child) {
88      int pi = 0;
89      int ci = 0;
90
91      while (ci != child.Length) {
92        if (parent[pi] != u) {
93          child[ci] = parent[pi];
94          ci++;
95        }
96        if (parent[pi] == v) {
97          child[ci] = u;
98          ci++;
99        }
100
101        pi++;
102      }
103    }
104
105    //inserts (u, x) after v in the child
106    private void InsertAfter(int u, int x, int v, PrinsEncoding parent, PrinsEncoding child) {
107      int pi = 0;
108      int ci = 0;
109
110      while (ci != child.Length) {
111        if (parent[pi] != u && parent[pi] != x) {
112          child[ci] = parent[pi];
113          ci++;
114        }
115        if (parent[pi] == v) {
116          child[ci] = u;
117          ci++;
118
119          child[ci] = x;
120          ci++;
121        }
122
123        pi++;
124      }
125    }
126
127    //inserts u before v in the child
128    private void InsertBefore(int u, int v, PrinsEncoding parent, PrinsEncoding child) {
129      int pi = 0;
130      int ci = 0;
131
132      while (ci != child.Length) {
133        if (parent[pi] == v) {
134          child[ci] = u;
135          ci++;
136        }
137        if (parent[pi] != u) {
138          child[ci] = parent[pi];
139          ci++;
140        }
141
142        pi++;
143      }
144    }
145
146    //inserts (u, x) before v in the child
147    private void InsertBefore(int u, int x, int v, PrinsEncoding parent, PrinsEncoding child) {
148      int pi = 0;
149      int ci = 0;
150
151      while (ci != child.Length) {
152        if (parent[pi] == v) {
153          child[ci] = u;
154          ci++;
155
156          child[ci] = x;
157          ci++;
158        }
159        if (parent[pi] != u && parent[pi] != x) {
160          child[ci] = parent[pi];
161          ci++;
162        }
163
164        pi++;
165      }
166    }
167
168    //swaps u and v
169    private void Swap(int u, int v, PrinsEncoding parent, PrinsEncoding child) {
170      for (int i = 0; i < child.Length; i++) {
171        if (parent[i] == u)
172          child[i] = v;
173        else if (parent[i] == v)
174          child[i] = u;
175        else
176          child[i] = parent[i];
177      }
178    }
179
180    //swaps (u, x) and v
181    private void Swap(int u, int x, int v, PrinsEncoding parent, PrinsEncoding child) {
182      int childIndex = 0;
183      int parentIndex = 0;
184
185      while (childIndex < child.Length) {
186        if (parent[parentIndex] == u) {
187          child[childIndex] = v;
188          parentIndex++;
189        } else if (parent[parentIndex] == v) {
190          child[childIndex] = u;
191          childIndex++;
192          child[childIndex] = x;
193        } else {
194          child[childIndex] = parent[parentIndex];
195        }
196
197        childIndex++;
198        parentIndex++;
199      }
200    }
201
202    //swaps (u, x) and (v, y)
203    private void Swap(int u, int x, int v, int y, PrinsEncoding parent, PrinsEncoding child) {
204      int i = 0;
205
206      while (i < child.Length) {
207        if (child[i] == u) {
208          child[i] = v;
209          i++;
210          child[i] = y;
211        } else if (child[i] == v) {
212          child[i] = u;
213          i++;
214          child[i] = x;
215        } else {
216          child[i] = parent[i];
217        }
218
219        i++;
220      }
221    }
222
223    //swaps (u, x) and (v, y) by (u, y) and (x, v)
224    private void Swap2(int u, int x, int v, int y, PrinsEncoding parent, PrinsEncoding child) {
225      int i = 0;
226
227      while (i < child.Length) {
228        if (parent[i] == x) {
229          child[i] = y;
230        } else if (parent[i] == v) {
231          child[i] = x;
232        } else if (parent[i] == y) {
233          child[i] = v;
234        } else {
235          child[i] = parent[i];
236        }
237
238        i++;
239      }
240    }
241
242    private void M1(PrinsEncoding parent, PrinsEncoding child, int u, int v) {
243      if (u != depot) {
244        if (v == depot) {
245          Tour tour = FindTour(child, u + 1);
246          v = tour.Stops[0] - 1;
247          InsertBefore(u, v, parent, child);
248        } else {
249          InsertAfter(u, v, parent, child);
250        }
251      }
252    }
253
254    private void M2(PrinsEncoding parent, PrinsEncoding child, int u, int v) {
255      if (u != depot) {
256        Tour tour = FindTour(child, u + 1);
257        int iu = tour.Stops.IndexOf(u + 1);
258        if (iu < tour.Stops.Count - 1) {
259          int x = tour.Stops[iu + 1] - 1;
260
261          if (v == depot) {
262            tour = FindTour(child, u + 1);
263            v = tour.Stops[0] - 1;
264            InsertBefore(u, x, v, parent, child);
265          } else {
266            InsertAfter(u, x, v, parent, child);
267          }
268        }
269      }
270    }
271
272    private void M3(PrinsEncoding parent, PrinsEncoding child, int u, int v) {
273      if (u != depot) {
274        Tour tour = FindTour(child, u + 1);
275        int iu = tour.Stops.IndexOf(u + 1);
276        if (iu < tour.Stops.Count - 1) {
277          int x = tour.Stops[iu + 1] - 1;
278
279          if (v == depot) {
280            tour = FindTour(child, u + 1);
281            v = tour.Stops[0] - 1;
282            InsertBefore(x, u, v, parent, child);
283          } else {
284            InsertAfter(x, u, v, parent, child);
285          }
286        }
287      }
288    }
289
290    private void M4(PrinsEncoding parent, PrinsEncoding child, int u, int v) {
291      if (u != depot && v != depot) {
292        Swap(u, v, parent, child);
293      }
294    }
295
296    private void M5(PrinsEncoding parent, PrinsEncoding child, int u, int v) {
297      if (u != depot && v != depot) {
298        Tour tour = FindTour(child, u + 1);
299        int iu = tour.Stops.IndexOf(u + 1);
300        if (iu < tour.Stops.Count - 1) {
301          int x = tour.Stops[iu + 1] - 1;
302
303          if (x != v)
304            Swap(u, x, v, parent, child);
305        }
306      }
307    }
308
309    private void M6(PrinsEncoding parent, PrinsEncoding child, int u, int v) {
310      if (u != depot && v != depot) {
311        Tour tour = FindTour(child, u + 1);
312        int iu = tour.Stops.IndexOf(u + 1);
313        if (iu < tour.Stops.Count - 1) {
314          int x = tour.Stops[iu + 1] - 1;
315
316          tour = FindTour(child, v + 1);
317          int iv = tour.Stops.IndexOf(v + 1);
318          if (iv < tour.Stops.Count - 1) {
319            int y = tour.Stops[iv + 1] - 1;
320
321            if (x != v && y != u)
322              Swap(u, x, v, y, parent, child);
323          }
324        }
325      }
326    }
327
328    private void M7(PrinsEncoding parent, PrinsEncoding child, int u, int v) {
329      if (u != depot && v != depot) {
330        Tour tu = FindTour(child, u + 1);
331        Tour tv = FindTour(child, v + 1);
332
333        if (tu.Stops[0] == tv.Stops[0]) {
334          int iu = tu.Stops.IndexOf(u + 1);
335          if (iu < tu.Stops.Count - 1) {
336            int x = tu.Stops[iu + 1] - 1;
337
338            int iv = tv.Stops.IndexOf(v + 1);
339            if (iv < tv.Stops.Count - 1) {
340              int y = tv.Stops[iv + 1] - 1;
341
342              if (x != v && y != u)
343                Swap(x, v, parent, child);
344            }
345          }
346        }
347      }
348    }
349
350    private void M8(PrinsEncoding parent, PrinsEncoding child, int u, int v) {
351      if (u != depot && v != depot) {
352        Tour tu = FindTour(child, u + 1);
353        Tour tv = FindTour(child, v + 1);
354
355        if (tu.Stops[0] != tv.Stops[0]) {
356          int iu = tu.Stops.IndexOf(u + 1);
357          if (iu < tu.Stops.Count - 1) {
358            int x = tu.Stops[iu + 1] - 1;
359
360            int iv = tv.Stops.IndexOf(v + 1);
361            if (iv < tv.Stops.Count - 1) {
362              int y = tv.Stops[iv + 1] - 1;
363
364              if (x != v && y != u)
365                Swap(x, v, parent, child);
366            }
367          }
368        }
369      }
370    }
371
372    private void M9(PrinsEncoding parent, PrinsEncoding child, int u, int v) {
373      if (u != depot && v != depot) {
374        Tour tu = FindTour(child, u + 1);
375        Tour tv = FindTour(child, v + 1);
376
377        if (tu.Stops[0] != tv.Stops[0]) {
378          int iu = tu.Stops.IndexOf(u + 1);
379          if (iu < tu.Stops.Count - 1) {
380            int x = tu.Stops[iu + 1] - 1;
381
382            int iv = tv.Stops.IndexOf(v + 1);
383            if (iv < tv.Stops.Count - 1) {
384              int y = tv.Stops[iv + 1] - 1;
385
386              if (x != v && y != u)
387                Swap2(u, x, v, y, parent, child);
388            }
389          }
390        }
391      }
392    }
393
394    protected PrinsEncoding Manipulate(PrinsEncoding individual,
395      double originalQuality, int u, int v) {
396      PrinsEncoding child = null;
397      bool improvement = false;
398
399      if (u != v) {
400        child = individual.Clone() as PrinsEncoding;
401        M1(individual, child, u, v);
402        improvement = GetQuality(child) < originalQuality;
403
404        if (!improvement) {
405          child = individual.Clone() as PrinsEncoding;
406          M2(individual, child, u, v);
407          improvement = GetQuality(child) < originalQuality;
408        }
409
410        if (!improvement) {
411          child = individual.Clone() as PrinsEncoding;
412          M3(individual, child, u, v);
413          improvement = GetQuality(child) < originalQuality;
414        }
415
416        if (!improvement) {
417          child = individual.Clone() as PrinsEncoding;
418          M4(individual, child, u, v);
419          improvement = GetQuality(child) < originalQuality;
420        }
421
422        if (!improvement) {
423          child = individual.Clone() as PrinsEncoding;
424          M5(individual, child, u, v);
425          improvement = GetQuality(child) < originalQuality;
426        }
427
428        if (!improvement) {
429          child = individual.Clone() as PrinsEncoding;
430          M6(individual, child, u, v);
431          improvement = GetQuality(child) < originalQuality;
432        }
433
434        if (!improvement) {
435          child = individual.Clone() as PrinsEncoding;
436          M7(individual, child, u, v);
437          improvement = GetQuality(child) < originalQuality;
438        }
439
440        if (!improvement) {
441          child = individual.Clone() as PrinsEncoding;
442          M8(individual, child, u, v);
443          improvement = GetQuality(child) < originalQuality;
444        }
445
446        if (!improvement) {
447          child = individual.Clone() as PrinsEncoding;
448          M9(individual, child, u, v);
449          improvement = GetQuality(child) < originalQuality;
450        }
451      }
452
453      if (improvement)
454        return child;
455      else
456        return null;
457    }
458  }
459}
Note: See TracBrowser for help on using the repository browser.