Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Permutation/3.2/OrderBasedCrossover.cs @ 1784

Last change on this file since 1784 was 1530, checked in by gkronber, 16 years ago

Moved source files of plugins Hive ... Visualization.Test into version-specific sub-folders. #576

File size: 4.5 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2008 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 System.Text;
25using HeuristicLab.Core;
26using HeuristicLab.Data;
27
28namespace HeuristicLab.Permutation {
29  /// <summary>
30  /// Performs a cross over permutation of two permutation arrays by taking randomly a selection of values
31  /// (not an interval!) from the first permutation keeping the correct order and filling
32  /// the missing entries with the elements from the second permutation, also in the right order.
33  /// </summary>
34  public class OrderBasedCrossover : PermutationCrossoverBase {
35    /// <inheritdoc select="summary"/>
36    public override string Description {
37      get { return @"TODO\r\nOperator description still missing ..."; }
38    }
39
40    /// <summary>
41    /// Performs a cross over permutation of <paramref name="parent1"/> and <paramref name="parent2"/> by
42    /// randomly selecting some values from the first permutation that will be inserted one after each
43    /// other; the missing ones are picked in the correct order from the second permutation.
44    /// </summary>
45    /// <param name="random">The random number generator.</param>
46    /// <param name="parent1">The parent scope 1 to cross over.</param>
47    /// <param name="parent2">The parent scope 2 to cross over.</param>
48    /// <returns>The created cross over permutation as int array.</returns>
49    public static int[] Apply(IRandom random, int[] parent1, int[] parent2) {
50      int length = parent1.Length;
51      int[] result = new int[length];
52      int[] selectedNumbers = new int[random.Next(length + 1)];
53      bool[] numberSelected = new bool[length];
54      int index, selectedIndex, currentIndex;
55
56      for (int i = 0; i < selectedNumbers.Length; i++) {  // select numbers for array
57        index = 0;
58        while (numberSelected[parent1[index]]) {  // find first valid index
59          index++;
60        }
61
62        selectedIndex = random.Next(length - i);
63        currentIndex = 0;
64        while ((index < parent1.Length) && (currentIndex != selectedIndex)) {  // find selected number
65          index++;
66          if (!numberSelected[parent1[index]]) {
67            currentIndex++;
68          }
69        }
70        numberSelected[parent1[index]] = true;
71      }
72
73      index = 0;
74      for (int i = 0; i < parent1.Length; i++) {  // copy selected numbers in array
75        if (numberSelected[parent1[i]]) {
76          selectedNumbers[index] = parent1[i];
77          index++;
78        }
79      }
80
81      index = 0;
82      for (int i = 0; i < result.Length; i++) {  // copy rest of second permutation and selected numbers in order of first permutation
83        if (numberSelected[parent2[i]]) {
84          result[i] = selectedNumbers[index];
85          index++;
86        } else {
87          result[i] = parent2[i];
88        }
89      }
90      return result;
91    }
92
93    /// <summary>
94    /// Performs an order-based crossover operation for two given parent permutations.
95    /// </summary>
96    /// <exception cref="InvalidOperationException">Thrown if there are not exactly two parents.</exception>
97    /// <param name="scope">The current scope.</param>
98    /// <param name="random">A random number generator.</param>
99    /// <param name="parents">An array containing the two permutations that should be crossed.</param>
100    /// <returns>The newly created permutation, resulting from the crossover operation.</returns>
101    protected override int[] Cross(IScope scope, IRandom random, int[][] parents) {
102      if (parents.Length != 2) throw new InvalidOperationException("ERROR in OrderBasedCrossover: The number of parents is not equal to 2");
103      return Apply(random, parents[0], parents[1]);
104    }
105  }
106}
Note: See TracBrowser for help on using the repository browser.