source: branches/2839_HiveProjectManagement/HeuristicLab.Encodings.PermutationEncoding/3.3/Crossovers/UniformLikeCrossover.cs @ 16057

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

#2839:

File size: 3.6 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 System;
23using System.Collections.Generic;
24using HeuristicLab.Common;
25using HeuristicLab.Core;
26using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
27
28namespace HeuristicLab.Encodings.PermutationEncoding {
29  [Item("UniformLikeCrossover", "The ULX crossover tries to maintain the position in the permutation. It randomly chooses from left to right one of its parents' alleles at each position. Missing entries are then filled randomly later. It is described in Tate, D. M. and Smith, A. E. 1995. A genetic approach to the quadratic assignment problem. Computers & Operations Research, vol. 22, pp. 73-83.")]
30  [StorableClass]
31  public sealed class UniformLikeCrossover : PermutationCrossover {
32    [StorableConstructor]
33    private UniformLikeCrossover(bool deserializing) : base(deserializing) { }
34    private UniformLikeCrossover(UniformLikeCrossover original, Cloner cloner) : base(original, cloner) { }
35    public UniformLikeCrossover() : base() { }
36
37    public override IDeepCloneable Clone(Cloner cloner) {
38      return new UniformLikeCrossover(this, cloner);
39    }
40
41    public static Permutation Apply(IRandom random, Permutation parent1, Permutation parent2) {
42      if (parent1.Length != parent2.Length) throw new ArgumentException("parent1 and parent2 are of different length.");
43      int length = parent1.Length;
44      int[] child = new int[length];
45      bool[] numberCopied = new bool[length];
46      List<int> unoccupied = new List<int>();
47
48      for (int i = 0; i < length; i++) {
49        bool copied = true;
50        if (parent1[i] == parent2[i]) {
51          child[i] = parent1[i];
52        } else if (!numberCopied[parent1[i]] && !numberCopied[parent2[i]]) {
53          child[i] = (random.NextDouble() < 0.5) ? parent1[i] : parent2[i];
54        } else if (!numberCopied[parent1[i]]) {
55          child[i] = parent1[i];
56        } else if (!numberCopied[parent2[i]]) {
57          child[i] = parent2[i];
58        } else {
59          copied = false;
60          unoccupied.Add(i);
61        }
62        if (copied) numberCopied[child[i]] = true;
63      }
64
65      if (unoccupied.Count > 0) {
66        for (int i = 0; i < length; i++) {
67          if (!numberCopied[i]) {
68            int r = random.Next(unoccupied.Count);
69            child[unoccupied[r]] = i;
70            unoccupied.RemoveAt(r);
71          }
72          if (unoccupied.Count == 0) break;
73        }
74      }
75
76      return new Permutation(parent1.PermutationType, child);
77    }
78
79    protected override Permutation Cross(IRandom random, ItemArray<Permutation> parents) {
80      if (parents.Length != 2) throw new InvalidOperationException("UniformLikeCrossover: The number of parents is not equal to 2.");
81      return Apply(random, parents[0], parents[1]);
82    }
83  }
84}
Note: See TracBrowser for help on using the repository browser.