Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Potvin/Manipulators/PotvinManipulator.cs @ 4179

Last change on this file since 4179 was 4179, checked in by svonolfe, 12 years ago

Refactored VRP based on the code review (#1039)

File size: 3.7 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 HeuristicLab.Optimization;
28
29namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
30  [Item("PotvinManipulator", "A VRP manipulation operation on a Potvin encoding.")]
31  [StorableClass]
32  public abstract class PotvinManipulator : VRPManipulator, IStochasticOperator {
33    public ILookupParameter<IRandom> RandomParameter {
34      get { return (LookupParameter<IRandom>)Parameters["Random"]; }
35    }
36
37    [StorableConstructor]
38    protected PotvinManipulator(bool deserializing) : base(deserializing) { }
39
40    public PotvinManipulator() {
41      Parameters.Add(new LookupParameter<IRandom>("Random", "The pseudo random number generator which should be used for stochastic manipulation operators."));
42    }
43
44    protected abstract void Manipulate(IRandom random, PotvinEncoding individual);
45
46    protected int SelectRandomTourBiasedByLength(IRandom random, PotvinEncoding individual) {
47      int tourIndex = -1;
48
49      double sum = 0.0;
50      double[] probabilities = new double[individual.Tours.Count];
51      for (int i = 0; i < individual.Tours.Count; i++) {
52        probabilities[i] = 1.0 / ((double)individual.Tours[i].Cities.Count / (double)Cities);
53        sum += probabilities[i];
54      }
55
56      for (int i = 0; i < probabilities.Length; i++)
57        probabilities[i] = probabilities[i] / sum;
58
59      double rand = random.NextDouble();
60      double cumulatedProbabilities = 0.0;
61      int index = 0;
62      while (tourIndex == -1 && index < probabilities.Length) {
63        if (cumulatedProbabilities <= rand && rand <= cumulatedProbabilities + probabilities[index])
64          tourIndex = index;
65
66        cumulatedProbabilities += probabilities[index];
67        index++;
68      }
69
70      return tourIndex;
71    }
72
73    protected bool FindInsertionPlace(PotvinEncoding individual, int city, int routeToAvoid, out int route, out int place) {
74      return individual.FindInsertionPlace(
75        DueTimeParameter.ActualValue, ServiceTimeParameter.ActualValue, ReadyTimeParameter.ActualValue,
76        DemandParameter.ActualValue, CapacityParameter.ActualValue, CoordinatesParameter.ActualValue,
77        DistanceMatrixParameter, UseDistanceMatrixParameter.ActualValue,
78        city, routeToAvoid, out route, out place);
79    }
80   
81    public override IOperation Apply() {
82      IVRPEncoding solution = VRPToursParameter.ActualValue;
83      if (!(solution is PotvinEncoding)) {
84        VRPToursParameter.ActualValue = PotvinEncoding.ConvertFrom(solution);
85      }
86     
87      Manipulate(RandomParameter.ActualValue, VRPToursParameter.ActualValue as PotvinEncoding);
88
89      return base.Apply();
90    }
91  }
92}
Note: See TracBrowser for help on using the repository browser.