1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 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 HEAL.Attic;


25  using HeuristicLab.Common;


26  using HeuristicLab.Core;


27  using HeuristicLab.Data;


28  using HeuristicLab.Encodings.PermutationEncoding;


29  using HeuristicLab.Operators;


30  using HeuristicLab.Optimization;


31  using HeuristicLab.Parameters;


32 


33  namespace HeuristicLab.Problems.PTSP {


34  /// <summary>


35  /// An operator that improves probabilistic traveling salesman solutions.


36  /// </summary>


37  /// <remarks>


38  /// The operator tries to improve the probabilistic traveling salesman solution by swapping two randomly chosen edges for a certain number of times.


39  /// </remarks>


40  [Item("pTSP Analytical 2.5 Local Improvement", "An operator that improves probabilistic traveling salesman solutions. The operator tries to improve the probabilistic traveling salesman solution by swapping two randomly chosen edges for a certain number of times.")]


41  [StorableType("6e07195e0da745ea93850c66594127db")]


42  public sealed class PTSPAnalyticalTwoPointFiveLocalImprovement : SingleSuccessorOperator, IAnalyticalPTSPOperator, ILocalImprovementOperator {


43 


44  public ILookupParameter<IntValue> LocalIterationsParameter {


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


46  }


47 


48  public IValueLookupParameter<IntValue> MaximumIterationsParameter {


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


50  }


51 


52  public ILookupParameter<IntValue> EvaluatedSolutionsParameter {


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


54  }


55 


56  public ILookupParameter<ResultCollection> ResultsParameter {


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


58  }


59 


60  public ILookupParameter<Permutation> PermutationParameter {


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


62  }


63 


64  public ILookupParameter<DoubleValue> QualityParameter {


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


66  }


67 


68  public ILookupParameter<BoolValue> MaximizationParameter {


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


70  }


71 


72  public ILookupParameter<IProbabilisticTSPData> ProbabilisticTSPDataParameter {


73  get { return (ILookupParameter<IProbabilisticTSPData>)Parameters["PTSP Data"]; }


74  }


75 


76  [StorableConstructor]


77  private PTSPAnalyticalTwoPointFiveLocalImprovement(StorableConstructorFlag _) : base(_) { }


78  private PTSPAnalyticalTwoPointFiveLocalImprovement(PTSPAnalyticalTwoPointFiveLocalImprovement original, Cloner cloner) : base(original, cloner) { }


79  public PTSPAnalyticalTwoPointFiveLocalImprovement()


80  : base() {


81  Parameters.Add(new LookupParameter<Permutation>("Permutation", "The solution as permutation."));


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


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


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


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


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


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


88  Parameters.Add(new LookupParameter<IProbabilisticTSPData>("PTSP Data", "The main parameters of the pTSP."));


89  }


90 


91  public override IDeepCloneable Clone(Cloner cloner) {


92  return new PTSPAnalyticalTwoPointFiveLocalImprovement(this, cloner);


93  }


94 


95  public static void Improve(Permutation assignment, IProbabilisticTSPData data, DoubleValue quality, IntValue localIterations, IntValue evaluatedSolutions, bool maximization, int maxIterations, CancellationToken cancellation) {


96  for (var i = localIterations.Value; i < maxIterations; i++) {


97  TwoPointFiveMove bestMove = null;


98  var bestQuality = quality.Value; // we have to make an improvement, so current quality is the baseline


99  var evaluations = 0.0;


100  foreach (var move in ExhaustiveTwoPointFiveMoveGenerator.Generate(assignment)) {


101  var moveQuality = PTSPAnalyticalTwoPointFiveMoveEvaluator.EvaluateMove(assignment, move, data);


102  evaluations++;


103  if (maximization && moveQuality > bestQuality


104   !maximization && moveQuality < bestQuality) {


105  bestQuality = moveQuality;


106  bestMove = move;


107  }


108  }


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


110  if (bestMove == null) break;


111  TwoPointFiveMoveMaker.Apply(assignment, bestMove);


112  quality.Value = bestQuality;


113  localIterations.Value++;


114  cancellation.ThrowIfCancellationRequested();


115  }


116  }


117 


118  public override IOperation Apply() {


119  var maxIterations = MaximumIterationsParameter.ActualValue.Value;


120  var assignment = PermutationParameter.ActualValue;


121  var maximization = MaximizationParameter.ActualValue.Value;


122  var quality = QualityParameter.ActualValue;


123  var localIterations = LocalIterationsParameter.ActualValue;


124  var evaluations = EvaluatedSolutionsParameter.ActualValue;


125  var data = ProbabilisticTSPDataParameter.ActualValue;


126  if (localIterations == null) {


127  localIterations = new IntValue(0);


128  LocalIterationsParameter.ActualValue = localIterations;


129  }


130 


131  Improve(assignment, data, quality, localIterations, evaluations, maximization, maxIterations, CancellationToken);


132 


133  localIterations.Value = 0;


134  return base.Apply();


135  }


136  }


137  }

