1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022015 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 


22  using System;


23  using System.Collections.Generic;


24  using HeuristicLab.Common;


25  using HeuristicLab.Core;


26  using HeuristicLab.Data;


27  using HeuristicLab.Optimization;


28  using HeuristicLab.Parameters;


29  using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;


30 


31  namespace HeuristicLab.Encodings.BinaryVectorEncoding {


32  /// <summary>


33  /// N point crossover for binary vectors.


34  /// </summary>


35  /// <remarks>


36  /// It is implemented as described in Eiben, A.E. and Smith, J.E. 2003. Introduction to Evolutionary Computation. Natural Computing Series, SpringerVerlag Berlin Heidelberg..


37  /// </remarks>


38  [Item("NPointCrossover", "N point crossover for binary vectors. It is implemented as described in Eiben, A.E. and Smith, J.E. 2003. Introduction to Evolutionary Computation. Natural Computing Series, SpringerVerlag Berlin Heidelberg.")]


39  [StorableClass]


40  public sealed class NPointCrossover : BinaryVectorCrossover {


41  /// <summary>


42  /// Number of crossover points.


43  /// </summary>


44  public IValueLookupParameter<IntValue> NParameter {


45  get { return (IValueLookupParameter<IntValue>)Parameters["N"]; }


46  }


47 


48  [StorableConstructor]


49  private NPointCrossover(bool deserializing) : base(deserializing) { }


50  private NPointCrossover(NPointCrossover original, Cloner cloner) : base(original, cloner) { }


51  /// <summary>


52  /// Initializes a new instance of <see cref="NPointCrossover"/>


53  /// </summary>


54  public NPointCrossover()


55  : base() {


56  Parameters.Add(new ValueLookupParameter<IntValue>("N", "Number of crossover points", new IntValue(2)));


57  }


58 


59  public override IDeepCloneable Clone(Cloner cloner) {


60  return new NPointCrossover(this, cloner);


61  }


62 


63  /// <summary>


64  /// Performs a N point crossover at randomly chosen positions of the two


65  /// given parent binary vectors.


66  /// </summary>


67  /// <exception cref="ArgumentException">Thrown when the value for N is invalid or when the parent vectors are of different length.</exception>


68  /// <param name="random">A random number generator.</param>


69  /// <param name="parent1">The first parent for crossover.</param>


70  /// <param name="parent2">The second parent for crossover.</param>


71  /// <param name="n">Number of crossover points.</param>


72  /// <returns>The newly created binary vector, resulting from the N point crossover.</returns>


73  public static BinaryVector Apply(IRandom random, BinaryVector parent1, BinaryVector parent2, int n) {


74  if (parent1.Length != parent2.Length)


75  throw new ArgumentException("NPointCrossover: The parents are of different length.");


76 


77  if (n > parent1.Length)


78  throw new ArgumentException("NPointCrossover: There cannot be more breakpoints than the size of the parents.");


79 


80  if (n < 1)


81  throw new ArgumentException("NPointCrossover: N cannot be < 1.");


82 


83  int length = parent1.Length;


84  bool[] result = new bool[length];


85  int[] breakpoints = new int[n];


86 


87  //choose break points


88  List<int> breakpointPool = new List<int>();


89 


90  for (int i = 0; i < length; i++)


91  breakpointPool.Add(i);


92 


93  for (int i = 0; i < n; i++) {


94  int index = random.Next(breakpointPool.Count);


95  breakpoints[i] = breakpointPool[index];


96  breakpointPool.RemoveAt(index);


97  }


98 


99  Array.Sort(breakpoints);


100 


101  //perform crossover


102  int arrayIndex = 0;


103  int breakPointIndex = 0;


104  bool firstParent = true;


105 


106  while (arrayIndex < length) {


107  if (breakPointIndex < breakpoints.Length &&


108  arrayIndex == breakpoints[breakPointIndex]) {


109  breakPointIndex++;


110  firstParent = !firstParent;


111  }


112 


113  if (firstParent)


114  result[arrayIndex] = parent1[arrayIndex];


115  else


116  result[arrayIndex] = parent2[arrayIndex];


117 


118  arrayIndex++;


119  }


120 


121  return new BinaryVector(result);


122  }


123 


124  /// <summary>


125  /// Performs a N point crossover at a randomly chosen position of two


126  /// given parent binary vectors.


127  /// </summary>


128  /// <exception cref="ArgumentException">Thrown if there are not exactly two parents.</exception>


129  /// <exception cref="InvalidOperationException">


130  /// Thrown when the N parameter could not be found.</description></item>


131  /// </exception>


132  /// <param name="random">A random number generator.</param>


133  /// <param name="parents">An array containing the two binary vectors that should be crossed.</param>


134  /// <returns>The newly created binary vector, resulting from the N point crossover.</returns>


135  protected override BinaryVector Cross(IRandom random, ItemArray<BinaryVector> parents) {


136  if (parents.Length != 2) throw new ArgumentException("ERROR in NPointCrossover: The number of parents is not equal to 2");


137 


138  if (NParameter.ActualValue == null) throw new InvalidOperationException("NPointCrossover: Parameter " + NParameter.ActualName + " could not be found.");


139 


140  return Apply(random, parents[0], parents[1], NParameter.ActualValue.Value);


141  }


142  }


143 


144  [Item("Npoint Crossover", "", ExcludeGenericTypeInfo = true)]


145  [StorableClass]


146  public sealed class NPointCrossover<TContext> : ParameterizedNamedItem, IBinaryCrossover<TContext>


147  where TContext : IMatingContext<BinaryVector>, IStochasticContext {


148 


149  [Storable]


150  private IValueParameter<IntValue> nparameter;


151  public int N {


152  get { return nparameter.Value.Value; }


153  set {


154  if (value < 1) throw new ArgumentException("Cannot set N to less than 1.");


155  nparameter.Value.Value = value;


156  }


157  }


158 


159  [StorableConstructor]


160  private NPointCrossover(bool deserializing) : base(deserializing) { }


161  private NPointCrossover(NPointCrossover<TContext> original, Cloner cloner)


162  : base(original, cloner) {


163  nparameter = cloner.Clone(original.nparameter);


164  }


165  public NPointCrossover() {


166  Parameters.Add(nparameter = new ValueParameter<IntValue>("N", "The number of crossover points.", new IntValue(1)));


167  }


168 


169 


170  public override IDeepCloneable Clone(Cloner cloner) {


171  return new NPointCrossover<TContext>(this, cloner);


172  }


173 


174  public void Cross(TContext context) {


175  context.Child.Solution = NPointCrossover.Apply(context.Random, context.Parents.Item1.Solution, context.Parents.Item2.Solution, N);


176  }


177  }


178  }

