#region License Information /* HeuristicLab * Copyright (C) 2002-2010 Heuristic and Evolutionary Algorithms Laboratory (HEAL) * * This file is part of HeuristicLab. * * HeuristicLab is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * HeuristicLab is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with HeuristicLab. If not, see . */ #endregion using System; using HeuristicLab.Core; using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; using HeuristicLab.Common; namespace HeuristicLab.Encodings.PermutationEncoding { /// /// An operator which performs the cyclic crossover on two permutations. /// /// 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. ///
[Item("CyclicCrossover", "An operator which performs the cyclic crossover on two permutations. 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.")] [StorableClass] public class CyclicCrossover : PermutationCrossover { [StorableConstructor] protected CyclicCrossover(bool deserializing) : base(deserializing) { } protected CyclicCrossover(CyclicCrossover original, Cloner cloner) : base(original, cloner) { } public CyclicCrossover() : base() { } public override IDeepCloneable Clone(Cloner cloner) { return new CyclicCrossover(this, cloner); } /// /// 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. ///
/// Thrown if the two parents are not of equal length. /// 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 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]; bool[] indexCopied = new bool[length]; int[] invParent1 = new int[length]; int[] invParent2 = new int[length]; // 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 numbers in the interval [0;N) with N = length of the permutation."); } // 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 indexCopied[j] = true; 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 indexCopied[j] = true; j = invParent1[result[j]]; // set position j to the position of the copied number in parent1 } } while (!indexCopied[j]); copyFromParent1 = !copyFromParent1; j = 0; while (j < length && indexCopied[j]) j++; } while (j < length); return new Permutation(parent1.PermutationType, result); } /// /// Checks number of parents and calls . /// /// Thrown if there are not exactly two parents. /// A random number generator. /// An array containing the two permutations that should be crossed. /// The newly created permutation, resulting from the crossover operation. 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]); } } }