1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022019 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.Collections.Generic;


23  using System.Linq;


24  using HeuristicLab.Common;


25  using HeuristicLab.Core;


26  using HEAL.Attic;


27 


28  namespace HeuristicLab.Encodings.LinearLinkageEncoding {


29  [Item("Lowest Index First Crossover", "The Lowest Index First Crossover (LIFX) is implemented as described in Ülker, Ö., Özcan, E., Korkmaz, E. E. 2007. Linear linkage encoding in grouping problems: applications on graph coloring and timetabling. In Practice and Theory of Automated Timetabling VI, pp. 347363. Springer Berlin Heidelberg.")]


30  [StorableType("1DFB1827AFE64210A542F9EA112FF039")]


31  public sealed class LowestIndexFirstCrossover : LinearLinkageCrossover {


32 


33  [StorableConstructor]


34  private LowestIndexFirstCrossover(StorableConstructorFlag _) : base(_) { }


35  private LowestIndexFirstCrossover(LowestIndexFirstCrossover original, Cloner cloner) : base(original, cloner) { }


36  public LowestIndexFirstCrossover() { }


37 


38  public override IDeepCloneable Clone(Cloner cloner) {


39  return new LowestIndexFirstCrossover(this, cloner);


40  }


41 


42  public static LinearLinkage Apply(IRandom random, ItemArray<LinearLinkage> parents) {


43  var len = parents[0].Length;


44  var p = random.Next(parents.Length);


45  var child = LinearLinkage.SingleElementGroups(len);


46  var remaining = new SortedSet<int>(Enumerable.Range(0, len));


47  do {


48  var i = remaining.Min;


49  foreach (var g in parents[p].GetGroupForward(i)) {


50  if (!remaining.Contains(g)) continue;


51  child[i] = g;


52  i = g;


53  remaining.Remove(g);


54  }


55  child[i] = i;


56  remaining.Remove(i);


57 


58  p = (p + 1) % parents.Length;


59  } while (remaining.Count > 0);


60 


61  return child;


62  }


63 


64  protected override LinearLinkage Cross(IRandom random, ItemArray<LinearLinkage> parents) {


65  return Apply(random, parents);


66  }


67  }


68  }

