Ignore:
Timestamp:
01/05/17 00:32:43 (3 years ago)
Author:
abeham
Message:

#2701:

  • LLE: Added equality comparer
  • MemPR:
    • Added GPR to learn about heuristic performance
    • Changed Breeding to do more exhaustive search on crossover
    • Added Delinking separately to Relinking
    • Rewrote d/relinking for LLE
    • Reduce usage of local search
    • Renamed TabuWalk to AdaptiveWalk
    • Rewrote adaptive walk for binary problems
    • Renamed LLE namespace to Grouping to avoid namespace clashes
File:
1 edited

Legend:

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

    r14496 r14544  
    3434using HeuristicLab.Random;
    3535
    36 namespace HeuristicLab.Algorithms.MemPR.LinearLinkage {
     36namespace HeuristicLab.Algorithms.MemPR.Grouping {
    3737  [Item("MemPR (linear linkage)", "MemPR implementation for linear linkage vectors.")]
    3838  [StorableClass]
    3939  [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    
     40  public class LinearLinkageMemPR : MemPRAlgorithm<SingleObjectiveBasicProblem<LinearLinkageEncoding>, LinearLinkage, LinearLinkageMemPRPopulationContext, LinearLinkageMemPRSolutionContext> {
    4341    [StorableConstructor]
    4442    protected LinearLinkageMemPR(bool deserializing) : base(deserializing) { }
     
    5755    }
    5856
    59     protected override bool Eq(ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> a, ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> b) {
     57    protected override bool Eq(ISingleObjectiveSolutionScope<LinearLinkage> a, ISingleObjectiveSolutionScope<LinearLinkage> b) {
    6058      var s1 = a.Solution;
    6159      var s2 = b.Solution;
     
    6664    }
    6765
    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) {
     66    protected override double Dist(ISingleObjectiveSolutionScope<LinearLinkage> a, ISingleObjectiveSolutionScope<LinearLinkage> b) {
     67      return Dist(a.Solution, b.Solution);
     68    }
     69
     70    private double Dist(LinearLinkage a, LinearLinkage b) {
     71      return 1.0 - HammingSimilarityCalculator.CalculateSimilarity(a, b);
     72    }
     73
     74    protected override ISingleObjectiveSolutionScope<LinearLinkage> ToScope(LinearLinkage code, double fitness = double.NaN) {
    7375      var creator = Problem.SolutionCreator as ILinearLinkageCreator;
    7476      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) {
     77      return new SingleObjectiveSolutionScope<LinearLinkage>(code, creator.LLEParameter.ActualName, fitness, Problem.Evaluator.QualityParameter.ActualName) {
    7678        Parent = Context.Scope
    7779      };
    7880    }
    7981
    80     protected override ISolutionSubspace<Encodings.LinearLinkageEncoding.LinearLinkage> CalculateSubspace(IEnumerable<Encodings.LinearLinkageEncoding.LinearLinkage> solutions, bool inverse = false) {
     82    protected override ISolutionSubspace<LinearLinkage> CalculateSubspace(IEnumerable<LinearLinkage> solutions, bool inverse = false) {
    8183      var pop = solutions.ToList();
    8284      var N = pop[0].Length;
     
    9294    }
    9395
    94     protected override int TabuWalk(
    95         ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> scope,
     96    protected override void AdaptiveWalk(
     97        ISingleObjectiveSolutionScope<LinearLinkage> scope,
    9698        int maxEvals, CancellationToken token,
    97         ISolutionSubspace<Encodings.LinearLinkageEncoding.LinearLinkage> sub_space = null) {
     99        ISolutionSubspace<LinearLinkage> sub_space = null) {
    98100      var maximization = Context.Problem.Maximization;
    99101      var subspace = sub_space is LinearLinkageSolutionSubspace ? ((LinearLinkageSolutionSubspace)sub_space).Subspace : null;
     
    104106        quality = scope.Fitness;
    105107        evaluations++;
    106         if (evaluations >= maxEvals) return evaluations;
     108        if (evaluations >= maxEvals) return;
    107109      }
    108110      var bestQuality = quality;
    109       var currentScope = (ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage>)scope.Clone();
     111      var currentScope = (ISingleObjectiveSolutionScope<LinearLinkage>)scope.Clone();
    110112      var current = currentScope.Solution;
    111       Encodings.LinearLinkageEncoding.LinearLinkage bestOfTheWalk = null;
     113      LinearLinkage bestOfTheWalk = null;
    112114      var bestOfTheWalkF = double.NaN;
    113115
     
    153155              }
    154156              if (FitnessComparer.IsBetter(maximization, bestOfTheRestF, bestOfTheWalkF)) {
    155                 bestOfTheWalk = (Encodings.LinearLinkageEncoding.LinearLinkage)current.Clone();
     157                bestOfTheWalk = (LinearLinkage)current.Clone();
    156158                bestOfTheWalkF = bestOfTheRestF;
    157159              }
     
    190192
    191193                if (FitnessComparer.IsBetter(maximization, moveF, bestOfTheWalkF)) {
    192                   bestOfTheWalk = (Encodings.LinearLinkageEncoding.LinearLinkage)current.Clone();
     194                  bestOfTheWalk = (LinearLinkage)current.Clone();
    193195                  bestOfTheWalkF = moveF;
    194196                }
     
    232234            }
    233235            if (FitnessComparer.IsBetter(maximization, bestOfTheRestF, bestOfTheWalkF)) {
    234               bestOfTheWalk = (Encodings.LinearLinkageEncoding.LinearLinkage)current.Clone();
     236              bestOfTheWalk = (LinearLinkage)current.Clone();
    235237              bestOfTheWalkF = bestOfTheRestF;
    236238            }
     
    247249        scope.Fitness = bestOfTheWalkF;
    248250      }
    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;
     251    }
     252
     253    protected override ISingleObjectiveSolutionScope<LinearLinkage> Breed(ISingleObjectiveSolutionScope<LinearLinkage> p1Scope, ISingleObjectiveSolutionScope<LinearLinkage> p2Scope, CancellationToken token) {
     254      var cache = new HashSet<LinearLinkage>(new LinearLinkageEqualityComparer());
     255      var cachehits = 0;
     256      var evaluations = 1;
     257      ISingleObjectiveSolutionScope<LinearLinkage> offspring = null;
     258      for (; evaluations < Context.LocalSearchEvaluations; evaluations++) {
     259        var code = GroupCrossover.Apply(Context.Random, p1Scope.Solution, p2Scope.Solution);
     260        if (cache.Contains(code)) {
     261          cachehits++;
     262          if (cachehits > 10) break;
     263          continue;
     264        }
     265        var probe = ToScope(code);
     266        Evaluate(probe, token);
     267        cache.Add(code);
     268        if (offspring == null || Context.IsBetter(probe, offspring)) {
     269          offspring = probe;
     270          if (Context.IsBetter(offspring, p1Scope) && Context.IsBetter(offspring, p2Scope))
     271            break;
     272        }
     273      }
     274      Context.IncrementEvaluatedSolutions(evaluations-1);
     275      return offspring;
     276    }
     277
     278    protected override ISingleObjectiveSolutionScope<LinearLinkage> Link(ISingleObjectiveSolutionScope<LinearLinkage> a, ISingleObjectiveSolutionScope<LinearLinkage> b, CancellationToken token, bool delink = false) {
     279      var evaluations = 0;
    284280      if (double.IsNaN(a.Fitness)) {
    285281        Evaluate(a, token);
    286         Context.IncrementEvaluatedSolutions(1);
     282        evaluations++;
    287283      }
    288284      if (double.IsNaN(b.Fitness)) {
    289285        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;
     286        evaluations++;
     287      }
     288
     289      var probe = (ISingleObjectiveSolutionScope<LinearLinkage>)a.Clone();
     290      ISingleObjectiveSolutionScope<LinearLinkage> best = null;
     291      while (true) {
     292        Move bestMove = null;
     293        var bestMoveQ = double.NaN;
     294        // this approach may not fully relink the two solutions
     295        foreach (var m in MoveGenerator.Generate(probe.Solution)) {
     296          var distBefore = Dist(probe, b);
     297          m.Apply(probe.Solution);
     298          var distAfter = Dist(probe, b);
     299          if (delink && distAfter > distBefore || !delink && distAfter < distBefore) {
     300            var beforeQ = probe.Fitness;
     301            Evaluate(probe, token);
     302            evaluations++;
     303            var q = probe.Fitness;
     304            m.Undo(probe.Solution);
     305            probe.Fitness = beforeQ;
     306
     307            if (Context.IsBetter(q, bestMoveQ)) {
     308              bestMove = m;
     309              bestMoveQ = q;
     310            }
     311            if (Context.IsBetter(q, beforeQ)) break;
     312          } else m.Undo(probe.Solution);
     313        }
     314        if (bestMove == null) break;
     315        bestMove.Apply(probe.Solution);
     316        probe.Fitness = bestMoveQ;
     317        if (best == null || Context.IsBetter(probe, best))
     318          best = (ISingleObjectiveSolutionScope<LinearLinkage>)probe.Clone();
     319      }
     320      Context.IncrementEvaluatedSolutions(evaluations);
     321
     322      return best ?? probe;
    317323    }
    318324  }
Note: See TracChangeset for help on using the changeset viewer.