Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
01/05/17 00:32:43 (7 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/MemPRAlgorithm.cs

    r14496 r14544  
    2424using System.ComponentModel;
    2525using System.Linq;
    26 using System.Runtime.CompilerServices;
    2726using System.Threading;
    2827using HeuristicLab.Algorithms.MemPR.Interfaces;
    29 using HeuristicLab.Algorithms.MemPR.Util;
    3028using HeuristicLab.Analysis;
    3129using HeuristicLab.Common;
    … …  
    3533using HeuristicLab.Parameters;
    3634using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     35using HeuristicLab.Random;
    3736
    3837namespace HeuristicLab.Algorithms.MemPR {
    … …  
    231230          var child = Create(token);
    232231          Context.LocalSearchEvaluations += HillClimb(child, token);
    233           if (Replace(child, token) >= 0)
    234             Analyze(token);
     232          Context.AddToPopulation(child);
     233          Context.BestQuality = child.Fitness;
     234          Analyze(token);
    235235          token.ThrowIfCancellationRequested();
    236236          if (Terminate()) return;
    … …  
    249249    private void Iterate(CancellationToken token) {
    250250      var replaced = false;
    251 
    252       var i1 = Context.Random.Next(Context.PopulationCount);
    253       var i2 = Context.Random.Next(Context.PopulationCount);
    254       while (i1 == i2) i2 = Context.Random.Next(Context.PopulationCount);
    255 
    256       var p1 = Context.AtPopulation(i1);
    257       var p2 = Context.AtPopulation(i2);
    258 
    259       var parentDist = Dist(p1, p2);
    260 
    261251      ISingleObjectiveSolutionScope<TSolution> offspring = null;
    262       int replPos = -1;
    263 
    264       if (Context.Random.NextDouble() > parentDist * parentDist) {
    265         offspring = BreedAndImprove(p1, p2, token);
    266         replPos = Replace(offspring, token);
    267         if (replPos >= 0) {
     252     
     253      offspring = Breed(token);
     254      if (offspring != null) {
     255        if (Context.PopulationCount < MaximumPopulationSize)
     256          HillClimb(offspring, token);
     257        var replNew = Replace(offspring, token);
     258        if (replNew) {
    268259          replaced = true;
    269260          Context.ByBreeding++;
    … …  
    271262      }
    272263
    273       if (Context.Random.NextDouble() < Math.Sqrt(parentDist)) {
    274         offspring = RelinkAndImprove(p1, p2, token);
    275         replPos = Replace(offspring, token);
    276         if (replPos >= 0) {
     264      offspring = Relink(token);
     265      if (offspring != null) {
     266        if (Context.PopulationCount < MaximumPopulationSize)
     267          HillClimb(offspring, token);
     268        if (Replace(offspring, token)) {
    277269          replaced = true;
    278270          Context.ByRelinking++;
    … …  
    280272      }
    281273
    282       offspring = PerformSampling(token);
    283       replPos = Replace(offspring, token);
    284       if (replPos >= 0) {
    285         replaced = true;
    286         Context.BySampling++;
    287       }
    288 
    289       if (!replaced) {
    290         offspring = Create(token);
    291         if (HillclimbingSuited(offspring)) {
     274      offspring = Delink(token);
     275      if (offspring != null) {
     276        if (Context.PopulationCount < MaximumPopulationSize)
    292277          HillClimb(offspring, token);
    293           replPos = Replace(offspring, token);
    294           if (replPos >= 0) {
     278        if (Replace(offspring, token)) {
     279          replaced = true;
     280          Context.ByDelinking++;
     281        }
     282      }
     283
     284      offspring = Sample(token);
     285      if (offspring != null) {
     286        if (Context.PopulationCount < MaximumPopulationSize)
     287          HillClimb(offspring, token);
     288        if (Replace(offspring, token)) {
     289          replaced = true;
     290          Context.BySampling++;
     291        }
     292      }
     293
     294      if (!replaced && offspring != null) {
     295        if (Context.HillclimbingSuited(offspring)) {
     296          HillClimb(offspring, token);
     297          if (Replace(offspring, token)) {
    295298            Context.ByHillclimbing++;
    296299            replaced = true;
    297300          }
    298         } else {
    299           offspring = (ISingleObjectiveSolutionScope<TSolution>)Context.AtPopulation(Context.Random.Next(Context.PopulationCount)).Clone();
    300           Mutate(offspring, token);
    301           PerformTabuWalk(offspring, Context.LocalSearchEvaluations, token);
    302           replPos = Replace(offspring, token);
    303           if (replPos >= 0) {
    304             Context.ByTabuwalking++;
    305             replaced = true;
    306           }
    307         }
    308       }
     301        }
     302      }
     303
     304      if (!replaced) {
     305        offspring = (ISingleObjectiveSolutionScope<TSolution>)Context.Population.SampleRandom(Context.Random).Clone();
     306        var before = offspring.Fitness;
     307        AdaptiveWalk(offspring, Context.LocalSearchEvaluations * 2, token);
     308        Context.AdaptivewalkingStat.Add(Tuple.Create(before, offspring.Fitness));
     309        if (Context.AdaptivewalkingStat.Count % 10 == 0) Context.RelearnAdaptiveWalkPerformanceModel();
     310        if (Replace(offspring, token)) {
     311          Context.ByAdaptivewalking++;
     312          replaced = true;
     313        }
     314      }
     315
    309316      Context.Iterations++;
    310317    }
    … …  
    327334        Results.Add(new Result("ByRelinking", new IntValue(Context.ByRelinking)));
    328335      else ((IntValue)res.Value).Value = Context.ByRelinking;
     336      if (!Results.TryGetValue("ByDelinking", out res))
     337        Results.Add(new Result("ByDelinking", new IntValue(Context.ByDelinking)));
     338      else ((IntValue)res.Value).Value = Context.ByDelinking;
    329339      if (!Results.TryGetValue("BySampling", out res))
    330340        Results.Add(new Result("BySampling", new IntValue(Context.BySampling)));
    … …  
    333343        Results.Add(new Result("ByHillclimbing", new IntValue(Context.ByHillclimbing)));
    334344      else ((IntValue)res.Value).Value = Context.ByHillclimbing;
    335       if (!Results.TryGetValue("ByTabuwalking", out res))
    336         Results.Add(new Result("ByTabuwalking", new IntValue(Context.ByTabuwalking)));
    337       else ((IntValue)res.Value).Value = Context.ByTabuwalking;
    338 
    339       var sp = new ScatterPlot("Parent1 vs Offspring", "");
    340       sp.Rows.Add(new ScatterPlotDataRow("corr", "", Context.BreedingStat.Select(x => new Point2D<double>(x.Item1, x.Item3))) { VisualProperties = { PointSize = 6 }});
    341       if (!Results.TryGetValue("BreedingStat1", out res)) {
    342         Results.Add(new Result("BreedingStat1", sp));
     345      if (!Results.TryGetValue("ByAdaptivewalking", out res))
     346        Results.Add(new Result("ByAdaptivewalking", new IntValue(Context.ByAdaptivewalking)));
     347      else ((IntValue)res.Value).Value = Context.ByAdaptivewalking;
     348
     349      var sp = new ScatterPlot("Breeding Correlation", "");
     350      sp.Rows.Add(new ScatterPlotDataRow("Parent1 vs Offspring", "", Context.BreedingStat.Select(x => new Point2D<double>(x.Item1, x.Item3))) { VisualProperties = { PointSize = 6 }});
     351      sp.Rows.Add(new ScatterPlotDataRow("Parent2 vs Offspring", "", Context.BreedingStat.Select(x => new Point2D<double>(x.Item2, x.Item3))) { VisualProperties = { PointSize = 6 } });
     352      if (!Results.TryGetValue("BreedingStat", out res)) {
     353        Results.Add(new Result("BreedingStat", sp));
    343354      } else res.Value = sp;
    344355
    345       sp = new ScatterPlot("Parent2 vs Offspring", "");
    346       sp.Rows.Add(new ScatterPlotDataRow("corr", "", Context.BreedingStat.Select(x => new Point2D<double>(x.Item2, x.Item3))) { VisualProperties = { PointSize = 6 } });
    347       if (!Results.TryGetValue("BreedingStat2", out res)) {
    348         Results.Add(new Result("BreedingStat2", sp));
     356      sp = new ScatterPlot("Relinking Correlation", "");
     357      sp.Rows.Add(new ScatterPlotDataRow("A vs Relink", "", Context.RelinkingStat.Select(x => new Point2D<double>(x.Item1, x.Item3))) { VisualProperties = { PointSize = 6 } });
     358      sp.Rows.Add(new ScatterPlotDataRow("B vs Relink", "", Context.RelinkingStat.Select(x => new Point2D<double>(x.Item2, x.Item3))) { VisualProperties = { PointSize = 6 } });
     359      if (!Results.TryGetValue("RelinkingStat", out res)) {
     360        Results.Add(new Result("RelinkingStat", sp));
    349361      } else res.Value = sp;
    350362
    351       sp = new ScatterPlot("Solution vs Local Optimum", "");
    352       sp.Rows.Add(new ScatterPlotDataRow("corr", "", Context.HillclimbingStat.Select(x => new Point2D<double>(x.Item1, x.Item2))) { VisualProperties = { PointSize = 6 } });
     363      sp = new ScatterPlot("Delinking Correlation", "");
     364      sp.Rows.Add(new ScatterPlotDataRow("A vs Delink", "", Context.DelinkingStat.Select(x => new Point2D<double>(x.Item1, x.Item3))) { VisualProperties = { PointSize = 6 } });
     365      sp.Rows.Add(new ScatterPlotDataRow("B vs Delink", "", Context.DelinkingStat.Select(x => new Point2D<double>(x.Item2, x.Item3))) { VisualProperties = { PointSize = 6 } });
     366      if (!Results.TryGetValue("DelinkingStat", out res)) {
     367        Results.Add(new Result("DelinkingStat", sp));
     368      } else res.Value = sp;
     369
     370      sp = new ScatterPlot("Sampling Correlation", "");
     371      sp.Rows.Add(new ScatterPlotDataRow("AvgFitness vs Sample", "", Context.SamplingStat.Select(x => new Point2D<double>(x.Item1, x.Item2))) { VisualProperties = { PointSize = 6 } });
     372      if (!Results.TryGetValue("SampleStat", out res)) {
     373        Results.Add(new Result("SampleStat", sp));
     374      } else res.Value = sp;
     375
     376      sp = new ScatterPlot("Hillclimbing Correlation", "");
     377      sp.Rows.Add(new ScatterPlotDataRow("Start vs End", "", Context.HillclimbingStat.Select(x => new Point2D<double>(x.Item1, x.Item2))) { VisualProperties = { PointSize = 6 } });
    353378      if (!Results.TryGetValue("HillclimbingStat", out res)) {
    354379        Results.Add(new Result("HillclimbingStat", sp));
    355380      } else res.Value = sp;
    356381
    357       sp = new ScatterPlot("Solution vs Tabu Walk", "");
    358       sp.Rows.Add(new ScatterPlotDataRow("corr", "", Context.TabuwalkingStat.Select(x => new Point2D<double>(x.Item1, x.Item2))) { VisualProperties = { PointSize = 6 } });
    359       if (!Results.TryGetValue("TabuwalkingStat", out res)) {
    360         Results.Add(new Result("TabuwalkingStat", sp));
     382      sp = new ScatterPlot("Adaptivewalking Correlation", "");
     383      sp.Rows.Add(new ScatterPlotDataRow("Start vs Best", "", Context.AdaptivewalkingStat.Select(x => new Point2D<double>(x.Item1, x.Item2))) { VisualProperties = { PointSize = 6 } });
     384      if (!Results.TryGetValue("AdaptivewalkingStat", out res)) {
     385        Results.Add(new Result("AdaptivewalkingStat", sp));
    361386      } else res.Value = sp;
    362387
     388      if (Context.BreedingPerformanceModel != null) {
     389        var sol = Context.GetSolution(Context.BreedingPerformanceModel, Context.BreedingStat);
     390        if (!Results.TryGetValue("Breeding Performance", out res)) {
     391          Results.Add(new Result("Breeding Performance", sol));
     392        } else res.Value = sol;
     393      }
     394      if (Context.RelinkingPerformanceModel != null) {
     395        var sol = Context.GetSolution(Context.RelinkingPerformanceModel, Context.RelinkingStat);
     396        if (!Results.TryGetValue("Relinking Performance", out res)) {
     397          Results.Add(new Result("Relinking Performance", sol));
     398        } else res.Value = sol;
     399      }
     400      if (Context.DelinkingPerformanceModel != null) {
     401        var sol = Context.GetSolution(Context.DelinkingPerformanceModel, Context.DelinkingStat);
     402        if (!Results.TryGetValue("Delinking Performance", out res)) {
     403          Results.Add(new Result("Delinking Performance", sol));
     404        } else res.Value = sol;
     405      }
     406      if (Context.SamplingPerformanceModel != null) {
     407        var sol = Context.GetSolution(Context.SamplingPerformanceModel, Context.SamplingStat);
     408        if (!Results.TryGetValue("Sampling Performance", out res)) {
     409          Results.Add(new Result("Sampling Performance", sol));
     410        } else res.Value = sol;
     411      }
     412      if (Context.HillclimbingPerformanceModel != null) {
     413        var sol = Context.GetSolution(Context.HillclimbingPerformanceModel, Context.HillclimbingStat);
     414        if (!Results.TryGetValue("Hillclimbing Performance", out res)) {
     415          Results.Add(new Result("Hillclimbing Performance", sol));
     416        } else res.Value = sol;
     417      }
     418      if (Context.AdaptiveWalkPerformanceModel != null) {
     419        var sol = Context.GetSolution(Context.AdaptiveWalkPerformanceModel, Context.AdaptivewalkingStat);
     420        if (!Results.TryGetValue("Adaptivewalk Performance", out res)) {
     421          Results.Add(new Result("Adaptivewalk Performance", sol));
     422        } else res.Value = sol;
     423      }
     424
    363425      RunOperator(Analyzer, Context.Scope, token);
    364426    }
    365427
    366     protected int Replace(ISingleObjectiveSolutionScope<TSolution> child, CancellationToken token) {
     428    protected bool Replace(ISingleObjectiveSolutionScope<TSolution> child, CancellationToken token) {
    367429      if (double.IsNaN(child.Fitness)) {
    368430        Evaluate(child, token);
    369431        Context.IncrementEvaluatedSolutions(1);
    370432      }
    371       if (IsBetter(child.Fitness, Context.BestQuality)) {
     433      if (Context.IsBetter(child.Fitness, Context.BestQuality)) {
    372434        Context.BestQuality = child.Fitness;
    373435        Context.BestSolution = (TSolution)child.Solution.Clone();
    … …  
    379441        if (Context.PopulationCount < popSize) {
    380442          Context.AddToPopulation(child);
    381           return Context.PopulationCount - 1;
     443          return true;// Context.PopulationCount - 1;
    382444        }
    383445       
    … …  
    385447        var candidates = Context.Population.Select((p, i) => new { Index = i, Individual = p })
    386448                                         .Where(x => x.Individual.Fitness == child.Fitness
    387                                            || IsBetter(child, x.Individual)).ToList();
    388         if (candidates.Count == 0) return -1;
     449                                           || Context.IsBetter(child, x.Individual)).ToList();
     450        if (candidates.Count == 0) return false;// -1;
    389451
    390452        var repCand = -1;
    … …  
    435497          // a worse solution with smallest distance is chosen
    436498          var minDist = double.MaxValue;
    437           foreach (var c in candidates.Where(x => IsBetter(child, x.Individual))) {
     499          foreach (var c in candidates.Where(x => Context.IsBetter(child, x.Individual))) {
    438500            var d = Dist(c.Individual, child);
    439501            if (d < minDist) {
    … …  
    447509        // no worse solutions and those on the same plateau are all better
    448510        // stretched out than the new one
    449         if (repCand < 0) return -1;
     511        if (repCand < 0) return false;// -1;
    450512       
    451513        Context.ReplaceAtPopulation(repCand, child);
    452         return repCand;
    453       }
    454       return -1;
    455     }
    456 
    457     [MethodImpl(MethodImplOptions.AggressiveInlining)]
    458     protected bool IsBetter(ISingleObjectiveSolutionScope<TSolution> a, ISingleObjectiveSolutionScope<TSolution> b) {
    459       return IsBetter(a.Fitness, b.Fitness);
    460     }
    461     [MethodImpl(MethodImplOptions.AggressiveInlining)]
    462     protected bool IsBetter(double a, double b) {
    463       return double.IsNaN(b) && !double.IsNaN(a)
    464         || Problem.Maximization && a > b
    465         || !Problem.Maximization && a < b;
     514        return true;// repCand;
     515      }
     516      return false;// -1;
    466517    }
    467518   
    … …  
    497548      var after = scope.Fitness;
    498549      Context.HillclimbingStat.Add(Tuple.Create(before, after));
     550      if (Context.HillclimbingStat.Count % 10 == 0) Context.RelearnHillclimbingPerformanceModel();
    499551      Context.IncrementEvaluatedSolutions(lscontext.EvaluatedSolutions);
    500552      return lscontext.EvaluatedSolutions;
    501553    }
    502554
    503     protected virtual void PerformTabuWalk(ISingleObjectiveSolutionScope<TSolution> scope, int steps, CancellationToken token, ISolutionSubspace<TSolution> subspace = null) {
     555    protected virtual void AdaptiveClimb(ISingleObjectiveSolutionScope<TSolution> scope, int maxEvals, CancellationToken token, ISolutionSubspace<TSolution> subspace = null) {
    504556      if (double.IsNaN(scope.Fitness)) {
    505557        Evaluate(scope, token);
    … …  
    508560      var before = scope.Fitness;
    509561      var newScope = (ISingleObjectiveSolutionScope<TSolution>)scope.Clone();
    510       var newSteps = TabuWalk(newScope, steps, token, subspace);
    511       Context.TabuwalkingStat.Add(Tuple.Create(before, newScope.Fitness));
    512       //Context.HcSteps = (int)Math.Ceiling(Context.HcSteps * (1.0 + Context.TabuwalkingStat.Count) / (2.0 + Context.TabuwalkingStat.Count) + newSteps / (2.0 + Context.TabuwalkingStat.Count));
    513       if (IsBetter(newScope, scope) || (newScope.Fitness == scope.Fitness && Dist(newScope, scope) > 0))
     562      AdaptiveWalk(newScope, maxEvals, token, subspace);
     563      Context.AdaptivewalkingStat.Add(Tuple.Create(before, newScope.Fitness));
     564      if (Context.AdaptivewalkingStat.Count % 10 == 0) Context.RelearnAdaptiveWalkPerformanceModel();
     565      if (Context.IsBetter(newScope, scope))
    514566        scope.Adopt(newScope);
    515567    }
    516     protected abstract int TabuWalk(ISingleObjectiveSolutionScope<TSolution> scope, int maxEvals, CancellationToken token, ISolutionSubspace<TSolution> subspace = null);
    517     protected virtual void TabuClimb(ISingleObjectiveSolutionScope<TSolution> scope, int steps, CancellationToken token, ISolutionSubspace<TSolution> subspace = null) {
    518       if (double.IsNaN(scope.Fitness)) {
    519         Evaluate(scope, token);
    520         Context.IncrementEvaluatedSolutions(1);
    521       }
    522       var before = scope.Fitness;
    523       var newScope = (ISingleObjectiveSolutionScope<TSolution>)scope.Clone();
    524       var newSteps = TabuWalk(newScope, steps, token, subspace);
    525       Context.TabuwalkingStat.Add(Tuple.Create(before, newScope.Fitness));
    526       //Context.HcSteps = (int)Math.Ceiling(Context.HcSteps * (1.0 + Context.TabuwalkingStat.Count) / (2.0 + Context.TabuwalkingStat.Count) + newSteps / (2.0 + Context.TabuwalkingStat.Count));
    527       if (IsBetter(newScope, scope) || (newScope.Fitness == scope.Fitness && Dist(newScope, scope) > 0))
    528         scope.Adopt(newScope);
    529     }
     568    protected abstract void AdaptiveWalk(ISingleObjectiveSolutionScope<TSolution> scope, int maxEvals, CancellationToken token, ISolutionSubspace<TSolution> subspace = null);
     569   
    530570    #endregion
    531    
     571
    532572    #region Breed
    533     protected virtual ISingleObjectiveSolutionScope<TSolution> PerformBreeding(CancellationToken token) {
    534       if (Context.PopulationCount < 2) throw new InvalidOperationException("Cannot breed from population with less than 2 individuals.");
     573    protected virtual ISingleObjectiveSolutionScope<TSolution> Breed(CancellationToken token) {
    535574      var i1 = Context.Random.Next(Context.PopulationCount);
    536575      var i2 = Context.Random.Next(Context.PopulationCount);
    … …  
    549588      }
    550589
    551       return BreedAndImprove(p1, p2, token);
    552     }
    553 
    554     protected virtual ISingleObjectiveSolutionScope<TSolution> BreedAndImprove(ISingleObjectiveSolutionScope<TSolution> p1, ISingleObjectiveSolutionScope<TSolution> p2, CancellationToken token) {
    555       var offspring = Cross(p1, p2, token);
    556       var subspace = CalculateSubspace(new[] { p1.Solution, p2.Solution });
    557       if (Context.Random.NextDouble() < MutationProbabilityMagicConst) {
    558         Mutate(offspring, token, subspace); // mutate the solutions, especially to widen the sub-space
    559       }
    560       if (double.IsNaN(offspring.Fitness)) {
    561         Evaluate(offspring, token);
    562         Context.IncrementEvaluatedSolutions(1);
    563       }
    564       Context.BreedingStat.Add(Tuple.Create(p1.Fitness, p2.Fitness, offspring.Fitness));
    565       if ((IsBetter(offspring, p1) && IsBetter(offspring, p2))
    566         || Context.Population.Any(p => IsBetter(offspring, p))) return offspring;
    567 
    568       if (HillclimbingSuited(offspring))
    569         HillClimb(offspring, token, subspace); // perform hillclimb in the solution sub-space
    570       return offspring;
    571     }
    572 
    573     protected abstract ISingleObjectiveSolutionScope<TSolution> Cross(ISingleObjectiveSolutionScope<TSolution> p1, ISingleObjectiveSolutionScope<TSolution> p2, CancellationToken token);
    574     protected abstract void Mutate(ISingleObjectiveSolutionScope<TSolution> offspring, CancellationToken token, ISolutionSubspace<TSolution> subspace = null);
     590      if (Context.BreedingSuited(p1, p2)) {
     591        var offspring = Breed(p1, p2, token);
     592
     593        if (double.IsNaN(offspring.Fitness)) {
     594          Evaluate(offspring, token);
     595          Context.IncrementEvaluatedSolutions(1);
     596        }
     597
     598        // new best solutions are improved using hill climbing in full solution space
     599        if (Context.Population.All(p => Context.IsBetter(offspring, p)))
     600          HillClimb(offspring, token);
     601        else HillClimb(offspring, token, CalculateSubspace(new[] { p1.Solution, p2.Solution }));
     602
     603        Context.AddBreedingResult(p1, p2, offspring);
     604        if (Context.BreedingStat.Count % 10 == 0) Context.RelearnBreedingPerformanceModel();
     605        return offspring;
     606      }
     607      return null;
     608    }
     609
     610    protected abstract ISingleObjectiveSolutionScope<TSolution> Breed(ISingleObjectiveSolutionScope<TSolution> p1, ISingleObjectiveSolutionScope<TSolution> p2, CancellationToken token);
    575611    #endregion
    576612
    577     #region Relink
    578     protected virtual ISingleObjectiveSolutionScope<TSolution> PerformRelinking(CancellationToken token) {
    579       if (Context.PopulationCount < 2) throw new InvalidOperationException("Cannot breed from population with less than 2 individuals.");
     613    #region Relink/Delink
     614    protected virtual ISingleObjectiveSolutionScope<TSolution> Relink(CancellationToken token) {
    580615      var i1 = Context.Random.Next(Context.PopulationCount);
    581616      var i2 = Context.Random.Next(Context.PopulationCount);
    … …  
    585620      var p2 = Context.AtPopulation(i2);
    586621
    587       return RelinkAndImprove(p1, p2, token);
    588     }
    589 
    590     protected virtual ISingleObjectiveSolutionScope<TSolution> RelinkAndImprove(ISingleObjectiveSolutionScope<TSolution> a, ISingleObjectiveSolutionScope<TSolution> b, CancellationToken token) {
    591       var child = Relink(a, b, token);
    592       if (IsBetter(child, a) && IsBetter(child, b)) return child;
    593 
    594       var dist1 = Dist(child, a);
    595       var dist2 = Dist(child, b);
    596       if (dist1 > 0 && dist2 > 0) {
    597         var subspace = CalculateSubspace(new[] { a.Solution, b.Solution }, inverse: true);
    598         if (HillclimbingSuited(child)) {
    599           HillClimb(child, token, subspace); // perform hillclimb in solution sub-space
    600         }
    601       }
    602       return child;
    603     }
    604 
    605     protected abstract ISingleObjectiveSolutionScope<TSolution> Relink(ISingleObjectiveSolutionScope<TSolution> a, ISingleObjectiveSolutionScope<TSolution> b, CancellationToken token);
     622      return Context.RelinkSuited(p1, p2) ? PerformRelinking(p1, p2, token, delink: false) : null;
     623    }
     624
     625    protected virtual ISingleObjectiveSolutionScope<TSolution> Delink(CancellationToken token) {
     626      var i1 = Context.Random.Next(Context.PopulationCount);
     627      var i2 = Context.Random.Next(Context.PopulationCount);
     628      while (i1 == i2) i2 = Context.Random.Next(Context.PopulationCount);
     629
     630      var p1 = Context.AtPopulation(i1);
     631      var p2 = Context.AtPopulation(i2);
     632
     633      return Context.DelinkSuited(p1, p2) ? PerformRelinking(p1, p2, token, delink: true) : null;
     634    }
     635
     636    protected virtual ISingleObjectiveSolutionScope<TSolution> PerformRelinking(ISingleObjectiveSolutionScope<TSolution> a, ISingleObjectiveSolutionScope<TSolution> b, CancellationToken token, bool delink = false) {
     637      var relink = Link(a, b, token, delink);
     638
     639      if (double.IsNaN(relink.Fitness)) {
     640        Evaluate(relink, token);
     641        Context.IncrementEvaluatedSolutions(1);
     642      }
     643
     644      // new best solutions are improved using hill climbing
     645      if (Context.Population.All(p => Context.IsBetter(relink, p)))
     646        HillClimb(relink, token);
     647
     648      if (delink) {
     649        Context.AddDelinkingResult(a, b, relink);
     650        if (Context.DelinkingStat.Count % 10 == 0) Context.RelearnDelinkingPerformanceModel();
     651      } else {
     652        Context.AddRelinkingResult(a, b, relink);
     653        if (context.RelinkingStat.Count % 10 == 0) Context.RelearnRelinkingPerformanceModel();
     654      }
     655      return relink;
     656    }
     657
     658    protected abstract ISingleObjectiveSolutionScope<TSolution> Link(ISingleObjectiveSolutionScope<TSolution> a, ISingleObjectiveSolutionScope<TSolution> b, CancellationToken token, bool delink = false);
    606659    #endregion
    607660
    608661    #region Sample
    609     protected virtual ISingleObjectiveSolutionScope<TSolution> PerformSampling(CancellationToken token) {
    610       SolutionModelTrainerParameter.Value.TrainModel(Context);
    611       var sample = ToScope(Context.Model.Sample());
    612       Evaluate(sample, token);
    613       Context.IncrementEvaluatedSolutions(1);
    614       if (Context.Population.Any(p => IsBetter(sample, p) || sample.Fitness == p.Fitness)) return sample;
    615 
    616       if (HillclimbingSuited(sample)) {
    617         var subspace = CalculateSubspace(Context.Population.Select(x => x.Solution));
    618         HillClimb(sample, token, subspace);
    619       }
    620       return sample;
     662    protected virtual ISingleObjectiveSolutionScope<TSolution> Sample(CancellationToken token) {
     663      if (Context.PopulationCount == MaximumPopulationSize && Context.SamplingSuited()) {
     664        SolutionModelTrainerParameter.Value.TrainModel(Context);
     665        ISingleObjectiveSolutionScope<TSolution> bestSample = null;
     666        var tries = 1;
     667        for (; tries < Context.LocalSearchEvaluations; tries++) {
     668          var sample = ToScope(Context.Model.Sample());
     669          Evaluate(sample, token);
     670          if (bestSample == null || Context.IsBetter(sample, bestSample)) {
     671            bestSample = sample;
     672          }
     673          if (Context.Population.Any(x => !Context.IsBetter(x, bestSample))) break;
     674        }
     675        Context.IncrementEvaluatedSolutions(tries);
     676        Context.AddSamplingResult(bestSample);
     677        if (Context.SamplingStat.Count % 10 == 0) Context.RelearnSamplingPerformanceModel();
     678        return bestSample;
     679      }
     680      return null;
    621681    }
    622682    #endregion
    623 
    624     protected bool HillclimbingSuited(ISingleObjectiveSolutionScope<TSolution> scope) {
    625       return Context.Random.NextDouble() < ProbabilityAccept(scope, Context.HillclimbingStat);
    626     }
    627     protected bool HillclimbingSuited(double startingFitness) {
    628       return Context.Random.NextDouble() < ProbabilityAccept(startingFitness, Context.HillclimbingStat);
    629     }
    630     protected bool TabuwalkingSuited(ISingleObjectiveSolutionScope<TSolution> scope) {
    631       return Context.Random.NextDouble() < ProbabilityAccept(scope, Context.TabuwalkingStat);
    632     }
    633     protected bool TabuwalkingSuited(double startingFitness) {
    634       return Context.Random.NextDouble() < ProbabilityAccept(startingFitness, Context.TabuwalkingStat);
    635     }
    636 
    637     protected double ProbabilityAccept(ISingleObjectiveSolutionScope<TSolution> scope, IList<Tuple<double, double>> data) {
    638       if (double.IsNaN(scope.Fitness)) {
    639         Evaluate(scope, CancellationToken.None);
    640         Context.IncrementEvaluatedSolutions(1);
    641       }
    642       return ProbabilityAccept(scope.Fitness, data);
    643     }
    644     protected double ProbabilityAccept(double startingFitness, IList<Tuple<double, double>> data) {
    645       if (data.Count < 10) return 1.0;
    646       int[] clusterValues;
    647       var centroids = CkMeans1D.Cluster(data.Select(x => x.Item1).ToArray(), 2, out clusterValues);
    648       var cluster = Math.Abs(startingFitness - centroids.First().Key) < Math.Abs(startingFitness - centroids.Last().Key) ? centroids.First().Value : centroids.Last().Value;
    649 
    650       var samples = 0;
    651       double meanStart = 0, meanStartOld = 0, meanEnd = 0, meanEndOld = 0;
    652       double varStart = 0, varStartOld = 0, varEnd = 0, varEndOld = 0;
    653       for (var i = 0; i < data.Count; i++) {
    654         if (clusterValues[i] != cluster) continue;
    655 
    656         samples++;
    657         var x = data[i].Item1;
    658         var y = data[i].Item2;
    659 
    660         if (samples == 1) {
    661           meanStartOld = x;
    662           meanEndOld = y;
    663         } else {
    664           meanStart = meanStartOld + (x - meanStartOld) / samples;
    665           meanEnd = meanEndOld + (x - meanEndOld) / samples;
    666           varStart = varStartOld + (x - meanStartOld) * (x - meanStart) / (samples - 1);
    667           varEnd = varEndOld + (x - meanEndOld) * (x - meanEnd) / (samples - 1);
    668 
    669           meanStartOld = meanStart;
    670           meanEndOld = meanEnd;
    671           varStartOld = varStart;
    672           varEndOld = varEnd;
    673         }
    674       }
    675       if (samples < 5) return 1.0;
    676       var cov = data.Select((v, i) => new { Index = i, Value = v }).Where(x => clusterValues[x.Index] == cluster).Select(x => x.Value).Sum(x => (x.Item1 - meanStart) * (x.Item2 - meanEnd)) / data.Count;
    677 
    678       var biasedMean = meanEnd + cov / varStart * (startingFitness - meanStart);
    679       var biasedStdev = Math.Sqrt(varEnd - (cov * cov) / varStart);
    680 
    681       if (Problem.Maximization) {
    682         var goal = Context.Population.Min(x => x.Fitness);
    683         var z = (goal - biasedMean) / biasedStdev;
    684         return 1.0 - Phi(z); // P(X >= z)
    685       } else {
    686         var goal = Context.Population.Max(x => x.Fitness);
    687         var z = (goal - biasedMean) / biasedStdev;
    688         return Phi(z); // P(X <= z)
    689       }
    690     }
    691683
    692684    protected virtual bool Terminate() {
    … …  
    730722    }
    731723    #endregion
    732 
    733     #region Math Helper
    734     // normal distribution CDF (left of x) for N(0;1) standard normal distribution
    735     // from http://www.johndcook.com/blog/csharp_phi/
    736     // license: "This code is in the public domain. Do whatever you want with it, no strings attached."
    737     // added: 2016-11-19 21:46 CET
    738     protected static double Phi(double x) {
    739       // constants
    740       double a1 = 0.254829592;
    741       double a2 = -0.284496736;
    742       double a3 = 1.421413741;
    743       double a4 = -1.453152027;
    744       double a5 = 1.061405429;
    745       double p = 0.3275911;
    746 
    747       // Save the sign of x
    748       int sign = 1;
    749       if (x < 0)
    750         sign = -1;
    751       x = Math.Abs(x) / Math.Sqrt(2.0);
    752 
    753       // A&S formula 7.1.26
    754       double t = 1.0 / (1.0 + p * x);
    755       double y = 1.0 - (((((a5 * t + a4) * t) + a3) * t + a2) * t + a1) * t * Math.Exp(-x * x);
    756 
    757       return 0.5 * (1.0 + sign * y);
    758     }
    759     #endregion
    760724  }
    761725}
Note: See TracChangeset for help on using the changeset viewer.