Free cookie consent management tool by TermsFeed Policy Generator

source: branches/QAPAlgorithms/HeuristicLab.Problems.QuadraticAssignment.Algorithms/3.3/QAPRandomizedRobustTabooSeachOperator.cs @ 6625

Last change on this file since 6625 was 6416, checked in by abeham, 13 years ago

#1541

  • Added PermutationView that allows to change the permutation type
  • Updated AFA and PopDiv Analyzer
  • Simplified QAP name to just the instance when loading from embedded resource
File size: 14.4 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;
23using HeuristicLab.Common;
24using HeuristicLab.Core;
25using HeuristicLab.Data;
26using HeuristicLab.Encodings.PermutationEncoding;
27using HeuristicLab.Operators;
28using HeuristicLab.Optimization;
29using HeuristicLab.Parameters;
30using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
31
32namespace HeuristicLab.Problems.QuadraticAssignment.Algorithms {
33  [Item("QAPRandomizedRobustTabooSeachOperator", "Performs an iteration of a modified robust taboo search algorithm based on Taillard 1991.")]
34  public sealed class QAPRandomizedRobustTabooSeachOperator : SingleSuccessorOperator, IIterationBasedOperator, IStochasticOperator {
35
36    #region Parameter Properties
37    public ILookupParameter<IntValue> IterationsParameter {
38      get { return (ILookupParameter<IntValue>)Parameters["Iterations"]; }
39    }
40    public ILookupParameter<IntValue> TabuTenureParameter {
41      get { return (ILookupParameter<IntValue>)Parameters["TabuTenure"]; }
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> ShortTermMemory2Parameter {
56      get { return (ILookupParameter<DoubleMatrix>)Parameters["ShortTermMemory2"]; }
57    }
58    public ILookupParameter<IntMatrix> LongTermMemoryParameter {
59      get { return (ILookupParameter<IntMatrix>)Parameters["LongTermMemory"]; }
60    }
61    public ILookupParameter<DoubleValue> QualityParameter {
62      get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }
63    }
64    public ILookupParameter<DoubleValue> BestQualityParameter {
65      get { return (ILookupParameter<DoubleValue>)Parameters["BestQuality"]; }
66    }
67    public ILookupParameter<ResultCollection> ResultsParameter {
68      get { return (ILookupParameter<ResultCollection>)Parameters["Results"]; }
69    }
70    public ILookupParameter<IntValue> LastGlobalImprovementParameter {
71      get { return (ILookupParameter<IntValue>)Parameters["LastGlobalImprovement"]; }
72    }
73    public ILookupParameter<DoubleValue> BestKnownQualityParameter {
74      get { return (ILookupParameter<DoubleValue>)Parameters["BestKnownQuality"]; }
75    }
76
77    public ILookupParameter<IRandom> RandomParameter {
78      get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
79    }
80    public IValueLookupParameter<IntValue> MaximumIterationsParameter {
81      get { return (IValueLookupParameter<IntValue>)Parameters["MaximumIterations"]; }
82    }
83    public IValueLookupParameter<IntValue> MinimumTabuTenureParameter {
84      get { return (IValueLookupParameter<IntValue>)Parameters["MinimumTabuTenure"]; }
85    }
86    public IValueLookupParameter<IntValue> MaximumTabuTenureParameter {
87      get { return (IValueLookupParameter<IntValue>)Parameters["MaximumTabuTenure"]; }
88    }
89    public IValueLookupParameter<IntValue> TabuTenureAdaptionIntervalParameter {
90      get { return (IValueLookupParameter<IntValue>)Parameters["TabuTenureAdaptionInterval"]; }
91    }
92    #endregion
93
94    [StorableConstructor]
95    private QAPRandomizedRobustTabooSeachOperator(bool deserializing) : base(deserializing) { }
96    private QAPRandomizedRobustTabooSeachOperator(QAPRandomizedRobustTabooSeachOperator original, Cloner cloner)
97      : base(original, cloner) {
98    }
99    public QAPRandomizedRobustTabooSeachOperator() {
100      Parameters.Add(new LookupParameter<IntValue>("Iterations", "The current iteration."));
101      Parameters.Add(new LookupParameter<IntValue>("TabuTenure", "The current tabu tenure."));
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>("ShortTermMemory2", "The table that stores the quality at which a certain facility has been assigned to a certain location."));
108      Parameters.Add(new LookupParameter<IntMatrix>("LongTermMemory", "Same as the tabu table, but constantly updates the information given the current solution."));
109      Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The quality value."));
110      Parameters.Add(new LookupParameter<DoubleValue>("BestQuality", "The best quality value."));
111      Parameters.Add(new ValueLookupParameter<IntValue>("MaximumIterations", "The number of iterations that the algorithm should run."));
112      Parameters.Add(new ValueLookupParameter<IntValue>("MinimumTabuTenure", "The minimum tabu tenure."));
113      Parameters.Add(new ValueLookupParameter<IntValue>("MaximumTabuTenure", "The maximum tabu tenure."));
114      Parameters.Add(new ValueLookupParameter<IntValue>("TabuTenureAdaptionInterval", "The amount of iterations that have to pass before the tabu tenure is adapted."));
115      Parameters.Add(new LookupParameter<IntValue>("LastGlobalImprovement", "The iteration at which the best solution so far has been improved."));
116      Parameters.Add(new LookupParameter<DoubleValue>("BestKnownQuality", "The best known quality is just used to store the iteration at which it was found."));
117      Parameters.Add(new LookupParameter<ResultCollection>("Results", "The collection to store results to."));
118    }
119
120    public override IDeepCloneable Clone(Cloner cloner) {
121      return new QAPRandomizedRobustTabooSeachOperator(this, cloner);
122    }
123
124    public override IOperation Apply() {
125      ResultCollection results = ResultsParameter.ActualValue;
126      IRandom random = RandomParameter.ActualValue;
127      int iteration = IterationsParameter.ActualValue.Value;
128
129      IntMatrix longTermMemory = LongTermMemoryParameter.ActualValue;
130      IntMatrix shortTermMemory = ShortTermMemoryParameter.ActualValue;
131      DoubleMatrix shortTermMemory2 = ShortTermMemory2Parameter.ActualValue;
132      DoubleMatrix weights = WeightsParameter.ActualValue;
133      DoubleMatrix distances = DistancesParameter.ActualValue;
134
135      DoubleValue quality = QualityParameter.ActualValue;
136      DoubleValue bestQuality = BestQualityParameter.ActualValue;
137      if (bestQuality == null) {
138        BestQualityParameter.ActualValue = (DoubleValue)quality.Clone();
139        bestQuality = BestQualityParameter.ActualValue;
140      }
141
142      Permutation solution = PermutationParameter.ActualValue;
143
144      for (int i = 0; i < solution.Length; i++)
145        longTermMemory[i, solution[i]] = iteration;
146
147      double minQuality = double.MaxValue, maxQuality = double.MinValue,
148        minImprovement = double.MaxValue, maxImprovement = double.MinValue,
149        minRevist = double.MaxValue, maxRevist = double.MinValue;
150      Swap2Move[] moves = ExhaustiveSwap2MoveGenerator.Apply(solution);
151      double[] moveQualities = new double[moves.Length];
152      for (int i = 0; i < moves.Length; i++) {
153        Swap2Move move = moves[i];
154        double moveQuality = QAPSwap2MoveEvaluator.Apply(solution, move, weights, distances);
155        moveQualities[i] = moveQuality;
156        if (moveQuality < minQuality) minQuality = moveQuality;
157        if (moveQuality > maxQuality) maxQuality = moveQuality;
158
159        double improvement = 0;
160        if (shortTermMemory[move.Index1, solution[move.Index2]] > 0)
161          improvement += Math.Max(0, shortTermMemory2[move.Index1, solution[move.Index2]] - quality.Value + moveQuality);
162        if (shortTermMemory[move.Index2, solution[move.Index1]] > 0)
163          improvement += Math.Max(0, shortTermMemory2[move.Index2, solution[move.Index1]] - quality.Value + moveQuality);
164        if (improvement > 0) {
165          if (improvement < minImprovement) minImprovement = improvement;
166          if (improvement > maxImprovement) maxImprovement = improvement;
167        }
168
169        double revisit = 0;
170        revisit += Math.Max(0, quality.Value - shortTermMemory2[move.Index1, solution[move.Index2]]);
171        revisit += Math.Max(0, quality.Value - shortTermMemory2[move.Index2, solution[move.Index1]]);
172        if (revisit > 0) {
173          if (revisit < minRevist) minRevist = revisit;
174          if (revisit > maxRevist) maxRevist = revisit;
175        }
176      }
177
178      Swap2Move selectedMove = null;
179      double bestInterestingness = double.MinValue, selectedMoveQuality = 0;
180      int equalInterestingCount = 0;
181      for (int i = 0; i < moves.Length; i++) {
182        Swap2Move move = moves[i];
183
184        double interestingness = 0;
185
186        if (maxQuality > minQuality)
187          interestingness += 4 * (maxQuality - moveQualities[i]) / (maxQuality - minQuality);
188
189        if (maxImprovement > minImprovement) {
190          double improvement = 0;
191          if (shortTermMemory[move.Index1, solution[move.Index2]] > 0)
192            improvement += Math.Max(0, shortTermMemory2[move.Index1, solution[move.Index2]] - quality.Value + moveQualities[i]);
193          if (shortTermMemory[move.Index2, solution[move.Index1]] > 0)
194            improvement += Math.Max(0, shortTermMemory2[move.Index2, solution[move.Index1]] - quality.Value + moveQualities[i]);
195          if (improvement > 0)
196            interestingness += 2 * (improvement - minImprovement) / (maxImprovement - minImprovement);
197        }
198
199        if (iteration > 0) {
200          interestingness += ((double)(iteration - longTermMemory[move.Index1, solution[move.Index2]]) / (double)iteration)
201            + ((double)(iteration - longTermMemory[move.Index2, solution[move.Index1]]) / (double)iteration);
202        }
203
204        if (maxRevist > minRevist) {
205          double revisit = 0;
206          revisit += Math.Max(0, quality.Value - shortTermMemory2[move.Index1, solution[move.Index2]]);
207          revisit += Math.Max(0, quality.Value - shortTermMemory2[move.Index2, solution[move.Index1]]);
208          if (revisit > 0)
209            interestingness += (revisit - minRevist) / (maxRevist - minRevist);
210        }
211
212        if (quality.Value + moveQualities[i] < bestQuality.Value) interestingness = double.MaxValue;
213        if (interestingness > bestInterestingness) {
214          bestInterestingness = interestingness;
215          selectedMove = moves[i];
216          selectedMoveQuality = moveQualities[i];
217          equalInterestingCount = 1;
218        } else if (interestingness == bestInterestingness) {
219          equalInterestingCount++;
220          if (random.NextDouble() < 1.0 / equalInterestingCount) {
221            selectedMove = moves[i];
222            selectedMoveQuality = moveQualities[i];
223          }
224        }
225      }
226
227      shortTermMemory[selectedMove.Index1, solution[selectedMove.Index1]] = iteration;
228      shortTermMemory[selectedMove.Index2, solution[selectedMove.Index2]] = iteration;
229      if (shortTermMemory2[selectedMove.Index1, solution[selectedMove.Index2]] > 0)
230        shortTermMemory2[selectedMove.Index1, solution[selectedMove.Index2]] = Math.Min(quality.Value + selectedMoveQuality, shortTermMemory2[selectedMove.Index1, solution[selectedMove.Index2]]);
231      else shortTermMemory2[selectedMove.Index1, solution[selectedMove.Index2]] = quality.Value + selectedMoveQuality;
232      if (shortTermMemory2[selectedMove.Index1, solution[selectedMove.Index1]] > 0)
233        shortTermMemory2[selectedMove.Index1, solution[selectedMove.Index1]] = Math.Min(quality.Value, shortTermMemory2[selectedMove.Index1, solution[selectedMove.Index1]]);
234      else shortTermMemory2[selectedMove.Index1, solution[selectedMove.Index1]] = quality.Value;
235      if (shortTermMemory2[selectedMove.Index2, solution[selectedMove.Index1]] > 0)
236        shortTermMemory2[selectedMove.Index2, solution[selectedMove.Index1]] = Math.Min(quality.Value + selectedMoveQuality, shortTermMemory2[selectedMove.Index2, solution[selectedMove.Index1]]);
237      else shortTermMemory2[selectedMove.Index2, solution[selectedMove.Index1]] = quality.Value + selectedMoveQuality;
238      if (shortTermMemory2[selectedMove.Index2, solution[selectedMove.Index2]] > 0)
239        shortTermMemory2[selectedMove.Index2, solution[selectedMove.Index2]] = Math.Min(quality.Value, shortTermMemory2[selectedMove.Index2, solution[selectedMove.Index2]]);
240      else shortTermMemory2[selectedMove.Index2, solution[selectedMove.Index2]] = quality.Value;
241
242      Swap2Manipulator.Apply(solution, selectedMove.Index1, selectedMove.Index2);
243      quality.Value += selectedMoveQuality;
244
245      if (quality.Value < bestQuality.Value) {
246        bestQuality.Value = quality.Value;
247        if (LastGlobalImprovementParameter.ActualValue == null)
248          LastGlobalImprovementParameter.ActualValue = new IntValue(iteration);
249        else LastGlobalImprovementParameter.ActualValue.Value = iteration;
250      }
251      if (!results.ContainsKey("GlobalBestFound")) results.Add(new Result("GlobalBestFound", new IntValue(-1)));
252      if (BestKnownQualityParameter.ActualValue.Value == bestQuality.Value
253        && ((IntValue)results["GlobalBestFound"].Value).Value < 0) {
254        ((IntValue)results["GlobalBestFound"].Value).Value = iteration;
255      }
256      return base.Apply();
257    }
258  }
259}
Note: See TracBrowser for help on using the repository browser.