Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Problems.QuadraticAssignment.Algorithms/3.3/RobustTabooSeachOperator.cs @ 11141

Last change on this file since 11141 was 9456, checked in by swagner, 12 years ago

Updated copyright year and added some missing license headers (#1889)
File size: 12.1 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2013 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.Common;
23using HeuristicLab.Core;
24using HeuristicLab.Data;
25using HeuristicLab.Encodings.PermutationEncoding;
26using HeuristicLab.Operators;
27using HeuristicLab.Optimization;
28using HeuristicLab.Parameters;
29using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
30
31namespace HeuristicLab.Problems.QuadraticAssignment.Algorithms {
32  [Item("RobustTabooSearchOperator", "Performs an iteration of the robust taboo search algorithm as descrbied in Taillard 1991.")]
33  [StorableClass]
34  public sealed class RobustTabooSeachOperator : SingleSuccessorOperator, IIterationBasedOperator, IStochasticOperator {
35
36    #region Parameter Properties
37    public ILookupParameter<IntValue> IterationsParameter {
38      get { return (ILookupParameter<IntValue>)Parameters["Iterations"]; }
39    }
40    public ILookupParameter<IRandom> RandomParameter {
41      get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
42    }
43    public ILookupParameter<Permutation> PermutationParameter {
44      get { return (ILookupParameter<Permutation>)Parameters["Permutation"]; }
45    }
46    public ILookupParameter<DoubleMatrix> WeightsParameter {
47      get { return (ILookupParameter<DoubleMatrix>)Parameters["Weights"]; }
48    }
49    public ILookupParameter<DoubleMatrix> DistancesParameter {
50      get { return (ILookupParameter<DoubleMatrix>)Parameters["Distances"]; }
51    }
52    public ILookupParameter<IntMatrix> ShortTermMemoryParameter {
53      get { return (ILookupParameter<IntMatrix>)Parameters["ShortTermMemory"]; }
54    }
55    public ILookupParameter<DoubleMatrix> MoveQualityMatrixParameter {
56      get { return (ILookupParameter<DoubleMatrix>)Parameters["MoveQualityMatrix"]; }
57    }
58    public ILookupParameter<DoubleValue> QualityParameter {
59      get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }
60    }
61    public ILookupParameter<DoubleValue> BestQualityParameter {
62      get { return (ILookupParameter<DoubleValue>)Parameters["BestQuality"]; }
63    }
64    public ILookupParameter<Swap2Move> LastMoveParameter {
65      get { return (ILookupParameter<Swap2Move>)Parameters["LastMove"]; }
66    }
67    public ILookupParameter<BoolValue> UseNewTabuTenureAdaptionSchemeParameter {
68      get { return (ILookupParameter<BoolValue>)Parameters["UseNewTabuTenureAdaptionScheme"]; }
69    }
70    public ILookupParameter<ResultCollection> ResultsParameter {
71      get { return (ILookupParameter<ResultCollection>)Parameters["Results"]; }
72    }
73
74    public IValueLookupParameter<IntValue> MaximumIterationsParameter {
75      get { return (IValueLookupParameter<IntValue>)Parameters["MaximumIterations"]; }
76    }
77    public IValueLookupParameter<IntValue> MinimumTabuTenureParameter {
78      get { return (IValueLookupParameter<IntValue>)Parameters["MinimumTabuTenure"]; }
79    }
80    public IValueLookupParameter<IntValue> MaximumTabuTenureParameter {
81      get { return (IValueLookupParameter<IntValue>)Parameters["MaximumTabuTenure"]; }
82    }
83    public IValueLookupParameter<BoolValue> UseAlternativeAspirationParameter {
84      get { return (IValueLookupParameter<BoolValue>)Parameters["UseAlternativeAspiration"]; }
85    }
86    public IValueLookupParameter<IntValue> AlternativeAspirationTenureParameter {
87      get { return (IValueLookupParameter<IntValue>)Parameters["AlternativeAspirationTenure"]; }
88    }
89
90    private ILookupParameter<BoolValue> AllMovesTabuParameter {
91      get { return (ILookupParameter<BoolValue>)Parameters["AllMovesTabu"]; }
92    }
93    #endregion
94
95    [StorableConstructor]
96    private RobustTabooSeachOperator(bool deserializing) : base(deserializing) { }
97    private RobustTabooSeachOperator(RobustTabooSeachOperator original, Cloner cloner)
98      : base(original, cloner) {
99    }
100    public RobustTabooSeachOperator() {
101      Parameters.Add(new LookupParameter<IntValue>("Iterations", "The current iteration."));
102      Parameters.Add(new LookupParameter<IRandom>("Random", "The random number generator to use."));
103      Parameters.Add(new LookupParameter<Permutation>("Permutation", "The permutation solution."));
104      Parameters.Add(new LookupParameter<DoubleMatrix>("Weights", "The weights matrix."));
105      Parameters.Add(new LookupParameter<DoubleMatrix>("Distances", "The distances matrix."));
106      Parameters.Add(new LookupParameter<IntMatrix>("ShortTermMemory", "The table that stores the iteration at which a certain facility has been assigned to a certain location."));
107      Parameters.Add(new LookupParameter<DoubleMatrix>("MoveQualityMatrix", "The quality of all swap moves as evaluated on the current permutation."));
108      Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The quality value."));
109      Parameters.Add(new LookupParameter<DoubleValue>("BestQuality", "The best quality value."));
110      Parameters.Add(new LookupParameter<Swap2Move>("LastMove", "The last move that was applied."));
111      Parameters.Add(new LookupParameter<BoolValue>("UseNewTabuTenureAdaptionScheme", "True if the new tabu tenure adaption should be used or false otherwise."));
112      Parameters.Add(new LookupParameter<ResultCollection>("Results", "Collection that houses the results of the algorithm."));
113      Parameters.Add(new ValueLookupParameter<IntValue>("MaximumIterations", "The number of iterations that the algorithm should run."));
114      Parameters.Add(new ValueLookupParameter<IntValue>("MinimumTabuTenure", "The minimum tabu tenure."));
115      Parameters.Add(new ValueLookupParameter<IntValue>("MaximumTabuTenure", "The maximum tabu tenure."));
116      Parameters.Add(new ValueLookupParameter<BoolValue>("UseAlternativeAspiration", "True if the alternative aspiration condition should be used that takes moves that have not been made for some time above others."));
117      Parameters.Add(new ValueLookupParameter<IntValue>("AlternativeAspirationTenure", "The time t that a move will be remembered for the alternative aspiration condition."));
118      Parameters.Add(new LookupParameter<BoolValue>("AllMovesTabu", "Indicates that all moves are tabu."));
119    }
120
121    public override IDeepCloneable Clone(Cloner cloner) {
122      return new RobustTabooSeachOperator(this, cloner);
123    }
124
125    [StorableHook(HookType.AfterDeserialization)]
126    private void AfterDeserialization() {
127      // BackwardsCompatibility3.3
128      #region Backwards compatible code, remove with 3.4
129      if (!Parameters.ContainsKey("AllMovesTabu")) {
130        Parameters.Add(new LookupParameter<BoolValue>("AllMovesTabu", "Indicates that all moves are tabu."));
131      }
132      #endregion
133    }
134
135    public override IOperation Apply() {
136      IRandom random = RandomParameter.ActualValue;
137      int iteration = IterationsParameter.ActualValue.Value;
138      IntMatrix shortTermMemory = ShortTermMemoryParameter.ActualValue;
139      DoubleMatrix weights = WeightsParameter.ActualValue;
140      DoubleMatrix distances = DistancesParameter.ActualValue;
141      DoubleMatrix moveQualityMatrix = MoveQualityMatrixParameter.ActualValue;
142
143      DoubleValue quality = QualityParameter.ActualValue;
144      DoubleValue bestQuality = BestQualityParameter.ActualValue;
145      if (bestQuality == null) {
146        BestQualityParameter.ActualValue = (DoubleValue)quality.Clone();
147        bestQuality = BestQualityParameter.ActualValue;
148      }
149      bool allMovesTabu = false;
150      if (AllMovesTabuParameter.ActualValue == null)
151        AllMovesTabuParameter.ActualValue = new BoolValue(false);
152      else allMovesTabu = AllMovesTabuParameter.ActualValue.Value;
153
154      int minTenure = MinimumTabuTenureParameter.ActualValue.Value;
155      int maxTenure = MaximumTabuTenureParameter.ActualValue.Value;
156      int alternativeAspirationTenure = AlternativeAspirationTenureParameter.ActualValue.Value;
157      bool useAlternativeAspiration = UseAlternativeAspirationParameter.ActualValue.Value;
158      Permutation solution = PermutationParameter.ActualValue;
159      Swap2Move lastMove = LastMoveParameter.ActualValue;
160
161      double bestMoveQuality = double.MaxValue;
162      Swap2Move bestMove = null;
163      bool already_aspired = false;
164
165      foreach (Swap2Move move in ExhaustiveSwap2MoveGenerator.Generate(solution)) {
166        double moveQuality;
167        if (lastMove == null)
168          moveQuality = QAPSwap2MoveEvaluator.Apply(solution, move, weights, distances);
169        else if (allMovesTabu) moveQuality = moveQualityMatrix[move.Index1, move.Index2];
170        else moveQuality = QAPSwap2MoveEvaluator.Apply(solution, move, moveQualityMatrix[move.Index1, move.Index2], weights, distances, lastMove);
171
172        moveQualityMatrix[move.Index1, move.Index2] = moveQuality;
173        moveQualityMatrix[move.Index2, move.Index1] = moveQuality;
174
175        bool autorized = shortTermMemory[move.Index1, solution[move.Index2]] < iteration
176                      || shortTermMemory[move.Index2, solution[move.Index1]] < iteration;
177
178        bool aspired = (shortTermMemory[move.Index1, solution[move.Index2]] < iteration - alternativeAspirationTenure
179                     && shortTermMemory[move.Index2, solution[move.Index1]] < iteration - alternativeAspirationTenure)
180                  || quality.Value + moveQuality < bestQuality.Value;
181
182        if ((aspired && !already_aspired) // the first alternative move is aspired
183          || (aspired && already_aspired && moveQuality < bestMoveQuality) // an alternative move was already aspired, but this is better
184          || (autorized && !aspired && !already_aspired && moveQuality < bestMoveQuality)) { // a regular better move is found
185          bestMove = move;
186          bestMoveQuality = moveQuality;
187          if (aspired) already_aspired = true;
188        }
189      }
190
191      ResultCollection results = ResultsParameter.ActualValue;
192      if (results != null) {
193        IntValue aspiredMoves = null;
194        if (!results.ContainsKey("AspiredMoves")) {
195          aspiredMoves = new IntValue(already_aspired ? 1 : 0);
196          results.Add(new Result("AspiredMoves", "Counts the number of moves that were selected because of the aspiration criteria.", aspiredMoves));
197        } else if (already_aspired) {
198          aspiredMoves = (IntValue)results["AspiredMoves"].Value;
199          aspiredMoves.Value++;
200        }
201      }
202
203      allMovesTabu = bestMove == null;
204      if (!allMovesTabu)
205        LastMoveParameter.ActualValue = bestMove;
206      AllMovesTabuParameter.ActualValue.Value = allMovesTabu;
207
208      if (allMovesTabu) return base.Apply();
209
210      bool useNewAdaptionScheme = UseNewTabuTenureAdaptionSchemeParameter.ActualValue.Value;
211      if (useNewAdaptionScheme) {
212        double r = random.NextDouble();
213        if (r == 0) r = 1; // transform to (0;1]
214        shortTermMemory[bestMove.Index1, solution[bestMove.Index1]] = (int)(iteration + r * r * r * maxTenure);
215        r = random.NextDouble();
216        if (r == 0) r = 1; // transform to (0;1]
217        shortTermMemory[bestMove.Index2, solution[bestMove.Index2]] = (int)(iteration + r * r * r * maxTenure);
218      } else {
219        shortTermMemory[bestMove.Index1, solution[bestMove.Index1]] = iteration + random.Next(minTenure, maxTenure);
220        shortTermMemory[bestMove.Index2, solution[bestMove.Index2]] = iteration + random.Next(minTenure, maxTenure);
221      }
222      Swap2Manipulator.Apply(solution, bestMove.Index1, bestMove.Index2);
223      quality.Value += bestMoveQuality;
224
225      if (quality.Value < bestQuality.Value) bestQuality.Value = quality.Value;
226
227      return base.Apply();
228    }
229  }
230}
Note: See TracBrowser for help on using the repository browser.