1 | #region License Information
|
---|
2 | /* HeuristicLab
|
---|
3 | * Copyright (C) 2002-2010 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 |
|
---|
22 | using System;
|
---|
23 | using HeuristicLab.Core;
|
---|
24 | using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
|
---|
25 |
|
---|
26 | namespace HeuristicLab.Permutation {
|
---|
27 | /// <summary>
|
---|
28 | /// An operator which performs the partially matched crossover on two permutations.
|
---|
29 | /// </summar>
|
---|
30 | /// <remarks>
|
---|
31 | /// Implemented as described in Fogel, D.B. 1988. An Evolutionary Approach to the Traveling Salesman Problem. Biological Cybernetics, 60, pp. 139-144, Springer-Verlag.
|
---|
32 | /// 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.
|
---|
33 | /// as the original source of the operator.
|
---|
34 | /// </remarks>
|
---|
35 | [Item("PartiallyMatchedCrossover", "An operator which performs the partially matched crossover on two permutations.")]
|
---|
36 | [EmptyStorableClass]
|
---|
37 | [Creatable("Test")]
|
---|
38 | public class PartiallyMatchedCrossover : PermutationCrossover {
|
---|
39 | /// <summary>
|
---|
40 | /// Performs the partially matched crossover on <paramref name="parent1"/> and <paramref name="parent2"/>.
|
---|
41 | /// </summary>
|
---|
42 | /// <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>
|
---|
43 | /// <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>
|
---|
44 | /// <remarks>
|
---|
45 | /// Initially the new offspring is a clone of <paramref name="parent2"/>.
|
---|
46 | /// Then a segment is extracted from <paramref name="parent1"/> and copied to the offspring position by position.
|
---|
47 | /// 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.
|
---|
48 | /// 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.
|
---|
49 | /// The '5' in the offspring is then moved to replace the '3' in the offspring and '3' is written at position 15.
|
---|
50 | /// </remarks>
|
---|
51 | /// <param name="random">A random number generator.</param>
|
---|
52 | /// <param name="parent1">The first parent permutation to cross.</param>
|
---|
53 | /// <param name="parent2">The second parent permutation to cross.</param>
|
---|
54 | /// <returns>The new permutation resulting from the crossover.</returns>
|
---|
55 | public static Permutation Apply(IRandom random, Permutation parent1, Permutation parent2) {
|
---|
56 | if (parent1.Length != parent2.Length) throw new ArgumentException("PartiallyMatchedCrossover: The parent permutations are of unequal length.");
|
---|
57 | if (parent1.Length < 4) throw new ArgumentException("PartiallyMatchedCrossover: The parent permutation must be at least of size 4.");
|
---|
58 | int length = parent1.Length;
|
---|
59 | int[] result = new int[length];
|
---|
60 | int[] invResult = new int[length];
|
---|
61 |
|
---|
62 | int breakPoint1, breakPoint2;
|
---|
63 | do {
|
---|
64 | breakPoint1 = random.Next(length - 1);
|
---|
65 | breakPoint2 = random.Next(breakPoint1 + 1, length);
|
---|
66 | } while (breakPoint2 - breakPoint1 >= length - 2); // prevent the case [0,length-1) -> clone of parent1
|
---|
67 |
|
---|
68 | // clone parent2 and calculate inverse permutation (number -> index)
|
---|
69 | try {
|
---|
70 | for (int j = 0; j < length; j++) {
|
---|
71 | result[j] = parent2[j];
|
---|
72 | invResult[result[j]] = j;
|
---|
73 | }
|
---|
74 | } catch (IndexOutOfRangeException) {
|
---|
75 | throw new InvalidOperationException("PartiallyMatchedCrossover: The permutation must consist of consecutive numbers from 0 to N-1 with N = length of the permutation.");
|
---|
76 | }
|
---|
77 |
|
---|
78 | for (int j = breakPoint1; j <= breakPoint2; j++) {
|
---|
79 | int orig = result[j]; // save the former value
|
---|
80 | result[j] = parent1[j]; // overwrite the former value with the new value
|
---|
81 | int index = invResult[result[j]]; // look where the new value is in the offspring
|
---|
82 | result[index] = orig; // write the former value to this position
|
---|
83 | invResult[orig] = index; // update the inverse mapping
|
---|
84 | // it's not necessary to do 'invResult[result[j]] = j' as this will not be needed again
|
---|
85 | }
|
---|
86 |
|
---|
87 | return new Permutation(result);
|
---|
88 | }
|
---|
89 |
|
---|
90 | /// <summary>
|
---|
91 | /// Checks number of parents and calls <see cref="Apply(Apply(IRandom, Permutation, Permutation)"/>.
|
---|
92 | /// </summary>
|
---|
93 | /// <exception cref="InvalidOperationException">Thrown if there are not exactly two permutations in <paramref name="parents"/>.</exception>
|
---|
94 | /// <param name="random">A random number generator.</param>
|
---|
95 | /// <param name="parents">An array containing the two permutations that should be crossed.</param>
|
---|
96 | /// <returns>The newly created permutation, resulting from the crossover operation.</returns>
|
---|
97 | protected override Permutation Cross(IRandom random, ItemArray<Permutation> parents) {
|
---|
98 | if (parents.Length != 2) throw new InvalidOperationException("PartiallyMatchedCrossover: The number of parents is not equal to 2.");
|
---|
99 | return Apply(random, parents[0], parents[1]);
|
---|
100 | }
|
---|
101 | }
|
---|
102 | }
|
---|