#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 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.
/// 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.
///
[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 {
[StorableConstructor]
protected PartiallyMatchedCrossover(bool deserializing) : base(deserializing) { }
protected PartiallyMatchedCrossover(PartiallyMatchedCrossover original, Cloner cloner) : base(original, cloner) { }
public PartiallyMatchedCrossover() : base() { }
public override IDeepCloneable Clone(Cloner cloner) {
return new PartiallyMatchedCrossover(this, cloner);
}
///
/// Performs the partially matched crossover on and .
///
/// Thrown when and are not of equal length or when the permutations are shorter than 4 elements.
/// Thrown if the numbers in the permutation elements are not in the range [0,N) with N = length of the permutation.
///
/// Initially the new offspring is a clone of .
/// Then a segment is extracted from 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 to . At position 15 there is a '3' in 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.
///
/// A random number generator.
/// The first parent permutation to cross.
/// The second parent permutation to cross.
/// The new permutation resulting from the crossover.
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);
}
///
/// Checks number of parents and calls .
///
/// Thrown if there are not exactly two permutations in .
/// 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("PartiallyMatchedCrossover: The number of parents is not equal to 2.");
return Apply(random, parents[0], parents[1]);
}
}
}