Free cookie consent management tool by TermsFeed Policy Generator

source: branches/PersistenceSpeedUp/HeuristicLab.Problems.VehicleRouting/3.3/ShakingOperators/VehicleRoutingShakingOperator.cs @ 14728

Last change on this file since 14728 was 6042, checked in by abeham, 14 years ago

#1425

  • Changed LocalImprovementOperators
    • Changed interface (made Problem a property, added a property that denotes the type of the problem that it can be applied on, added some general parameters)
    • Added some parameters and wiring
    • Changed move discovery and parameterization and added a helper class to ease finding compatible move operators
    • Discovering only IMultiMoveOperators and IExhaustiveMoveOperators and putting the multi move ones first
    • Fixed bug in Apply method that could create an endless string of nested execution contexts
    • Removed all problem specific analyzers in the two local improvement operators and only left the BestAverageWorstQualityAnalyzer since it doesn't make any sense to perform diversity or allele analysis during local improvement in the most common case and those analyzers take a lot of time (one can always add them manually should he/she be interested). The analyzers in the VNS's Analyzer parameter are left untouched.
  • Removed shaking operator and interface from VNS plugin and added that to Optimization and Optimization.Operators
  • Changed some ValueParameters to ConstrainedValueParameters and added type discovery to fill them (using the ProblemType property to get compatible local improvement operators)
  • Added missing GPL license headers
  • Changed some ValueParameters to the new FixedValueParameters
  • Added an additional encoding specific ShakingOperator to each encoding and added that to each problem
    • reason is that only the problem/encoding can really decide if a shaking operator is meaningful or not
  • Fixed an unrelated bug in the BestAverageWorstQualityAnalyzer that I encountered (and made the fix backwards compatible)
    • Also added a snippet for creating the backwards compatible comment marker and region
  • Fixed the operator graph of the VNS main loop
    • The condition to continue only when the local search was not successful is not necessary and is not part of the VNS definition as far as I know it (only condition to break the inner loop is when k reaches k_max)
  • Changed the ShakingOperator to input current index and output the maximum number of neighborhoods instead of a boolean that indicates that the last index has been reached since the maximum number is a little more generally useful and equally powerful in modeling
    • Remodeled the VNS main loop to check for k < k_max in order to continue the inner loop
  • other changes that I forgot...

Still necessary

  • test, test, test
  • check for backwards compatible breakers
  • add a maximum evaluated solutions stop criterion
  • optionally: implement fast problem specific local search improvement operators that do not build on the whole generic overhead (e.g. a 2-opt TSP specific local search operator). The idea of VNS is really to converge to a local optimum which is difficult to achieve using the current rather limited termination options
File size: 7.2 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2011 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 System.Linq;
24using HeuristicLab.Collections;
25using HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Data;
28using HeuristicLab.Optimization;
29using HeuristicLab.Optimization.Operators;
30using HeuristicLab.Parameters;
31using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
32using HeuristicLab.PluginInfrastructure;
33using HeuristicLab.Problems.VehicleRouting.Encodings.General;
34
35namespace HeuristicLab.Problems.VehicleRouting {
36  [Item("VRPShakingOperator", "A shaking operator for VNS that applies available mutation operators.")]
37  [StorableClass]
38  public class VehicleRoutingShakingOperator : ShakingOperator<IVRPManipulator>, IVRPMultiNeighborhoodShakingOperator, IStochasticOperator {
39    #region Parameters
40    public ILookupParameter<IVRPEncoding> VRPToursParameter {
41      get { return (ILookupParameter<IVRPEncoding>)Parameters["VRPTours"]; }
42    }
43
44    public ILookupParameter<IRandom> RandomParameter {
45      get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
46    }
47
48    public ILookupParameter<DoubleMatrix> CoordinatesParameter {
49      get { return (ILookupParameter<DoubleMatrix>)Parameters["Coordinates"]; }
50    }
51
52    public int Cities {
53      get {
54        if (CoordinatesParameter.ActualValue != null)
55          return CoordinatesParameter.ActualValue.Rows;
56        else return 0;
57      }
58    }
59
60    public ILookupParameter<DoubleMatrix> DistanceMatrixParameter {
61      get { return (ILookupParameter<DoubleMatrix>)Parameters["DistanceMatrix"]; }
62    }
63
64    public ILookupParameter<BoolValue> UseDistanceMatrixParameter {
65      get { return (ILookupParameter<BoolValue>)Parameters["UseDistanceMatrix"]; }
66    }
67
68    public ILookupParameter<IntValue> VehiclesParameter {
69      get { return (ILookupParameter<IntValue>)Parameters["Vehicles"]; }
70    }
71
72    public ILookupParameter<DoubleValue> CapacityParameter {
73      get { return (ILookupParameter<DoubleValue>)Parameters["Capacity"]; }
74    }
75
76    public ILookupParameter<DoubleArray> DemandParameter {
77      get { return (ILookupParameter<DoubleArray>)Parameters["Demand"]; }
78    }
79
80    public ILookupParameter<DoubleArray> ReadyTimeParameter {
81      get { return (ILookupParameter<DoubleArray>)Parameters["ReadyTime"]; }
82    }
83
84    public ILookupParameter<DoubleArray> DueTimeParameter {
85      get { return (ILookupParameter<DoubleArray>)Parameters["DueTime"]; }
86    }
87
88    public ILookupParameter<DoubleArray> ServiceTimeParameter {
89      get { return (ILookupParameter<DoubleArray>)Parameters["ServiceTime"]; }
90    }
91    #endregion
92
93    [StorableConstructor]
94    protected VehicleRoutingShakingOperator(bool deserializing) : base(deserializing) { }
95    protected VehicleRoutingShakingOperator(VehicleRoutingShakingOperator original, Cloner cloner) : base(original, cloner) { }
96    public override IDeepCloneable Clone(Cloner cloner) {
97      return new VehicleRoutingShakingOperator(this, cloner);
98    }
99    public VehicleRoutingShakingOperator()
100      : base() {
101      Parameters.Add(new LookupParameter<IVRPEncoding>("VRPTours", "The vrp tour encoding to shake."));
102      Parameters.Add(new LookupParameter<IRandom>("Random", "The random number generator that will be used for stochastic shaking operators."));
103      Parameters.Add(new LookupParameter<DoubleMatrix>("Coordinates", "The coordinates of the cities."));
104      Parameters.Add(new LookupParameter<DoubleMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
105      Parameters.Add(new LookupParameter<BoolValue>("UseDistanceMatrix", "True if a distance matrix should be calculated and used for evaluation, otherwise false."));
106      Parameters.Add(new LookupParameter<IntValue>("Vehicles", "The number of vehicles."));
107      Parameters.Add(new LookupParameter<DoubleValue>("Capacity", "The capacity of each vehicle."));
108      Parameters.Add(new LookupParameter<DoubleArray>("Demand", "The demand of each customer."));
109      Parameters.Add(new LookupParameter<DoubleArray>("ReadyTime", "The ready time of each customer."));
110      Parameters.Add(new LookupParameter<DoubleArray>("DueTime", "The due time of each customer."));
111      Parameters.Add(new LookupParameter<DoubleArray>("ServiceTime", "The service time of each customer."));
112
113      foreach (IVRPManipulator shaker in ApplicationManager.Manager.GetInstances<IVRPManipulator>().OrderBy(x => x.Name))
114        if (!(shaker is MultiVRPSolutionManipulator)) Operators.Add(shaker);
115    }
116
117    #region Wiring of some parameters
118    protected override void Operators_ItemsAdded(object sender, CollectionItemsChangedEventArgs<IndexedItem<IVRPManipulator>> e) {
119      base.Operators_ItemsAdded(sender, e);
120      ParameterizeOperators(e.Items);
121    }
122
123    protected override void Operators_ItemsReplaced(object sender, CollectionItemsChangedEventArgs<IndexedItem<IVRPManipulator>> e) {
124      base.Operators_ItemsReplaced(sender, e);
125      ParameterizeOperators(e.Items);
126    }
127
128    private void ParameterizeOperators(IEnumerable<IndexedItem<IVRPManipulator>> items) {
129      if (items.Any()) {
130        foreach (IStochasticOperator op in items.Select(x => x.Value).OfType<IStochasticOperator>())
131          op.RandomParameter.ActualName = RandomParameter.Name;
132        foreach (IVRPManipulator op in items.Select(x => x.Value).OfType<IVRPManipulator>()) {
133          op.VRPToursParameter.ActualName = VRPToursParameter.Name;
134          if (op.CoordinatesParameter != null) op.CoordinatesParameter.ActualName = CoordinatesParameter.Name;
135          if (op.DistanceMatrixParameter != null) op.DistanceMatrixParameter.ActualName = DistanceMatrixParameter.Name;
136          if (op.UseDistanceMatrixParameter != null) op.UseDistanceMatrixParameter.ActualName = UseDistanceMatrixParameter.Name;
137          if (op.VehiclesParameter != null) op.VehiclesParameter.ActualName = VehiclesParameter.Name;
138          if (op.CapacityParameter != null) op.CapacityParameter.ActualName = CapacityParameter.Name;
139          if (op.DemandParameter != null) op.DemandParameter.ActualName = DemandParameter.Name;
140          if (op.ReadyTimeParameter != null) op.ReadyTimeParameter.ActualName = ReadyTimeParameter.Name;
141          if (op.DueTimeParameter != null) op.DueTimeParameter.ActualName = DueTimeParameter.Name;
142          if (op.ServiceTimeParameter != null) op.ServiceTimeParameter.ActualName = ServiceTimeParameter.Name;
143        }
144      }
145    }
146    #endregion
147  }
148}
Note: See TracBrowser for help on using the repository browser.