source: branches/2994-AutoDiffForIntervals/HeuristicLab.Encodings.PermutationEncoding/3.3/Crossovers/PartiallyMatchedCrossover.cs @ 17209

Last change on this file since 17209 was 17209, checked in by gkronber, 4 months ago

#2994: merged r17132:17198 from trunk to branch

File size: 6.5 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 HeuristicLab.Common;
24using HeuristicLab.Core;
25using HEAL.Attic;
26
27namespace HeuristicLab.Encodings.PermutationEncoding {
28  /// <summary>
29  /// An operator which performs the partially matched crossover on two permutations.
30  /// </summary>
31  /// <remarks>
32  /// It is implemented as described in Fogel, D.B. 1988. An Evolutionary Approach to the Traveling Salesman Problem. Biological Cybernetics, 60, pp. 139-144, Springer-Verlag.
33  /// which references Goldberg, D.E., and Lingle, R. 1985. Alleles, loci, and the traveling salesman problem. Proceedings of an International Conference on Genetic Algorithms and their Applications. Carnegie-Mellon University, pp. 154-159.
34  /// as the original source of the operator.
35  /// </remarks>
36  [Item("PartiallyMatchedCrossover", "An operator which performs the partially matched crossover on two permutations. It is implemented as described in Fogel, D.B. 1988. An Evolutionary Approach to the Traveling Salesman Problem. Biological Cybernetics, 60, pp. 139-144, Springer-Verlag.")]
37  [StorableType("BE92E88C-0A05-4E56-884A-BAFFE6A86F4F")]
38  public class PartiallyMatchedCrossover : PermutationCrossover {
39    [StorableConstructor]
40    protected PartiallyMatchedCrossover(StorableConstructorFlag _) : base(_) { }
41    protected PartiallyMatchedCrossover(PartiallyMatchedCrossover original, Cloner cloner) : base(original, cloner) { }
42    public PartiallyMatchedCrossover() : base() { }
43
44    public override IDeepCloneable Clone(Cloner cloner) {
45      return new PartiallyMatchedCrossover(this, cloner);
46    }
47
48    /// <summary>
49    /// Performs the partially matched crossover on <paramref name="parent1"/> and <paramref name="parent2"/>.
50    /// </summary>
51    /// <exception cref="ArgumentException">Thrown when <paramref name="parent1"/> and <paramref name="parent2"/> are not of equal length or when the permutations are shorter than 4 elements.</exception>
52    /// <exception cref="InvalidOperationException">Thrown if the numbers in the permutation elements are not in the range [0,N) with N = length of the permutation.</exception>
53    /// <remarks>
54    /// Initially the new offspring is a clone of <paramref name="parent2"/>.
55    /// Then a segment is extracted from <paramref name="parent1"/> and copied to the offspring position by position.
56    /// Whenever a position is copied, the number at that position currently in the offspring is transfered to the position where the copied number has been.
57    /// E.g.: Position 15 is selected to be copied from <paramref name="parent1"/> to <paramref name="parent2"/>. At position 15 there is a '3' in <paramref name="parent1"/> and a '5' in the new offspring.
58    /// The '5' in the offspring is then moved to replace the '3' in the offspring and '3' is written at position 15.
59    /// </remarks>
60    /// <param name="random">A random number generator.</param>
61    /// <param name="parent1">The first parent permutation to cross.</param>
62    /// <param name="parent2">The second parent permutation to cross.</param>
63    /// <returns>The new permutation resulting from the crossover.</returns>
64    public static Permutation Apply(IRandom random, Permutation parent1, Permutation parent2) {
65      if (parent1.Length != parent2.Length) throw new ArgumentException("PartiallyMatchedCrossover: The parent permutations are of unequal length.");
66      if (parent1.Length < 4) throw new ArgumentException("PartiallyMatchedCrossover: The parent permutation must be at least of size 4.");
67      int length = parent1.Length;
68      int[] result = new int[length];
69      int[] invResult = new int[length];
70
71      int breakPoint1, breakPoint2;
72      do {
73        breakPoint1 = random.Next(length - 1);
74        breakPoint2 = random.Next(breakPoint1 + 1, length);
75      } while (breakPoint2 - breakPoint1 >= length - 2); // prevent the case [0,length-1) -> clone of parent1
76
77      // clone parent2 and calculate inverse permutation (number -> index)
78      try {
79        for (int j = 0; j < length; j++) {
80          result[j] = parent2[j];
81          invResult[result[j]] = j;
82        }
83      }
84      catch (IndexOutOfRangeException) {
85        throw new InvalidOperationException("PartiallyMatchedCrossover: The permutation must consist of consecutive numbers from 0 to N-1 with N = length of the permutation.");
86      }
87
88      for (int j = breakPoint1; j <= breakPoint2; j++) {
89        int orig = result[j]; // save the former value
90        result[j] = parent1[j]; // overwrite the former value with the new value
91        int index = invResult[result[j]]; // look where the new value is in the offspring
92        result[index] = orig; // write the former value to this position
93        invResult[orig] = index; // update the inverse mapping
94        // it's not necessary to do 'invResult[result[j]] = j' as this will not be needed again
95      }
96
97      return new Permutation(parent1.PermutationType, result);
98    }
99
100    /// <summary>
101    /// Checks number of parents and calls <see cref="Apply(IRandom, Permutation, Permutation)"/>.
102    /// </summary>
103    /// <exception cref="InvalidOperationException">Thrown if there are not exactly two permutations in <paramref name="parents"/>.</exception>
104    /// <param name="random">A random number generator.</param>
105    /// <param name="parents">An array containing the two permutations that should be crossed.</param>
106    /// <returns>The newly created permutation, resulting from the crossover operation.</returns>
107    protected override Permutation Cross(IRandom random, ItemArray<Permutation> parents) {
108      if (parents.Length != 2) throw new InvalidOperationException("PartiallyMatchedCrossover: The number of parents is not equal to 2.");
109      return Apply(random, parents[0], parents[1]);
110    }
111  }
112}
Note: See TracBrowser for help on using the repository browser.