source: branches/2839_HiveProjectManagement/HeuristicLab.Encodings.ScheduleEncoding/3.3/JobSequenceMatrix/Crossovers/JSMSXXCrossover.cs @ 16057

Last change on this file since 16057 was 16057, checked in by jkarder, 15 months ago

#2839:

File size: 3.8 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using HeuristicLab.Common;
23using HeuristicLab.Core;
24using HeuristicLab.Encodings.PermutationEncoding;
25using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
26
27namespace HeuristicLab.Encodings.ScheduleEncoding.JobSequenceMatrix {
28  [Item("JSMSubsequenceExchangeCrossover", "Represents a crossover operation identifiying and exchanging equal subsequences of the parents to generate offspring.")]
29  [StorableClass]
30  public class JSMSXXCrossover : JSMCrossover {
31
32    [StorableConstructor]
33    protected JSMSXXCrossover(bool deserializing) : base(deserializing) { }
34    protected JSMSXXCrossover(JSMSXXCrossover original, Cloner cloner) : base(original, cloner) { }
35    public JSMSXXCrossover() : base() { }
36
37    public override IDeepCloneable Clone(Cloner cloner) {
38      return new JSMSXXCrossover(this, cloner);
39    }
40
41    public static JSMEncoding Apply(IRandom random, JSMEncoding parent1, JSMEncoding parent2) {
42      var result = new JSMEncoding();
43      int subSequenceLength = random.Next(parent1.JobSequenceMatrix[0].Length);
44      for (int i = 0; i < parent1.JobSequenceMatrix.Count; i++) {
45        var p1 = (Permutation)parent1.JobSequenceMatrix[i].Clone();
46        var p2 = (Permutation)parent2.JobSequenceMatrix[i].Clone();
47        FindAndExchangeSubsequences(p1, p2, subSequenceLength);
48        result.JobSequenceMatrix.Add(p1);
49      }
50      return result;
51    }
52
53    private static void FindAndExchangeSubsequences(Permutation p1, Permutation p2, int subSequenceLength) {
54      for (int i = 0; i <= p1.Length - subSequenceLength; i++) {
55        int[] ss1 = GetSubSequenceAtPosition(p1, i, subSequenceLength);
56        for (int j = 0; j <= p2.Length - subSequenceLength; j++) {
57          int[] ss2 = GetSubSequenceAtPosition(p2, j, subSequenceLength);
58          if (AreEqualSubsequences(ss1, ss2)) {
59            ExchangeSubsequences(p1, i, p2, j, subSequenceLength);
60            return;
61          }
62        }
63      }
64    }
65
66    private static void ExchangeSubsequences(Permutation p1, int index1, Permutation p2, int index2, int subSequenceLength) {
67      var aux = (Permutation)p1.Clone();
68      for (int i = 0; i < subSequenceLength; i++) {
69        p1[i + index1] = p2[i + index2];
70        p2[i + index2] = aux[i + index1];
71      }
72    }
73
74    private static bool AreEqualSubsequences(int[] ss1, int[] ss2) {
75      int counter = 0;
76      for (int i = 0; i < ss1.Length; i++) {
77        for (int j = 0; j < ss2.Length; j++) {
78          if (ss1[i] == ss2[j])
79            counter++;
80        }
81      }
82      return counter == ss1.Length;
83    }
84
85    private static int[] GetSubSequenceAtPosition(Permutation p1, int index, int subSequenceLength) {
86      var result = new int[subSequenceLength];
87      for (int i = 0; i < subSequenceLength; i++)
88        result[i] = p1[i + index];
89
90      return result;
91    }
92
93    public override JSMEncoding Cross(IRandom random, JSMEncoding parent1, JSMEncoding parent2) {
94      return Apply(random, parent1, parent2);
95    }
96  }
97}
Note: See TracBrowser for help on using the repository browser.