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.Collections.Generic;


24  using System.Linq;


25  using HeuristicLab.Common;


26  using HeuristicLab.Core;


27  using HeuristicLab.Data;


28  using HeuristicLab.Encodings.PermutationEncoding;


29  using HeuristicLab.Optimization.Operators;


30  using HeuristicLab.Parameters;


31  using HEAL.Attic;


32 


33  namespace HeuristicLab.Problems.TravelingSalesman {


34  /// <summary>


35  /// An operator that relinks paths between traveling salesman solutions using a multiple guiding strategy.


36  /// </summary>


37  /// <remarks>


38  /// The operator incrementally changes the initiating solution towards the guiding solution by correcting edges as needed. For each city it choses the best edge from all guiding solutions.


39  /// </remarks>


40  [Item("TSPMultipleGuidesPathRelinker", "An operator that relinks paths between traveling salesman solutions using a multiple guiding strategy. The operator incrementally changes the initiating solution towards the guiding solution by correcting edges as needed. For each city it choses the best edge from all guiding solutions.")]


41  [StorableType("6B5B2622AB1D47E68BBCC6088D393149")]


42  public sealed class TSPMultipleGuidesPathRelinker : SingleObjectivePathRelinker {


43  #region Parameter properties


44  public ILookupParameter<DistanceMatrix> DistanceMatrixParameter {


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


46  }


47  #endregion


48 


49  #region Properties


50  public DistanceMatrix DistanceMatrix {


51  get { return DistanceMatrixParameter.ActualValue; }


52  }


53  #endregion


54 


55  [StorableConstructor]


56  private TSPMultipleGuidesPathRelinker(StorableConstructorFlag _) : base(_) { }


57  private TSPMultipleGuidesPathRelinker(TSPMultipleGuidesPathRelinker original, Cloner cloner) : base(original, cloner) { }


58  public TSPMultipleGuidesPathRelinker()


59  : base() {


60  #region Create parameters


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


62  #endregion


63  }


64 


65  public override IDeepCloneable Clone(Cloner cloner) {


66  return new TSPMultipleGuidesPathRelinker(this, cloner);


67  }


68 


69  public static ItemArray<IItem> Apply(IItem initiator, IItem[] guides, DistanceMatrix distances, PercentValue n) {


70  if (!(initiator is Permutation)  guides.Any(x => !(x is Permutation)))


71  throw new ArgumentException("Cannot relink path because some of the provided solutions have the wrong type.");


72  if (n.Value <= 0.0)


73  throw new ArgumentException("RelinkingAccuracy must be greater than 0.");


74 


75  Permutation v1 = initiator.Clone() as Permutation;


76  Permutation[] targets = new Permutation[guides.Length];


77  Array.Copy(guides, targets, guides.Length);


78 


79  if (targets.Any(x => x.Length != v1.Length))


80  throw new ArgumentException("At least one solution is of different length.");


81 


82  IList<Permutation> solutions = new List<Permutation>();


83  for (int i = 0; i < v1.Length; i++) {


84  int currCityIndex = i;


85  int bestCityIndex = (i + 1) % v1.Length;


86  double currDistance = distances[v1[currCityIndex], v1[bestCityIndex]];


87  // check each guiding solution


88  targets.ToList().ForEach(solution => {


89  // locate current city


90  var node = solution.Select((x, index) => new { Id = x, Index = index }).Single(x => x.Id == v1[currCityIndex]);


91  int pred = solution[(node.Index  1 + solution.Length) % solution.Length];


92  int succ = solution[(node.Index + 1) % solution.Length];


93  // get distances to neighbors


94  var results = new[] { pred, succ }.Select(x => new { Id = x, Distance = distances[x, node.Id] });


95  var bestCity = results.Where(x => x.Distance < currDistance).OrderBy(x => x.Distance).FirstOrDefault();


96  if (bestCity != null) {


97  bestCityIndex = v1.Select((x, index) => new { Id = x, Index = index }).Single(x => x.Id == bestCity.Id).Index;


98  currDistance = bestCity.Distance;


99  }


100  });


101  Invert(v1, currCityIndex + 1, bestCityIndex);


102  solutions.Add(v1.Clone() as Permutation);


103  }


104 


105  IList<IItem> selection = new List<IItem>();


106  if (solutions.Count > 0) {


107  int noSol = (int)(solutions.Count * n.Value);


108  if (noSol <= 0) noSol++;


109  double stepSize = (double)solutions.Count / (double)noSol;


110  for (int i = 0; i < noSol; i++)


111  selection.Add(solutions.ElementAt((int)((i + 1) * stepSize  stepSize * 0.5)));


112  }


113 


114  return new ItemArray<IItem>(selection);


115  }


116 


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


118  if (i != j)


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


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


121  // XOR swap


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


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


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


125  }


126  }


127 


128  protected override ItemArray<IItem> Relink(ItemArray<IItem> parents, PercentValue n) {


129  if (parents.Length < 2)


130  throw new ArgumentException("The number of parents is smaller than 2.");


131  return Apply(parents[0], parents.Skip(1).ToArray(), DistanceMatrix, n);


132  }


133  }


134  }

