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

Last change on this file since 17241 was 17241, checked in by abeham, 11 months ago

#2521: worked on refactoring TSP

File size: 5.9 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 HEAL.Attic;
26using HeuristicLab.Common;
27using HeuristicLab.Core;
28using HeuristicLab.Data;
29using HeuristicLab.Encodings.PermutationEncoding;
30using HeuristicLab.Optimization.Operators;
31using HeuristicLab.Parameters;
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("13e879fd-7621-402e-9345-7dbfdd78e3b6")]
42  public sealed class TSPMultipleGuidesPathRelinker : SingleObjectivePathRelinker {
43    [Storable] public ILookupParameter<ITSPData> TSPDataParameter { get; private set; }
44
45    [StorableConstructor]
46    private TSPMultipleGuidesPathRelinker(StorableConstructorFlag _) : base(_) { }
47    private TSPMultipleGuidesPathRelinker(TSPMultipleGuidesPathRelinker original, Cloner cloner)
48      : base(original, cloner) {
49      TSPDataParameter = cloner.Clone(original.TSPDataParameter);
50    }
51    public TSPMultipleGuidesPathRelinker()
52      : base() {
53      Parameters.Add(TSPDataParameter = new LookupParameter<ITSPData>("TSPData", "The main parameters of the TSP."));
54    }
55
56    public override IDeepCloneable Clone(Cloner cloner) {
57      return new TSPMultipleGuidesPathRelinker(this, cloner);
58    }
59
60    public static ItemArray<IItem> Apply(IItem initiator, IItem[] guides, ITSPData tspData, PercentValue n) {
61      if (!(initiator is Permutation) || guides.Any(x => !(x is Permutation)))
62        throw new ArgumentException("Cannot relink path because some of the provided solutions have the wrong type.");
63      if (n.Value <= 0.0)
64        throw new ArgumentException("RelinkingAccuracy must be greater than 0.");
65
66      Permutation v1 = initiator.Clone() as Permutation;
67      Permutation[] targets = new Permutation[guides.Length];
68      Array.Copy(guides, targets, guides.Length);
69
70      if (targets.Any(x => x.Length != v1.Length))
71        throw new ArgumentException("At least one solution is of different length.");
72
73      IList<Permutation> solutions = new List<Permutation>();
74      for (int i = 0; i < v1.Length; i++) {
75        int currCityIndex = i;
76        int bestCityIndex = (i + 1) % v1.Length;
77        double currDistance = tspData.GetDistance(v1[currCityIndex], v1[bestCityIndex]);
78        // check each guiding solution
79        targets.ToList().ForEach(solution => {
80          // locate current city
81          var node = solution.Select((x, index) => new { Id = x, Index = index }).Single(x => x.Id == v1[currCityIndex]);
82          int pred = solution[(node.Index - 1 + solution.Length) % solution.Length];
83          int succ = solution[(node.Index + 1) % solution.Length];
84          // get distances to neighbors
85          var results = new[] { pred, succ }.Select(x => new { Id = x, Distance = tspData.GetDistance(x, node.Id) });
86          var bestCity = results.Where(x => x.Distance < currDistance).OrderBy(x => x.Distance).FirstOrDefault();
87          if (bestCity != null) {
88            bestCityIndex = v1.Select((x, index) => new { Id = x, Index = index }).Single(x => x.Id == bestCity.Id).Index;
89            currDistance = bestCity.Distance;
90          }
91        });
92        Invert(v1, currCityIndex + 1, bestCityIndex);
93        solutions.Add(v1.Clone() as Permutation);
94      }
95
96      IList<IItem> selection = new List<IItem>();
97      if (solutions.Count > 0) {
98        int noSol = (int)(solutions.Count * n.Value);
99        if (noSol <= 0) noSol++;
100        double stepSize = (double)solutions.Count / (double)noSol;
101        for (int i = 0; i < noSol; i++)
102          selection.Add(solutions.ElementAt((int)((i + 1) * stepSize - stepSize * 0.5)));
103      }
104
105      return new ItemArray<IItem>(selection);
106    }
107
108    private static void Invert(Permutation sol, int i, int j) {
109      if (i != j)
110        for (int a = 0; a < Math.Abs(i - j) / 2; a++)
111          if (sol[(i + a) % sol.Length] != sol[(j - a + sol.Length) % sol.Length]) {
112            // XOR swap
113            sol[(i + a) % sol.Length] ^= sol[(j - a + sol.Length) % sol.Length];
114            sol[(j - a + sol.Length) % sol.Length] ^= sol[(i + a) % sol.Length];
115            sol[(i + a) % sol.Length] ^= sol[(j - a + sol.Length) % sol.Length];
116          }
117    }
118
119    protected override ItemArray<IItem> Relink(ItemArray<IItem> parents, PercentValue n) {
120      if (parents.Length < 2)
121        throw new ArgumentException("The number of parents is smaller than 2.");
122      return Apply(parents[0], parents.Skip(1).ToArray(), TSPDataParameter.ActualValue, n);
123    }
124  }
125}
Note: See TracBrowser for help on using the repository browser.