source: branches/2521_ProblemRefactoring/HeuristicLab.Problems.TravelingSalesman/3.3/PathRelinkers/TSPMultipleGuidesPathRelinker.cs @ 17226

Last change on this file since 17226 was 17226, checked in by mkommend, 12 months ago

#2521: Merged trunk changes into problem refactoring branch.

File size: 6.2 KB
Line 
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
22using System;
23using System.Collections.Generic;
24using System.Linq;
25using HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Data;
28using HeuristicLab.Encodings.PermutationEncoding;
29using HeuristicLab.Optimization.Operators;
30using HeuristicLab.Parameters;
31using HEAL.Attic;
32
33namespace 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("6B5B2622-AB1D-47E6-8BBC-C6088D393149")]
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}
Note: See TracBrowser for help on using the repository browser.