#region License Information /* HeuristicLab * Copyright (C) 2002-2018 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.Common; using HeuristicLab.Core; using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; namespace HeuristicLab.Encodings.PermutationEncoding { /// /// An operator which performs a slight variant of the order crossover on two permutations. /// /// /// It is implemented as described in Affenzeller, M. et al. 2009. Genetic Algorithms and Genetic Programming - Modern Concepts and Practical Applications. CRC Press. p. 135.
/// Crosses two permutations by copying a randomly chosen interval from the first permutation, preserving /// the positions. But then, instead of starting from the end of the copied interval, the missing values are copied from the start of the permutation in the order they occur. ///
[Item("OrderCrossover2", "An operator which performs an order crossover of two permutations. It is implemented as described in Affenzeller, M. et al. 2009. Genetic Algorithms and Genetic Programming - Modern Concepts and Practical Applications. CRC Press. p. 135.")] [StorableClass] public class OrderCrossover2 : PermutationCrossover { [StorableConstructor] protected OrderCrossover2(bool deserializing) : base(deserializing) { } protected OrderCrossover2(OrderCrossover2 original, Cloner cloner) : base(original, cloner) { } public OrderCrossover2() : base() { } public override IDeepCloneable Clone(Cloner cloner) { return new OrderCrossover2(this, cloner); } /// /// Performs a slight variation of the order crossover of two permutations. /// /// Thrown when and are not of equal length. /// /// Crosses two permutations by copying a randomly chosen interval from the first permutation, preserving /// the positions. Then, from the beginning of the permutation, copies the missing values from the second permutation /// in the order they occur. /// /// 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("OrderCrossover2: The parent permutations are of unequal length."); int[] result = new int[parent1.Length]; bool[] copied = new bool[result.Length]; int breakPoint1 = random.Next(result.Length - 1); int breakPoint2 = random.Next(breakPoint1 + 1, result.Length); for (int i = breakPoint1; i <= breakPoint2; i++) { // copy part of first permutation result[i] = parent1[i]; copied[parent1[i]] = true; } int index = 0; for (int i = 0; i < parent2.Length; i++) { // copy remaining part of second permutation if (index == breakPoint1) { // skip already copied part index = breakPoint2 + 1; } if (!copied[parent2[i]]) { result[index] = parent2[i]; index++; } } return new Permutation(parent1.PermutationType, result); } /// /// Checks number of parents and calls . /// /// Thrown if there are not exactly two parents. /// A random number generator. /// An array containing the two permutations that should be crossed. /// The new permutation resulting from the crossover. protected override Permutation Cross(IRandom random, ItemArray parents) { if (parents.Length != 2) throw new InvalidOperationException("OrderCrossover2: Number of parents is not equal to 2."); return Apply(random, parents[0], parents[1]); } } }