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  Permutation currSol = CurrentScope.Variables[SolutionParameter.ActualName].Value as Permutation;


98  if (currSol == null)


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


100  if (currSol.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  int a = Random.Next(currSol.Length);


105  int b = Random.Next(currSol.Length);


106  double oldFirstEdgeLength = DistanceMatrix[currSol[a], currSol[(a  1 + currSol.Length) % currSol.Length]];


107  double oldSecondEdgeLength = DistanceMatrix[currSol[b], currSol[(b + 1) % currSol.Length]];


108  double newFirstEdgeLength = DistanceMatrix[currSol[b], currSol[(a  1 + currSol.Length) % currSol.Length]];


109  double newSecondEdgeLength = DistanceMatrix[currSol[a], currSol[(b + 1 + currSol.Length) % currSol.Length]];


110  if (newFirstEdgeLength + newSecondEdgeLength < oldFirstEdgeLength + oldSecondEdgeLength)


111  Invert(currSol, a, b);


112  }


113 


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


115 


116  return base.Apply();


117  }


118 


119  private void Invert(Permutation sol, int i, int j) {


120  if (i != j)


121  for (int a = 0; a < Math.Abs(i  j) / 2; a++)


122  if (sol[(i + a) % sol.Length] != sol[(j  a + sol.Length) % sol.Length]) {


123  // XOR swap


124  sol[(i + a) % sol.Length] ^= sol[(j  a + sol.Length) % sol.Length];


125  sol[(j  a + sol.Length) % sol.Length] ^= sol[(i + a) % sol.Length];


126  sol[(i + a) % sol.Length] ^= sol[(j  a + sol.Length) % sol.Length];


127  }


128  }


129  }


130  }

