Changeset 2829


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

Implemented CyclicCrossover, updated documentation in MaximalPreservativeCrossover and PartiallyMatchedCrossover #889

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

Legend:

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

    r1530 r2829  
    11#region License Information
    22/* HeuristicLab
    3  * Copyright (C) 2002-2008 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
     3 * Copyright (C) 2002-2010 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
    44 *
    55 * This file is part of HeuristicLab.
     
    2121
    2222using System;
    23 using System.Collections.Generic;
    24 using System.Text;
    2523using HeuristicLab.Core;
    26 using HeuristicLab.Data;
     24using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2725
    2826namespace HeuristicLab.Permutation {
    2927  /// <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.
    3229  /// </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.
    3932  /// </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 {
    4637    /// <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"/>.
    5039    /// </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>
    5149    /// <param name="random">The random number generator.</param>
    5250    /// <param name="parent1">The parent scope 1 to cross over.</param>
    5351    /// <param name="parent2">The parent scope 2 to cross over.</param>
    5452    /// <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");
    5655      int length = parent1.Length;
    57       int[] result = new int[length];
     56      Permutation result = new Permutation(length);
    5857      bool[] indexCopied = new bool[length];
    59       int j, number;
     58      int[] invParent1 = new int[length];
     59      int[] invParent2 = new int[length];
    6060
    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;
    7066        }
     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");
    7169      }
    7270
    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
    7891      return result;
    7992    }
    8093
    8194    /// <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)"/>.
    8396    /// </summary>
    8497    /// <exception cref="InvalidOperationException">Thrown if there are not exactly two parents.</exception>
     
    87100    /// <param name="parents">An array containing the two permutations that should be crossed.</param>
    88101    /// <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 in CyclicCrossover: 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");
    91104      return Apply(random, parents[0], parents[1]);
    92105    }
  • trunk/sources/HeuristicLab.Permutation/3.3/HeuristicLab.Permutation-3.3.csproj

    r2820 r2829  
    8282  <ItemGroup>
    8383    <None Include="HeuristicLabPermutationPlugin.cs.frame" />
     84    <Compile Include="CyclicCrossover.cs" />
    8485    <Compile Include="InversionManipulator.cs">
    8586      <SubType>Code</SubType>
  • trunk/sources/HeuristicLab.Permutation/3.3/MaximalPreservativeCrossover.cs

    r2823 r2829  
    2929  /// Performs a crossover between two permuation arrays by preserving a large number of edges in both parents.
    3030  /// The operator also maintains the position in the arrays to some extent.
    31   /// 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.
     31  /// 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.
     32  ///
    3233  /// 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.
     34  /// This recommendation is mentioned in Pohlheim, H. 1999. Evolutionäre Algorithmen: Verfahren, Operatoren und Hinweise für die Praxis, p. 44, Springer.
     35  /// If the length of the permutation is smaller than 15, the size of the segment is always equal to 3.
    3336  /// </remarks>
    34   [Item("MaximalPreservativeCrossover", "An operator which performs the maximal preservative crossover on two permutations.")]
     37  [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.")]
    3538  [EmptyStorableClass]
    3639  [Creatable("Test")]
     
    4043    /// by preserving a large number of edges in both parents.
    4144    /// </summary>
    42     /// <exception cref="InvalidOperationException">Thrown if the numbers in the permutation array are not in the range [0,N) with N = length of the permutation.</exception>
    4345    /// <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>
     46    /// <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>
    4447    /// <remarks>
    4548    /// First one segment is copied from the first parent to the offspring in the same position.
     
    6063      int breakPoint1, breakPoint2, subsegmentLength, index;
    6164
    62       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.
     65      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.
    6366      breakPoint1 = random.Next(length);
    6467      breakPoint2 = breakPoint1 + subsegmentLength;
     
    126129
    127130    /// <summary>
    128     /// Checks number of parents and calls <see cref="Apply"/>.
     131    /// Checks number of parents and calls <see cref="Apply(IRandom, Permutation, Permutation)"/>.
    129132    /// </summary>
    130133    /// <exception cref="InvalidOperationException">Thrown if there are not exactly two permutations in <paramref name="parents"/>.</exception>
  • trunk/sources/HeuristicLab.Permutation/3.3/PartiallyMatchedCrossover.cs

    r2823 r2829  
    3333  /// as the original source of the operator.
    3434  /// </remarks>
    35   [Item("PartiallyMatchedCrossover", "An operator which performs the partially matched crossover on two permutations.")]
     35  [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.")]
    3636  [EmptyStorableClass]
    3737  [Creatable("Test")]
     
    4141    /// </summary>
    4242    /// <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>
    4344    /// <remarks>
    44     /// First a segment from the first parent is copied to the offspring.
    45     /// Then the rest of the offspring is filled with the numbers from parent2.
    46     /// When a number is encountered in parent2 that is included in the segment which came from the first parent,
    47     /// the number in parent2 is used that was replaced by the corresponding number from parent1.
     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.
    4850    /// </remarks>
    4951    /// <param name="random">A random number generator.</param>
     
    6567
    6668      // clone parent2 and calculate inverse permutation (number -> index)
    67       for (int j = 0; j < length; j++) {
    68         result[j] = parent2[j];
    69         invResult[result[j]] = j;
     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");
    7076      }
    7177
     
    7379        int orig = result[j]; // save the former value
    7480        result[j] = parent1[j]; // overwrite the former value with the new value
    75         int index = invResult[result[j]]; // look where the new value is in the child
     81        int index = invResult[result[j]]; // look where the new value is in the offspring
    7682        result[index] = orig; // write the former value to this position
    7783        invResult[orig] = index; // update the inverse mapping
     
    8389
    8490    /// <summary>
    85     /// Checks number of parents and calls <see cref="Apply"/>.
     91    /// Checks number of parents and calls <see cref="Apply(Apply(IRandom, Permutation, Permutation)"/>.
    8692    /// </summary>
    8793    /// <exception cref="InvalidOperationException">Thrown if there are not exactly two permutations in <paramref name="parents"/>.</exception>
Note: See TracChangeset for help on using the changeset viewer.