Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
01/13/17 18:18:37 (7 years ago)
Author:
abeham
Message:

#2701:

  • Tagged unbiased models with property
  • Changed default configuration
  • Added solution distance to breeding, relinking and delinking performance models
  • Changed sampling model to base prediction on average distance in genotype space
  • Changed target for hillclimber and relinking to relative (quality improvement)
  • changed breeding to count cache hits per crossover
File:
1 edited

Legend:

Unmodified
Added
Removed

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

    r14562 r14563  
    138138    [Storable]
    139139    private BestAverageWorstQualityAnalyzer qualityAnalyzer;
     140    [Storable]
     141    private QualityPerClockAnalyzer qualityPerClockAnalyzer;
     142    [Storable]
     143    private QualityPerEvaluationsAnalyzer qualityPerEvaluationsAnalyzer;
    140144
    141145    [StorableConstructor]
    … …  
    144148      context = cloner.Clone(original.context);
    145149      qualityAnalyzer = cloner.Clone(original.qualityAnalyzer);
     150      qualityPerClockAnalyzer = cloner.Clone(original.qualityPerClockAnalyzer);
     151      qualityPerEvaluationsAnalyzer = cloner.Clone(original.qualityPerEvaluationsAnalyzer);
     152
    146153      RegisterEventHandlers();
    147154    }
    … …  
    150157      Parameters.Add(new FixedValueParameter<IntValue>("MaximumPopulationSize", "The maximum size of the population that is evolved.", new IntValue(20)));
    151158      Parameters.Add(new OptionalValueParameter<IntValue>("MaximumEvaluations", "The maximum number of solution evaluations."));
    152       Parameters.Add(new OptionalValueParameter<TimeSpanValue>("MaximumExecutionTime", "The maximum runtime.", new TimeSpanValue(TimeSpan.FromMinutes(1))));
     159      Parameters.Add(new OptionalValueParameter<TimeSpanValue>("MaximumExecutionTime", "The maximum runtime.", new TimeSpanValue(TimeSpan.FromMinutes(10))));
    153160      Parameters.Add(new OptionalValueParameter<DoubleValue>("TargetQuality", "The target quality at which the algorithm terminates."));
    154161      Parameters.Add(new FixedValueParameter<BoolValue>("SetSeedRandomly", "Whether each run of the algorithm should be conducted with a new random seed.", new BoolValue(true)));
    … …  
    158165
    159166      qualityAnalyzer = new BestAverageWorstQualityAnalyzer();
     167      qualityPerClockAnalyzer = new QualityPerClockAnalyzer();
     168      qualityPerEvaluationsAnalyzer = new QualityPerEvaluationsAnalyzer();
     169
    160170      RegisterEventHandlers();
    161171    }
    … …  
    193203            foreach (var param in analyzer.Parameters.OfType<IScopeTreeLookupParameter>())
    194204              param.Depth = 1;
    195             multiAnalyzer.Operators.Add(analyzer, analyzer.EnabledByDefault);
     205            multiAnalyzer.Operators.Add(analyzer, analyzer.EnabledByDefault || analyzer is ISimilarityBasedOperator);
    196206          }
    197207        }
    198208        multiAnalyzer.Operators.Add(qualityAnalyzer, qualityAnalyzer.EnabledByDefault);
     209        multiAnalyzer.Operators.Add(qualityPerClockAnalyzer, true);
     210        multiAnalyzer.Operators.Add(qualityPerEvaluationsAnalyzer, true);
    199211      }
    200212    }
    … …  
    300312
    301313      if (!replaced) {
    302         offspring = (ISingleObjectiveSolutionScope<TSolution>)Context.Population.SampleRandom(Context.Random).Clone();
    303         var before = offspring.Fitness;
     314        var before = Context.Population.SampleRandom(Context.Random);
     315        offspring = (ISingleObjectiveSolutionScope<TSolution>)before.Clone();
    304316        AdaptiveWalk(offspring, Context.LocalSearchEvaluations * 2, token);
    305         Context.AdaptivewalkingStat.Add(Tuple.Create(before, offspring.Fitness));
    306         if (Context.AdaptivewalkingStat.Count % 10 == 0) Context.RelearnAdaptiveWalkPerformanceModel();
     317        if (!Eq(before, offspring))
     318          Context.AddAdaptivewalkingResult(before, offspring);
    307319        if (Replace(offspring, token)) {
    308320          Context.ByAdaptivewalking++;
    … …  
    345357
    346358      var sp = new ScatterPlot("Breeding Correlation", "");
    347       sp.Rows.Add(new ScatterPlotDataRow("Parent1 vs Offspring", "", Context.BreedingStat.Select(x => new Point2D<double>(x.Item1, x.Item3))) { VisualProperties = { PointSize = 6 }});
    348       sp.Rows.Add(new ScatterPlotDataRow("Parent2 vs Offspring", "", Context.BreedingStat.Select(x => new Point2D<double>(x.Item2, x.Item3))) { VisualProperties = { PointSize = 6 } });
     359      sp.Rows.Add(new ScatterPlotDataRow("Parent1 vs Offspring", "", Context.BreedingStat.Select(x => new Point2D<double>(x.Item1, x.Item4))) { VisualProperties = { PointSize = 6 }});
     360      sp.Rows.Add(new ScatterPlotDataRow("Parent2 vs Offspring", "", Context.BreedingStat.Select(x => new Point2D<double>(x.Item2, x.Item4))) { VisualProperties = { PointSize = 6 } });
     361      sp.Rows.Add(new ScatterPlotDataRow("Parent Distance vs Offspring", "", Context.BreedingStat.Select(x => new Point2D<double>(x.Item3, x.Item4))) { VisualProperties = { PointSize = 6 } });
    349362      if (!Results.TryGetValue("BreedingStat", out res)) {
    350363        Results.Add(new Result("BreedingStat", sp));
    … …  
    352365
    353366      sp = new ScatterPlot("Relinking Correlation", "");
    354       sp.Rows.Add(new ScatterPlotDataRow("A vs Relink", "", Context.RelinkingStat.Select(x => new Point2D<double>(x.Item1, x.Item3))) { VisualProperties = { PointSize = 6 } });
    355       sp.Rows.Add(new ScatterPlotDataRow("B vs Relink", "", Context.RelinkingStat.Select(x => new Point2D<double>(x.Item2, x.Item3))) { VisualProperties = { PointSize = 6 } });
     367      sp.Rows.Add(new ScatterPlotDataRow("A vs Relink", "", Context.RelinkingStat.Select(x => new Point2D<double>(x.Item1, x.Item4))) { VisualProperties = { PointSize = 6 } });
     368      sp.Rows.Add(new ScatterPlotDataRow("B vs Relink", "", Context.RelinkingStat.Select(x => new Point2D<double>(x.Item2, x.Item4))) { VisualProperties = { PointSize = 6 } });
     369      sp.Rows.Add(new ScatterPlotDataRow("d(A,B) vs Offspring", "", Context.RelinkingStat.Select(x => new Point2D<double>(x.Item3, x.Item4))) { VisualProperties = { PointSize = 6 } });
    356370      if (!Results.TryGetValue("RelinkingStat", out res)) {
    357371        Results.Add(new Result("RelinkingStat", sp));
    … …  
    359373
    360374      sp = new ScatterPlot("Delinking Correlation", "");
    361       sp.Rows.Add(new ScatterPlotDataRow("A vs Delink", "", Context.DelinkingStat.Select(x => new Point2D<double>(x.Item1, x.Item3))) { VisualProperties = { PointSize = 6 } });
    362       sp.Rows.Add(new ScatterPlotDataRow("B vs Delink", "", Context.DelinkingStat.Select(x => new Point2D<double>(x.Item2, x.Item3))) { VisualProperties = { PointSize = 6 } });
     375      sp.Rows.Add(new ScatterPlotDataRow("A vs Delink", "", Context.DelinkingStat.Select(x => new Point2D<double>(x.Item1, x.Item4))) { VisualProperties = { PointSize = 6 } });
     376      sp.Rows.Add(new ScatterPlotDataRow("B vs Delink", "", Context.DelinkingStat.Select(x => new Point2D<double>(x.Item2, x.Item4))) { VisualProperties = { PointSize = 6 } });
     377      sp.Rows.Add(new ScatterPlotDataRow("d(A,B) vs Offspring", "", Context.DelinkingStat.Select(x => new Point2D<double>(x.Item3, x.Item4))) { VisualProperties = { PointSize = 6 } });
    363378      if (!Results.TryGetValue("DelinkingStat", out res)) {
    364379        Results.Add(new Result("DelinkingStat", sp));
    … …  
    372387
    373388      sp = new ScatterPlot("Hillclimbing Correlation", "");
    374       sp.Rows.Add(new ScatterPlotDataRow("Start vs End", "", Context.HillclimbingStat.Select(x => new Point2D<double>(x.Item1, x.Item2))) { VisualProperties = { PointSize = 6 } });
     389      sp.Rows.Add(new ScatterPlotDataRow("Start vs Improvement", "", Context.HillclimbingStat.Select(x => new Point2D<double>(x.Item1, x.Item2))) { VisualProperties = { PointSize = 6 } });
    375390      if (!Results.TryGetValue("HillclimbingStat", out res)) {
    376391        Results.Add(new Result("HillclimbingStat", sp));
    … …  
    535550        Context.IncrementEvaluatedSolutions(1);
    536551      }
    537       var before = scope.Fitness;
     552      var before = (ISingleObjectiveSolutionScope<TSolution>)scope.Clone();
    538553      var lscontext = Context.CreateSingleSolutionContext(scope);
    539554      LocalSearchParameter.Value.Optimize(lscontext);
    540       var after = scope.Fitness;
    541       Context.HillclimbingStat.Add(Tuple.Create(before, after));
    542       if (Context.HillclimbingStat.Count % 10 == 0) Context.RelearnHillclimbingPerformanceModel();
     555      Context.AddHillclimbingResult(before, scope);
    543556      Context.IncrementEvaluatedSolutions(lscontext.EvaluatedSolutions);
    544557      return lscontext.EvaluatedSolutions;
    … …  
    550563        Context.IncrementEvaluatedSolutions(1);
    551564      }
    552       var before = scope.Fitness;
    553565      var newScope = (ISingleObjectiveSolutionScope<TSolution>)scope.Clone();
    554566      AdaptiveWalk(newScope, maxEvals, token, subspace);
    555       Context.AdaptivewalkingStat.Add(Tuple.Create(before, newScope.Fitness));
    556       if (Context.AdaptivewalkingStat.Count % 10 == 0) Context.RelearnAdaptiveWalkPerformanceModel();
    557       if (Context.IsBetter(newScope, scope))
     567     
     568      if (Context.IsBetter(newScope, scope)) {
     569        Context.AddAdaptivewalkingResult(scope, newScope);
    558570        scope.Adopt(newScope);
     571      } else if (!Eq(newScope, scope))
     572        Context.AddAdaptivewalkingResult(scope, newScope);
    559573    }
    560574    protected abstract void AdaptiveWalk(ISingleObjectiveSolutionScope<TSolution> scope, int maxEvals, CancellationToken token, ISolutionSubspace<TSolution> subspace = null);
    … …  
    580594      }
    581595
    582       if (Context.BreedingSuited(p1, p2)) {
    583         var offspring = Breed(p1, p2, token);
    584 
    585         if (double.IsNaN(offspring.Fitness)) {
    586           Context.Evaluate(offspring, token);
    587           Context.IncrementEvaluatedSolutions(1);
    588         }
    589 
    590         // new best solutions are improved using hill climbing in full solution space
    591         if (Context.Population.All(p => Context.IsBetter(offspring, p)))
    592           HillClimb(offspring, token);
    593         else if (!Eq(offspring, p1) && !Eq(offspring, p2) && Context.HillclimbingSuited(offspring.Fitness))
    594           HillClimb(offspring, token, CalculateSubspace(new[] { p1.Solution, p2.Solution }, inverse: false));
    595 
    596         Context.AddBreedingResult(p1, p2, offspring);
    597         if (Context.BreedingStat.Count % 10 == 0) Context.RelearnBreedingPerformanceModel();
    598         return offspring;
    599       }
    600       return null;
     596      if (!Context.BreedingSuited(p1, p2, Dist(p1, p2))) return null;
     597
     598      var offspring = Breed(p1, p2, token);
     599
     600      if (double.IsNaN(offspring.Fitness)) {
     601        Context.Evaluate(offspring, token);
     602        Context.IncrementEvaluatedSolutions(1);
     603      }
     604
     605      Context.AddBreedingResult(p1, p2, Dist(p1, p2), offspring);
     606
     607      // new best solutions are improved using hill climbing in full solution space
     608      if (Context.Population.All(p => Context.IsBetter(offspring, p)))
     609        HillClimb(offspring, token);
     610      else if (!Eq(offspring, p1) && !Eq(offspring, p2) && Context.HillclimbingSuited(offspring.Fitness))
     611        HillClimb(offspring, token, CalculateSubspace(new[] { p1.Solution, p2.Solution }, inverse: false));
     612
     613      return offspring;
    601614    }
    602615
    … …  
    613626      var p2 = Context.AtPopulation(i2);
    614627
    615       if (!Context.RelinkSuited(p1, p2)) return null;
     628      if (!Context.RelinkSuited(p1, p2, Dist(p1, p2))) return null;
    616629
    617630      var link = PerformRelinking(p1, p2, token, delink: false);
    618       if (double.IsNaN(link.Fitness)) {
    619         Context.Evaluate(link, token);
    620         Context.IncrementEvaluatedSolutions(1);
    621       }
     631
    622632      // new best solutions are improved using hill climbing in full solution space
    623633      if (Context.Population.All(p => Context.IsBetter(link, p)))
    … …  
    637647      var p2 = Context.AtPopulation(i2);
    638648     
    639       if (!Context.DelinkSuited(p1, p2)) return null;
     649      if (!Context.DelinkSuited(p1, p2, Dist(p1, p2))) return null;
    640650
    641651      var link = PerformRelinking(p1, p2, token, delink: true);
    642       if (double.IsNaN(link.Fitness)) {
    643         Context.Evaluate(link, token);
    644         Context.IncrementEvaluatedSolutions(1);
    645       }
     652
    646653      // new best solutions are improved using hill climbing in full solution space
    647654      if (Context.Population.All(p => Context.IsBetter(link, p)))
    648655        HillClimb(link, token);
    649       // intentionally not making hill climbing after delinking in sub-space
     656      // intentionally not making hill climbing otherwise after delinking in sub-space
    650657      return link;
    651658    }
    … …  
    659666      }
    660667
    661       // new best solutions are improved using hill climbing
    662       if (Context.Population.All(p => Context.IsBetter(relink, p)))
    663         HillClimb(relink, token);
    664 
    665668      if (delink) {
    666         Context.AddDelinkingResult(a, b, relink);
    667         if (Context.DelinkingStat.Count % 10 == 0) Context.RelearnDelinkingPerformanceModel();
     669        Context.AddDelinkingResult(a, b, Dist(a, b), relink);
    668670      } else {
    669         Context.AddRelinkingResult(a, b, relink);
    670         if (context.RelinkingStat.Count % 10 == 0) Context.RelearnRelinkingPerformanceModel();
    671       }
     671        Context.AddRelinkingResult(a, b, Dist(a, b), relink);
     672      }
     673
    672674      return relink;
    673675    }
    … …  
    682684        ISingleObjectiveSolutionScope<TSolution> bestSample = null;
    683685        var tries = 1;
     686        var avgDist = (from a in Context.Population.Shuffle(Context.Random)
     687                       from b in Context.Population.Shuffle(Context.Random)
     688                       select Dist(a, b)).Average();
    684689        for (; tries < 100; tries++) {
    685690          var sample = Context.ToScope(Context.Model.Sample());
    … …  
    689694            if (Context.Population.Any(x => !Context.IsBetter(x, bestSample))) break;
    690695          }
    691           if (!Context.SamplingSuited()) break;
     696          if (!Context.SamplingSuited(avgDist)) break;
    692697        }
    693698        Context.IncrementEvaluatedSolutions(tries);
    694         Context.AddSamplingResult(bestSample);
    695         if (Context.SamplingStat.Count % 10 == 0) Context.RelearnSamplingPerformanceModel();
     699        Context.AddSamplingResult(bestSample, avgDist);
    696700        return bestSample;
    697701      }
Note: See TracChangeset for help on using the changeset viewer.