1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022013 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.Common;


24  using HeuristicLab.Core;


25  using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;


26 


27  namespace HeuristicLab.Encodings.PermutationEncoding {


28  /// <summary>


29  /// An operator which performs the cyclic crossover on two permutations.


30  /// </summary>


31  /// <remarks>It is implemented as described in Eiben, A.E. and Smith, J.E. 2003. Introduction to Evolutionary Computation. Natural Computing Series, SpringerVerlag Berlin Heidelberg.<br />


32  /// The operator first determines all cycles in the permutation and then composes the offspring by alternating between the cycles of the two parents.


33  /// </remarks>


34  [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, SpringerVerlag Berlin Heidelberg.")]


35  [StorableClass]


36  public class CyclicCrossover : PermutationCrossover {


37  [StorableConstructor]


38  protected CyclicCrossover(bool deserializing) : base(deserializing) { }


39  protected CyclicCrossover(CyclicCrossover original, Cloner cloner) : base(original, cloner) { }


40  public CyclicCrossover() : base() { }


41 


42  public override IDeepCloneable Clone(Cloner cloner) {


43  return new CyclicCrossover(this, cloner);


44  }


45 


46  /// <summary>


47  /// Performs the cyclic crossover on <paramref name="parent1"/> and <paramref name="parent2"/>.


48  /// </summary>


49  /// <exception cref="ArgumentException">Thrown when <paramref name="parent1"/> and <paramref name="parent2"/> are not of equal length.</exception>


50  /// <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>


51  /// <remarks>


52  /// First this method randomly determines from which parent to start with equal probability.


53  /// Then it copies the first cycle from the chosen parent starting from index 0 in the permutation.


54  /// 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.


55  /// It continues to switch between parents for each completed cycle until no new cycle is found anymore.<br /><br />


56  /// The stochasticity of this operator is rather low. There are only two possible outcomes for a given pair of parents.


57  /// </remarks>


58  /// <exception cref="ArgumentException">Thrown if the two parents are not of equal length.</exception>


59  /// <param name="random">The random number generator.</param>


60  /// <param name="parent1">The parent scope 1 to cross over.</param>


61  /// <param name="parent2">The parent scope 2 to cross over.</param>


62  /// <returns>The created cross over permutation as int array.</returns>


63  public static Permutation Apply(IRandom random, Permutation parent1, Permutation parent2) {


64  if (parent1.Length != parent2.Length) throw new ArgumentException("CyclicCrossover: The parent permutations are of unequal length.");


65  int length = parent1.Length;


66  int[] result = new int[length];


67  bool[] indexCopied = new bool[length];


68  int[] invParent1 = new int[length];


69  int[] invParent2 = new int[length];


70 


71  // calculate inverse mappings (number > index) for parent1 and parent2


72  try {


73  for (int i = 0; i < length; i++) {


74  invParent1[parent1[i]] = i;


75  invParent2[parent2[i]] = i;


76  }


77  }


78  catch (IndexOutOfRangeException) {


79  throw new InvalidOperationException("CyclicCrossover: The permutation must consist of numbers in the interval [0;N) with N = length of the permutation.");


80  }


81 


82  // randomly choose whether to start copying from parent1 or parent2


83  bool copyFromParent1 = ((random.NextDouble() < 0.5) ? (false) : (true));


84 


85  int j = 0;


86  do {


87  do {


88  if (copyFromParent1) {


89  result[j] = parent1[j]; // copy number at position j from parent1


90  indexCopied[j] = true;


91  j = invParent2[result[j]]; // set position j to the position of the copied number in parent2


92  } else {


93  result[j] = parent2[j]; // copy number at position j from parent2


94  indexCopied[j] = true;


95  j = invParent1[result[j]]; // set position j to the position of the copied number in parent1


96  }


97  } while (!indexCopied[j]);


98  copyFromParent1 = !copyFromParent1;


99  j = 0;


100  while (j < length && indexCopied[j]) j++;


101  } while (j < length);


102 


103  return new Permutation(parent1.PermutationType, result);


104  }


105 


106  /// <summary>


107  /// Checks number of parents and calls <see cref="Apply(IRandom, Permutation, Permutation)"/>.


108  /// </summary>


109  /// <exception cref="InvalidOperationException">Thrown if there are not exactly two parents.</exception>


110  /// <param name="random">A random number generator.</param>


111  /// <param name="parents">An array containing the two permutations that should be crossed.</param>


112  /// <returns>The newly created permutation, resulting from the crossover operation.</returns>


113  protected override Permutation Cross(IRandom random, ItemArray<Permutation> parents) {


114  if (parents.Length != 2) throw new InvalidOperationException("CyclicCrossover: The number of parents is not equal to 2.");


115  return Apply(random, parents[0], parents[1]);


116  }


117  }


118  }

