Changeset 2820


Ignore:
Timestamp:
02/17/10 18:32:57 (11 years ago)
Author:
abeham
Message:

Added MPX and PMX together with reference (#889)

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

Legend:

Unmodified
Added
Removed
  • trunk/sources/HeuristicLab.Permutation/3.3/HeuristicLab.Permutation-3.3.csproj

    r2794 r2820  
    8585      <SubType>Code</SubType>
    8686    </Compile>
     87    <Compile Include="MaximalPreservativeCrossover.cs" />
     88    <Compile Include="PartiallyMatchedCrossover.cs" />
    8789    <Compile Include="PermutationManipulator.cs" />
    8890    <Compile Include="HeuristicLabPermutationPlugin.cs" />
  • trunk/sources/HeuristicLab.Permutation/3.3/MaximalPreservativeCrossover.cs

    r1530 r2820  
    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 {
    29   /// <summary>
    30   /// Performs a cross over permutation between two permuation arrays by preserving a preferably big
    31   /// region from one permutation array.
    32   /// </summary>
    33   public class MaximalPreservativeCrossover : PermutationCrossoverBase {
    34     /// <inheritdoc select="summary"/>
    35     public override string Description {
    36       get { return @"TODO\r\nOperator description still missing ..."; }
     27  /// <summary>An operator which performs the maximal preservative crossover on two permutations.</summary>
     28  /// <remarks>
     29  /// Performs a crossover between two permuation arrays by preserving a large number of edges in both parents.
     30  /// 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.
     32  /// 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.
     33  /// </remarks>
     34  [Item("MaximalPreservativeCrossover", "An operator which performs the maximal preservative crossover on two permutations.")]
     35  [EmptyStorableClass]
     36  [Creatable("Test")]
     37  public class MaximalPreservativeCrossover : PermutationCrossover {
     38    /// <summary>
     39    /// Performs the maximal preservative crossover on <paramref name="parent1"/> and <paramref name="parent2"/>
     40    /// by preserving a large number of edges in both parents.
     41    /// </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>
     43    /// <remarks>
     44    /// First one segment is copied from the first parent to the offspring in the same position.
     45    /// Then the tour is completed by adding the next number from the second parent if such an edge exists,
     46    /// or from the first parent, or from the next number of the second parent.
     47    /// The last case results in an unwanted mutation.
     48    /// </remarks>
     49    /// <param name="random">A random number generator.</param>
     50    /// <param name="parent1">The first parent permutation to cross.</param>
     51    /// <param name="parent2">The second parent permutation to cross.</param>
     52    /// <returns>The new permutation resulting from the crossover.</returns>
     53    public static Permutation Apply(IRandom random, Permutation parent1, Permutation parent2) {
     54      if (parent1.Length != parent2.Length) throw new ArgumentException("MaximalPreservativeCrossover: The parent permutations are of unequal length");
     55      if (parent1.Length < 4) throw new ArgumentException("MaximalPreservativeCrossover: The parent permutation must be at least of size 4");
     56      int length = parent1.Length;
     57      Permutation result = new Permutation(length);
     58      bool[] numberCopied = new bool[length];
     59      int breakPoint1, breakPoint2, subsegmentLength, index;
     60
     61      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.
     62      breakPoint1 = random.Next(length);
     63      breakPoint2 = breakPoint1 + subsegmentLength;
     64      if (breakPoint2 >= length) breakPoint2 -= length;
     65
     66      // copy string between position [breakPoint1, breakPoint2) from parent1 to the offspring
     67      index = breakPoint1;
     68      do {
     69        result[index] = parent1[index];
     70        numberCopied[result[index]] = true;
     71        index++;
     72        if (index >= length) index -= length;
     73      } while (index != breakPoint2);
     74
     75      // calculate inverse permutation (number -> index) to help finding the follower of a given number
     76      int[] invParent1 = new int[length];
     77      int[] invParent2 = new int[length];
     78      try {
     79        for (int i = 0; i < length; i++) {
     80          invParent1[parent1[i]] = i;
     81          invParent2[parent2[i]] = i;
     82        }
     83      } catch (IndexOutOfRangeException) {
     84        throw new InvalidOperationException("MaximalPreservativeCrossover: The permutation must consist of consecutive numbers from 0 to N-1 with N = length of the permutation");
     85      }
     86
     87      int prevIndex = ((index > 0) ? (index - 1) : (length - 1));
     88      do {
     89        // look for the follower of the last number in parent2
     90        int p2Follower = GetFollower(parent2, invParent2[result[prevIndex]]);
     91        if (!numberCopied[p2Follower]) {
     92          result[index] = p2Follower;
     93        } else {
     94          // if that follower has already been added, look for the follower of the last number in parent1
     95          int p1Follower = GetFollower(parent1, invParent1[result[prevIndex]]);
     96          if (!numberCopied[p1Follower]) {
     97            result[index] = p1Follower;
     98          } else {
     99            // if that has also been added, look for the next not already added number in parent2
     100            int tempIndex = index;
     101            for (int i = 0; i < parent2.Length; i++) {
     102              if (!numberCopied[parent2[tempIndex]]) {
     103                result[index] = parent2[tempIndex];
     104                break;
     105              }
     106              tempIndex++;
     107              if (tempIndex >= parent2.Length) tempIndex = 0;
     108            }
     109          }
     110        }
     111        numberCopied[result[index]] = true;
     112        prevIndex = index;
     113        index++;
     114        if (index >= length) index -= length;
     115      } while (index != breakPoint1);
     116
     117      return result;
     118    }
     119
     120    private static int GetFollower(Permutation parent, int index) {
     121      if (index + 1 == parent.Length)
     122        return parent[0];
     123      return parent[index + 1];
    37124    }
    38125
    39126    /// <summary>
    40     /// Performs a cross over permutation of <paramref name="parent1"/> and <paramref name="parent2"/>
    41     /// by preserving a preferably big randomly chosen region of one permutation and taking
    42     /// the missing ones from the other permuation array.
     127    /// Checks number of parents and calls <see cref="Apply"/>.
    43128    /// </summary>
    44     /// <param name="random">The random number generator.</param>
    45     /// <param name="parent1">The permutation array of parent 1.</param>
    46     /// <param name="parent2">The permutation array of parent 2.</param>
    47     /// <returns>The created cross over permutation as int array.</returns>
    48     public static int[] Apply(IRandom random, int[] parent1, int[] parent2) {
    49       int length = parent1.Length;
    50       int[] result = new int[length];
    51       bool[] numberCopied = new bool[length];
    52       int breakPoint1, breakPoint2, subsegmentLength, index;
    53 
    54       if (length >= 20) {  // length of subsegment must be >= 10 and <= length / 2
    55         breakPoint1 = random.Next(length - 9);
    56         subsegmentLength = random.Next(10, Math.Min((int)(length / 2), length - breakPoint1) + 1);
    57         breakPoint2 = breakPoint1 + subsegmentLength - 1;
    58       } else {
    59         breakPoint1 = random.Next(length - 1);
    60         breakPoint2 = random.Next(breakPoint1 + 1, length);
    61       }
    62 
    63       index = 0;
    64       for (int i = breakPoint1; i <= breakPoint2; i++) {  // copy part of first permutation
    65         result[index] = parent1[i];
    66         numberCopied[result[index]] = true;
    67         index++;
    68       }
    69 
    70       for (int i = 0; i < parent2.Length; i++) {  // copy remaining part of second permutation
    71         if (!numberCopied[parent2[i]]) {
    72           result[index] = parent2[i];
    73           index++;
    74         }
    75       }
    76       return result;
    77     }
    78 
    79     /// <summary>
    80     /// Performs a maximal preservative crossover operation for two given parent permutations.
    81     /// </summary>
    82     /// <exception cref="InvalidOperationException">Thrown if there are not exactly two parents.</exception>
     129    /// <exception cref="InvalidOperationException">Thrown if there are not exactly two permutations in <paramref name="parents"/>.</exception>
    83130    /// <param name="scope">The current scope.</param>
    84131    /// <param name="random">A random number generator.</param>
    85132    /// <param name="parents">An array containing the two permutations that should be crossed.</param>
    86133    /// <returns>The newly created permutation, resulting from the crossover operation.</returns>
    87     protected override int[] Cross(IScope scope, IRandom random, int[][] parents) {
    88       if (parents.Length != 2) throw new InvalidOperationException("ERROR in MaximalPreservativeCrossover: The number of parents is not equal to 2");
     134    protected override Permutation Cross(IRandom random, ItemArray<Permutation> parents) {
     135      if (parents.Length != 2) throw new InvalidOperationException("MaximalPreservativeCrossover: Number of parents is not equal to 2.");
    89136      return Apply(random, parents[0], parents[1]);
    90137    }
  • trunk/sources/HeuristicLab.Permutation/3.3/PartiallyMatchedCrossover.cs

    r1530 r2820  
    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 permuation arrays
    31   /// by taking a randomly chosen interval from the first, keeping the position,
    32   /// then all positions from the second permutation which are still free in the child
    33   /// (the position is free and the value is "free")
    34   /// and then missing ones from the second array in the order they occur in the second array.
    35   /// </summary>
    36   public class PartiallyMatchedCrossover : PermutationCrossoverBase {
    37     /// <inheritdoc select="summary"/>
    38     public override string Description {
    39       get { return @"TODO\r\nOperator description still missing ..."; }
    40     }
    41 
     28  /// An operator which performs the partially matched crossover on two permutations.
     29  /// </summar>
     30  /// <remarks>
     31  /// Implemented as described in Fogel, D.B. 1988. An Evolutionary Approach to the Traveling Salesman Problem. Biological Cybernetics, 60, pp. 139-144, Springer-Verlag.
     32  /// which references Goldberg, D.E., and Lingle, R. 1985. Alleles, loci, and the traveling salesman problem. Proceedings of an International Conference on Genetic Algorithms and their Applications. Carnegie-Mellon University, pp. 154-159.
     33  /// as the original source of the operator.
     34  /// </remarks>
     35  [Item("PartiallyMatchedCrossover", "An operator which performs the partially matched crossover on two permutations.")]
     36  [EmptyStorableClass]
     37  [Creatable("Test")]
     38  public class PartiallyMatchedCrossover : PermutationCrossover {
    4239    /// <summary>
    43     /// Performs a cross over permuation of <paramref name="parent1"/> and <paramref name="parent2"/>
    44     /// by taking a randomly chosen interval from <paramref name="parent1"/>, preserving the position,
    45     /// then all positions from <paramref name="parent2"/> which are still free in the child
    46     /// (the position is free and the value is "free")
    47     /// and then missing ones from <paramref name="parent2"/> in the order they occur
    48     /// in <paramref name="parent2"/>.
     40    /// Performs the partially matched crossover on <paramref name="parent1"/> and <paramref name="parent2"/>.
    4941    /// </summary>
    50     /// <param name="random">The random number generator.</param>
    51     /// <param name="parent1">The parent scope 1 to cross over.</param>
    52     /// <param name="parent2">The parent scope 2 to cross over.</param>
    53     /// <returns>The created cross over permutation as int array.</returns>
    54     public static int[] Apply(IRandom random, int[] parent1, int[] parent2) {
     42    /// <remarks>
     43    /// First a segment from the first parent is copied to the offspring.
     44    /// Then the rest of the offspring is filled with the numbers from parent2.
     45    /// When a number is encountered in parent2 that is included in the segment which came from the first parent,
     46    /// the number in parent2 is used that was replaced by the corresponding number from parent1.
     47    /// </remarks>
     48    /// <param name="random">A random number generator.</param>
     49    /// <param name="parent1">The first parent permutation to cross.</param>
     50    /// <param name="parent2">The second parent permutation to cross.</param>
     51    /// <returns>The new permutation resulting from the crossover.</returns>
     52    public static Permutation Apply(IRandom random, Permutation parent1, Permutation parent2) {
    5553      int length = parent1.Length;
    56       int[] result = new int[length];
     54      Permutation result = new Permutation(length);
    5755      bool[] numbersCopied = new bool[length];
    5856
     
    6563      }
    6664
    67       int index = breakPoint1;
    68       int i = (breakPoint1 == 0 ? (breakPoint2 + 1) : 0);
     65      // calculate the inverse permutation (number -> index) of parent1
     66      int[] invParent1 = new int[length];
     67      for (int j = 0; j < length; j++) {
     68        invParent1[parent1[j]] = j;
     69      }
     70
     71      int i = ((breakPoint1 == 0) ? (breakPoint2 + 1) : (0));
    6972      while (i < length) {  // copy rest from second permutation
    7073        if (!numbersCopied[parent2[i]]) {  // copy directly
    7174          result[i] = parent2[i];
    7275        } else {  // copy from area between breakpoints
    73           while (numbersCopied[parent2[index]]) {  // find next valid index
    74             index++;
    75           }
    76           result[i] = parent2[index];
    77           index++;
     76          int index = invParent1[parent2[i]]; // find the index of the corresponding occupied number in parent1
     77          result[i] = parent2[index]; // use that index to take the number from parent2
    7878        }
    7979
     
    8787
    8888    /// <summary>
    89     /// Performs a partially matched crossover operation for two given parent permutations.
     89    /// Checks number of parents and calls <see cref="Apply"/>.
    9090    /// </summary>
    91     /// <exception cref="InvalidOperationException">Thrown if there are not exactly two parents.</exception>
     91    /// <exception cref="InvalidOperationException">Thrown if there are not exactly two permutations in <paramref name="parents"/>.</exception>
    9292    /// <param name="scope">The current scope.</param>
    9393    /// <param name="random">A random number generator.</param>
    9494    /// <param name="parents">An array containing the two permutations that should be crossed.</param>
    9595    /// <returns>The newly created permutation, resulting from the crossover operation.</returns>
    96     protected override int[] Cross(IScope scope, IRandom random, int[][] parents) {
    97       if (parents.Length != 2) throw new InvalidOperationException("ERROR in PartiallyMatchedCrossover: The number of parents is not equal to 2");
     96    protected override Permutation Cross(IRandom random, ItemArray<Permutation> parents) {
     97      if (parents.Length != 2) throw new InvalidOperationException("PartiallyMatchedCrossover: The number of parents is not equal to 2");
    9898      return Apply(random, parents[0], parents[1]);
    9999    }
Note: See TracChangeset for help on using the changeset viewer.