[2] | 1 | #region License Information
|
---|
| 2 | /* HeuristicLab
|
---|
[2820] | 3 | * Copyright (C) 2002-2010 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
|
---|
[2] | 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 |
|
---|
| 22 | using System;
|
---|
[3376] | 23 | using HeuristicLab.Common;
|
---|
[2] | 24 | using HeuristicLab.Core;
|
---|
[2820] | 25 | using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
|
---|
[2] | 26 |
|
---|
[3053] | 27 | namespace HeuristicLab.Encodings.PermutationEncoding {
|
---|
[2820] | 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.
|
---|
[2835] | 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.
|
---|
[2829] | 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.
|
---|
[2820] | 36 | /// </remarks>
|
---|
[2871] | 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.")]
|
---|
[3017] | 38 | [StorableClass]
|
---|
[2820] | 39 | public class MaximalPreservativeCrossover : PermutationCrossover {
|
---|
[850] | 40 | /// <summary>
|
---|
[2820] | 41 | /// Performs the maximal preservative crossover on <paramref name="parent1"/> and <paramref name="parent2"/>
|
---|
| 42 | /// by preserving a large number of edges in both parents.
|
---|
[850] | 43 | /// </summary>
|
---|
[2823] | 44 | /// <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>
|
---|
[2835] | 45 | /// <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>
|
---|
[2820] | 46 | /// <remarks>
|
---|
| 47 | /// First one segment is copied from the first parent to the offspring in the same position.
|
---|
| 48 | /// Then the tour is completed by adding the next number from the second parent if such an edge exists,
|
---|
| 49 | /// or from the first parent, or from the next number of the second parent.
|
---|
| 50 | /// The last case results in an unwanted mutation.
|
---|
| 51 | /// </remarks>
|
---|
| 52 | /// <param name="random">A random number generator.</param>
|
---|
| 53 | /// <param name="parent1">The first parent permutation to cross.</param>
|
---|
| 54 | /// <param name="parent2">The second parent permutation to cross.</param>
|
---|
| 55 | /// <returns>The new permutation resulting from the crossover.</returns>
|
---|
| 56 | public static Permutation Apply(IRandom random, Permutation parent1, Permutation parent2) {
|
---|
[2835] | 57 | if (parent1.Length != parent2.Length) throw new ArgumentException("MaximalPreservativeCrossover: The parent permutations are of unequal length.");
|
---|
| 58 | if (parent1.Length < 4) throw new ArgumentException("MaximalPreservativeCrossover: The parent permutation must be at least of size 4.");
|
---|
[2] | 59 | int length = parent1.Length;
|
---|
[2830] | 60 | int[] result = new int[length];
|
---|
[2] | 61 | bool[] numberCopied = new bool[length];
|
---|
| 62 | int breakPoint1, breakPoint2, subsegmentLength, index;
|
---|
| 63 |
|
---|
[2829] | 64 | 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.
|
---|
[2820] | 65 | breakPoint1 = random.Next(length);
|
---|
| 66 | breakPoint2 = breakPoint1 + subsegmentLength;
|
---|
| 67 | if (breakPoint2 >= length) breakPoint2 -= length;
|
---|
[2] | 68 |
|
---|
[2820] | 69 | // copy string between position [breakPoint1, breakPoint2) from parent1 to the offspring
|
---|
| 70 | index = breakPoint1;
|
---|
| 71 | do {
|
---|
| 72 | result[index] = parent1[index];
|
---|
[2] | 73 | numberCopied[result[index]] = true;
|
---|
| 74 | index++;
|
---|
[2820] | 75 | if (index >= length) index -= length;
|
---|
| 76 | } while (index != breakPoint2);
|
---|
| 77 |
|
---|
| 78 | // calculate inverse permutation (number -> index) to help finding the follower of a given number
|
---|
| 79 | int[] invParent1 = new int[length];
|
---|
| 80 | int[] invParent2 = new int[length];
|
---|
| 81 | try {
|
---|
| 82 | for (int i = 0; i < length; i++) {
|
---|
| 83 | invParent1[parent1[i]] = i;
|
---|
| 84 | invParent2[parent2[i]] = i;
|
---|
| 85 | }
|
---|
| 86 | } catch (IndexOutOfRangeException) {
|
---|
[2835] | 87 | throw new InvalidOperationException("MaximalPreservativeCrossover: The permutation must consist of numbers in the interval [0;N) with N = length of the permutation.");
|
---|
[2] | 88 | }
|
---|
| 89 |
|
---|
[2820] | 90 | int prevIndex = ((index > 0) ? (index - 1) : (length - 1));
|
---|
| 91 | do {
|
---|
| 92 | // look for the follower of the last number in parent2
|
---|
| 93 | int p2Follower = GetFollower(parent2, invParent2[result[prevIndex]]);
|
---|
| 94 | if (!numberCopied[p2Follower]) {
|
---|
| 95 | result[index] = p2Follower;
|
---|
| 96 | } else {
|
---|
| 97 | // if that follower has already been added, look for the follower of the last number in parent1
|
---|
| 98 | int p1Follower = GetFollower(parent1, invParent1[result[prevIndex]]);
|
---|
| 99 | if (!numberCopied[p1Follower]) {
|
---|
| 100 | result[index] = p1Follower;
|
---|
| 101 | } else {
|
---|
| 102 | // if that has also been added, look for the next not already added number in parent2
|
---|
| 103 | int tempIndex = index;
|
---|
| 104 | for (int i = 0; i < parent2.Length; i++) {
|
---|
| 105 | if (!numberCopied[parent2[tempIndex]]) {
|
---|
| 106 | result[index] = parent2[tempIndex];
|
---|
| 107 | break;
|
---|
| 108 | }
|
---|
| 109 | tempIndex++;
|
---|
| 110 | if (tempIndex >= parent2.Length) tempIndex = 0;
|
---|
| 111 | }
|
---|
| 112 | }
|
---|
[2] | 113 | }
|
---|
[2820] | 114 | numberCopied[result[index]] = true;
|
---|
| 115 | prevIndex = index;
|
---|
| 116 | index++;
|
---|
| 117 | if (index >= length) index -= length;
|
---|
| 118 | } while (index != breakPoint1);
|
---|
| 119 |
|
---|
[3231] | 120 | return new Permutation(parent1.PermutationType, result);
|
---|
[2] | 121 | }
|
---|
| 122 |
|
---|
[2820] | 123 | private static int GetFollower(Permutation parent, int index) {
|
---|
| 124 | if (index + 1 == parent.Length)
|
---|
| 125 | return parent[0];
|
---|
| 126 | return parent[index + 1];
|
---|
| 127 | }
|
---|
| 128 |
|
---|
[850] | 129 | /// <summary>
|
---|
[2829] | 130 | /// Checks number of parents and calls <see cref="Apply(IRandom, Permutation, Permutation)"/>.
|
---|
[850] | 131 | /// </summary>
|
---|
[2820] | 132 | /// <exception cref="InvalidOperationException">Thrown if there are not exactly two permutations in <paramref name="parents"/>.</exception>
|
---|
[1218] | 133 | /// <param name="random">A random number generator.</param>
|
---|
| 134 | /// <param name="parents">An array containing the two permutations that should be crossed.</param>
|
---|
| 135 | /// <returns>The newly created permutation, resulting from the crossover operation.</returns>
|
---|
[2820] | 136 | protected override Permutation Cross(IRandom random, ItemArray<Permutation> parents) {
|
---|
| 137 | if (parents.Length != 2) throw new InvalidOperationException("MaximalPreservativeCrossover: Number of parents is not equal to 2.");
|
---|
[1218] | 138 | return Apply(random, parents[0], parents[1]);
|
---|
[2] | 139 | }
|
---|
| 140 | }
|
---|
| 141 | }
|
---|