1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022012 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, ILocalImprovementOperator {


37 


38  public Type ProblemType {


39  get { return typeof(QuadraticAssignmentProblem); }


40  }


41 


42  [Storable]


43  private QuadraticAssignmentProblem problem;


44  public IProblem Problem {


45  get { return problem; }


46  set { problem = (QuadraticAssignmentProblem)value; }


47  }


48 


49  public ILookupParameter<IntValue> LocalIterationsParameter {


50  get { return (ILookupParameter<IntValue>)Parameters["LocalIterations"]; }


51  }


52 


53  public IValueLookupParameter<IntValue> MaximumIterationsParameter {


54  get { return (IValueLookupParameter<IntValue>)Parameters["MaximumIterations"]; }


55  }


56 


57  public ILookupParameter<IntValue> EvaluatedSolutionsParameter {


58  get { return (ILookupParameter<IntValue>)Parameters["EvaluatedSolutions"]; }


59  }


60 


61  public ILookupParameter<ResultCollection> ResultsParameter {


62  get { return (ILookupParameter<ResultCollection>)Parameters["Results"]; }


63  }


64 


65  public ILookupParameter<Permutation> AssignmentParameter {


66  get { return (ILookupParameter<Permutation>)Parameters["Assignment"]; }


67  }


68 


69  public ILookupParameter<DoubleValue> QualityParameter {


70  get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }


71  }


72 


73  public ILookupParameter<BoolValue> MaximizationParameter {


74  get { return (ILookupParameter<BoolValue>)Parameters["Maximization"]; }


75  }


76 


77  public ILookupParameter<DoubleMatrix> WeightsParameter {


78  get { return (ILookupParameter<DoubleMatrix>)Parameters["Weights"]; }


79  }


80 


81  public ILookupParameter<DoubleMatrix> DistancesParameter {


82  get { return (ILookupParameter<DoubleMatrix>)Parameters["Distances"]; }


83  }


84 


85  public IValueLookupParameter<BoolValue> UseFastEvaluationParameter {


86  get { return (IValueLookupParameter<BoolValue>)Parameters["UseFastEvaluation"]; }


87  }


88 


89  [StorableConstructor]


90  protected QAPExhaustiveSwap2LocalImprovement(bool deserializing) : base(deserializing) { }


91  protected QAPExhaustiveSwap2LocalImprovement(QAPExhaustiveSwap2LocalImprovement original, Cloner cloner)


92  : base(original, cloner) {


93  this.problem = cloner.Clone(original.problem);


94  }


95  public QAPExhaustiveSwap2LocalImprovement()


96  : base() {


97  Parameters.Add(new LookupParameter<IntValue>("LocalIterations", "The number of iterations that have already been performed."));


98  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)));


99  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)."));


100  Parameters.Add(new LookupParameter<ResultCollection>("Results", "The collection where to store results."));


101  Parameters.Add(new LookupParameter<Permutation>("Assignment", "The permutation that is to be locally optimized."));


102  Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The quality value of the assignment."));


103  Parameters.Add(new LookupParameter<BoolValue>("Maximization", "True if the problem should be maximized or minimized."));


104  Parameters.Add(new LookupParameter<DoubleMatrix>("Weights", "The weights matrix."));


105  Parameters.Add(new LookupParameter<DoubleMatrix>("Distances", "The distances matrix."));


106  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)));


107  }


108 


109  public override IDeepCloneable Clone(Cloner cloner) {


110  return new QAPExhaustiveSwap2LocalImprovement(this, cloner);


111  }


112 


113  // BackwardsCompatibility3.3


114  #region Backwards compatible code, remove with 3.4


115  [StorableHook(HookType.AfterDeserialization)]


116  private void AfterDeserialization() {


117  if (!Parameters.ContainsKey("LocalIterations"))


118  Parameters.Add(new LookupParameter<IntValue>("LocalIterations", "The number of iterations that have already been performed."));


119  if (!Parameters.ContainsKey("UseFastEvaluation"))


120  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)));


121  }


122  #endregion


123 


124  public static void Improve(Permutation assignment, DoubleMatrix weights, DoubleMatrix distances, DoubleValue quality, IntValue localIterations, IntValue evaluatedSolutions, bool maximization, int maxIterations, CancellationToken cancellation) {


125  double evalSolPerMove = 4.0 / assignment.Length;


126 


127  for (int i = localIterations.Value; i < maxIterations; i++) {


128  Swap2Move bestMove = null;


129  double bestQuality = 0; // we have to make an improvement, so 0 is the baseline


130  double evaluations = 0.0;


131  foreach (Swap2Move move in ExhaustiveSwap2MoveGenerator.Generate(assignment)) {


132  double moveQuality = QAPSwap2MoveEvaluator.Apply(assignment, move, weights, distances);


133  evaluations += evalSolPerMove;


134  if (maximization && moveQuality > bestQuality


135   !maximization && moveQuality < bestQuality) {


136  bestQuality = moveQuality;


137  bestMove = move;


138  }


139  }


140  evaluatedSolutions.Value += (int)Math.Ceiling(evaluations);


141  if (bestMove == null) break;


142  Swap2Manipulator.Apply(assignment, bestMove.Index1, bestMove.Index2);


143  quality.Value += bestQuality;


144  localIterations.Value++;


145  cancellation.ThrowIfCancellationRequested();


146  }


147  }


148 


149  public static void ImproveFast(Permutation assignment, DoubleMatrix weights, DoubleMatrix distances, DoubleValue quality, IntValue localIterations, IntValue evaluatedSolutions, bool maximization, int maxIterations, CancellationToken cancellation) {


150  Swap2Move bestMove = null;


151  double evaluations = 0.0;


152  var lastQuality = new double[assignment.Length, assignment.Length];


153  for (int i = localIterations.Value; i < maxIterations; i++) {


154  double bestQuality = 0; // we have to make an improvement, so 0 is the baseline


155  var lastMove = bestMove;


156  bestMove = null;


157  foreach (Swap2Move move in ExhaustiveSwap2MoveGenerator.Generate(assignment)) {


158  double moveQuality;


159  if (lastMove == null) {


160  moveQuality = QAPSwap2MoveEvaluator.Apply(assignment, move, weights, distances);


161  evaluations += 4.0 / assignment.Length;


162  } else {


163  moveQuality = QAPSwap2MoveEvaluator.Apply(assignment, move, lastQuality[move.Index1, move.Index2], weights, distances, lastMove);


164  if (move.Index1 == lastMove.Index1  move.Index2 == lastMove.Index1  move.Index1 == lastMove.Index2  move.Index2 == lastMove.Index2)


165  evaluations += 4.0 / assignment.Length;


166  else evaluations += 2.0 / (assignment.Length * assignment.Length);


167  }


168  lastQuality[move.Index1, move.Index2] = moveQuality;


169  if (maximization && moveQuality > bestQuality


170   !maximization && moveQuality < bestQuality) {


171  bestQuality = moveQuality;


172  bestMove = move;


173  }


174  }


175  if (bestMove == null) break;


176  Swap2Manipulator.Apply(assignment, bestMove.Index1, bestMove.Index2);


177  quality.Value += bestQuality;


178  localIterations.Value++;


179  if (cancellation.IsCancellationRequested) {


180  evaluatedSolutions.Value += (int)Math.Round(evaluations);


181  throw new OperationCanceledException();


182  }


183  }


184  evaluatedSolutions.Value += (int)Math.Round(evaluations);


185  }


186 


187  public override IOperation Apply() {


188  var maxIterations = MaximumIterationsParameter.ActualValue.Value;


189  var assignment = AssignmentParameter.ActualValue;


190  var maximization = MaximizationParameter.ActualValue.Value;


191  var weights = WeightsParameter.ActualValue;


192  var distances = DistancesParameter.ActualValue;


193  var quality = QualityParameter.ActualValue;


194  var localIterations = LocalIterationsParameter.ActualValue;


195  var evaluations = EvaluatedSolutionsParameter.ActualValue;


196  if (localIterations == null) {


197  localIterations = new IntValue(0);


198  LocalIterationsParameter.ActualValue = localIterations;


199  }


200 


201  if (UseFastEvaluationParameter.ActualValue.Value)


202  ImproveFast(assignment, weights, distances, quality, localIterations, evaluations, maximization, maxIterations, CancellationToken);


203  else Improve(assignment, weights, distances, quality, localIterations, evaluations, maximization, maxIterations, CancellationToken);


204 


205  return base.Apply();


206  }


207  }


208  }

