1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022015 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 


22  using System;


23  using System.Threading;


24  using HeuristicLab.Common;


25  using HeuristicLab.Core;


26  using HeuristicLab.Data;


27  using HeuristicLab.Encodings.PermutationEncoding;


28  using HeuristicLab.Operators;


29  using HeuristicLab.Optimization;


30  using HeuristicLab.Parameters;


31  using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;


32 


33  namespace 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  }

