Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
12/07/16 23:46:29 (7 years ago)
Author:
abeham
Message:

#2701:

  • Added MemPR for linear linkage (tabu walk still missing)
  • Added graph coloring problem
Location:
branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/LinearLinkage
Files:
1 added
1 copied

Legend:

Unmodified
Added
Removed

  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/LinearLinkage/LinearLinkageMemPR.cs

    r14456 r14466  
    2525using System.Threading;
    2626using HeuristicLab.Algorithms.MemPR.Interfaces;
     27using HeuristicLab.Algorithms.MemPR.Util;
    2728using HeuristicLab.Common;
    2829using HeuristicLab.Core;
    29 using HeuristicLab.Encodings.BinaryVectorEncoding;
     30using HeuristicLab.Encodings.LinearLinkageEncoding;
    3031using HeuristicLab.Optimization;
    3132using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    … …  
    3334using HeuristicLab.Random;
    3435
    35 namespace HeuristicLab.Algorithms.MemPR.Binary {
    36   [Item("MemPR (binary)", "MemPR implementation for binary vectors.")]
     36namespace HeuristicLab.Algorithms.MemPR.LinearLinkage {
     37  [Item("MemPR (linear linkage)", "MemPR implementation for linear linkage vectors.")]
    3738  [StorableClass]
    3839  [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms, Priority = 999)]
    39   public class BinaryMemPR : MemPRAlgorithm<SingleObjectiveBasicProblem<BinaryVectorEncoding>, BinaryVector, BinaryMemPRPopulationContext, BinaryMemPRSolutionContext> {
     40  public class LinearLinkageMemPR : MemPRAlgorithm<SingleObjectiveBasicProblem<LinearLinkageEncoding>, Encodings.LinearLinkageEncoding.LinearLinkage, LinearLinkageMemPRPopulationContext, LinearLinkageMemPRSolutionContext> {
    4041    private const double UncommonBitSubsetMutationProbabilityMagicConst = 0.05;
    4142   
    4243    [StorableConstructor]
    43     protected BinaryMemPR(bool deserializing) : base(deserializing) { }
    44     protected BinaryMemPR(BinaryMemPR original, Cloner cloner) : base(original, cloner) { }
    45     public BinaryMemPR() {
    46       foreach (var trainer in ApplicationManager.Manager.GetInstances<ISolutionModelTrainer<BinaryMemPRPopulationContext>>())
     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>>())
    4748        SolutionModelTrainerParameter.ValidValues.Add(trainer);
    4849     
    49       foreach (var localSearch in ApplicationManager.Manager.GetInstances<ILocalSearch<BinaryMemPRSolutionContext>>()) {
     50      foreach (var localSearch in ApplicationManager.Manager.GetInstances<ILocalSearch<LinearLinkageMemPRSolutionContext>>()) {
    5051        LocalSearchParameter.ValidValues.Add(localSearch);
    5152      }
    … …  
    5354
    5455    public override IDeepCloneable Clone(Cloner cloner) {
    55       return new BinaryMemPR(this, cloner);
    56     }
    57 
    58     protected override bool Eq(ISingleObjectiveSolutionScope<BinaryVector> a, ISingleObjectiveSolutionScope<BinaryVector> b) {
    59       var len = a.Solution.Length;
    60       var acode = a.Solution;
    61       var bcode = b.Solution;
    62       for (var i = 0; i < len; i++)
    63         if (acode[i] != bcode[i]) return false;
    64       return true;
    65     }
    66 
    67     protected override double Dist(ISingleObjectiveSolutionScope<BinaryVector> a, ISingleObjectiveSolutionScope<BinaryVector> b) {
    68       var len = a.Solution.Length;
    69       var acode = a.Solution;
    70       var bcode = b.Solution;
    71       var hamming = 0;
    72       for (var i = 0; i < len; i++)
    73         if (acode[i] != bcode[i]) hamming++;
    74       return hamming / (double)len;
    75     }
    76 
    77     protected override ISingleObjectiveSolutionScope<BinaryVector> ToScope(BinaryVector code, double fitness = double.NaN) {
    78       var creator = Problem.SolutionCreator as IBinaryVectorCreator;
    79       if (creator == null) throw new InvalidOperationException("Can only solve binary encoded problems with MemPR (binary)");
    80       return new SingleObjectiveSolutionScope<BinaryVector>(code, creator.BinaryVectorParameter.ActualName, fitness, Problem.Evaluator.QualityParameter.ActualName) {
     56      return new LinearLinkageMemPR(this, cloner);
     57    }
     58
     59    protected override bool Eq(ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> a, ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> b) {
     60      return a.Solution.SequenceEqual(b.Solution);
     61    }
     62
     63    protected override double Dist(ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> a, ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> b) {
     64      if (a.Solution.Length != b.Solution.Length) throw new ArgumentException("Comparing encodings of unequal length");
     65      var dist = 0;
     66      for (var i = 0; i < a.Solution.Length; i++) {
     67        if (a.Solution[i] != b.Solution[i]) dist++;
     68      }
     69      return dist / (double)a.Solution.Length;
     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) {
    8176        Parent = Context.Scope
    8277      };
    8378    }
    8479
    85     protected override ISolutionSubspace<BinaryVector> CalculateSubspace(IEnumerable<BinaryVector> solutions, bool inverse = false) {
     80    protected override ISolutionSubspace<Encodings.LinearLinkageEncoding.LinearLinkage> CalculateSubspace(IEnumerable<Encodings.LinearLinkageEncoding.LinearLinkage> solutions, bool inverse = false) {
    8681      var pop = solutions.ToList();
    8782      var N = pop[0].Length;
    … …  
    9489        }
    9590      }
    96       return new BinarySolutionSubspace(subspace);
    97     }
    98 
    99     protected override int TabuWalk(ISingleObjectiveSolutionScope<BinaryVector> scope, int maxEvals, CancellationToken token, ISolutionSubspace<BinaryVector> subspace = null) {
    100       var evaluations = 0;
    101       var subset = subspace != null ? ((BinarySolutionSubspace)subspace).Subspace : null;
    102       if (double.IsNaN(scope.Fitness)) {
    103         Evaluate(scope, token);
    104         evaluations++;
    105       }
    106       SingleObjectiveSolutionScope<BinaryVector> bestOfTheWalk = null;
    107       var currentScope = (SingleObjectiveSolutionScope<BinaryVector>)scope.Clone();
    108       var current = currentScope.Solution;
    109       var N = current.Length;
    110       var tabu = new Tuple<double, double>[N];
    111       for (var i = 0; i < N; i++) tabu[i] = Tuple.Create(current[i] ? double.NaN : currentScope.Fitness, !current[i] ? double.NaN : currentScope.Fitness);
    112       var subN = subset != null ? subset.Count(x => x) : N;
    113       if (subN == 0) return 0;
    114       var order = Enumerable.Range(0, N).Where(x => subset == null || subset[x]).Shuffle(Context.Random).ToArray();
    115 
    116       var steps = 0;
    117       var stepsUntilBestOfWalk = 0;
    118       for (var iter = 0; iter < int.MaxValue; iter++) {
    119         var allTabu = true;
    120         var bestOfTheRestF = double.NaN;
    121         int bestOfTheRest = -1;
    122         var improved = false;
    123 
    124         for (var i = 0; i < subN; i++) {
    125           var idx = order[i];
    126           var before = currentScope.Fitness;
    127           current[idx] = !current[idx];
    128           Evaluate(currentScope, token);
    129           evaluations++;
    130           var after = currentScope.Fitness;
    131 
    132           if (IsBetter(after, before) && (bestOfTheWalk == null || IsBetter(after, bestOfTheWalk.Fitness))) {
    133             bestOfTheWalk = (SingleObjectiveSolutionScope<BinaryVector>)currentScope.Clone();
    134             stepsUntilBestOfWalk = steps;
    135           }
    136 
    137           var qualityToBeat = current[idx] ? tabu[idx].Item2 : tabu[idx].Item1;
    138           var isTabu = !IsBetter(after, qualityToBeat);
    139           if (!isTabu) allTabu = false;
    140 
    141           if (IsBetter(after, before) && !isTabu) {
    142             improved = true;
    143             steps++;
    144             tabu[idx] = current[idx] ? Tuple.Create(after, tabu[idx].Item2) : Tuple.Create(tabu[idx].Item1, after);
    145           } else { // undo the move
    146             if (!isTabu && IsBetter(after, bestOfTheRestF)) {
    147               bestOfTheRest = idx;
    148               bestOfTheRestF = after;
    149             }
    150             current[idx] = !current[idx];
    151             currentScope.Fitness = before;
    152           }
    153           if (evaluations >= maxEvals) break;
    154         }
    155         if (!allTabu && !improved) {
    156           var better = currentScope.Fitness;
    157           current[bestOfTheRest] = !current[bestOfTheRest];
    158           tabu[bestOfTheRest] = current[bestOfTheRest] ? Tuple.Create(better, tabu[bestOfTheRest].Item2) : Tuple.Create(tabu[bestOfTheRest].Item1, better);
    159           currentScope.Fitness = bestOfTheRestF;
    160           steps++;
    161         } else if (allTabu) break;
    162         if (evaluations >= maxEvals) break;
    163       }
    164 
    165       Context.IncrementEvaluatedSolutions(evaluations);
    166       scope.Adopt(bestOfTheWalk ?? currentScope);
    167       return stepsUntilBestOfWalk;
    168     }
    169 
    170     protected override ISingleObjectiveSolutionScope<BinaryVector> Cross(ISingleObjectiveSolutionScope<BinaryVector> p1, ISingleObjectiveSolutionScope<BinaryVector> p2, CancellationToken token) {
    171       var offspring = (ISingleObjectiveSolutionScope<BinaryVector>)p1.Clone();
    172       offspring.Fitness = double.NaN;
    173       var code = offspring.Solution;
    174       var p2Code = p2.Solution;
    175       var bp = 0;
    176       var lastbp = 0;
    177       for (var i = 0; i < code.Length; i++) {
    178         if (bp % 2 == 1) {
    179           code[i] = p2Code[i];
    180         }
    181         if (Context.Random.Next(code.Length) < i - lastbp + 1) {
    182           bp = (bp + 1) % 2;
    183           lastbp = i;
    184         }
    185       }
    186       return offspring;
    187     }
    188 
    189     protected override void Mutate(ISingleObjectiveSolutionScope<BinaryVector> offspring, CancellationToken token, ISolutionSubspace<BinaryVector> subspace = null) {
    190       var subset = subspace != null ? ((BinarySolutionSubspace)subspace).Subspace : null;
    191       offspring.Fitness = double.NaN;
    192       var code = offspring.Solution;
    193       for (var i = 0; i < code.Length; i++) {
    194         if (subset != null && subset[i]) continue;
     91      return new LinearLinkageSolutionSubspace(subspace);
     92    }
     93
     94    protected override int TabuWalk(ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> scope, int maxEvals, CancellationToken token, ISolutionSubspace<Encodings.LinearLinkageEncoding.LinearLinkage> subspace = null) {
     95      return 0;
     96    }
     97
     98    protected override ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> Cross(ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> p1Scope, ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> p2Scope, CancellationToken token) {
     99      var p1 = p1Scope.Solution;
     100      var p2 = p2Scope.Solution;
     101      var transfered = new bool[p1.Length];
     102      var subspace = new bool[p1.Length];
     103      var lleeChild = new int[p1.Length];
     104      var lleep1 = p1.ToLLEe();
     105      var lleep2 = p2.ToLLEe();
     106      for (var i = p1.Length - 1; i >= 0; i--) {
     107        // Step 1
     108        subspace[i] = p1[i] != p2[i];
     109        var p1IsEnd = p1[i] == i;
     110        var p2IsEnd = p2[i] == i;
     111        if (p1IsEnd & p2IsEnd) {
     112          transfered[i] = true;
     113        } else if (p1IsEnd | p2IsEnd) {
     114          transfered[i] = Context.Random.NextDouble() < 0.5;
     115        }
     116        lleeChild[i] = i;
     117
     118        // Step 2
     119        if (transfered[i]) continue;
     120        var end1 = lleep1[i];
     121        var end2 = lleep2[i];
     122        var containsEnd1 = transfered[end1];
     123        var containsEnd2 = transfered[end2];
     124        if (containsEnd1 & containsEnd2) {
     125          if (Context.Random.NextDouble() < 0.5) {
     126            lleeChild[i] = end1;
     127          } else {
     128            lleeChild[i] = end2;
     129          }
     130        } else if (containsEnd1) {
     131          lleeChild[i] = end1;
     132        } else if (containsEnd2) {
     133          lleeChild[i] = end2;
     134        } else {
     135          if (Context.Random.NextDouble() < 0.5) {
     136            lleeChild[i] = lleeChild[p1[i]];
     137          } else {
     138            lleeChild[i] = lleeChild[p2[i]];
     139          }
     140        }
     141      }
     142      var child = new Encodings.LinearLinkageEncoding.LinearLinkage(lleeChild.Length);
     143      child.FromLLEe(lleeChild);
     144     
     145      return ToScope(child);
     146    }
     147
     148    protected override void Mutate(ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> offspring, CancellationToken token, ISolutionSubspace<Encodings.LinearLinkageEncoding.LinearLinkage> subspace = null) {
     149      var lle = offspring.Solution;
     150      var subset = subspace is LinearLinkageSolutionSubspace ? ((LinearLinkageSolutionSubspace)subspace).Subspace : null;
     151      for (var i = 0; i < lle.Length - 1; i++) {
     152        if (subset == null || subset[i]) continue; // mutation works against crossover so aims to mutate noTouch points
    195153        if (Context.Random.NextDouble() < UncommonBitSubsetMutationProbabilityMagicConst) {
    196           code[i] = !code[i];
    197           if (subset != null) subset[i] = true;
    198         }
    199       }
    200     }
    201 
    202     protected override ISingleObjectiveSolutionScope<BinaryVector> Relink(ISingleObjectiveSolutionScope<BinaryVector> a, ISingleObjectiveSolutionScope<BinaryVector> b, CancellationToken token) {
     154          subset[i] = true;
     155          var index = Context.Random.Next(i, lle.Length);
     156          for (var j = index - 1; j >= i; j--) {
     157            if (lle[j] == index) index = j;
     158          }
     159          lle[i] = index;
     160          index = i;
     161          var idx2 = i;
     162          for (var j = i - 1; j >= 0; j--) {
     163            if (lle[j] == lle[index]) {
     164              lle[j] = idx2;
     165              index = idx2 = j;
     166            } else if (lle[j] == idx2) idx2 = j;
     167          }
     168        }
     169      }
     170    }
     171
     172    protected override ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> Relink(ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> a, ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> b, CancellationToken token) {
     173      var maximization = Context.Problem.Maximization;
    203174      if (double.IsNaN(a.Fitness)) {
    204175        Evaluate(a, token);
    … …  
    209180        Context.IncrementEvaluatedSolutions(1);
    210181      }
    211       if (Context.Random.NextDouble() < 0.5)
    212         return IsBetter(a, b) ? Relink(a, b, token, false) : Relink(b, a, token, true);
    213       else return IsBetter(a, b) ? Relink(b, a, token, true) : Relink(a, b, token, false);
    214     }
    215 
    216     protected virtual ISingleObjectiveSolutionScope<BinaryVector> Relink(ISingleObjectiveSolutionScope<BinaryVector> betterScope, ISingleObjectiveSolutionScope<BinaryVector> worseScope, CancellationToken token, bool fromWorseToBetter) {
    217       var evaluations = 0;
    218       var childScope = (ISingleObjectiveSolutionScope<BinaryVector>)(fromWorseToBetter ? worseScope : betterScope).Clone();
    219       var child = childScope.Solution;
    220       var better = betterScope.Solution;
    221       var worse = worseScope.Solution;
    222       ISingleObjectiveSolutionScope<BinaryVector> best = null;
    223       var cF = fromWorseToBetter ? worseScope.Fitness : betterScope.Fitness;
    224       var bF = double.NaN;
    225       var order = Enumerable.Range(0, better.Length).Shuffle(Context.Random).ToArray();
    226       while (true) {
    227         var bestS = double.NaN;
    228         var bestIdx = -1;
    229         for (var i = 0; i < child.Length; i++) {
    230           var idx = order[i];
    231           // either move from worse to better or move from better away from worse
    232           if (fromWorseToBetter && child[idx] == better[idx] ||
    233             !fromWorseToBetter && child[idx] != worse[idx]) continue;
    234           child[idx] = !child[idx]; // move
    235           Evaluate(childScope, token);
    236           evaluations++;
    237           var s = childScope.Fitness;
    238           childScope.Fitness = cF;
    239           child[idx] = !child[idx]; // undo move
    240           if (IsBetter(s, cF)) {
    241             bestS = s;
    242             bestIdx = idx;
    243             break; // first-improvement
    244           }
    245           if (double.IsNaN(bestS) || IsBetter(s, bestS)) {
    246             // least-degrading
    247             bestS = s;
    248             bestIdx = idx;
    249           }
    250         }
    251         if (bestIdx < 0) break;
    252         child[bestIdx] = !child[bestIdx];
    253         cF = bestS;
    254         childScope.Fitness = cF;
    255         if (IsBetter(cF, bF)) {
    256           bF = cF;
    257           best = (ISingleObjectiveSolutionScope<BinaryVector>)childScope.Clone();
    258         }
    259       }
    260       Context.IncrementEvaluatedSolutions(evaluations);
    261       return best ?? childScope;
     182      var child = (ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage>)a.Clone();
     183      var cgroups = child.Solution.GetGroups().Select(x => new HashSet<int>(x)).ToList();
     184      var g2 = b.Solution.GetGroups().ToList();
     185      var order = Enumerable.Range(0, g2.Count).Shuffle(Context.Random).ToList();
     186      ISingleObjectiveSolutionScope <Encodings.LinearLinkageEncoding.LinearLinkage> bestChild = null;
     187      for (var j = 0; j < g2.Count; j++) {
     188        var g = g2[order[j]];
     189        var changed = false;
     190        for (var k = j; k < cgroups.Count; k++) {
     191          foreach (var f in g) if (cgroups[k].Remove(f)) changed = true;
     192          if (cgroups[k].Count == 0) {
     193            cgroups.RemoveAt(k);
     194            k--;
     195          }
     196        }
     197        cgroups.Insert(0, new HashSet<int>(g));
     198        child.Solution.SetGroups(cgroups);
     199        if (changed) {
     200          Evaluate(child, token);
     201          if (bestChild == null || FitnessComparer.IsBetter(maximization, child.Fitness, bestChild.Fitness)) {
     202            bestChild = (ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage>)child.Clone();
     203          }
     204        }
     205      };
     206      return bestChild;
    262207    }
    263208  }
Note: See TracChangeset for help on using the changeset viewer.