Free cookie consent management tool by TermsFeed Policy Generator

source: stable/HeuristicLab.Problems.TravelingSalesman/3.3/PathRelinkers/TSPSimultaneousPathRelinker.cs @ 17097

Last change on this file since 17097 was 17097, checked in by mkommend, 5 years ago

#2520: Merged 16565 - 16579 into stable.

File size: 4.9 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2019 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 HEAL.Attic;
31
32namespace HeuristicLab.Problems.TravelingSalesman {
33  /// <summary>
34  /// An operator that relinks paths between traveling salesman solutions starting from both ends.
35  /// </summary>
36  /// <remarks>
37  /// The operator incrementally assimilates the initiating solution into the guiding solution and vice versa by correcting edges as needed.
38  /// </remarks>
39  [Item("TSPSimultaneousPathRelinker", "An operator that relinks paths between traveling salesman solutions starting from both ends. The operator incrementally assimilates the initiating solution into the guiding solution and vice versa by correcting edges as needed.")]
40  [StorableType("D44D112E-5139-4848-8A2B-66CFC5784EE4")]
41  public sealed class TSPSimultaneousPathRelinker : SingleObjectivePathRelinker {
42    [StorableConstructor]
43    private TSPSimultaneousPathRelinker(StorableConstructorFlag _) : base(_) { }
44    private TSPSimultaneousPathRelinker(TSPSimultaneousPathRelinker original, Cloner cloner) : base(original, cloner) { }
45    public TSPSimultaneousPathRelinker() : base() { }
46
47    public override IDeepCloneable Clone(Cloner cloner) {
48      return new TSPSimultaneousPathRelinker(this, cloner);
49    }
50
51    public static ItemArray<IItem> Apply(IItem initiator, IItem guide, PercentValue n) {
52      if (!(initiator is Permutation) || !(guide is Permutation))
53        throw new ArgumentException("Cannot relink path because one of the provided solutions or both have the wrong type.");
54      if (n.Value <= 0.0)
55        throw new ArgumentException("RelinkingAccuracy must be greater than 0.");
56
57      Permutation firstInitiator = initiator.Clone() as Permutation;
58      Permutation firstGuide = guide.Clone() as Permutation;
59      Permutation secondInitiator = firstGuide.Clone() as Permutation;
60      Permutation secondGuide = firstInitiator.Clone() as Permutation;
61
62      if (firstInitiator.Length != firstGuide.Length)
63        throw new ArgumentException("The solutions are of different length.");
64
65      IList<Permutation> solutions = new List<Permutation>();
66      for (int i = 0; i < firstInitiator.Length / 2; i++) {
67        if (firstInitiator[i] != firstGuide[i]) {
68          var target = firstInitiator.Select((x, index) => new { Value = x, ValueIndex = index }).First(x => x.Value == firstGuide[i]);
69          // XOR swap
70          firstInitiator[i] ^= firstInitiator[target.ValueIndex];
71          firstInitiator[target.ValueIndex] ^= firstInitiator[i];
72          firstInitiator[i] ^= firstInitiator[target.ValueIndex];
73          solutions.Add(firstInitiator.Clone() as Permutation);
74        }
75        int j = secondInitiator.Length - 1 - i;
76        if (secondInitiator[j] != secondGuide[j]) {
77          var target = secondInitiator.Select((x, index) => new { Value = x, ValueIndex = index }).First(x => x.Value == secondGuide[j]);
78          // XOR swap
79          secondInitiator[j] ^= secondInitiator[target.ValueIndex];
80          secondInitiator[target.ValueIndex] ^= secondInitiator[j];
81          secondInitiator[j] ^= secondInitiator[target.ValueIndex];
82          solutions.Add(secondInitiator.Clone() as Permutation);
83        }
84      }
85
86      IList<IItem> selection = new List<IItem>();
87      if (solutions.Count > 0) {
88        int noSol = (int)(solutions.Count * n.Value);
89        if (noSol <= 0) noSol++;
90        double stepSize = (double)solutions.Count / (double)noSol;
91        for (int i = 0; i < noSol; i++)
92          selection.Add(solutions.ElementAt((int)((i + 1) * stepSize - stepSize * 0.5)));
93      }
94
95      return new ItemArray<IItem>(selection);
96    }
97
98    protected override ItemArray<IItem> Relink(ItemArray<IItem> parents, PercentValue n) {
99      if (parents.Length != 2)
100        throw new ArgumentException("The number of parents is not equal to 2.");
101      return Apply(parents[0], parents[1], n);
102    }
103  }
104}
Note: See TracBrowser for help on using the repository browser.