# Changeset 2829

Ignore:
Timestamp:
02/18/10 20:42:37 (11 years ago)
Message:

Implemented CyclicCrossover, updated documentation in MaximalPreservativeCrossover and PartiallyMatchedCrossover #889

Location:
trunk/sources/HeuristicLab.Permutation/3.3
Files:
4 edited

Unmodified
Removed
• ## trunk/sources/HeuristicLab.Permutation/3.3/CyclicCrossover.cs

 r1530 #region License Information /* HeuristicLab * Copyright (C) 2002-2008 Heuristic and Evolutionary Algorithms Laboratory (HEAL) * Copyright (C) 2002-2010 Heuristic and Evolutionary Algorithms Laboratory (HEAL) * * This file is part of HeuristicLab. using System; using System.Collections.Generic; using System.Text; using HeuristicLab.Core; using HeuristicLab.Data; using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; namespace HeuristicLab.Permutation { /// /// Performs a cross over permutation between two int arrays by taking first a whole cycle and then the /// missing ones from the second parent. /// An operator which performs the cyclic crossover on two permutations. /// /// A whole cycle means:
/// Start at a randomly chosen position x in parent1 and transfer it to the child at the same position. /// Now this position x is no longer available for the node on position x in parent2, so /// the value of the node at position x in parent2 is searched in parent1 and is then transferred /// to the child preserving the position. Now this new position y is no longer available for the node in parent2 ....
/// This procedure is repeated till it is again at position x, then the cycle is over. /// It is implemented as described in Eiben, A.E. and Smith, J.E. 2003. Introduction to Evolutionary Computation. Natural Computing Series, Springer-Verlag Berlin Heidelberg.
/// The operator first determines all cycles in the permutation and then composes the offspring by alternating between the cycles of the two parents. ///
public class CyclicCrossover : PermutationCrossoverBase { /// public override string Description { get { return @"TODO\r\nOperator description still missing ..."; } } [Item("CyclicCrossover", "An operator which performs the cyclic crossover on two permutations as described in Eiben, A.E. and Smith, J.E. 2003. Introduction to Evolutionary Computation. Natural Computing Series, Springer-Verlag Berlin Heidelberg.")] [EmptyStorableClass] [Creatable("Test")] public class CyclicCrossover : PermutationCrossover { /// /// Performs a cross over permutation of and /// by copying a whole cycle starting at a randomly chosen position in parent1 and taking the rest /// from parent2. /// Performs the cyclic crossover on and . /// /// Thrown when and are not of equal length. /// Thrown if the numbers in the permutation elements are not in the range [0,N) with N = length of the permutation. /// /// First this method randomly determines from which parent to start with equal probability. /// Then it copies the first cycle from the chosen parent starting from index 0 in the permutation. /// After the cycle is complete it copies the next cycle starting from the index closest to 0 which was not yet copied from the other parent. /// It continues to switch between parents for each completed cycle until no new cycle is found anymore.

/// The stochasticity of this operator is rather low. There are only two possible outcomes for a given pair of parents. ///
/// The random number generator. /// The parent scope 1 to cross over. /// The parent scope 2 to cross over. /// The created cross over permutation as int array. public static int[] Apply(IRandom random, int[] parent1, int[] parent2) { public static Permutation Apply(IRandom random, Permutation parent1, Permutation parent2) { if (parent1.Length != parent2.Length) throw new ArgumentException("CyclicCrossover: The parent permutations are of unequal length"); int length = parent1.Length; int[] result = new int[length]; Permutation result = new Permutation(length); bool[] indexCopied = new bool[length]; int j, number; int[] invParent1 = new int[length]; int[] invParent2 = new int[length]; j = random.Next(length);  // get number to start cycle while (!indexCopied[j]) {  // copy whole cycle to new permutation result[j] = parent1[j]; number = parent2[j]; indexCopied[j] = true; j = 0; while ((j < length) && (parent1[j] != number)) {  // search copied number in second permutation j++; // calculate inverse mappings (number -> index) for parent1 and parent2 try { for (int i = 0; i < length; i++) { invParent1[parent1[i]] = i; invParent2[parent2[i]] = i; } } catch (IndexOutOfRangeException) { throw new InvalidOperationException("CyclicCrossover: The permutation must consist of consecutive numbers from 0 to N-1 with N = length of the permutation"); } for (int i = 0; i < length; i++) {  // copy rest of secound permutation to new permutation if (!indexCopied[i]) { result[i] = parent2[i]; } } // randomly choose whether to start copying from parent1 or parent2 bool copyFromParent1 = ((random.NextDouble() < 0.5) ? (false) : (true)); int j = 0; do { do { if (copyFromParent1) { result[j] = parent1[j]; // copy number at position j from parent1 j = invParent2[result[j]]; // set position j to the position of the copied number in parent2 } else { result[j] = parent2[j]; // copy number at position j from parent2 j = invParent1[result[j]]; // set position j to the position of the copied number in parent1 } indexCopied[j] = true; } while (!indexCopied[j]); copyFromParent1 = !copyFromParent1; j = 0; while (j < length && indexCopied[j]) j++; } while (j < length); return result; } /// /// Performs a cyclic crossover operation for two given parent permutations. /// Checks number of parents and calls . /// /// Thrown if there are not exactly two parents. /// An array containing the two permutations that should be crossed. /// The newly created permutation, resulting from the crossover operation. protected override int[] Cross(IScope scope, IRandom random, int[][] parents) { if (parents.Length != 2) throw new InvalidOperationException("ERROR in CyclicCrossover: The number of parents is not equal to 2"); protected override Permutation Cross(IRandom random, ItemArray parents) { if (parents.Length != 2) throw new InvalidOperationException("CyclicCrossover: The number of parents is not equal to 2"); return Apply(random, parents[0], parents[1]); }
• ## trunk/sources/HeuristicLab.Permutation/3.3/HeuristicLab.Permutation-3.3.csproj

 r2820 Code
• ## trunk/sources/HeuristicLab.Permutation/3.3/MaximalPreservativeCrossover.cs

 r2823 /// Performs a crossover between two permuation arrays by preserving a large number of edges in both parents. /// The operator also maintains the position in the arrays to some extent. /// It is implemented as described in Mühlenbein, H. Evolution in time and space - the parallel genetic algorithm. FOUNDATIONS OF GENETIC ALGORITHMS, Morgan Kaufmann, 1991, 316-337. /// 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. /// /// 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. /// This recommendation is mentioned in Pohlheim, H. 1999. Evolutionäre Algorithmen: Verfahren, Operatoren und Hinweise für die Praxis, p. 44, Springer. /// If the length of the permutation is smaller than 15, the size of the segment is always equal to 3. /// [Item("MaximalPreservativeCrossover", "An operator which performs the maximal preservative crossover on two permutations.")] [Item("MaximalPreservativeCrossover", "An operator which performs the maximal preservative crossover on two permutations 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.")] [EmptyStorableClass] [Creatable("Test")] /// by preserving a large number of edges in both parents. /// /// Thrown if the numbers in the permutation array are not in the range [0,N) with N = length of the permutation. /// Thrown when and are not of equal length or when the permutations are shorter than 4 elements. /// Thrown if the numbers in the permutation elements are not in the range [0,N) with N = length of the permutation. /// /// First one segment is copied from the first parent to the offspring in the same position. int breakPoint1, breakPoint2, subsegmentLength, index; 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. 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. breakPoint1 = random.Next(length); breakPoint2 = breakPoint1 + subsegmentLength; /// /// Checks number of parents and calls . /// Checks number of parents and calls . /// /// Thrown if there are not exactly two permutations in .
• ## trunk/sources/HeuristicLab.Permutation/3.3/PartiallyMatchedCrossover.cs

 r2823 /// as the original source of the operator. /// [Item("PartiallyMatchedCrossover", "An operator which performs the partially matched crossover on two permutations.")] [Item("PartiallyMatchedCrossover", "An operator which performs the partially matched crossover on two permutations as described in Fogel, D.B. 1988. An Evolutionary Approach to the Traveling Salesman Problem. Biological Cybernetics, 60, pp. 139-144, Springer-Verlag.")] [EmptyStorableClass] [Creatable("Test")] /// /// Thrown when and are not of equal length or when the permutations are shorter than 4 elements. /// Thrown if the numbers in the permutation elements are not in the range [0,N) with N = length of the permutation. /// /// First a segment from the first parent is copied to the offspring. /// Then the rest of the offspring is filled with the numbers from parent2. /// When a number is encountered in parent2 that is included in the segment which came from the first parent, /// the number in parent2 is used that was replaced by the corresponding number from parent1. /// Initially the new offspring is a clone of . /// Then a segment is extracted from and copied to the offspring position by position. /// 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. /// E.g.: Position 15 is selected to be copied from to . At position 15 there is a '3' in and a '5' in the new offspring. /// The '5' in the offspring is then moved to replace the '3' in the offspring and '3' is written at position 15. /// /// A random number generator. // clone parent2 and calculate inverse permutation (number -> index) for (int j = 0; j < length; j++) { result[j] = parent2[j]; invResult[result[j]] = j; try { for (int j = 0; j < length; j++) { result[j] = parent2[j]; invResult[result[j]] = j; } } catch (IndexOutOfRangeException) { throw new InvalidOperationException("PartiallyMatchedCrossover: The permutation must consist of consecutive numbers from 0 to N-1 with N = length of the permutation"); } int orig = result[j]; // save the former value result[j] = parent1[j]; // overwrite the former value with the new value int index = invResult[result[j]]; // look where the new value is in the child int index = invResult[result[j]]; // look where the new value is in the offspring result[index] = orig; // write the former value to this position invResult[orig] = index; // update the inverse mapping /// /// Checks number of parents and calls . /// Checks number of parents and calls . /// /// Thrown if there are not exactly two permutations in .
Note: See TracChangeset for help on using the changeset viewer.