1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022016 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 System.Linq;


25  using System.Threading;


26  using HeuristicLab.Algorithms.MemPR.Interfaces;


27  using HeuristicLab.Algorithms.MemPR.Util;


28  using HeuristicLab.Common;


29  using HeuristicLab.Core;


30  using HeuristicLab.Encodings.LinearLinkageEncoding;


31  using HeuristicLab.Optimization;


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


33  using HeuristicLab.PluginInfrastructure;


34  using HeuristicLab.Random;


35 


36  namespace HeuristicLab.Algorithms.MemPR.LinearLinkage {


37  [Item("MemPR (linear linkage)", "MemPR implementation for linear linkage vectors.")]


38  [StorableClass]


39  [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms, Priority = 999)]


40  public class LinearLinkageMemPR : MemPRAlgorithm<SingleObjectiveBasicProblem<LinearLinkageEncoding>, Encodings.LinearLinkageEncoding.LinearLinkage, LinearLinkageMemPRPopulationContext, LinearLinkageMemPRSolutionContext> {


41  private const double UncommonBitSubsetMutationProbabilityMagicConst = 0.05;


42 


43  [StorableConstructor]


44  protected LinearLinkageMemPR(bool deserializing) : base(deserializing) { }


45  protected LinearLinkageMemPR(LinearLinkageMemPR original, Cloner cloner) : base(original, cloner) { }


46  public LinearLinkageMemPR() {


47  foreach (var trainer in ApplicationManager.Manager.GetInstances<ISolutionModelTrainer<LinearLinkageMemPRPopulationContext>>())


48  SolutionModelTrainerParameter.ValidValues.Add(trainer);


49 


50  foreach (var localSearch in ApplicationManager.Manager.GetInstances<ILocalSearch<LinearLinkageMemPRSolutionContext>>()) {


51  LocalSearchParameter.ValidValues.Add(localSearch);


52  }


53  }


54 


55  public override IDeepCloneable Clone(Cloner cloner) {


56  return new LinearLinkageMemPR(this, cloner);


57  }


58 


59  protected override bool Eq(ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> a, ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> b) {


60  var s1 = a.Solution;


61  var s2 = b.Solution;


62  if (s1.Length != s2.Length) return false;


63  for (var i = 0; i < s1.Length; i++)


64  if (s1[i] != s2[i]) return false;


65  return true;


66  }


67 


68  protected override double Dist(ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> a, ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> b) {


69  return 1.0  HammingSimilarityCalculator.CalculateSimilarity(a.Solution, b.Solution);


70  }


71 


72  protected override ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> ToScope(Encodings.LinearLinkageEncoding.LinearLinkage code, double fitness = double.NaN) {


73  var creator = Problem.SolutionCreator as ILinearLinkageCreator;


74  if (creator == null) throw new InvalidOperationException("Can only solve linear linkage encoded problems with MemPR (linear linkage)");


75  return new SingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage>(code, creator.LLEParameter.ActualName, fitness, Problem.Evaluator.QualityParameter.ActualName) {


76  Parent = Context.Scope


77  };


78  }


79 


80  protected override ISolutionSubspace<Encodings.LinearLinkageEncoding.LinearLinkage> CalculateSubspace(IEnumerable<Encodings.LinearLinkageEncoding.LinearLinkage> solutions, bool inverse = false) {


81  var pop = solutions.ToList();


82  var N = pop[0].Length;


83  var subspace = new bool[N];


84  for (var i = 0; i < N; i++) {


85  var val = pop[0][i];


86  if (inverse) subspace[i] = true;


87  for (var p = 1; p < pop.Count; p++) {


88  if (pop[p][i] != val) subspace[i] = !inverse;


89  }


90  }


91  return new LinearLinkageSolutionSubspace(subspace);


92  }


93 


94  protected override int TabuWalk(


95  ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> scope,


96  int maxEvals, CancellationToken token,


97  ISolutionSubspace<Encodings.LinearLinkageEncoding.LinearLinkage> sub_space = null) {


98  var maximization = Context.Problem.Maximization;


99  var subspace = sub_space is LinearLinkageSolutionSubspace ? ((LinearLinkageSolutionSubspace)sub_space).Subspace : null;


100  var evaluations = 0;


101  var quality = scope.Fitness;


102  if (double.IsNaN(quality)) {


103  Evaluate(scope, token);


104  quality = scope.Fitness;


105  evaluations++;


106  if (evaluations >= maxEvals) return evaluations;


107  }


108  var bestQuality = quality;


109  var currentScope = (ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage>)scope.Clone();


110  var current = currentScope.Solution;


111  Encodings.LinearLinkageEncoding.LinearLinkage bestOfTheWalk = null;


112  var bestOfTheWalkF = double.NaN;


113 


114  var tabu = new double[current.Length, current.Length];


115  for (var i = 0; i < current.Length; i++) {


116  for (var j = i; j < current.Length; j++) {


117  tabu[i, j] = tabu[j, i] = maximization ? double.MinValue : double.MaxValue;


118  }


119  tabu[i, current[i]] = quality;


120  }


121 


122  // this dictionary holds the last relevant links


123  var groupItems = new List<int>();


124  var lleb = current.ToBackLinks();


125  Move bestOfTheRest = null;


126  var bestOfTheRestF = double.NaN;


127  var lastAppliedMove = 1;


128  for (var iter = 0; iter < int.MaxValue; iter++) {


129  // clear the dictionary before a new pass through the array is made


130  groupItems.Clear();


131  for (var i = 0; i < current.Length; i++) {


132  if (subspace != null && !subspace[i]) {


133  if (lleb[i] != i)


134  groupItems.Remove(lleb[i]);


135  groupItems.Add(i);


136  continue;


137  }


138 


139  var next = current[i];


140 


141  if (lastAppliedMove == i) {


142  if (bestOfTheRest != null) {


143  bestOfTheRest.Apply(current);


144  bestOfTheRest.ApplyToLLEb(lleb);


145  currentScope.Fitness = bestOfTheRestF;


146  quality = bestOfTheRestF;


147  if (maximization) {


148  tabu[i, next] = Math.Max(tabu[i, next], bestOfTheRestF);


149  tabu[i, current[i]] = Math.Max(tabu[i, current[i]], bestOfTheRestF);


150  } else {


151  tabu[i, next] = Math.Min(tabu[i, next], bestOfTheRestF);


152  tabu[i, current[i]] = Math.Min(tabu[i, current[i]], bestOfTheRestF);


153  }


154  if (FitnessComparer.IsBetter(maximization, bestOfTheRestF, bestOfTheWalkF)) {


155  bestOfTheWalk = (Encodings.LinearLinkageEncoding.LinearLinkage)current.Clone();


156  bestOfTheWalkF = bestOfTheRestF;


157  }


158  bestOfTheRest = null;


159  bestOfTheRestF = double.NaN;


160  lastAppliedMove = i;


161  } else {


162  lastAppliedMove = 1;


163  }


164  break;


165  } else {


166  foreach (var move in MoveGenerator.GenerateForItem(i, groupItems, current, lleb)) {


167  // we intend to break link i > next


168  var qualityToBreak = tabu[i, next];


169  move.Apply(current);


170  var qualityToRestore = tabu[i, current[i]]; // current[i] is new next


171  Evaluate(currentScope, token);


172  evaluations++;


173  var moveF = currentScope.Fitness;


174  var isNotTabu = FitnessComparer.IsBetter(maximization, moveF, qualityToBreak)


175  && FitnessComparer.IsBetter(maximization, moveF, qualityToRestore);


176  var isImprovement = FitnessComparer.IsBetter(maximization, moveF, quality);


177  var isAspired = FitnessComparer.IsBetter(maximization, moveF, bestQuality);


178  if ((isNotTabu && isImprovement)  isAspired) {


179  if (maximization) {


180  tabu[i, next] = Math.Max(tabu[i, next], moveF);


181  tabu[i, current[i]] = Math.Max(tabu[i, current[i]], moveF);


182  } else {


183  tabu[i, next] = Math.Min(tabu[i, next], moveF);


184  tabu[i, current[i]] = Math.Min(tabu[i, current[i]], moveF);


185  }


186  quality = moveF;


187  if (isAspired) bestQuality = quality;


188 


189  move.ApplyToLLEb(lleb);


190 


191  if (FitnessComparer.IsBetter(maximization, moveF, bestOfTheWalkF)) {


192  bestOfTheWalk = (Encodings.LinearLinkageEncoding.LinearLinkage)current.Clone();


193  bestOfTheWalkF = moveF;


194  }


195 


196  bestOfTheRest = null;


197  bestOfTheRestF = double.NaN;


198  lastAppliedMove = i;


199  break;


200  } else {


201  if (isNotTabu) {


202  if (FitnessComparer.IsBetter(maximization, moveF, bestOfTheRestF)) {


203  bestOfTheRest = move;


204  bestOfTheRestF = moveF;


205  }


206  }


207  move.Undo(current);


208  currentScope.Fitness = quality;


209  }


210  if (evaluations >= maxEvals) break;


211  }


212  }


213  if (lleb[i] != i)


214  groupItems.Remove(lleb[i]);


215  groupItems.Add(i);


216  if (evaluations >= maxEvals) break;


217  if (token.IsCancellationRequested) break;


218  }


219  if (lastAppliedMove == 1) { // no move has been applied


220  if (bestOfTheRest != null) {


221  var i = bestOfTheRest.Item;


222  var next = current[i];


223  bestOfTheRest.Apply(current);


224  currentScope.Fitness = bestOfTheRestF;


225  quality = bestOfTheRestF;


226  if (maximization) {


227  tabu[i, next] = Math.Max(tabu[i, next], bestOfTheRestF);


228  tabu[i, current[i]] = Math.Max(tabu[i, current[i]], bestOfTheRestF);


229  } else {


230  tabu[i, next] = Math.Min(tabu[i, next], bestOfTheRestF);


231  tabu[i, current[i]] = Math.Min(tabu[i, current[i]], bestOfTheRestF);


232  }


233  if (FitnessComparer.IsBetter(maximization, bestOfTheRestF, bestOfTheWalkF)) {


234  bestOfTheWalk = (Encodings.LinearLinkageEncoding.LinearLinkage)current.Clone();


235  bestOfTheWalkF = bestOfTheRestF;


236  }


237 


238  bestOfTheRest = null;


239  bestOfTheRestF = double.NaN;


240  } else break;


241  }


242  if (evaluations >= maxEvals) break;


243  if (token.IsCancellationRequested) break;


244  }


245  if (bestOfTheWalk != null) {


246  scope.Solution = bestOfTheWalk;


247  scope.Fitness = bestOfTheWalkF;


248  }


249  return evaluations;


250  }


251 


252  protected override ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> Cross(ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> p1Scope, ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> p2Scope, CancellationToken token) {


253  var p1 = p1Scope.Solution;


254  var p2 = p2Scope.Solution;


255  return ToScope(GroupCrossover.Apply(Context.Random, p1, p2));


256  }


257 


258  protected override void Mutate(ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> offspring, CancellationToken token, ISolutionSubspace<Encodings.LinearLinkageEncoding.LinearLinkage> subspace = null) {


259  var lle = offspring.Solution;


260  var subset = subspace is LinearLinkageSolutionSubspace ? ((LinearLinkageSolutionSubspace)subspace).Subspace : null;


261  for (var i = 0; i < lle.Length  1; i++) {


262  if (subset == null  subset[i]) continue; // mutation works against crossover so aims to mutate noTouch points


263  if (Context.Random.NextDouble() < UncommonBitSubsetMutationProbabilityMagicConst) {


264  subset[i] = true;


265  var index = Context.Random.Next(i, lle.Length);


266  for (var j = index  1; j >= i; j) {


267  if (lle[j] == index) index = j;


268  }


269  lle[i] = index;


270  index = i;


271  var idx2 = i;


272  for (var j = i  1; j >= 0; j) {


273  if (lle[j] == lle[index]) {


274  lle[j] = idx2;


275  index = idx2 = j;


276  } else if (lle[j] == idx2) idx2 = j;


277  }


278  }


279  }


280  }


281 


282  protected override ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> Relink(ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> a, ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> b, CancellationToken token) {


283  var maximization = Context.Problem.Maximization;


284  if (double.IsNaN(a.Fitness)) {


285  Evaluate(a, token);


286  Context.IncrementEvaluatedSolutions(1);


287  }


288  if (double.IsNaN(b.Fitness)) {


289  Evaluate(b, token);


290  Context.IncrementEvaluatedSolutions(1);


291  }


292  var child = (ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage>)a.Clone();


293  var cgroups = child.Solution.GetGroups().Select(x => new HashSet<int>(x)).ToList();


294  var g2 = b.Solution.GetGroups().ToList();


295  var order = Enumerable.Range(0, g2.Count).Shuffle(Context.Random).ToList();


296  ISingleObjectiveSolutionScope <Encodings.LinearLinkageEncoding.LinearLinkage> bestChild = null;


297  for (var j = 0; j < g2.Count; j++) {


298  var g = g2[order[j]];


299  var changed = false;


300  for (var k = j; k < cgroups.Count; k++) {


301  foreach (var f in g) if (cgroups[k].Remove(f)) changed = true;


302  if (cgroups[k].Count == 0) {


303  cgroups.RemoveAt(k);


304  k;


305  }


306  }


307  cgroups.Insert(0, new HashSet<int>(g));


308  child.Solution.SetGroups(cgroups);


309  if (changed) {


310  Evaluate(child, token);


311  if (bestChild == null  FitnessComparer.IsBetter(maximization, child.Fitness, bestChild.Fitness)) {


312  bestChild = (ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage>)child.Clone();


313  }


314  }


315  };


316  return bestChild;


317  }


318  }


319  }

