source: branches/ProblemRefactoring/HeuristicLab.Problems.QuadraticAssignment/3.3/LocalImprovement/QAPExhaustiveSwap2LocalImprovement.cs @ 13396

Last change on this file since 13396 was 13396, checked in by abeham, 4 years ago

#2521:

  • Refactored QuadraticAssignmentProblem to use new SingleObjectiveProblem
    • Removed QAPEvaluator
    • Adapted RobustTabooSearch
  • Introduced several interfaces in PermutationEncoding necessary for wiring
  • Changed all Encodings to use IItem instead of IOperator in ConfigureOperators (name still unchanged)
  • Added a protected MaximizationParameter property in SingleObjectiveProblem (necessary for wiring)
  • Changed AlleleFrequnencyAnalyzer to use ISolution interface instead of IItem
  • Added a comment to ISolutionCreator<TSolution> of some changes that would be welcomed
File size: 10.2 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.Threading;
24using HeuristicLab.Common;
25using HeuristicLab.Core;
26using HeuristicLab.Data;
27using HeuristicLab.Encodings.PermutationEncoding;
28using HeuristicLab.Operators;
29using HeuristicLab.Optimization;
30using HeuristicLab.Parameters;
31using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
32
33namespace HeuristicLab.Problems.QuadraticAssignment {
34  [Item("QAPExhaustiveSwap2LocalImprovement", "Takes a solution and finds the local optimum with respect to the swap2 neighborhood by decending along the steepest gradient.")]
35  [StorableClass]
36  public class QAPExhaustiveSwap2LocalImprovement : SingleSuccessorOperator, IQAPLocalImprovementOperator, ISingleObjectiveOperator {
37
38    public ILookupParameter<IntValue> LocalIterationsParameter {
39      get { return (ILookupParameter<IntValue>)Parameters["LocalIterations"]; }
40    }
41
42    public IValueLookupParameter<IntValue> MaximumIterationsParameter {
43      get { return (IValueLookupParameter<IntValue>)Parameters["MaximumIterations"]; }
44    }
45
46    public ILookupParameter<IntValue> EvaluatedSolutionsParameter {
47      get { return (ILookupParameter<IntValue>)Parameters["EvaluatedSolutions"]; }
48    }
49
50    public ILookupParameter<ResultCollection> ResultsParameter {
51      get { return (ILookupParameter<ResultCollection>)Parameters["Results"]; }
52    }
53
54    public ILookupParameter<Permutation> PermutationParameter {
55      get { return (ILookupParameter<Permutation>)Parameters["Permutation"]; }
56    }
57
58    public ILookupParameter<DoubleValue> QualityParameter {
59      get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }
60    }
61
62    public ILookupParameter<BoolValue> MaximizationParameter {
63      get { return (ILookupParameter<BoolValue>)Parameters["Maximization"]; }
64    }
65
66    public ILookupParameter<DoubleMatrix> WeightsParameter {
67      get { return (ILookupParameter<DoubleMatrix>)Parameters["Weights"]; }
68    }
69
70    public ILookupParameter<DoubleMatrix> DistancesParameter {
71      get { return (ILookupParameter<DoubleMatrix>)Parameters["Distances"]; }
72    }
73
74    public IValueLookupParameter<BoolValue> UseFastEvaluationParameter {
75      get { return (IValueLookupParameter<BoolValue>)Parameters["UseFastEvaluation"]; }
76    }
77
78    [StorableConstructor]
79    protected QAPExhaustiveSwap2LocalImprovement(bool deserializing) : base(deserializing) { }
80    protected QAPExhaustiveSwap2LocalImprovement(QAPExhaustiveSwap2LocalImprovement original, Cloner cloner)
81      : base(original, cloner) {
82    }
83    public QAPExhaustiveSwap2LocalImprovement()
84      : base() {
85      Parameters.Add(new LookupParameter<IntValue>("LocalIterations", "The number of iterations that have already been performed."));
86      Parameters.Add(new ValueLookupParameter<IntValue>("MaximumIterations", "The maximum amount of iterations that should be performed (note that this operator will abort earlier when a local optimum is reached).", new IntValue(10000)));
87      Parameters.Add(new LookupParameter<IntValue>("EvaluatedSolutions", "The amount of evaluated solutions (here a move is counted only as 4/n evaluated solutions with n being the length of the permutation)."));
88      Parameters.Add(new LookupParameter<ResultCollection>("Results", "The collection where to store results."));
89      Parameters.Add(new LookupParameter<Permutation>("Permutation", "The permutation that is to be locally optimized."));
90      Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The quality value of the assignment."));
91      Parameters.Add(new LookupParameter<BoolValue>("Maximization", "True if the problem should be maximized or minimized."));
92      Parameters.Add(new LookupParameter<DoubleMatrix>("Weights", "The weights matrix."));
93      Parameters.Add(new LookupParameter<DoubleMatrix>("Distances", "The distances matrix."));
94      Parameters.Add(new ValueLookupParameter<BoolValue>("UseFastEvaluation", "Enabling this option will use a NxN double matrix to save the last move qualities. The moves of the first iteration will then be evaluated in O(N) while all further moves will be evaluated in O(1).", new BoolValue(true)));
95    }
96
97    public override IDeepCloneable Clone(Cloner cloner) {
98      return new QAPExhaustiveSwap2LocalImprovement(this, cloner);
99    }
100
101    // BackwardsCompatibility3.3
102    #region Backwards compatible code, remove with 3.4
103    [StorableHook(HookType.AfterDeserialization)]
104    private void AfterDeserialization() {
105      if (!Parameters.ContainsKey("LocalIterations"))
106        Parameters.Add(new LookupParameter<IntValue>("LocalIterations", "The number of iterations that have already been performed."));
107      if (!Parameters.ContainsKey("UseFastEvaluation"))
108        Parameters.Add(new ValueLookupParameter<BoolValue>("UseFastEvaluation", "Enabling this option will use a NxN double matrix to save the last move qualities. The moves of the first iteration will then be evaluated in O(N) while all further moves will be evaluated in O(1).", new BoolValue(false)));
109    }
110    #endregion
111
112    public static void Improve(Permutation assignment, DoubleMatrix weights, DoubleMatrix distances, DoubleValue quality, IntValue localIterations, IntValue evaluatedSolutions, bool maximization, int maxIterations, CancellationToken cancellation) {
113      double evalSolPerMove = 4.0 / assignment.Length;
114
115      for (int i = localIterations.Value; i < maxIterations; i++) {
116        Swap2Move bestMove = null;
117        double bestQuality = 0; // we have to make an improvement, so 0 is the baseline
118        double evaluations = 0.0;
119        foreach (Swap2Move move in ExhaustiveSwap2MoveGenerator.Generate(assignment)) {
120          double moveQuality = QAPSwap2MoveEvaluator.Apply(assignment, move, weights, distances);
121          evaluations += evalSolPerMove;
122          if (maximization && moveQuality > bestQuality
123            || !maximization && moveQuality < bestQuality) {
124            bestQuality = moveQuality;
125            bestMove = move;
126          }
127        }
128        evaluatedSolutions.Value += (int)Math.Ceiling(evaluations);
129        if (bestMove == null) break;
130        Swap2Manipulator.Apply(assignment, bestMove.Index1, bestMove.Index2);
131        quality.Value += bestQuality;
132        localIterations.Value++;
133        cancellation.ThrowIfCancellationRequested();
134      }
135    }
136
137    public static void ImproveFast(Permutation assignment, DoubleMatrix weights, DoubleMatrix distances, DoubleValue quality, IntValue localIterations, IntValue evaluatedSolutions, bool maximization, int maxIterations, CancellationToken cancellation) {
138      Swap2Move bestMove = null;
139      double evaluations = 0.0;
140      var lastQuality = new double[assignment.Length, assignment.Length];
141      for (int i = localIterations.Value; i < maxIterations; i++) {
142        double bestQuality = 0; // we have to make an improvement, so 0 is the baseline
143        var lastMove = bestMove;
144        bestMove = null;
145        foreach (Swap2Move move in ExhaustiveSwap2MoveGenerator.Generate(assignment)) {
146          double moveQuality;
147          if (lastMove == null) {
148            moveQuality = QAPSwap2MoveEvaluator.Apply(assignment, move, weights, distances);
149            evaluations += 4.0 / assignment.Length;
150          } else {
151            moveQuality = QAPSwap2MoveEvaluator.Apply(assignment, move, lastQuality[move.Index1, move.Index2], weights, distances, lastMove);
152            if (move.Index1 == lastMove.Index1 || move.Index2 == lastMove.Index1 || move.Index1 == lastMove.Index2 || move.Index2 == lastMove.Index2)
153              evaluations += 4.0 / assignment.Length;
154            else evaluations += 2.0 / (assignment.Length * assignment.Length);
155          }
156          lastQuality[move.Index1, move.Index2] = moveQuality;
157          if (maximization && moveQuality > bestQuality
158            || !maximization && moveQuality < bestQuality) {
159            bestQuality = moveQuality;
160            bestMove = move;
161          }
162        }
163        if (bestMove == null) break;
164        Swap2Manipulator.Apply(assignment, bestMove.Index1, bestMove.Index2);
165        quality.Value += bestQuality;
166        localIterations.Value++;
167        if (cancellation.IsCancellationRequested) {
168          evaluatedSolutions.Value += (int)Math.Round(evaluations);
169          throw new OperationCanceledException();
170        }
171      }
172      evaluatedSolutions.Value += (int)Math.Round(evaluations);
173    }
174
175    public override IOperation Apply() {
176      var maxIterations = MaximumIterationsParameter.ActualValue.Value;
177      var assignment = PermutationParameter.ActualValue;
178      var maximization = MaximizationParameter.ActualValue.Value;
179      var weights = WeightsParameter.ActualValue;
180      var distances = DistancesParameter.ActualValue;
181      var quality = QualityParameter.ActualValue;
182      var localIterations = LocalIterationsParameter.ActualValue;
183      var evaluations = EvaluatedSolutionsParameter.ActualValue;
184      if (localIterations == null) {
185        localIterations = new IntValue(0);
186        LocalIterationsParameter.ActualValue = localIterations;
187      }
188
189      if (UseFastEvaluationParameter.ActualValue.Value)
190        ImproveFast(assignment, weights, distances, quality, localIterations, evaluations, maximization, maxIterations, CancellationToken);
191      else Improve(assignment, weights, distances, quality, localIterations, evaluations, maximization, maxIterations, CancellationToken);
192
193      localIterations.Value = 0;
194      return base.Apply();
195    }
196  }
197}
Note: See TracBrowser for help on using the repository browser.