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


29  using HeuristicLab.Common;


30  using HeuristicLab.Core;


31  using HeuristicLab.Encodings.LinearLinkageEncoding;


32  using HeuristicLab.Optimization;


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


34  using HeuristicLab.PluginInfrastructure;


35  using HeuristicLab.Random;


36 


37  namespace HeuristicLab.Algorithms.MemPR.LinearLinkage {


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


39  [StorableClass]


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


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


42  private const double UncommonBitSubsetMutationProbabilityMagicConst = 0.05;


43 


44  [StorableConstructor]


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


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


47  public LinearLinkageMemPR() {


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


49  SolutionModelTrainerParameter.ValidValues.Add(trainer);


50 


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


52  LocalSearchParameter.ValidValues.Add(localSearch);


53  }


54  }


55 


56  public override IDeepCloneable Clone(Cloner cloner) {


57  return new LinearLinkageMemPR(this, cloner);


58  }


59 


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


61  var s1 = a.Solution;


62  var s2 = b.Solution;


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


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


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


66  return true;


67  }


68 


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


70  return HammingSimilarityCalculator.CalculateSimilarity(a.Solution, b.Solution);


71  }


72 


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


74  var creator = Problem.SolutionCreator as ILinearLinkageCreator;


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


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


77  Parent = Context.Scope


78  };


79  }


80 


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


82  var pop = solutions.ToList();


83  var N = pop[0].Length;


84  var subspace = new bool[N];


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


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


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


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


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


90  }


91  }


92  return new LinearLinkageSolutionSubspace(subspace);


93  }


94 


95  protected override int TabuWalk(


96  ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> scope,


97  int maxEvals, CancellationToken token,


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


99  var maximization = Context.Problem.Maximization;


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


101  var evaluations = 0;


102  var quality = scope.Fitness;


103  if (double.IsNaN(quality)) {


104  Evaluate(scope, token);


105  quality = scope.Fitness;


106  evaluations++;


107  if (evaluations >= maxEvals) return evaluations;


108  }


109  var bestQuality = quality;


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


111  var current = currentScope.Solution;


112  Encodings.LinearLinkageEncoding.LinearLinkage bestOfTheWalk = null;


113  var bestOfTheWalkF = double.NaN;


114 


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


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


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


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


119  }


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


121  }


122 


123  // this dictionary holds the last relevant links


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


125  var lleb = current.ToBackLinks();


126  Move bestOfTheRest = null;


127  var bestOfTheRestF = double.NaN;


128  var lastAppliedMove = 1;


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


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


131  groupItems.Clear();


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


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


134  if (lleb[i] != i)


135  groupItems.Remove(lleb[i]);


136  groupItems.Add(i);


137  continue;


138  }


139 


140  var next = current[i];


141 


142  if (lastAppliedMove == i) {


143  if (bestOfTheRest != null) {


144  bestOfTheRest.Apply(current);


145  bestOfTheRest.ApplyToLLEb(lleb);


146  currentScope.Fitness = bestOfTheRestF;


147  quality = bestOfTheRestF;


148  if (maximization) {


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


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


151  } else {


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


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


154  }


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


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


157  bestOfTheWalkF = bestOfTheRestF;


158  }


159  bestOfTheRest = null;


160  bestOfTheRestF = double.NaN;


161  lastAppliedMove = i;


162  } else {


163  lastAppliedMove = 1;


164  }


165  break;


166  } else {


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


168  // we intend to break link i > next


169  var qualityToBreak = tabu[i, next];


170  move.Apply(current);


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


172  Evaluate(currentScope, token);


173  evaluations++;


174  var moveF = currentScope.Fitness;


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


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


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


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


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


180  if (maximization) {


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


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


183  } else {


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


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


186  }


187  quality = moveF;


188  if (isAspired) bestQuality = quality;


189 


190  move.ApplyToLLEb(lleb);


191 


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


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


194  bestOfTheWalkF = moveF;


195  }


196 


197  bestOfTheRest = null;


198  bestOfTheRestF = double.NaN;


199  lastAppliedMove = i;


200  break;


201  } else {


202  if (isNotTabu) {


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


204  bestOfTheRest = move;


205  bestOfTheRestF = moveF;


206  }


207  }


208  move.Undo(current);


209  currentScope.Fitness = quality;


210  }


211  if (evaluations >= maxEvals) break;


212  }


213  }


214  if (lleb[i] != i)


215  groupItems.Remove(lleb[i]);


216  groupItems.Add(i);


217  if (evaluations >= maxEvals) break;


218  if (token.IsCancellationRequested) break;


219  }


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


221  if (bestOfTheRest != null) {


222  var i = bestOfTheRest.Item;


223  var next = current[i];


224  bestOfTheRest.Apply(current);


225  currentScope.Fitness = bestOfTheRestF;


226  quality = bestOfTheRestF;


227  if (maximization) {


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


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


230  } else {


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


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


233  }


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


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


236  bestOfTheWalkF = bestOfTheRestF;


237  }


238 


239  bestOfTheRest = null;


240  bestOfTheRestF = double.NaN;


241  } else break;


242  }


243  if (evaluations >= maxEvals) break;


244  if (token.IsCancellationRequested) break;


245  }


246  if (bestOfTheWalk != null) {


247  scope.Solution = bestOfTheWalk;


248  scope.Fitness = bestOfTheWalkF;


249  }


250  return evaluations;


251  }


252 


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


254  var p1 = p1Scope.Solution;


255  var p2 = p2Scope.Solution;


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


257  }


258 


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


260  var lle = offspring.Solution;


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


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


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


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


265  subset[i] = true;


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


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


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


269  }


270  lle[i] = index;


271  index = i;


272  var idx2 = i;


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


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


275  lle[j] = idx2;


276  index = idx2 = j;


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


278  }


279  }


280  }


281  }


282 


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


284  var maximization = Context.Problem.Maximization;


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


286  Evaluate(a, token);


287  Context.IncrementEvaluatedSolutions(1);


288  }


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


290  Evaluate(b, token);


291  Context.IncrementEvaluatedSolutions(1);


292  }


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


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


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


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


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


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


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


300  var changed = false;


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


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


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


304  cgroups.RemoveAt(k);


305  k;


306  }


307  }


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


309  child.Solution.SetGroups(cgroups);


310  if (changed) {


311  Evaluate(child, token);


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


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


314  }


315  }


316  };


317  return bestChild;


318  }


319  }


320  }

