Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Crossovers/MaximalPreservativeCrossover.cs @ 12012

Last change on this file since 12012 was 12012, checked in by ascheibe, 9 years ago

#2212 merged r12008, r12009, r12010 back into trunk

File size: 8.1 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2015 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 HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
26
27namespace HeuristicLab.Encodings.PermutationEncoding {
28  /// <summary>An operator which performs the maximal preservative crossover on two permutations.</summary>
29  /// <remarks>
30  /// Performs a crossover between two permuation arrays by preserving a large number of edges in both parents.
31  /// The operator also maintains the position in the arrays to some extent.
32  /// It is implemented as described in Mühlenbein, H. 1991. Evolution in time and space - the parallel genetic algorithm. FOUNDATIONS OF GENETIC ALGORITHMS, pp. 316-337. Morgan Kaufmann.<br /><br />
33  /// The length of the segment copied from the first parent to the offspring is uniformly distributed in the interval [3;N/3) with N = length of the permutation.
34  /// This recommendation is mentioned in Pohlheim, H. 1999. Evolutionäre Algorithmen: Verfahren, Operatoren und Hinweise für die Praxis, p. 44, Springer.
35  /// If the length of the permutation is smaller than 15, the size of the segment is always equal to 3.
36  /// </remarks>
37  [Item("MaximalPreservativeCrossover", "An operator which performs the maximal preservative crossover on two permutations. It is implemented as described in Mühlenbein, H. 1991. Evolution in time and space - the parallel genetic algorithm. FOUNDATIONS OF GENETIC ALGORITHMS, pp. 316-337. Morgan Kaufmann.")]
38  [StorableClass]
39  public class MaximalPreservativeCrossover : PermutationCrossover {
40    [StorableConstructor]
41    protected MaximalPreservativeCrossover(bool deserializing) : base(deserializing) { }
42    protected MaximalPreservativeCrossover(MaximalPreservativeCrossover original, Cloner cloner) : base(original, cloner) { }
43    public MaximalPreservativeCrossover() : base() { }
44
45    public override IDeepCloneable Clone(Cloner cloner) {
46      return new MaximalPreservativeCrossover(this, cloner);
47    }
48
49    /// <summary>
50    /// Performs the maximal preservative crossover on <paramref name="parent1"/> and <paramref name="parent2"/>
51    /// by preserving a large number of edges in both parents.
52    /// </summary>
53    /// <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>
54    /// <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>
55    /// <remarks>
56    /// First one segment is copied from the first parent to the offspring in the same position.
57    /// Then the tour is completed by adding the next number from the second parent if such an edge exists,
58    /// or from the first parent, or from the next number of the second parent.
59    /// The last case results in an unwanted mutation.
60    /// </remarks>
61    /// <param name="random">A random number generator.</param>
62    /// <param name="parent1">The first parent permutation to cross.</param>
63    /// <param name="parent2">The second parent permutation to cross.</param>
64    /// <returns>The new permutation resulting from the crossover.</returns>
65    public static Permutation Apply(IRandom random, Permutation parent1, Permutation parent2) {
66      if (parent1.Length != parent2.Length) throw new ArgumentException("MaximalPreservativeCrossover: The parent permutations are of unequal length.");
67      if (parent1.Length < 4) throw new ArgumentException("MaximalPreservativeCrossover: The parent permutation must be at least of size 4.");
68      int length = parent1.Length;
69      int[] result = new int[length];
70      bool[] numberCopied = new bool[length];
71      int breakPoint1, breakPoint2, subsegmentLength, index;
72
73      subsegmentLength = random.Next(3, Math.Max(length / 3, 4)); // as mentioned in Pohlheim, H. Evolutionäre Algorithmen: Verfahren, Operatoren und Hinweise für die Praxis, 1999, p.44, Springer.
74      breakPoint1 = random.Next(length);
75      breakPoint2 = breakPoint1 + subsegmentLength;
76      if (breakPoint2 >= length) breakPoint2 -= length;
77
78      // copy string between position [breakPoint1, breakPoint2) from parent1 to the offspring
79      index = breakPoint1;
80      do {
81        result[index] = parent1[index];
82        numberCopied[result[index]] = true;
83        index++;
84        if (index >= length) index -= length;
85      } while (index != breakPoint2);
86
87      // calculate inverse permutation (number -> index) to help finding the follower of a given number
88      int[] invParent1 = new int[length];
89      int[] invParent2 = new int[length];
90      try {
91        for (int i = 0; i < length; i++) {
92          invParent1[parent1[i]] = i;
93          invParent2[parent2[i]] = i;
94        }
95      }
96      catch (IndexOutOfRangeException) {
97        throw new InvalidOperationException("MaximalPreservativeCrossover: The permutation must consist of numbers in the interval [0;N) with N = length of the permutation.");
98      }
99
100      int prevIndex = ((index > 0) ? (index - 1) : (length - 1));
101      do {
102        // look for the follower of the last number in parent2
103        int p2Follower = GetFollower(parent2, invParent2[result[prevIndex]]);
104        if (!numberCopied[p2Follower]) {
105          result[index] = p2Follower;
106        } else {
107          // if that follower has already been added, look for the follower of the last number in parent1
108          int p1Follower = GetFollower(parent1, invParent1[result[prevIndex]]);
109          if (!numberCopied[p1Follower]) {
110            result[index] = p1Follower;
111          } else {
112            // if that has also been added, look for the next not already added number in parent2
113            int tempIndex = index;
114            for (int i = 0; i < parent2.Length; i++) {
115              if (!numberCopied[parent2[tempIndex]]) {
116                result[index] = parent2[tempIndex];
117                break;
118              }
119              tempIndex++;
120              if (tempIndex >= parent2.Length) tempIndex = 0;
121            }
122          }
123        }
124        numberCopied[result[index]] = true;
125        prevIndex = index;
126        index++;
127        if (index >= length) index -= length;
128      } while (index != breakPoint1);
129
130      return new Permutation(parent1.PermutationType, result);
131    }
132
133    private static int GetFollower(Permutation parent, int index) {
134      if (index + 1 == parent.Length)
135        return parent[0];
136      return parent[index + 1];
137    }
138
139    /// <summary>
140    /// Checks number of parents and calls <see cref="Apply(IRandom, Permutation, Permutation)"/>.
141    /// </summary>
142    /// <exception cref="InvalidOperationException">Thrown if there are not exactly two permutations in <paramref name="parents"/>.</exception>
143    /// <param name="random">A random number generator.</param>
144    /// <param name="parents">An array containing the two permutations that should be crossed.</param>
145    /// <returns>The newly created permutation, resulting from the crossover operation.</returns>
146    protected override Permutation Cross(IRandom random, ItemArray<Permutation> parents) {
147      if (parents.Length != 2) throw new InvalidOperationException("MaximalPreservativeCrossover: Number of parents is not equal to 2.");
148      return Apply(random, parents[0], parents[1]);
149    }
150  }
151}
Note: See TracBrowser for help on using the repository browser.