1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022014 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 HeuristicLab.Common;


24  using HeuristicLab.Core;


25  using HeuristicLab.Data;


26  using HeuristicLab.Encodings.PermutationEncoding;


27  using HeuristicLab.Operators;


28  using HeuristicLab.Optimization;


29  using HeuristicLab.Parameters;


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


31 


32  namespace HeuristicLab.Problems.TravelingSalesman {


33  /// <summary>


34  /// An operator that improves traveling salesman solutions.


35  /// </summary>


36  /// <remarks>


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


38  /// </remarks>


39  [Item("TSPImprovementOperator", "An operator that improves traveling salesman solutions. The operator tries to improve the traveling salesman solution by swapping two randomly chosen edges for a certain number of times.")]


40  [StorableClass]


41  public sealed class TSPImprovementOperator : SingleSuccessorOperator, ISingleObjectiveImprovementOperator {


42  #region Parameter properties


43  public ScopeParameter CurrentScopeParameter {


44  get { return (ScopeParameter)Parameters["CurrentScope"]; }


45  }


46  public ILookupParameter<DistanceMatrix> DistanceMatrixParameter {


47  get { return (ILookupParameter<DistanceMatrix>)Parameters["DistanceMatrix"]; }


48  }


49  public IValueParameter<IntValue> ImprovementAttemptsParameter {


50  get { return (IValueParameter<IntValue>)Parameters["ImprovementAttempts"]; }


51  }


52  public ILookupParameter<IRandom> RandomParameter {


53  get { return (ILookupParameter<IRandom>)Parameters["Random"]; }


54  }


55  public IValueLookupParameter<IItem> SolutionParameter {


56  get { return (IValueLookupParameter<IItem>)Parameters["Solution"]; }


57  }


58  #endregion


59 


60  #region Properties


61  public IScope CurrentScope {


62  get { return CurrentScopeParameter.ActualValue; }


63  }


64  public DistanceMatrix DistanceMatrix {


65  get { return DistanceMatrixParameter.ActualValue; }


66  set { DistanceMatrixParameter.ActualValue = value; }


67  }


68  public IntValue ImprovementAttempts {


69  get { return ImprovementAttemptsParameter.Value; }


70  set { ImprovementAttemptsParameter.Value = value; }


71  }


72  public IRandom Random {


73  get { return RandomParameter.ActualValue; }


74  set { RandomParameter.ActualValue = value; }


75  }


76  #endregion


77 


78  [StorableConstructor]


79  private TSPImprovementOperator(bool deserializing) : base(deserializing) { }


80  private TSPImprovementOperator(TSPImprovementOperator original, Cloner cloner) : base(original, cloner) { }


81  public TSPImprovementOperator()


82  : base() {


83  #region Create parameters


84  Parameters.Add(new ScopeParameter("CurrentScope", "The current scope that contains the solution to be improved."));


85  Parameters.Add(new LookupParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));


86  Parameters.Add(new ValueParameter<IntValue>("ImprovementAttempts", "The number of improvement attempts the operator should perform.", new IntValue(100)));


87  Parameters.Add(new LookupParameter<IRandom>("Random", "A pseudo random number generator."));


88  Parameters.Add(new ValueLookupParameter<IItem>("Solution", "The solution to be improved. This parameter is used for name translation only."));


89  #endregion


90  }


91 


92  public override IDeepCloneable Clone(Cloner cloner) {


93  return new TSPImprovementOperator(this, cloner);


94  }


95 


96  public override IOperation Apply() {


97  var solution = CurrentScope.Variables[SolutionParameter.ActualName].Value as Permutation;


98  if (solution == null)


99  throw new ArgumentException("Cannot improve solution because it has the wrong type.");


100  if (solution.PermutationType != PermutationTypes.RelativeUndirected)


101  throw new ArgumentException("Cannot improve solution because the permutation type is not supported.");


102 


103  for (int i = 0; i < ImprovementAttempts.Value; i++) {


104  var move = StochasticInversionSingleMoveGenerator.Apply(solution, Random);


105  double moveQualtiy = TSPInversionMovePathEvaluator.EvaluateByDistanceMatrix(solution, move, DistanceMatrix);


106  if (moveQualtiy < 0)


107  InversionManipulator.Apply(solution, move.Index1, move.Index2);


108  }


109 


110  CurrentScope.Variables.Add(new Variable("LocalEvaluatedSolutions", ImprovementAttempts));


111 


112  return base.Apply();


113  }


114  }


115  }

