Changeset 14551


Ignore:
Timestamp:
01/08/17 22:16:19 (3 years ago)
Author:
abeham
Message:

#2701: refactored breeding, removed hillclimbing after breeding

Location:
branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Binary/BinaryMemPR.cs

    r14550 r14551  
    2727using HeuristicLab.Common;
    2828using HeuristicLab.Core;
     29using HeuristicLab.Data;
    2930using HeuristicLab.Encodings.BinaryVectorEncoding;
    3031using HeuristicLab.Optimization;
     
    156157      var evaluations = 0;
    157158      var N = p1.Solution.Length;
    158       if (double.IsNaN(p1.Fitness)) {
    159         Evaluate(p1, token);
    160         evaluations++;
    161       }
    162       if (double.IsNaN(p2.Fitness)) {
    163         Evaluate(p2, token);
    164         evaluations++;
    165       }
    166       var better = Problem.Maximization ? Math.Max(p1.Fitness, p2.Fitness)
    167                                         : Math.Min(p1.Fitness, p2.Fitness);
    168 
     159
     160      var probe = ToScope((BinaryVector)p1.Solution.Clone());
    169161
    170162      var cache = new HashSet<BinaryVector>(new BinaryVectorEqualityComparer());
     
    172164      cache.Add(p2.Solution);
    173165
     166      var cacheHits = 0;
    174167      ISingleObjectiveSolutionScope<BinaryVector> offspring = null;
    175       var probe = ToScope(new BinaryVector(N));
    176       // first try all possible combinations of 1-point crossover
    177       /*var order = Enumerable.Range(1, N - 2).Where(x => p1.Solution[x] != p2.Solution[x]).Shuffle(Context.Random).ToList();
    178       foreach (var b in order) {
    179         for (var i = 0; i <= b; i++)
    180           probe.Solution[i] = p1.Solution[i];
    181         for (var i = b + 1; i < probe.Solution.Length; i++)
    182           probe.Solution[i] = p2.Solution[i];
    183 
    184         // only add to cache, because all solutions must be unique
    185         if (cache.Contains(probe.Solution)) continue;
    186         cache.Add(probe.Solution);
     168      while (evaluations < N) {
     169        BinaryVector c = null;
     170        var xochoice = Context.Random.Next(3);
     171        switch (xochoice) {
     172          case 0: c = NPointCrossover.Apply(Context.Random, p1.Solution, p2.Solution, new IntValue(1)); break;
     173          case 1: c = NPointCrossover.Apply(Context.Random, p1.Solution, p2.Solution, new IntValue(2)); break;
     174          case 2: c = UniformCrossover.Apply(Context.Random, p1.Solution, p2.Solution); break;
     175        }
     176        if (cache.Contains(c)) {
     177          cacheHits++;
     178          if (cacheHits > 10) break;
     179          continue;
     180        }
    187181        Evaluate(probe, token);
    188182        evaluations++;
     183        cache.Add(c);
    189184        if (offspring == null || Context.IsBetter(probe, offspring)) {
    190           // immediately return upon finding a better offspring than better parent
    191           if (Context.IsBetter(probe.Fitness, better)) {
    192             Context.IncrementEvaluatedSolutions(evaluations);
    193             return probe;
    194           }
    195           offspring = (ISingleObjectiveSolutionScope<BinaryVector>)probe.Clone();
    196         }
    197       }*/
    198 
    199       var cacheHits = 0;
    200       // if we got some evaluations left, try uniform crossover
    201       while (evaluations < Math.Min(Context.LocalSearchEvaluations, N)) {
    202         probe.Solution = UniformCrossover.Apply(Context.Random, p1.Solution, p2.Solution);
    203         if (cache.Contains(probe.Solution)) {
    204           cacheHits++;
    205           if (cacheHits > 10) break; // variability of uniform crossover is too low -> parents are too similar
    206           continue;
    207         } else cache.Add(probe.Solution);
    208         Evaluate(probe, token);
    209         evaluations++;
    210         if (offspring == null || Context.IsBetter(probe, offspring)) {
    211           // immediately return upon finding a better offspring than better parent
    212           if (Context.IsBetter(probe.Fitness, better)) {
    213             Context.IncrementEvaluatedSolutions(evaluations);
    214             return probe;
    215           }
    216           offspring = (ISingleObjectiveSolutionScope<BinaryVector>)probe.Clone();
     185          offspring = probe;
     186          if (Context.IsBetter(offspring, p1) && Context.IsBetter(offspring, p2))
     187            break;
    217188        }
    218189      }
    219190      Context.IncrementEvaluatedSolutions(evaluations);
    220       // return best offspring found
    221191      return offspring ?? probe;
    222192    }
     
    224194    protected override ISingleObjectiveSolutionScope<BinaryVector> Link(ISingleObjectiveSolutionScope<BinaryVector> a, ISingleObjectiveSolutionScope<BinaryVector> b, CancellationToken token, bool delink = false) {
    225195      var evaluations = 0;
    226       if (double.IsNaN(a.Fitness)) {
    227         Evaluate(a, token);
    228         evaluations++;
    229       }
    230       if (double.IsNaN(b.Fitness)) {
    231         Evaluate(b, token);
    232         evaluations++;
    233       }
    234 
    235196      var childScope = (ISingleObjectiveSolutionScope<BinaryVector>)a.Clone();
    236197      var child = childScope.Solution;
  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/LinearLinkage/LinearLinkageMemPR.cs

    r14550 r14551  
    248248    }
    249249
    250     protected override ISingleObjectiveSolutionScope<LinearLinkage> Breed(ISingleObjectiveSolutionScope<LinearLinkage> p1Scope, ISingleObjectiveSolutionScope<LinearLinkage> p2Scope, CancellationToken token) {
     250    protected override ISingleObjectiveSolutionScope<LinearLinkage> Breed(ISingleObjectiveSolutionScope<LinearLinkage> p1, ISingleObjectiveSolutionScope<LinearLinkage> p2, CancellationToken token) {
    251251      var cache = new HashSet<LinearLinkage>(new LinearLinkageEqualityComparer());
     252      cache.Add(p1.Solution);
     253      cache.Add(p2.Solution);
     254
    252255      var cachehits = 0;
    253       var evaluations = 1;
     256      var evaluations = 0;
     257      var probe = ToScope((LinearLinkage)p1.Solution.Clone());
    254258      ISingleObjectiveSolutionScope<LinearLinkage> offspring = null;
    255       for (; evaluations < p1Scope.Solution.Length; evaluations++) {
    256         var code = GroupCrossover.Apply(Context.Random, p1Scope.Solution, p2Scope.Solution);
    257         if (cache.Contains(code)) {
     259      while (evaluations < p1.Solution.Length) {
     260        LinearLinkage c = null;
     261        if (Context.Random.NextDouble() < 0.8)
     262          c = GroupCrossover.Apply(Context.Random, p1.Solution, p2.Solution);
     263        else c = SinglePointCrossover.Apply(Context.Random, p1.Solution, p2.Solution);
     264       
     265        if (cache.Contains(c)) {
    258266          cachehits++;
    259267          if (cachehits > 10) break;
    260268          continue;
    261269        }
    262         var probe = ToScope(code);
    263270        Evaluate(probe, token);
    264         cache.Add(code);
     271        evaluations++;
     272        cache.Add(c);
    265273        if (offspring == null || Context.IsBetter(probe, offspring)) {
    266274          offspring = probe;
    267           if (Context.IsBetter(offspring, p1Scope) && Context.IsBetter(offspring, p2Scope))
     275          if (Context.IsBetter(offspring, p1) && Context.IsBetter(offspring, p2))
    268276            break;
    269277        }
    270278      }
    271       Context.IncrementEvaluatedSolutions(evaluations-1);
    272       return offspring;
     279      Context.IncrementEvaluatedSolutions(evaluations);
     280      return offspring ?? probe;
    273281    }
    274282
  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/MemPRAlgorithm.cs

    r14550 r14551  
    660660      if (Context.Population.All(p => Context.IsBetter(link, p)))
    661661        HillClimb(link, token);
    662       /*else if (!Eq(link, p1) && !Eq(link, p2) && Context.HillclimbingSuited(link.Fitness))
    663         HillClimb(link, token, CalculateSubspace(new[] { p1.Solution, p2.Solution }, inverse: false));*/
    664 
     662      // intentionally not making hill climbing after delinking in sub-space
    665663      return link;
    666664    }
  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/PermutationMemPR.cs

    r14550 r14551  
    395395    private ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> CrossAbsolute(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p1, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p2, CancellationToken token) {
    396396      var cache = new HashSet<Encodings.PermutationEncoding.Permutation>(new PermutationEqualityComparer());
     397      cache.Add(p1.Solution);
     398      cache.Add(p2.Solution);
     399
    397400      var cacheHits = 0;
    398       var evaluations = 1;
     401      var evaluations = 0;
    399402      ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> offspring = null;
    400       for (; evaluations <= p1.Solution.Length; evaluations++) {
     403      while (evaluations < p1.Solution.Length) {
    401404        Encodings.PermutationEncoding.Permutation c = null;
    402405        var xochoice = Context.Random.Next(3);
     
    413416        var probe = ToScope(c);
    414417        Evaluate(probe, token);
     418        evaluations++;
    415419        cache.Add(c);
    416420        if (offspring == null || Context.IsBetter(probe, offspring)) {
     
    420424        }
    421425      }
    422       Context.IncrementEvaluatedSolutions(evaluations-1);
     426      Context.IncrementEvaluatedSolutions(evaluations);
    423427      return offspring;
    424428    }
     
    426430    private ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> CrossRelativeDirected(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p1, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p2, CancellationToken token) {
    427431      var cache = new HashSet<Encodings.PermutationEncoding.Permutation>(new PermutationEqualityComparer());
     432      cache.Add(p1.Solution);
     433      cache.Add(p2.Solution);
     434
    428435      var cacheHits = 0;
    429       var evaluations = 1;
     436      var evaluations = 0;
    430437      ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> offspring = null;
    431       for (; evaluations <= p1.Solution.Length; evaluations++) {
     438      while(evaluations < p1.Solution.Length) {
    432439        Encodings.PermutationEncoding.Permutation c = null;
    433440        var xochoice = Context.Random.Next(3);
     
    444451        var probe = ToScope(c);
    445452        Evaluate(probe, token);
     453        evaluations++;
    446454        cache.Add(c);
    447455        if (offspring == null || Context.IsBetter(probe, offspring)) {
     
    451459        }
    452460      }
    453       Context.IncrementEvaluatedSolutions(evaluations-1);
     461      Context.IncrementEvaluatedSolutions(evaluations);
    454462      return offspring;
    455463    }
     
    457465    private ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> CrossRelativeUndirected(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p1, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p2, CancellationToken token) {
    458466      var cache = new HashSet<Encodings.PermutationEncoding.Permutation>(new PermutationEqualityComparer());
     467      cache.Add(p1.Solution);
     468      cache.Add(p2.Solution);
     469
    459470      var cacheHits = 0;
    460       var evaluations = 1;
     471      var evaluations = 0;
    461472      ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> offspring = null;
    462       for (; evaluations <= p1.Solution.Length; evaluations++) {
     473      while(evaluations <= p1.Solution.Length) {
    463474        Encodings.PermutationEncoding.Permutation c = null;
    464475        var xochoice = Context.Random.Next(3);
     
    475486        var probe = ToScope(c);
    476487        Evaluate(probe, token);
     488        evaluations++;
    477489        cache.Add(c);
    478490        if (offspring == null || Context.IsBetter(probe, offspring)) {
     
    482494        }
    483495      }
    484       Context.IncrementEvaluatedSolutions(evaluations-1);
     496      Context.IncrementEvaluatedSolutions(evaluations);
    485497      return offspring;
    486498    }
    487499
    488500    protected override ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> Link(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> a, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> b, CancellationToken token, bool delink = false) {
    489       if (double.IsNaN(a.Fitness)) {
    490         Evaluate(a, token);
    491         Context.IncrementEvaluatedSolutions(1);
    492       }
    493       if (double.IsNaN(b.Fitness)) {
    494         Evaluate(b, token);
    495         Context.IncrementEvaluatedSolutions(1);
    496       }
    497 
    498501      var wrapper = new EvaluationWrapper<Encodings.PermutationEncoding.Permutation>(Problem, ToScope(null));
    499502      double quality;
     
    626629      Context.IncrementEvaluatedSolutions(evaluations);
    627630
    628       if (VALIDATE && bestChild != null && !bestChild.Validate()) throw new ArgumentException("Relinking produced invalid child");
    629       if (VALIDATE && Dist(child, p2) > 0) throw new InvalidOperationException("Child is not equal to p2 after relinking");
     631      if (VALIDATE && bestChild != null && !bestChild.Validate()) throw new ArgumentException("Delinking produced invalid child");
    630632
    631633      return bestChild ?? child;
Note: See TracChangeset for help on using the changeset viewer.