source: branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Prins/Manipulators/PrinsLSManipulator.cs @ 7855

Last change on this file since 7855 was 7855, checked in by svonolfe, 7 years ago

Deactivated LS manipulators by default (#1177)

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