Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/Manipulators/AlbaLambdaInterchangeManipulator.cs @ 12394

Last change on this file since 12394 was 12012, checked in by ascheibe, 10 years ago

#2212 merged r12008, r12009, r12010 back into trunk

File size: 4.6 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 System;
23using System.Collections.Generic;
24using HeuristicLab.Common;
25using HeuristicLab.Core;
26using HeuristicLab.Data;
27using HeuristicLab.Parameters;
28using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
29
30namespace HeuristicLab.Problems.VehicleRouting.Encodings.Alba {
31  [Item("AlbaLambdaInterchangeManipulator", "An operator which applies the lambda interchange 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 AlbaLambdaInterchangeManipulator : AlbaManipulator {
34    public IValueParameter<IntValue> LambdaParameter {
35      get { return (IValueParameter<IntValue>)Parameters["Lambda"]; }
36    }
37
38    [StorableConstructor]
39    private AlbaLambdaInterchangeManipulator(bool deserializing) : base(deserializing) { }
40
41    public AlbaLambdaInterchangeManipulator()
42      : base() {
43      Parameters.Add(new ValueParameter<IntValue>("Lambda", "The lambda value.", new IntValue(1)));
44    }
45
46    public override IDeepCloneable Clone(Cloner cloner) {
47      return new AlbaLambdaInterchangeManipulator(this, cloner);
48    }
49
50    private AlbaLambdaInterchangeManipulator(AlbaLambdaInterchangeManipulator original, Cloner cloner)
51      : base(original, cloner) {
52    }
53
54    public static void Apply(AlbaEncoding individual, int tour1Index, int position1, int length1,
55      int tour2Index, int position2, int length2) {
56      List<Tour> tours = individual.GetTours();
57
58      Tour tour1 = tours[tour1Index];
59      int tour1Start = -1;
60      for (int i = 0; i < individual.Length; i++) {
61        if (individual[i] == tour1.Stops[0] - 1) {
62          tour1Start = i;
63          break;
64        }
65      }
66
67      Tour tour2 = tours[tour2Index];
68      int tour2Start = -1;
69      for (int i = 0; i < individual.Length; i++) {
70        if (individual[i] == tour2.Stops[0] - 1) {
71          tour2Start = i;
72          break;
73        }
74      }
75
76      AlbaEncoding original = individual.Clone() as AlbaEncoding;
77      int index = 0;
78
79      int start1 = tour1Start + position1;
80      int end1 = start1 + length1;
81
82      int start2 = tour2Start + position2;
83      int end2 = start2 + length2;
84
85      for (int i = 0; i < original.Length; i++) {
86        if (index == start1) {
87          if (end2 - start2 == 0)
88            index = end1;
89          else
90            index = start2;
91        } else if (index == start2) {
92          if (end1 - start1 == 0)
93            index = end2;
94          else
95            index = start1;
96        } else if (index == end1) {
97          index = end2;
98        } else if (index == end2) {
99          index = end1;
100        }
101
102        individual[i] = original[index];
103
104        index++;
105      }
106    }
107
108    protected override void Manipulate(IRandom rand, AlbaEncoding individual) {
109      List<Tour> tours = individual.GetTours();
110      if (tours.Count > 1) {
111        int lambda = LambdaParameter.Value.Value;
112
113        int route1Index = rand.Next(tours.Count);
114        Tour route1 = tours[route1Index];
115
116
117        int route2Index = rand.Next(tours.Count - 1);
118        if (route2Index >= route1Index)
119          route2Index += 1;
120        Tour route2 = tours[route2Index];
121
122        int length1 = rand.Next(Math.Min(lambda + 1, route1.Stops.Count + 1));
123        int index1 = rand.Next(route1.Stops.Count - length1 + 1);
124
125        int l2Min = 0;
126        if (length1 == 0)
127          l2Min = 1;
128        int length2 = rand.Next(l2Min, Math.Min(lambda + 1, route2.Stops.Count + 1));
129        int index2 = rand.Next(route2.Stops.Count - length2 + 1);
130
131        Apply(individual, route1Index, index1, length1,
132          route2Index, index2, length2);
133      }
134    }
135  }
136}
Note: See TracBrowser for help on using the repository browser.