Free cookie consent management tool by TermsFeed Policy Generator

source: branches/VRP/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Alba/Manipulators/AlbaIntraRouteInversionManipulator.cs @ 4346

Last change on this file since 4346 was 4346, checked in by svonolfe, 14 years ago

Renamed operators, added comments according to code review (#1039)

File size: 3.3 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;
28using System.Collections.Generic;
29
30namespace HeuristicLab.Problems.VehicleRouting.Encodings.Alba {
31  [Item("AlbaIntraRouteInversionManipulator", "An operator which applies the SLS operation to a VRP representation. It is implemented as described in Alba, E. and Dorronsoro, B. (2004). Solving the Vehicle Routing Problem by Using Cellular Genetic Algorithms.")]
32  [StorableClass]
33  public sealed class AlbaIntraRouteInversionManipulator : AlbaManipulator {   
34    [StorableConstructor]
35    private AlbaIntraRouteInversionManipulator(bool deserializing) : base(deserializing) { }
36
37    public AlbaIntraRouteInversionManipulator()
38      : base() {
39     }
40
41    public static void Apply(AlbaEncoding individual, int index1, int index2) {
42      if (index1 != -1 && index2 != -1) {
43        int breakPoint1 = index1 + 1;
44        int breakPoint2 = index2;
45        for (int i = 0; i <= (breakPoint2 - breakPoint1) / 2; i++) {  // invert permutation between breakpoints
46          int temp = individual[breakPoint1 + i];
47          individual[breakPoint1 + i] = individual[breakPoint2 - i];
48          individual[breakPoint2 - i] = temp;
49        }
50      }
51    }
52
53    protected override void Manipulate(IRandom rand, AlbaEncoding individual) {
54      int index1 = -1;
55      int index2 = -1;
56
57      List<Tour> validTours = new List<Tour>();
58      foreach (Tour tour in individual.GetTours()) {
59        if (tour.Cities.Count >= 4)
60          validTours.Add(tour);
61      }
62
63      if (validTours.Count > 0) {
64        Tour chosenTour = validTours[rand.Next(validTours.Count)];
65        int currentTourStart = -1;
66        for (int i = 0; i < individual.Length; i++) {
67          if (individual[i] + 1 == chosenTour.Cities[0]) {
68            currentTourStart = i;
69            break;
70          }
71        }
72
73        int currentTourEnd = currentTourStart;
74        while (currentTourEnd < individual.Length &&
75          individual[currentTourEnd] < individual.Cities) {
76          currentTourEnd++;
77        }
78
79        int tourLength = currentTourEnd - currentTourStart;
80        int a = rand.Next(tourLength - 3);
81        index1 = currentTourStart + a;
82        index2 = currentTourStart + rand.Next(a + 2, tourLength - 1);
83      }
84
85      Apply(individual, index1, index2);
86    }
87  }
88}
Note: See TracBrowser for help on using the repository browser.