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.Parameters;


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


29  using HeuristicLab.Encodings.MoveVectorEncoding;


30  using HeuristicLab.Data.MoveVectorData;


31 


32  namespace HeuristicLab.Encodings.BinaryVectorEncoding {


33  /// <summary>


34  /// N point crossover for move vectors.


35  /// </summary>


36  /// <remarks>


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


38  /// </remarks>


39  [Item("NPointCrossover", "N point crossover for move 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.")]


40  [StorableClass]


41  public sealed class NPointCrossover : MoveVectorCrossover


42  {


43  /// <summary>


44  /// Number of crossover points.


45  /// </summary>


46  public IValueLookupParameter<IntValue> NParameter {


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


48  }


49 


50  [StorableConstructor]


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


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


53  /// <summary>


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


55  /// </summary>


56  public NPointCrossover()


57  : base() {


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


59  }


60 


61  public override IDeepCloneable Clone(Cloner cloner) {


62  return new NPointCrossover(this, cloner);


63  }


64 


65  public static MoveVector Apply(IRandom random, MoveVector parent1, MoveVector parent2, IntValue n) {


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


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


68 


69  if (n.Value > parent1.Length)


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


71 


72  if (n.Value < 1)


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


74 


75  int length = parent1.Length;


76  MoveVector result = new MoveVector(length, parent1.MoveTypes);


77  int[] breakpoints = new int[n.Value];


78 


79  //choose break points


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


81 


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


83  breakpointPool.Add(i);


84 


85  for (int i = 0; i < n.Value; i++) {


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


87  breakpoints[i] = breakpointPool[index];


88  breakpointPool.RemoveAt(index);


89  }


90 


91  Array.Sort(breakpoints);


92 


93  //perform crossover


94  int arrayIndex = 0;


95  int breakPointIndex = 0;


96  bool firstParent = true;


97 


98  while (arrayIndex < length) {


99  if (breakPointIndex < breakpoints.Length &&


100  arrayIndex == breakpoints[breakPointIndex]) {


101  breakPointIndex++;


102  firstParent = !firstParent;


103  }


104 


105  if (firstParent)


106  result[arrayIndex] = parent1[arrayIndex];


107  else


108  result[arrayIndex] = parent2[arrayIndex];


109 


110  arrayIndex++;


111  }


112 


113  return result;


114  }


115 


116  protected override MoveVector Cross(IRandom random, ItemArray<MoveVector> parents) {


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


118 


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


120 


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


122  }


123  }


124  }

