- Timestamp:
- 02/18/10 20:42:37 (15 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/sources/HeuristicLab.Permutation/3.3/CyclicCrossover.cs
r1530 r2829 1 1 #region License Information 2 2 /* HeuristicLab 3 * Copyright (C) 2002-20 08Heuristic and Evolutionary Algorithms Laboratory (HEAL)3 * Copyright (C) 2002-2010 Heuristic and Evolutionary Algorithms Laboratory (HEAL) 4 4 * 5 5 * This file is part of HeuristicLab. … … 21 21 22 22 using System; 23 using System.Collections.Generic;24 using System.Text;25 23 using HeuristicLab.Core; 26 using HeuristicLab. Data;24 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; 27 25 28 26 namespace HeuristicLab.Permutation { 29 27 /// <summary> 30 /// Performs a cross over permutation between two int arrays by taking first a whole cycle and then the 31 /// missing ones from the second parent. 28 /// An operator which performs the cyclic crossover on two permutations. 32 29 /// </summary> 33 /// <remarks>A whole cycle means: <br/> 34 /// Start at a randomly chosen position x in parent1 and transfer it to the child at the same position. 35 /// Now this position x is no longer available for the node on position x in parent2, so 36 /// the value of the node at position x in parent2 is searched in parent1 and is then transferred 37 /// to the child preserving the position. Now this new position y is no longer available for the node in parent2 ....<br/> 38 /// This procedure is repeated till it is again at position x, then the cycle is over. 30 /// <remarks>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.<br /> 31 /// The operator first determines all cycles in the permutation and then composes the offspring by alternating between the cycles of the two parents. 39 32 /// </remarks> 40 public class CyclicCrossover : PermutationCrossoverBase { 41 /// <inheritdoc select="summary"/> 42 public override string Description { 43 get { return @"TODO\r\nOperator description still missing ..."; } 44 } 45 33 [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.")] 34 [EmptyStorableClass] 35 [Creatable("Test")] 36 public class CyclicCrossover : PermutationCrossover { 46 37 /// <summary> 47 /// Performs a cross over permutation of <paramref name="parent1"/> and <paramref name="parent2"/> 48 /// by copying a whole cycle starting at a randomly chosen position in parent1 and taking the rest 49 /// from parent2. 38 /// Performs the cyclic crossover on <paramref name="parent1"/> and <paramref name="parent2"/>. 50 39 /// </summary> 40 /// <exception cref="ArgumentException">Thrown when <paramref name="parent1"/> and <paramref name="parent2"/> are not of equal length.</exception> 41 /// <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> 42 /// <remarks> 43 /// First this method randomly determines from which parent to start with equal probability. 44 /// Then it copies the first cycle from the chosen parent starting from index 0 in the permutation. 45 /// 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. 46 /// It continues to switch between parents for each completed cycle until no new cycle is found anymore.<br /><br /> 47 /// The stochasticity of this operator is rather low. There are only two possible outcomes for a given pair of parents. 48 /// </remarks> 51 49 /// <param name="random">The random number generator.</param> 52 50 /// <param name="parent1">The parent scope 1 to cross over.</param> 53 51 /// <param name="parent2">The parent scope 2 to cross over.</param> 54 52 /// <returns>The created cross over permutation as int array.</returns> 55 public static int[] Apply(IRandom random, int[] parent1, int[] parent2) { 53 public static Permutation Apply(IRandom random, Permutation parent1, Permutation parent2) { 54 if (parent1.Length != parent2.Length) throw new ArgumentException("CyclicCrossover: The parent permutations are of unequal length"); 56 55 int length = parent1.Length; 57 int[] result = new int[length];56 Permutation result = new Permutation(length); 58 57 bool[] indexCopied = new bool[length]; 59 int j, number; 58 int[] invParent1 = new int[length]; 59 int[] invParent2 = new int[length]; 60 60 61 j = random.Next(length); // get number to start cycle 62 while (!indexCopied[j]) { // copy whole cycle to new permutation 63 result[j] = parent1[j]; 64 number = parent2[j]; 65 indexCopied[j] = true; 66 67 j = 0; 68 while ((j < length) && (parent1[j] != number)) { // search copied number in second permutation 69 j++; 61 // calculate inverse mappings (number -> index) for parent1 and parent2 62 try { 63 for (int i = 0; i < length; i++) { 64 invParent1[parent1[i]] = i; 65 invParent2[parent2[i]] = i; 70 66 } 67 } catch (IndexOutOfRangeException) { 68 throw new InvalidOperationException("CyclicCrossover: The permutation must consist of consecutive numbers from 0 to N-1 with N = length of the permutation"); 71 69 } 72 70 73 for (int i = 0; i < length; i++) { // copy rest of secound permutation to new permutation 74 if (!indexCopied[i]) { 75 result[i] = parent2[i]; 76 } 77 } 71 // randomly choose whether to start copying from parent1 or parent2 72 bool copyFromParent1 = ((random.NextDouble() < 0.5) ? (false) : (true)); 73 74 int j = 0; 75 do { 76 do { 77 if (copyFromParent1) { 78 result[j] = parent1[j]; // copy number at position j from parent1 79 j = invParent2[result[j]]; // set position j to the position of the copied number in parent2 80 } else { 81 result[j] = parent2[j]; // copy number at position j from parent2 82 j = invParent1[result[j]]; // set position j to the position of the copied number in parent1 83 } 84 indexCopied[j] = true; 85 } while (!indexCopied[j]); 86 copyFromParent1 = !copyFromParent1; 87 j = 0; 88 while (j < length && indexCopied[j]) j++; 89 } while (j < length); 90 78 91 return result; 79 92 } 80 93 81 94 /// <summary> 82 /// Performs a cyclic crossover operation for two given parent permutations.95 /// Checks number of parents and calls <see cref="Apply(IRandom, Permutation, Permutation)"/>. 83 96 /// </summary> 84 97 /// <exception cref="InvalidOperationException">Thrown if there are not exactly two parents.</exception> … … 87 100 /// <param name="parents">An array containing the two permutations that should be crossed.</param> 88 101 /// <returns>The newly created permutation, resulting from the crossover operation.</returns> 89 protected override int[] Cross(IScope scope, IRandom random, int[][]parents) {90 if (parents.Length != 2) throw new InvalidOperationException(" ERROR inCyclicCrossover: The number of parents is not equal to 2");102 protected override Permutation Cross(IRandom random, ItemArray<Permutation> parents) { 103 if (parents.Length != 2) throw new InvalidOperationException("CyclicCrossover: The number of parents is not equal to 2"); 91 104 return Apply(random, parents[0], parents[1]); 92 105 }
Note: See TracChangeset
for help on using the changeset viewer.