source: trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Crossovers/PartiallyMatchedCrossover.cs @ 4068

#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 <http://www.gnu.org/licenses/>.
 */
#endregion

using System;
using HeuristicLab.Core;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;

namespace HeuristicLab.Encodings.PermutationEncoding {
  /// <summary>
  /// An operator which performs the partially matched crossover on two permutations.
  /// </summar>
  /// <remarks>
  /// It is implemented as described in Fogel, D.B. 1988. An Evolutionary Approach to the Traveling Salesman Problem. Biological Cybernetics, 60, pp. 139-144, Springer-Verlag.
  /// 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.
  /// as the original source of the operator.
  /// </remarks>
  [Item("PartiallyMatchedCrossover", "An operator which performs the partially matched crossover on two permutations. It is implemented as described in Fogel, D.B. 1988. An Evolutionary Approach to the Traveling Salesman Problem. Biological Cybernetics, 60, pp. 139-144, Springer-Verlag.")]
  [StorableClass]
  public class PartiallyMatchedCrossover : PermutationCrossover {
    /// <summary>
    /// Performs the partially matched crossover on <paramref name="parent1"/> and <paramref name="parent2"/>.
    /// </summary>
    /// <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>
    /// <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>
    /// <remarks>
    /// Initially the new offspring is a clone of <paramref name="parent2"/>.
    /// Then a segment is extracted from <paramref name="parent1"/> and copied to the offspring position by position.
    /// 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.
    /// 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.
    /// The '5' in the offspring is then moved to replace the '3' in the offspring and '3' is written at position 15.
    /// </remarks>
    /// <param name="random">A random number generator.</param>
    /// <param name="parent1">The first parent permutation to cross.</param>
    /// <param name="parent2">The second parent permutation to cross.</param>
    /// <returns>The new permutation resulting from the crossover.</returns>
    public static Permutation Apply(IRandom random, Permutation parent1, Permutation parent2) {
      if (parent1.Length != parent2.Length) throw new ArgumentException("PartiallyMatchedCrossover: The parent permutations are of unequal length.");
      if (parent1.Length < 4) throw new ArgumentException("PartiallyMatchedCrossover: The parent permutation must be at least of size 4.");
      int length = parent1.Length;
      int[] result = new int[length];
      int[] invResult = new int[length];

      int breakPoint1, breakPoint2;
      do {
        breakPoint1 = random.Next(length - 1);
        breakPoint2 = random.Next(breakPoint1 + 1, length);
      } while (breakPoint2 - breakPoint1 >= length - 2); // prevent the case [0,length-1) -> clone of parent1

      // clone parent2 and calculate inverse permutation (number -> index)
      try {
        for (int j = 0; j < length; j++) {
          result[j] = parent2[j];
          invResult[result[j]] = j;
        }
      }
      catch (IndexOutOfRangeException) {
        throw new InvalidOperationException("PartiallyMatchedCrossover: The permutation must consist of consecutive numbers from 0 to N-1 with N = length of the permutation.");
      }

      for (int j = breakPoint1; j <= breakPoint2; j++) {
        int orig = result[j]; // save the former value
        result[j] = parent1[j]; // overwrite the former value with the new value
        int index = invResult[result[j]]; // look where the new value is in the offspring
        result[index] = orig; // write the former value to this position
        invResult[orig] = index; // update the inverse mapping
        // it's not necessary to do 'invResult[result[j]] = j' as this will not be needed again
      }

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

    /// <summary>
    /// Checks number of parents and calls <see cref="Apply(Apply(IRandom, Permutation, Permutation)"/>.
    /// </summary>
    /// <exception cref="InvalidOperationException">Thrown if there are not exactly two permutations in <paramref name="parents"/>.</exception>
    /// <param name="random">A random number generator.</param>
    /// <param name="parents">An array containing the two permutations that should be crossed.</param>
    /// <returns>The newly created permutation, resulting from the crossover operation.</returns>
    protected override Permutation Cross(IRandom random, ItemArray<Permutation> parents) {
      if (parents.Length != 2) throw new InvalidOperationException("PartiallyMatchedCrossover: The number of parents is not equal to 2.");
      return Apply(random, parents[0], parents[1]);
    }
  }
}