Free cookie consent management tool by TermsFeed Policy Generator

Changeset 14544


Ignore:
Timestamp:
01/05/17 00:32:43 (6 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
Location:
branches/MemPRAlgorithm
Files:
20 edited
1 copied

Legend:

Unmodified
Added
Removed

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

    r14496 r14544  
    3838  [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms, Priority = 999)]
    3939  public class BinaryMemPR : MemPRAlgorithm<SingleObjectiveBasicProblem<BinaryVectorEncoding>, BinaryVector, BinaryMemPRPopulationContext, BinaryMemPRSolutionContext> {
    40     private const double UncommonBitSubsetMutationProbabilityMagicConst = 0.05;
    41    
    4240    [StorableConstructor]
    4341    protected BinaryMemPR(bool deserializing) : base(deserializing) { }
    … …  
    9189    }
    9290
    93     protected override int TabuWalk(ISingleObjectiveSolutionScope<BinaryVector> scope, int maxEvals, CancellationToken token, ISolutionSubspace<BinaryVector> subspace = null) {
     91    protected override void AdaptiveWalk(ISingleObjectiveSolutionScope<BinaryVector> scope, int maxEvals, CancellationToken token, ISolutionSubspace<BinaryVector> subspace = null) {
    9492      var evaluations = 0;
    9593      var subset = subspace != null ? ((BinarySolutionSubspace)subspace).Subspace : null;
    … …  
    102100      var current = currentScope.Solution;
    103101      var N = current.Length;
    104       var tabu = new Tuple<double, double>[N];
    105       for (var i = 0; i < N; i++) tabu[i] = Tuple.Create(current[i] ? double.NaN : currentScope.Fitness, !current[i] ? double.NaN : currentScope.Fitness);
     102
    106103      var subN = subset != null ? subset.Count(x => x) : N;
    107       if (subN == 0) return 0;
     104      if (subN == 0) return;
    108105      var order = Enumerable.Range(0, N).Where(x => subset == null || subset[x]).Shuffle(Context.Random).ToArray();
    109106
    110       var steps = 0;
    111       var stepsUntilBestOfWalk = 0;
     107      var max = Context.Population.Max(x => x.Fitness);
     108      var min = Context.Population.Min(x => x.Fitness);
     109      var range = (max - min);
     110      if (range.IsAlmost(0)) range = Math.Abs(max * 0.05);
     111      //else range += range * 0.05;
     112      if (range.IsAlmost(0)) { // because min = max = 0
     113        Context.IncrementEvaluatedSolutions(evaluations);
     114        return;
     115      }
     116
     117      //var upperBound = Problem.Maximization ? min - range : max + range;
     118      //var lowerBound = Problem.Maximization ? max : min;
     119      var temp = 1.0;
    112120      for (var iter = 0; iter < int.MaxValue; iter++) {
    113         var allTabu = true;
    114         var bestOfTheRestF = double.NaN;
    115         int bestOfTheRest = -1;
    116         var improved = false;
     121        var moved = false;
    117122
    118123        for (var i = 0; i < subN; i++) {
    … …  
    124129          var after = currentScope.Fitness;
    125130
    126           if (IsBetter(after, before) && (bestOfTheWalk == null || IsBetter(after, bestOfTheWalk.Fitness))) {
     131          if (Context.IsBetter(after, before) && (bestOfTheWalk == null || Context.IsBetter(after, bestOfTheWalk.Fitness))) {
    127132            bestOfTheWalk = (SingleObjectiveSolutionScope<BinaryVector>)currentScope.Clone();
    128             stepsUntilBestOfWalk = steps;
    129           }
    130 
    131           var qualityToBeat = current[idx] ? tabu[idx].Item2 : tabu[idx].Item1;
    132           var isTabu = !IsBetter(after, qualityToBeat);
    133           if (!isTabu) allTabu = false;
    134 
    135           if (IsBetter(after, before) && !isTabu) {
    136             improved = true;
    137             steps++;
    138             tabu[idx] = current[idx] ? Tuple.Create(after, tabu[idx].Item2) : Tuple.Create(tabu[idx].Item1, after);
    139           } else { // undo the move
    140             if (!isTabu && IsBetter(after, bestOfTheRestF)) {
    141               bestOfTheRest = idx;
    142               bestOfTheRestF = after;
     133          }
     134          var diff = Problem.Maximization ? after - before : before - after;
     135          if (diff > 0) moved = true;
     136          else {
     137            var prob = Math.Exp(temp * diff / range);
     138            if (Context.Random.NextDouble() >= prob) {
     139              // the move is not good enough -> undo the move
     140              current[idx] = !current[idx];
     141              currentScope.Fitness = before;
    143142            }
    144             current[idx] = !current[idx];
    145             currentScope.Fitness = before;
    146           }
     143          }
     144          temp += 100.0 / maxEvals;
    147145          if (evaluations >= maxEvals) break;
    148146        }
    149         if (!allTabu && !improved) {
    150           var better = currentScope.Fitness;
    151           current[bestOfTheRest] = !current[bestOfTheRest];
    152           tabu[bestOfTheRest] = current[bestOfTheRest] ? Tuple.Create(better, tabu[bestOfTheRest].Item2) : Tuple.Create(tabu[bestOfTheRest].Item1, better);
    153           currentScope.Fitness = bestOfTheRestF;
    154           steps++;
    155         } else if (allTabu) break;
     147        if (!moved) break;
    156148        if (evaluations >= maxEvals) break;
    157149      }
    … …  
    159151      Context.IncrementEvaluatedSolutions(evaluations);
    160152      scope.Adopt(bestOfTheWalk ?? currentScope);
    161       return stepsUntilBestOfWalk;
    162     }
    163 
    164     protected override ISingleObjectiveSolutionScope<BinaryVector> Cross(ISingleObjectiveSolutionScope<BinaryVector> p1, ISingleObjectiveSolutionScope<BinaryVector> p2, CancellationToken token) {
    165       var offspring = (ISingleObjectiveSolutionScope<BinaryVector>)p1.Clone();
    166       offspring.Fitness = double.NaN;
    167       var code = offspring.Solution;
    168       var p2Code = p2.Solution;
    169       var bp = 0;
    170       var lastbp = 0;
    171       for (var i = 0; i < code.Length; i++) {
    172         if (bp % 2 == 1) {
    173           code[i] = p2Code[i];
    174         }
    175         if (Context.Random.Next(code.Length) < i - lastbp + 1) {
    176           bp = (bp + 1) % 2;
    177           lastbp = i;
    178         }
    179       }
     153    }
     154
     155    protected override ISingleObjectiveSolutionScope<BinaryVector> Breed(ISingleObjectiveSolutionScope<BinaryVector> p1, ISingleObjectiveSolutionScope<BinaryVector> p2, CancellationToken token) {
     156      var evaluations = 0;
     157      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
     169      var offspring = ToScope(null);
     170      var probe = ToScope(new BinaryVector(N));
     171      var order = Enumerable.Range(0, N - 1).Shuffle(Context.Random).ToList();
     172      for (var x = 0; x < N - 1; x++) {
     173        var b = order[x];
     174        if (p1.Solution[b] == p2.Solution[b]) continue;
     175        for (var i = 0; i <= b; i++)
     176          probe.Solution[i] = p1.Solution[i];
     177        for (var i = b + 1; i < probe.Solution.Length; i++)
     178          probe.Solution[i] = p2.Solution[i];
     179
     180        Evaluate(probe, token);
     181        evaluations++;
     182        if (Context.IsBetter(probe, offspring)) {
     183          if (Context.IsBetter(probe.Fitness, better)) {
     184            Context.IncrementEvaluatedSolutions(evaluations);
     185            return probe;
     186          }
     187          offspring = (ISingleObjectiveSolutionScope<BinaryVector>)probe.Clone();
     188        }
     189      }
     190
     191      while (evaluations < Context.LocalSearchEvaluations) {
     192        probe.Solution = UniformCrossover.Apply(Context.Random, p1.Solution, p2.Solution);
     193        Evaluate(probe, token);
     194        evaluations++;
     195        if (Context.IsBetter(probe, offspring)) {
     196          if (Context.IsBetter(probe.Fitness, better)) {
     197            Context.IncrementEvaluatedSolutions(evaluations);
     198            return probe;
     199          }
     200          offspring = (ISingleObjectiveSolutionScope<BinaryVector>)probe.Clone();
     201        }
     202      }
     203      Context.IncrementEvaluatedSolutions(evaluations);
    180204      return offspring;
    181205    }
    182206
    183     protected override void Mutate(ISingleObjectiveSolutionScope<BinaryVector> offspring, CancellationToken token, ISolutionSubspace<BinaryVector> subspace = null) {
    184       var subset = subspace != null ? ((BinarySolutionSubspace)subspace).Subspace : null;
    185       offspring.Fitness = double.NaN;
    186       var code = offspring.Solution;
    187       for (var i = 0; i < code.Length; i++) {
    188         if (subset != null && subset[i]) continue;
    189         if (Context.Random.NextDouble() < UncommonBitSubsetMutationProbabilityMagicConst) {
    190           code[i] = !code[i];
    191           if (subset != null) subset[i] = true;
    192         }
    193       }
    194     }
    195 
    196     protected override ISingleObjectiveSolutionScope<BinaryVector> Relink(ISingleObjectiveSolutionScope<BinaryVector> a, ISingleObjectiveSolutionScope<BinaryVector> b, CancellationToken token) {
     207    protected override ISingleObjectiveSolutionScope<BinaryVector> Link(ISingleObjectiveSolutionScope<BinaryVector> a, ISingleObjectiveSolutionScope<BinaryVector> b, CancellationToken token, bool delink = false) {
     208      var evaluations = 0;
    197209      if (double.IsNaN(a.Fitness)) {
    198210        Evaluate(a, token);
    199         Context.IncrementEvaluatedSolutions(1);
     211        evaluations++;
    200212      }
    201213      if (double.IsNaN(b.Fitness)) {
    202214        Evaluate(b, token);
    203         Context.IncrementEvaluatedSolutions(1);
    204       }
    205       if (Context.Random.NextDouble() < 0.5)
    206         return IsBetter(a, b) ? Relink(a, b, token, false) : Relink(b, a, token, true);
    207       else return IsBetter(a, b) ? Relink(b, a, token, true) : Relink(a, b, token, false);
    208     }
    209 
    210     protected virtual ISingleObjectiveSolutionScope<BinaryVector> Relink(ISingleObjectiveSolutionScope<BinaryVector> betterScope, ISingleObjectiveSolutionScope<BinaryVector> worseScope, CancellationToken token, bool fromWorseToBetter) {
    211       var evaluations = 0;
    212       var childScope = (ISingleObjectiveSolutionScope<BinaryVector>)(fromWorseToBetter ? worseScope : betterScope).Clone();
     215        evaluations++;
     216      }
     217
     218      var childScope = (ISingleObjectiveSolutionScope<BinaryVector>)a.Clone();
    213219      var child = childScope.Solution;
    214       var better = betterScope.Solution;
    215       var worse = worseScope.Solution;
    216220      ISingleObjectiveSolutionScope<BinaryVector> best = null;
    217       var cF = fromWorseToBetter ? worseScope.Fitness : betterScope.Fitness;
     221      var cF = a.Fitness;
    218222      var bF = double.NaN;
    219       var order = Enumerable.Range(0, better.Length).Shuffle(Context.Random).ToArray();
     223      var order = Enumerable.Range(0, child.Length)
     224        .Where(x => !delink && child[x] != b.Solution[x] || delink && child[x] == b.Solution[x])
     225        .Shuffle(Context.Random).ToList();
     226      if (order.Count == 0) return childScope;
     227
    220228      while (true) {
    221229        var bestS = double.NaN;
    222         var bestIdx = -1;
    223         for (var i = 0; i < child.Length; i++) {
     230        var bestI = -1;
     231        for (var i = 0; i < order.Count; i++) {
    224232          var idx = order[i];
    225           // either move from worse to better or move from better away from worse
    226           if (fromWorseToBetter && child[idx] == better[idx] ||
    227             !fromWorseToBetter && child[idx] != worse[idx]) continue;
    228233          child[idx] = !child[idx]; // move
    229234          Evaluate(childScope, token);
    … …  
    232237          childScope.Fitness = cF;
    233238          child[idx] = !child[idx]; // undo move
    234           if (IsBetter(s, cF)) {
     239          if (Context.IsBetter(s, cF)) {
    235240            bestS = s;
    236             bestIdx = idx;
     241            bestI = i;
    237242            break; // first-improvement
    238243          }
    239           if (double.IsNaN(bestS) || IsBetter(s, bestS)) {
     244          if (Context.IsBetter(s, bestS)) {
    240245            // least-degrading
    241246            bestS = s;
    242             bestIdx = idx;
    243           }
    244         }
    245         if (bestIdx < 0) break;
    246         child[bestIdx] = !child[bestIdx];
     247            bestI = i;
     248          }
     249        }
     250        child[order[bestI]] = !child[order[bestI]];
     251        order.RemoveAt(bestI);
    247252        cF = bestS;
    248253        childScope.Fitness = cF;
    249         if (IsBetter(cF, bF)) {
     254        if (Context.IsBetter(cF, bF)) {
    250255          bF = cF;
    251256          best = (ISingleObjectiveSolutionScope<BinaryVector>)childScope.Clone();
    252257        }
     258        if (order.Count == 0) break;
    253259      }
    254260      Context.IncrementEvaluatedSolutions(evaluations);

  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/HeuristicLab.Algorithms.MemPR-3.3.csproj

    r14496 r14544  
    7474  </PropertyGroup>
    7575  <ItemGroup>
     76    <Reference Include="ALGLIB-3.7.0, Version=3.7.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     77      <SpecificVersion>False</SpecificVersion>
     78      <HintPath>..\..\bin\ALGLIB-3.7.0.dll</HintPath>
     79      <Private>False</Private>
     80    </Reference>
    7681    <Reference Include="System" />
    7782    <Reference Include="System.Core" />
    … …  
    128133  </ItemGroup>
    129134  <ItemGroup>
     135    <ProjectReference Include="..\..\HeuristicLab.Algorithms.DataAnalysis\3.4\HeuristicLab.Algorithms.DataAnalysis-3.4.csproj">
     136      <Project>{2e782078-fa81-4b70-b56f-74ce38dac6c8}</Project>
     137      <Name>HeuristicLab.Algorithms.DataAnalysis-3.4</Name>
     138      <Private>False</Private>
     139    </ProjectReference>
    130140    <ProjectReference Include="..\..\HeuristicLab.Analysis\3.3\HeuristicLab.Analysis-3.3.csproj">
    131141      <Project>{887425b4-4348-49ed-a457-b7d2c26ddbf9}</Project>
    … …  
    202212      <Name>HeuristicLab.PluginInfrastructure-3.3</Name>
    203213      <Private>False</Private>
     214    </ProjectReference>
     215    <ProjectReference Include="..\..\HeuristicLab.Problems.DataAnalysis\3.4\HeuristicLab.Problems.DataAnalysis-3.4.csproj">
     216      <Project>{df87c13e-a889-46ff-8153-66dcaa8c5674}</Project>
     217      <Name>HeuristicLab.Problems.DataAnalysis-3.4</Name>
    204218    </ProjectReference>
    205219    <ProjectReference Include="..\..\HeuristicLab.Random\3.3\HeuristicLab.Random-3.3.csproj">

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

    r14466 r14544  
    2222using System.Collections.Generic;
    2323using HeuristicLab.Algorithms.MemPR.Binary;
    24 using HeuristicLab.Algorithms.MemPR.LinearLinkage;
     24using HeuristicLab.Algorithms.MemPR.Grouping;
    2525using HeuristicLab.Algorithms.MemPR.Permutation;
    2626using HeuristicLab.Core;

  • 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  }

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

    r14466 r14544  
    2828using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2929
    30 namespace HeuristicLab.Algorithms.MemPR.LinearLinkage {
     30namespace HeuristicLab.Algorithms.MemPR.Grouping {
    3131  [Item("MemPR Population Context (linear linkage)", "MemPR population context for linear linkage encoded problems.")]
    3232  [StorableClass]
    33   public sealed class LinearLinkageMemPRPopulationContext : MemPRPopulationContext<SingleObjectiveBasicProblem<LinearLinkageEncoding>, Encodings.LinearLinkageEncoding.LinearLinkage, LinearLinkageMemPRPopulationContext, LinearLinkageMemPRSolutionContext> {
     33  public sealed class LinearLinkageMemPRPopulationContext : MemPRPopulationContext<SingleObjectiveBasicProblem<LinearLinkageEncoding>, LinearLinkage, LinearLinkageMemPRPopulationContext, LinearLinkageMemPRSolutionContext> {
    3434
    3535    [StorableConstructor]
    … …  
    4444    }
    4545
    46     public override LinearLinkageMemPRSolutionContext CreateSingleSolutionContext(ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> solution) {
     46    public override LinearLinkageMemPRSolutionContext CreateSingleSolutionContext(ISingleObjectiveSolutionScope<LinearLinkage> solution) {
    4747      return new LinearLinkageMemPRSolutionContext(this, solution);
    4848    }
    … …  
    5151  [Item("MemPR Solution Context (linear linkage)", "MemPR solution context for linear linkage encoded problems.")]
    5252  [StorableClass]
    53   public sealed class LinearLinkageMemPRSolutionContext : MemPRSolutionContext<SingleObjectiveBasicProblem<LinearLinkageEncoding>, Encodings.LinearLinkageEncoding.LinearLinkage, LinearLinkageMemPRPopulationContext, LinearLinkageMemPRSolutionContext>, ILinearLinkageSubspaceContext {
     53  public sealed class LinearLinkageMemPRSolutionContext : MemPRSolutionContext<SingleObjectiveBasicProblem<LinearLinkageEncoding>, LinearLinkage, LinearLinkageMemPRPopulationContext, LinearLinkageMemPRSolutionContext>, ILinearLinkageSubspaceContext {
    5454
    5555    [Storable]
    … …  
    5858      get { return subspace.Value; }
    5959    }
    60     ISolutionSubspace<Encodings.LinearLinkageEncoding.LinearLinkage> ISolutionSubspaceContext<Encodings.LinearLinkageEncoding.LinearLinkage>.Subspace {
     60    ISolutionSubspace<LinearLinkage> ISolutionSubspaceContext<LinearLinkage>.Subspace {
    6161      get { return Subspace; }
    6262    }
    … …  
    6868
    6969    }
    70     public LinearLinkageMemPRSolutionContext(LinearLinkageMemPRPopulationContext baseContext, ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> solution)
     70    public LinearLinkageMemPRSolutionContext(LinearLinkageMemPRPopulationContext baseContext, ISingleObjectiveSolutionScope<LinearLinkage> solution)
    7171      : base(baseContext, solution) {
    7272

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

    r14466 r14544  
    2323using HeuristicLab.Common;
    2424using HeuristicLab.Core;
     25using HeuristicLab.Encodings.LinearLinkageEncoding;
    2526using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2627
    27 namespace HeuristicLab.Algorithms.MemPR.LinearLinkage {
     28namespace HeuristicLab.Algorithms.MemPR.Grouping {
    2829  [Item("Solution subspace (linear linkage)", "")]
    2930  [StorableClass]
    30   public sealed class LinearLinkageSolutionSubspace : Item, ISolutionSubspace<Encodings.LinearLinkageEncoding.LinearLinkage> {
     31  public sealed class LinearLinkageSolutionSubspace : Item, ISolutionSubspace<LinearLinkage> {
    3132
    3233    [Storable]

  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/LinearLinkage/LocalSearch/ExhaustiveSubspace.cs

    r14466 r14544  
    2929using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    3030
    31 namespace HeuristicLab.Algorithms.MemPR.LinearLinkage.LocalSearch {
     31namespace HeuristicLab.Algorithms.MemPR.Grouping.LocalSearch {
    3232  [Item("Exhaustive Local (Subspace) Search (linear linkage)", "", ExcludeGenericTypeInfo = true)]
    3333  [StorableClass]
    3434  public class ExhaustiveSubspace<TContext> : NamedItem, ILocalSearch<TContext>
    35       where TContext : ISingleSolutionHeuristicAlgorithmContext<SingleObjectiveBasicProblem<LinearLinkageEncoding>, Encodings.LinearLinkageEncoding.LinearLinkage>, ILinearLinkageSubspaceContext {
     35      where TContext : ISingleSolutionHeuristicAlgorithmContext<SingleObjectiveBasicProblem<LinearLinkageEncoding>, LinearLinkage>, ILinearLinkageSubspaceContext {
    3636
    3737    [StorableConstructor]
    … …  
    4848
    4949    public void Optimize(TContext context) {
    50       var evalWrapper = new EvaluationWrapper<Encodings.LinearLinkageEncoding.LinearLinkage>(context.Problem, context.Solution);
     50      var evalWrapper = new EvaluationWrapper<LinearLinkage>(context.Problem, context.Solution);
    5151      var quality = context.Solution.Fitness;
    5252      try {

  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/LinearLinkage/LocalSearch/StaticAPI/ExhaustiveLocalSearch.cs

    r14477 r14544  
    2626using HeuristicLab.Collections;
    2727using HeuristicLab.Core;
    28 
    29 namespace HeuristicLab.Algorithms.MemPR.LinearLinkage.LocalSearch {
     28using HeuristicLab.Encodings.LinearLinkageEncoding;
     29
     30namespace HeuristicLab.Algorithms.MemPR.Grouping.LocalSearch {
    3031  public static class ExhaustiveLocalSearch {
    31     public static Tuple<int, int> Optimize(IRandom random, Encodings.LinearLinkageEncoding.LinearLinkage solution, ref double quality, bool maximization, Func<Encodings.LinearLinkageEncoding.LinearLinkage, IRandom, double> eval, CancellationToken token, bool[] subspace = null) {
     32    public static Tuple<int, int> Optimize(IRandom random, LinearLinkage solution, ref double quality, bool maximization, Func<LinearLinkage, IRandom, double> eval, CancellationToken token, bool[] subspace = null) {
    3233      var evaluations = 0;
    3334      var current = solution;
    … …  
    153154    }
    154155
    155     public static Tuple<int, int> OptimizeSwapOnly(IRandom random, Encodings.LinearLinkageEncoding.LinearLinkage solution, ref double quality, bool maximization, Func<Encodings.LinearLinkageEncoding.LinearLinkage, IRandom, double> eval, CancellationToken token) {
     156    public static Tuple<int, int> OptimizeSwapOnly(IRandom random, LinearLinkage solution, ref double quality, bool maximization, Func<LinearLinkage, IRandom, double> eval, CancellationToken token) {
    156157      var evaluations = 0;
    157158      var current = solution;

  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/LinearLinkage/SolutionModel/Univariate/StaticAPI/Trainer.cs

    r14466 r14544  
    2323using HeuristicLab.Algorithms.MemPR.Interfaces;
    2424using HeuristicLab.Core;
     25using HeuristicLab.Encodings.LinearLinkageEncoding;
    2526
    26 namespace HeuristicLab.Algorithms.MemPR.LinearLinkage.SolutionModel.Univariate {
     27namespace HeuristicLab.Algorithms.MemPR.Grouping.SolutionModel.Univariate {
    2728  public static class Trainer {
    2829
    29     public static ISolutionModel<Encodings.LinearLinkageEncoding.LinearLinkage> Train(IRandom random,
    30         IEnumerable<Encodings.LinearLinkageEncoding.LinearLinkage> pop) {
     30    public static ISolutionModel<LinearLinkage> Train(IRandom random,
     31        IEnumerable<LinearLinkage> pop) {
    3132      return UnivariateModel.Create(random, pop);
    3233    }

  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/LinearLinkage/SolutionModel/Univariate/UnbiasedModelTrainer.cs

    r14466 r14544  
    2424using HeuristicLab.Common;
    2525using HeuristicLab.Core;
     26using HeuristicLab.Encodings.LinearLinkageEncoding;
    2627using HeuristicLab.Optimization;
    2728using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2829
    29 namespace HeuristicLab.Algorithms.MemPR.LinearLinkage.SolutionModel.Univariate {
     30namespace HeuristicLab.Algorithms.MemPR.Grouping.SolutionModel.Univariate {
    3031  [Item("Unbiased Univariate Model Trainer (linear linkage)", "", ExcludeGenericTypeInfo = true)]
    3132  [StorableClass]
    3233  public class UniasedModelTrainer<TContext> : NamedItem, ISolutionModelTrainer<TContext>
    33     where TContext : IPopulationBasedHeuristicAlgorithmContext<SingleObjectiveBasicProblem<Encodings.LinearLinkageEncoding.LinearLinkageEncoding>, Encodings.LinearLinkageEncoding.LinearLinkage>, ISolutionModelContext<Encodings.LinearLinkageEncoding.LinearLinkage> {
     34    where TContext : IPopulationBasedHeuristicAlgorithmContext<SingleObjectiveBasicProblem<LinearLinkageEncoding>, LinearLinkage>, ISolutionModelContext<LinearLinkage> {
    3435   
    3536    [StorableConstructor]

  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/LinearLinkage/SolutionModel/Univariate/UnivariateSolutionModel.cs

    r14487 r14544  
    2626using HeuristicLab.Core;
    2727using HeuristicLab.Data;
     28using HeuristicLab.Encodings.LinearLinkageEncoding;
    2829using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2930
    30 namespace HeuristicLab.Algorithms.MemPR.LinearLinkage.SolutionModel.Univariate {
     31namespace HeuristicLab.Algorithms.MemPR.Grouping.SolutionModel.Univariate {
    3132  [Item("Univariate solution model (linear linkage)", "")]
    3233  [StorableClass]
    33   public sealed class UnivariateModel : Item, ISolutionModel<Encodings.LinearLinkageEncoding.LinearLinkage> {
     34  public sealed class UnivariateModel : Item, ISolutionModel<LinearLinkage> {
    3435    [Storable]
    3536    public IntMatrix Frequencies { get; set; }
    … …  
    6162    }
    6263
    63     public Encodings.LinearLinkageEncoding.LinearLinkage Sample() {
     64    public LinearLinkage Sample() {
    6465      var N = Frequencies.Rows;
    65       var centroid = Encodings.LinearLinkageEncoding.LinearLinkage.SingleElementGroups(N);
     66      var centroid = LinearLinkage.SingleElementGroups(N);
    6667      var dict = new Dictionary<int, int>();
    6768      for (var i = N - 1; i >= 0; i--) {
    … …  
    8788    }
    8889
    89     public static ISolutionModel<Encodings.LinearLinkageEncoding.LinearLinkage> Create(IRandom random, IEnumerable<Encodings.LinearLinkageEncoding.LinearLinkage> population) {
     90    public static ISolutionModel<LinearLinkage> Create(IRandom random, IEnumerable<LinearLinkage> population) {
    9091      var iter = population.GetEnumerator();
    9192      if (!iter.MoveNext()) throw new ArgumentException("Cannot create solution model from empty population.");

  • 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}

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

    r14496 r14544  
    2323using System.Collections.Generic;
    2424using System.Linq;
     25using System.Runtime.CompilerServices;
     26using System.Threading;
     27using HeuristicLab.Algorithms.DataAnalysis;
    2528using HeuristicLab.Algorithms.MemPR.Interfaces;
    2629using HeuristicLab.Common;
    … …  
    3033using HeuristicLab.Parameters;
    3134using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     35using HeuristicLab.Problems.DataAnalysis;
    3236using HeuristicLab.Random;
     37using ExecutionContext = HeuristicLab.Core.ExecutionContext;
    3338
    3439namespace HeuristicLab.Algorithms.MemPR {
    … …  
    123128
    124129    [Storable]
     130    private IValueParameter<IntValue> byDelinking;
     131    public int ByDelinking {
     132      get { return byDelinking.Value.Value; }
     133      set { byDelinking.Value.Value = value; }
     134    }
     135
     136    [Storable]
    125137    private IValueParameter<IntValue> bySampling;
    126138    public int BySampling {
    … …  
    137149
    138150    [Storable]
    139     private IValueParameter<IntValue> byTabuwalking;
    140     public int ByTabuwalking {
    141       get { return byTabuwalking.Value.Value; }
    142       set { byTabuwalking.Value.Value = value; }
     151    private IValueParameter<IntValue> byAdaptivewalking;
     152    public int ByAdaptivewalking {
     153      get { return byAdaptivewalking.Value.Value; }
     154      set { byAdaptivewalking.Value.Value = value; }
    143155    }
    144156
    … …  
    162174      return scope.SubScopes[index] as ISingleObjectiveSolutionScope<TSolution>;
    163175    }
     176    public void SortPopulation() {
     177      scope.SubScopes.Replace(scope.SubScopes.OfType<ISingleObjectiveSolutionScope<TSolution>>().OrderBy(x => Problem.Maximization ? -x.Fitness : x.Fitness).ToList());
     178    }
    164179    public int PopulationCount {
    165180      get { return scope.SubScopes.Count; }
    166181    }
    167182
     183    [Storable]
     184    private IConfidenceRegressionModel breedingPerformanceModel;
     185    public IConfidenceRegressionModel BreedingPerformanceModel {
     186      get { return breedingPerformanceModel; }
     187    }
    168188    [Storable]
    169189    private List<Tuple<double, double, double>> breedingStat;
    … …  
    172192    }
    173193    [Storable]
     194    private IConfidenceRegressionModel relinkingPerformanceModel;
     195    public IConfidenceRegressionModel RelinkingPerformanceModel {
     196      get { return relinkingPerformanceModel; }
     197    }
     198    [Storable]
     199    private List<Tuple<double, double, double>> relinkingStat;
     200    public List<Tuple<double, double, double>> RelinkingStat {
     201      get { return relinkingStat; }
     202    }
     203    [Storable]
     204    private IConfidenceRegressionModel delinkingPerformanceModel;
     205    public IConfidenceRegressionModel DelinkingPerformanceModel {
     206      get { return delinkingPerformanceModel; }
     207    }
     208    [Storable]
     209    private List<Tuple<double, double, double>> delinkingStat;
     210    public List<Tuple<double, double, double>> DelinkingStat {
     211      get { return delinkingStat; }
     212    }
     213    [Storable]
     214    private IConfidenceRegressionModel samplingPerformanceModel;
     215    public IConfidenceRegressionModel SamplingPerformanceModel {
     216      get { return samplingPerformanceModel; }
     217    }
     218    [Storable]
     219    private List<Tuple<double, double>> samplingStat;
     220    public List<Tuple<double, double>> SamplingStat {
     221      get { return samplingStat; }
     222    }
     223    [Storable]
     224    private IConfidenceRegressionModel hillclimbingPerformanceModel;
     225    public IConfidenceRegressionModel HillclimbingPerformanceModel {
     226      get { return hillclimbingPerformanceModel; }
     227    }
     228    [Storable]
    174229    private List<Tuple<double, double>> hillclimbingStat;
    175230    public List<Tuple<double, double>> HillclimbingStat {
    … …  
    177232    }
    178233    [Storable]
    179     private List<Tuple<double, double>> tabuwalkingStat;
    180     public List<Tuple<double, double>> TabuwalkingStat {
    181       get { return tabuwalkingStat; }
     234    private IConfidenceRegressionModel adaptiveWalkPerformanceModel;
     235    public IConfidenceRegressionModel AdaptiveWalkPerformanceModel {
     236      get { return adaptiveWalkPerformanceModel; }
     237    }
     238    [Storable]
     239    private List<Tuple<double, double>> adaptivewalkingStat;
     240    public List<Tuple<double, double>> AdaptivewalkingStat {
     241      get { return adaptivewalkingStat; }
    182242    }
    183243
    … …  
    199259      byBreeding = cloner.Clone(original.byBreeding);
    200260      byRelinking = cloner.Clone(original.byRelinking);
     261      byDelinking = cloner.Clone(original.byDelinking);
    201262      bySampling = cloner.Clone(original.bySampling);
    202263      byHillclimbing = cloner.Clone(original.byHillclimbing);
    203       byTabuwalking = cloner.Clone(original.byTabuwalking);
     264      byAdaptivewalking = cloner.Clone(original.byAdaptivewalking);
    204265      random = cloner.Clone(original.random);
     266      breedingPerformanceModel = cloner.Clone(original.breedingPerformanceModel);
    205267      breedingStat = original.breedingStat.Select(x => Tuple.Create(x.Item1, x.Item2, x.Item3)).ToList();
     268      relinkingPerformanceModel = cloner.Clone(original.relinkingPerformanceModel);
     269      relinkingStat = original.relinkingStat.Select(x => Tuple.Create(x.Item1, x.Item2, x.Item3)).ToList();
     270      delinkingPerformanceModel = cloner.Clone(original.delinkingPerformanceModel);
     271      delinkingStat = original.delinkingStat.Select(x => Tuple.Create(x.Item1, x.Item2, x.Item3)).ToList();
     272      samplingPerformanceModel = cloner.Clone(original.samplingPerformanceModel);
     273      samplingStat = original.samplingStat.Select(x => Tuple.Create(x.Item1, x.Item2)).ToList();
     274      hillclimbingPerformanceModel = cloner.Clone(original.hillclimbingPerformanceModel);
    206275      hillclimbingStat = original.hillclimbingStat.Select(x => Tuple.Create(x.Item1, x.Item2)).ToList();
    207       tabuwalkingStat = original.tabuwalkingStat.Select(x => Tuple.Create(x.Item1, x.Item2)).ToList();
    208 
     276      adaptiveWalkPerformanceModel = cloner.Clone(original.adaptiveWalkPerformanceModel);
     277      adaptivewalkingStat = original.adaptivewalkingStat.Select(x => Tuple.Create(x.Item1, x.Item2)).ToList();
     278     
    209279      Model = cloner.Clone(original.Model);
    210280    }
    … …  
    222292      Parameters.Add(byBreeding = new ValueParameter<IntValue>("ByBreeding", new IntValue(0)));
    223293      Parameters.Add(byRelinking = new ValueParameter<IntValue>("ByRelinking", new IntValue(0)));
     294      Parameters.Add(byDelinking = new ValueParameter<IntValue>("ByDelinking", new IntValue(0)));
    224295      Parameters.Add(bySampling = new ValueParameter<IntValue>("BySampling", new IntValue(0)));
    225296      Parameters.Add(byHillclimbing = new ValueParameter<IntValue>("ByHillclimbing", new IntValue(0)));
    226       Parameters.Add(byTabuwalking = new ValueParameter<IntValue>("ByTabuwalking", new IntValue(0)));
     297      Parameters.Add(byAdaptivewalking = new ValueParameter<IntValue>("ByAdaptivewalking", new IntValue(0)));
    227298      Parameters.Add(random = new ValueParameter<IRandom>("Random", new MersenneTwister()));
    228299
    229300      breedingStat = new List<Tuple<double, double, double>>();
     301      relinkingStat = new List<Tuple<double, double, double>>();
     302      delinkingStat = new List<Tuple<double, double, double>>();
     303      samplingStat = new List<Tuple<double, double>>();
    230304      hillclimbingStat = new List<Tuple<double, double>>();
    231       tabuwalkingStat = new List<Tuple<double, double>>();
     305      adaptivewalkingStat = new List<Tuple<double, double>>();
    232306    }
    233307
    … …  
    239313    }
    240314
     315    public void RelearnBreedingPerformanceModel() {
     316      breedingPerformanceModel = RunRegression(PrepareRegression(BreedingStat), breedingPerformanceModel).Model;
     317    }
     318    public bool BreedingSuited(ISingleObjectiveSolutionScope<TSolution> p1, ISingleObjectiveSolutionScope<TSolution> p2) {
     319      if (breedingPerformanceModel == null) return true;
     320      double minI1 = double.MaxValue, minI2 = double.MaxValue, maxI1 = double.MinValue, maxI2 = double.MinValue;
     321      foreach (var d in BreedingStat) {
     322        if (d.Item1 < minI1) minI1 = d.Item1;
     323        if (d.Item1 > maxI1) maxI1 = d.Item1;
     324        if (d.Item2 < minI2) minI2 = d.Item2;
     325        if (d.Item2 > maxI2) maxI2 = d.Item2;
     326      }
     327      if (IsBetter(p1, p2)) {
     328        if (p1.Fitness < minI1 || p1.Fitness > maxI1 || p2.Fitness < minI2 || p2.Fitness > maxI2)
     329          return true;
     330        return Random.NextDouble() < ProbabilityAccept3dModel(p1.Fitness, p2.Fitness, breedingPerformanceModel);
     331      }
     332      if (p1.Fitness < minI2 || p1.Fitness > maxI2 || p2.Fitness < minI1 || p2.Fitness > maxI1)
     333        return true;
     334      return Random.NextDouble() < ProbabilityAccept3dModel(p2.Fitness, p1.Fitness, breedingPerformanceModel);
     335    }
     336
     337    public void RelearnRelinkingPerformanceModel() {
     338      relinkingPerformanceModel = RunRegression(PrepareRegression(RelinkingStat), relinkingPerformanceModel).Model;
     339    }
     340    public bool RelinkSuited(ISingleObjectiveSolutionScope<TSolution> p1, ISingleObjectiveSolutionScope<TSolution> p2) {
     341      if (relinkingPerformanceModel == null) return true;
     342      double minI1 = double.MaxValue, minI2 = double.MaxValue, maxI1 = double.MinValue, maxI2 = double.MinValue;
     343      foreach (var d in RelinkingStat) {
     344        if (d.Item1 < minI1) minI1 = d.Item1;
     345        if (d.Item1 > maxI1) maxI1 = d.Item1;
     346        if (d.Item2 < minI2) minI2 = d.Item2;
     347        if (d.Item2 > maxI2) maxI2 = d.Item2;
     348      }
     349      if (IsBetter(p1, p2)) {
     350        if (p1.Fitness < minI1 || p1.Fitness > maxI1 || p2.Fitness < minI2 || p2.Fitness > maxI2)
     351          return true;
     352        return Random.NextDouble() < ProbabilityAccept3dModel(p1.Fitness, p2.Fitness, relinkingPerformanceModel);
     353      }
     354      if (p1.Fitness < minI2 || p1.Fitness > maxI2 || p2.Fitness < minI1 || p2.Fitness > maxI1)
     355        return true;
     356      return Random.NextDouble() < ProbabilityAccept3dModel(p2.Fitness, p1.Fitness, relinkingPerformanceModel);
     357    }
     358
     359    public void RelearnDelinkingPerformanceModel() {
     360      delinkingPerformanceModel = RunRegression(PrepareRegression(DelinkingStat), delinkingPerformanceModel).Model;
     361    }
     362    public bool DelinkSuited(ISingleObjectiveSolutionScope<TSolution> p1, ISingleObjectiveSolutionScope<TSolution> p2) {
     363      if (delinkingPerformanceModel == null) return true;
     364      double minI1 = double.MaxValue, minI2 = double.MaxValue, maxI1 = double.MinValue, maxI2 = double.MinValue;
     365      foreach (var d in DelinkingStat) {
     366        if (d.Item1 < minI1) minI1 = d.Item1;
     367        if (d.Item1 > maxI1) maxI1 = d.Item1;
     368        if (d.Item2 < minI2) minI2 = d.Item2;
     369        if (d.Item2 > maxI2) maxI2 = d.Item2;
     370      }
     371      if (IsBetter(p1, p2)) {
     372        if (p1.Fitness < minI1 || p1.Fitness > maxI1 || p2.Fitness < minI2 || p2.Fitness > maxI2)
     373          return true;
     374        return Random.NextDouble() < ProbabilityAccept3dModel(p1.Fitness, p2.Fitness, delinkingPerformanceModel);
     375      }
     376      if (p1.Fitness < minI2 || p1.Fitness > maxI2 || p2.Fitness < minI1 || p2.Fitness > maxI1)
     377        return true;
     378      return Random.NextDouble() < ProbabilityAccept3dModel(p2.Fitness, p1.Fitness, delinkingPerformanceModel);
     379    }
     380
     381    public void RelearnSamplingPerformanceModel() {
     382      samplingPerformanceModel = RunRegression(PrepareRegression(SamplingStat), samplingPerformanceModel).Model;
     383    }
     384    public bool SamplingSuited() {
     385      if (samplingPerformanceModel == null) return true;
     386      return Random.NextDouble() < ProbabilityAccept2dModel(Population.Average(x => x.Fitness), samplingPerformanceModel);
     387    }
     388
     389    public void RelearnHillclimbingPerformanceModel() {
     390      hillclimbingPerformanceModel = RunRegression(PrepareRegression(HillclimbingStat), hillclimbingPerformanceModel).Model;
     391    }
     392    public bool HillclimbingSuited(ISingleObjectiveSolutionScope<TSolution> scope) {
     393      if (hillclimbingPerformanceModel == null) return true;
     394      if (scope.Fitness < HillclimbingStat.Min(x => x.Item1) || scope.Fitness > HillclimbingStat.Max(x => x.Item1))
     395        return true;
     396      return Random.NextDouble() < ProbabilityAccept2dModel(scope.Fitness, hillclimbingPerformanceModel);
     397    }
     398    public bool HillclimbingSuited(double startingFitness) {
     399      if (hillclimbingPerformanceModel == null) return true;
     400      if (startingFitness < HillclimbingStat.Min(x => x.Item1) || startingFitness > HillclimbingStat.Max(x => x.Item1))
     401        return true;
     402      return Random.NextDouble() < ProbabilityAccept2dModel(startingFitness, hillclimbingPerformanceModel);
     403    }
     404
     405    public void RelearnAdaptiveWalkPerformanceModel() {
     406      adaptiveWalkPerformanceModel = RunRegression(PrepareRegression(AdaptivewalkingStat), adaptiveWalkPerformanceModel).Model;
     407    }
     408    public bool AdaptivewalkingSuited(ISingleObjectiveSolutionScope<TSolution> scope) {
     409      if (adaptiveWalkPerformanceModel == null) return true;
     410      if (scope.Fitness < AdaptivewalkingStat.Min(x => x.Item1) || scope.Fitness > AdaptivewalkingStat.Max(x => x.Item1))
     411        return true;
     412      return Random.NextDouble() < ProbabilityAccept2dModel(scope.Fitness, adaptiveWalkPerformanceModel);
     413    }
     414    public bool AdaptivewalkingSuited(double startingFitness) {
     415      if (adaptiveWalkPerformanceModel == null) return true;
     416      if (startingFitness < AdaptivewalkingStat.Min(x => x.Item1) || startingFitness > AdaptivewalkingStat.Max(x => x.Item1))
     417        return true;
     418      return Random.NextDouble() < ProbabilityAccept2dModel(startingFitness, adaptiveWalkPerformanceModel);
     419    }
     420
     421    public IConfidenceRegressionSolution GetSolution(IConfidenceRegressionModel model, List<Tuple<double, double>> data) {
     422      return new ConfidenceRegressionSolution(model, PrepareRegression(data));
     423    }
     424    public IConfidenceRegressionSolution GetSolution(IConfidenceRegressionModel model, List<Tuple<double, double, double>> data) {
     425      return new ConfidenceRegressionSolution(model, PrepareRegression(data));
     426    }
     427
     428    protected RegressionProblemData PrepareRegression(List<Tuple<double, double>> sample) {
     429      var inCol = new List<double>();
     430      var outCol = new List<double>();
     431      foreach (var next in sample.Shuffle(Random)) {
     432        inCol.Add(next.Item1);
     433        outCol.Add(next.Item2);
     434      }
     435      var ds = new Dataset(new[] { "in", "out" }, new[] { inCol, outCol });
     436      var regPrb = new RegressionProblemData(ds, new[] { "in" }, "out") {
     437        TrainingPartition = { Start = 0, End = Math.Min(50, sample.Count) },
     438        TestPartition = { Start = Math.Min(50, sample.Count), End = sample.Count }
     439      };
     440      return regPrb;
     441    }
     442
     443    protected RegressionProblemData PrepareRegression(List<Tuple<double, double, double>> sample) {
     444      var in1Col = new List<double>();
     445      var in2Col = new List<double>();
     446      var outCol = new List<double>();
     447      foreach (var next in sample.Shuffle(Random)) {
     448        in1Col.Add(next.Item1);
     449        in2Col.Add(next.Item2);
     450        outCol.Add(next.Item3);
     451      }
     452      var ds = new Dataset(new[] { "in1", "in2", "out" }, new[] { in1Col, in2Col, outCol });
     453      var regPrb = new RegressionProblemData(ds, new[] { "in1", "in2" }, "out") {
     454        TrainingPartition = { Start = 0, End = Math.Min(50, sample.Count) },
     455        TestPartition = { Start = Math.Min(50, sample.Count), End = sample.Count }
     456      };
     457      return regPrb;
     458    }
     459
     460    protected static IConfidenceRegressionSolution RunRegression(RegressionProblemData trainingData, IConfidenceRegressionModel baseLineModel = null) {
     461      var baseline = baseLineModel != null ? new ConfidenceRegressionSolution(baseLineModel, trainingData) : null;
     462      var gpr = new GaussianProcessRegression { Problem = { ProblemData = trainingData } };
     463      if (trainingData.InputVariables.CheckedItems.Any(x => alglib.pearsoncorr2(trainingData.Dataset.GetDoubleValues(x.Value.Value).ToArray(), trainingData.TargetVariableValues.ToArray()) > 0.8)) {
     464        gpr.MeanFunction = new MeanZero();
     465        var cov1 = new CovarianceSum();
     466        cov1.Terms.Add(new CovarianceLinearArd());
     467        cov1.Terms.Add(new CovarianceConst());
     468        gpr.CovarianceFunction = cov1;
     469      }
     470      IConfidenceRegressionSolution solution = null;
     471      var cnt = 0;
     472      do {
     473        ExecuteAlgorithm(gpr);
     474        solution = (IConfidenceRegressionSolution)gpr.Results["Solution"].Value;
     475        cnt++;
     476      } while (cnt < 10 && (solution == null || solution.TrainingRSquared.IsAlmost(0)));
     477      if (baseline == null) return solution;
     478      if (trainingData.Dataset.Rows < 60)
     479        return solution.TrainingMeanAbsoluteError < baseline.TrainingMeanAbsoluteError ? solution : baseline;
     480      return solution.TestMeanAbsoluteError < baseline.TestMeanAbsoluteError ? solution : baseline;
     481    }
     482
     483    protected static void ExecuteAlgorithm(IAlgorithm algorithm) {
     484      using (var evt = new AutoResetEvent(false)) {
     485        EventHandler exeStateChanged = (o, args) => {
     486          if (algorithm.ExecutionState == ExecutionState.Paused || algorithm.ExecutionState == ExecutionState.Stopped)
     487            evt.Set();
     488        };
     489        algorithm.ExecutionStateChanged += exeStateChanged;
     490        algorithm.Prepare(true);
     491        algorithm.Start();
     492        evt.WaitOne();
     493        algorithm.ExecutionStateChanged -= exeStateChanged;
     494      }
     495    }
     496
     497    protected double ProbabilityAccept(ISingleObjectiveSolutionScope<TSolution> scope, IList<Tuple<double, double>> data) {
     498      if (double.IsNaN(scope.Fitness)) throw new ArgumentException("solution not evaluated or quality unknown", "scope");
     499      return ProbabilityAccept2d(scope.Fitness, data);
     500    }
     501
     502    private double ProbabilityAccept2dModel(double a, IConfidenceRegressionModel model) {
     503      var ds = new Dataset(new[] { "in", "out" }, new[] { new List<double> { a }, new List<double> { double.NaN } });
     504      var mean = model.GetEstimatedValues(ds, new[] { 0 }).Single();
     505      var sdev = Math.Sqrt(model.GetEstimatedVariances(ds, new[] { 0 }).Single());
     506
     507      var goal = Problem.Maximization ? Population.Min(x => x.Fitness) : Population.Max(x => x.Fitness);
     508      var z = (goal - mean) / sdev;
     509      return Problem.Maximization ? 1.0 - Phi(z) /* P(X >= z) */ : Phi(z); // P(X <= z)
     510    }
     511    protected double ProbabilityAccept2d(double startingFitness, IList<Tuple<double, double>> data) {
     512      if (data.Count < 10) return 1.0;
     513      var samples = 0;
     514      double meanStart = 0, meanStartOld = 0, meanEnd = 0, meanEndOld = 0;
     515      double varStart = 0, varStartOld = 0, varEnd = 0, varEndOld = 0;
     516      for (var i = 0; i < data.Count; i++) {
     517        samples++;
     518        var x = data[i].Item1;
     519        var y = data[i].Item2;
     520
     521        if (samples == 1) {
     522          meanStartOld = x;
     523          meanEndOld = y;
     524        } else {
     525          meanStart = meanStartOld + (x - meanStartOld) / samples;
     526          meanEnd = meanEndOld + (y - meanEndOld) / samples;
     527          varStart = varStartOld + (x - meanStartOld) * (x - meanStart) / (samples - 1);
     528          varEnd = varEndOld + (y - meanEndOld) * (y - meanEnd) / (samples - 1);
     529
     530          meanStartOld = meanStart;
     531          meanEndOld = meanEnd;
     532          varStartOld = varStart;
     533          varEndOld = varEnd;
     534        }
     535      }
     536      var cov = data.Select((v, i) => new { Index = i, Value = v }).Select(x => x.Value).Sum(x => (x.Item1 - meanStart) * (x.Item2 - meanEnd)) / data.Count;
     537
     538      var biasedMean = meanEnd + cov / varStart * (startingFitness - meanStart);
     539      var biasedStdev = Math.Sqrt(varEnd - (cov * cov) / varStart);
     540
     541      if (Problem.Maximization) {
     542        var goal = Population.Min(x => x.Fitness);
     543        var z = (goal - biasedMean) / biasedStdev;
     544        return 1.0 - Phi(z); // P(X >= z)
     545      } else {
     546        var goal = Population.Max(x => x.Fitness);
     547        var z = (goal - biasedMean) / biasedStdev;
     548        return Phi(z); // P(X <= z)
     549      }
     550    }
     551
     552    private double ProbabilityAccept3dModel(double a, double b, IConfidenceRegressionModel model) {
     553      var ds = new Dataset(new[] { "in1", "in2", "out" }, new[] { new List<double> { a }, new List<double> { b }, new List<double> { double.NaN } });
     554      var mean = model.GetEstimatedValues(ds, new[] { 0 }).Single();
     555      var sdev = Math.Sqrt(model.GetEstimatedVariances(ds, new[] { 0 }).Single());
     556
     557      var goal = Problem.Maximization ? Population.Min(x => x.Fitness) : Population.Max(x => x.Fitness);
     558      var z = (goal - mean) / sdev;
     559      return Problem.Maximization ? 1.0 - Phi(z) /* P(X >= z) */ : Phi(z); // P(X <= z)
     560    }
     561    protected double ProbabilityAccept3d(double startingFitness1, double startingFitness2, IList<Tuple<double, double, double>> data) {
     562      if (data.Count < 20) return 1.0;
     563      var samples = 0;
     564      double meanX1 = 0, meanX1Old = 0, meanX2 = 0, meanX2Old = 0, meanY = 0, meanYOld = 0;
     565      double varX1 = 0, varX1Old = 0, varX2 = 0, varX2Old = 0, varY = 0, varYOld = 0;
     566      for (var i = 0; i < data.Count; i++) {
     567        samples++;
     568        var x1 = data[i].Item1;
     569        var x2 = data[i].Item2;
     570        var y = data[i].Item3;
     571
     572        if (samples == 1) {
     573          meanX1Old = x1;
     574          meanX2Old = x2;
     575          meanYOld = y;
     576        } else {
     577          meanX1 = meanX1Old + (x1 - meanX1Old) / samples;
     578          meanX2 = meanX2Old + (x2 - meanX2Old) / samples;
     579          meanY = meanYOld + (y - meanYOld) / samples;
     580          varX1 = varX1Old + (x1 - meanX1Old) * (x1 - meanX1) / (samples - 1);
     581          varX2 = varX2Old + (x2 - meanX2Old) * (x2 - meanX2) / (samples - 1);
     582          varY = varYOld + (y - meanYOld) * (y - meanY) / (samples - 1);
     583
     584          meanX1Old = meanX1;
     585          meanX2Old = meanX2;
     586          meanYOld = meanY;
     587          varX1Old = varX1;
     588          varX2Old = varX2;
     589          varYOld = varY;
     590        }
     591      }
     592      double covX1X2 = 0, covX1Y = 0, covX2Y = 0;
     593      for (var i = 0; i < data.Count; i++) {
     594        covX1X2 += (data[i].Item1 - meanX1) * (data[i].Item2 - meanX2) / data.Count;
     595        covX1Y += (data[i].Item1 - meanX1) * (data[i].Item3 - meanY) / data.Count;
     596        covX2Y += (data[i].Item2 - meanX2) * (data[i].Item3 - meanY) / data.Count;
     597      }
     598
     599      var biasedMean = meanY + ((covX1Y * varX2 - covX2Y * covX1X2) * (startingFitness1 - meanX1) - (covX1Y * covX1X2 - covX2Y * varX1) * (startingFitness2 - meanX2)) / (varX1 * varX2 - covX1X2 * covX1X2);
     600      var biasedStdev = Math.Sqrt(varY - (covX1Y * covX1Y * varX2 - 2 * covX1Y * covX2Y * covX1X2 + covX2Y * covX2Y * varX1) / (varX1 * varX2 - covX1X2 * covX1X2));
     601      if (Problem.Maximization) {
     602        var goal = Population.Min(x => x.Fitness);
     603        var z = (goal - biasedMean) / biasedStdev;
     604        return 1.0 - Phi(z); // P(X >= z)
     605      } else {
     606        var goal = Population.Max(x => x.Fitness);
     607        var z = (goal - biasedMean) / biasedStdev;
     608        return Phi(z); // P(X <= z)
     609      }
     610    }
     611
     612    [MethodImpl(MethodImplOptions.AggressiveInlining)]
     613    public bool IsBetter(ISingleObjectiveSolutionScope<TSolution> a, ISingleObjectiveSolutionScope<TSolution> b) {
     614      return IsBetter(a.Fitness, b.Fitness);
     615    }
     616    [MethodImpl(MethodImplOptions.AggressiveInlining)]
     617    public bool IsBetter(double a, double b) {
     618      return double.IsNaN(b) && !double.IsNaN(a)
     619        || Problem.Maximization && a > b
     620        || !Problem.Maximization && a < b;
     621    }
     622
     623    public void AddBreedingResult(ISingleObjectiveSolutionScope<TSolution> a, ISingleObjectiveSolutionScope<TSolution> b, ISingleObjectiveSolutionScope<TSolution> child) {
     624      if (IsBetter(a, b))
     625        BreedingStat.Add(Tuple.Create(a.Fitness, b.Fitness, child.Fitness));
     626      else BreedingStat.Add(Tuple.Create(b.Fitness, a.Fitness, child.Fitness));
     627    }
     628
     629    public void AddRelinkingResult(ISingleObjectiveSolutionScope<TSolution> a, ISingleObjectiveSolutionScope<TSolution> b, ISingleObjectiveSolutionScope<TSolution> child) {
     630      if (IsBetter(a, b))
     631        RelinkingStat.Add(Tuple.Create(a.Fitness, b.Fitness, child.Fitness));
     632      else RelinkingStat.Add(Tuple.Create(b.Fitness, a.Fitness, child.Fitness));
     633    }
     634
     635    public void AddDelinkingResult(ISingleObjectiveSolutionScope<TSolution> a, ISingleObjectiveSolutionScope<TSolution> b, ISingleObjectiveSolutionScope<TSolution> child) {
     636      if (IsBetter(a, b))
     637        DelinkingStat.Add(Tuple.Create(a.Fitness, b.Fitness, child.Fitness));
     638      else DelinkingStat.Add(Tuple.Create(b.Fitness, a.Fitness, child.Fitness));
     639    }
     640
     641    public void AddSamplingResult(ISingleObjectiveSolutionScope<TSolution> sample) {
     642      SamplingStat.Add(Tuple.Create(Population.Average(x => x.Fitness), sample.Fitness));
     643    }
     644
     645    public void AddHillclimbingResult(ISingleObjectiveSolutionScope<TSolution> input, ISingleObjectiveSolutionScope<TSolution> outcome) {
     646      HillclimbingStat.Add(Tuple.Create(input.Fitness, outcome.Fitness));
     647    }
     648
     649    public void AddTabuwalkingResult(ISingleObjectiveSolutionScope<TSolution> input, ISingleObjectiveSolutionScope<TSolution> outcome) {
     650      AdaptivewalkingStat.Add(Tuple.Create(input.Fitness, outcome.Fitness));
     651    }
     652
    241653    #region IExecutionContext members
    242654    public IAtomicOperation CreateOperation(IOperator op) {
    … …  
    254666    public IAtomicOperation CreateChildOperation(IOperator op, IScope s) {
    255667      return new ExecutionContext(this, op, s);
     668    }
     669    #endregion
     670
     671    #region Math Helper
     672    // normal distribution CDF (left of x) for N(0;1) standard normal distribution
     673    // from http://www.johndcook.com/blog/csharp_phi/
     674    // license: "This code is in the public domain. Do whatever you want with it, no strings attached."
     675    // added: 2016-11-19 21:46 CET
     676    protected static double Phi(double x) {
     677      // constants
     678      double a1 = 0.254829592;
     679      double a2 = -0.284496736;
     680      double a3 = 1.421413741;
     681      double a4 = -1.453152027;
     682      double a5 = 1.061405429;
     683      double p = 0.3275911;
     684
     685      // Save the sign of x
     686      int sign = 1;
     687      if (x < 0)
     688        sign = -1;
     689      x = Math.Abs(x) / Math.Sqrt(2.0);
     690
     691      // A&S formula 7.1.26
     692      double t = 1.0 / (1.0 + p * x);
     693      double y = 1.0 - (((((a5 * t + a4) * t) + a3) * t + a2) * t + a1) * t * Math.Exp(-x * x);
     694
     695      return 0.5 * (1.0 + sign * y);
    256696    }
    257697    #endregion

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

    r14477 r14544  
    3939  [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms, Priority = 999)]
    4040  public class PermutationMemPR : MemPRAlgorithm<SingleObjectiveBasicProblem<PermutationEncoding>, Encodings.PermutationEncoding.Permutation, PermutationMemPRPopulationContext, PermutationMemPRSolutionContext> {
    41     private const double UncommonBitSubsetMutationProbabilityMagicConst = 0.05;
    42 
    4341#if DEBUG
    4442    private const bool VALIDATE = true;
    … …  
    144142    }
    145143
    146     protected override int TabuWalk(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> scope, int maxEvals, CancellationToken token, ISolutionSubspace<Encodings.PermutationEncoding.Permutation> subspace = null) {
     144    protected override void AdaptiveWalk(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> scope, int maxEvals, CancellationToken token, ISolutionSubspace<Encodings.PermutationEncoding.Permutation> subspace = null) {
    147145      var wrapper = new EvaluationWrapper<Encodings.PermutationEncoding.Permutation>(Context.Problem, scope);
    148146      var quality = scope.Fitness;
    149147      try {
    150         return TabuWalk(Context.Random, scope.Solution, wrapper.Evaluate, ref quality, maxEvals, subspace != null ? ((PermutationSolutionSubspace)subspace).Subspace : null);
     148        TabuWalk(Context.Random, scope.Solution, wrapper.Evaluate, ref quality, maxEvals, subspace != null ? ((PermutationSolutionSubspace)subspace).Subspace : null);
    151149      } finally {
    152150        scope.Fitness = quality;
    … …  
    154152    }
    155153
    156     public int TabuWalk(IRandom random, Encodings.PermutationEncoding.Permutation perm, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, ref double quality, int maxEvals = int.MaxValue, bool[,] subspace = null) {
    157       int newSteps = 0;
     154    public void TabuWalk(IRandom random, Encodings.PermutationEncoding.Permutation perm, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, ref double quality, int maxEvals = int.MaxValue, bool[,] subspace = null) {
    158155      switch (perm.PermutationType) {
    159156        case PermutationTypes.Absolute:
    160           newSteps = TabuWalkSwap(random, perm, eval, ref quality, maxEvals, subspace);
     157          TabuWalkSwap(random, perm, eval, ref quality, maxEvals, subspace);
    161158          break;
    162159        case PermutationTypes.RelativeDirected:
    163           newSteps = TabuWalkShift(random, perm, eval, ref quality, maxEvals, subspace);
     160          TabuWalkShift(random, perm, eval, ref quality, maxEvals, subspace);
    164161          break;
    165162        case PermutationTypes.RelativeUndirected:
    166           newSteps = TabuWalkOpt(random, perm, eval, ref quality, maxEvals, subspace);
     163          TabuWalkOpt(random, perm, eval, ref quality, maxEvals, subspace);
    167164          break;
    168165        default: throw new ArgumentException(string.Format("Permutation type {0} is not known", perm.PermutationType));
    169166      }
    170167      if (VALIDATE && !perm.Validate()) throw new ArgumentException("TabuWalk produced invalid child");
    171       return newSteps;
    172168    }
    173169
    … …  
    382378    }
    383379
    384     protected override ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> Cross(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p1, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p2, CancellationToken token) {
    385       Encodings.PermutationEncoding.Permutation child = null;
     380    protected override ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> Breed(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p1, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p2, CancellationToken token) {
     381      ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> child = null;
    386382
    387383      if (p1.Solution.PermutationType == PermutationTypes.Absolute) {
    388         child = CyclicCrossover.Apply(Context.Random, p1.Solution, p2.Solution);
     384        child = CrossAbsolute(p1, p2, token);
    389385      } else if (p1.Solution.PermutationType == PermutationTypes.RelativeDirected) {
    390         child = PartiallyMatchedCrossover.Apply(Context.Random, p1.Solution, p2.Solution);
     386        child = CrossRelativeDirected(p1, p2, token);
    391387      } else if (p1.Solution.PermutationType == PermutationTypes.RelativeUndirected) {
    392         child = EdgeRecombinationCrossover.Apply(Context.Random, p1.Solution, p2.Solution);
     388        child = CrossRelativeUndirected(p1, p2, token);
    393389      } else throw new ArgumentException(string.Format("Unknown permutation type {0}", p1.Solution.PermutationType));
    394390
    395       if (VALIDATE && !child.Validate()) throw new ArgumentException("Cross produced invalid child");
    396       return ToScope(child);
    397     }
    398 
    399     protected override void Mutate(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> offspring, CancellationToken token, ISolutionSubspace<Encodings.PermutationEncoding.Permutation> subspace = null) {
    400       Mutate(Context.Random, offspring.Solution, UncommonBitSubsetMutationProbabilityMagicConst, subspace != null ? ((PermutationSolutionSubspace)subspace).Subspace : null);
    401     }
    402 
    403     public static void Mutate(IRandom random, Encodings.PermutationEncoding.Permutation perm, double p, bool[,] subspace) {
    404       switch (perm.PermutationType) {
    405         case PermutationTypes.Absolute:
    406           MutateSwap(random, perm, p, subspace);
    407           break;
    408         case PermutationTypes.RelativeDirected:
    409           MutateShift(random, perm, p, subspace);
    410           break;
    411         case PermutationTypes.RelativeUndirected:
    412           MutateOpt(random, perm, p, subspace);
    413           break;
    414         default: throw new ArgumentException(string.Format("Permutation type {0} is not known", perm.PermutationType));
    415       }
    416       if (VALIDATE && !perm.Validate()) throw new ArgumentException("Mutate produced invalid child");
    417     }
    418 
    419     public static void MutateSwap(IRandom random, Encodings.PermutationEncoding.Permutation perm, double p, bool[,] subspace) {
    420       //Log("BEFOR: {0}", string.Join(", ", lle));
    421       // The goal of the mutation is to disrupt crossover when it's in an agreeing position
    422       var options = new List<int>(Enumerable.Range(0, perm.Length).Where(x => subspace == null || !subspace[x, 0]));
    423       if (options.Count < 1) return;
    424 
    425       for (var i = options.Count - 1; i > 0; i--) {
    426         if (random.NextDouble() < p) {
    427           var j = random.Next(0, i);
    428           var h = perm[options[i]];
    429           perm[options[i]] = perm[options[j]];
    430           perm[options[j]] = h;
    431           if (subspace != null) {
    432             subspace[options[i], 0] = true;
    433             subspace[options[j], 0] = true;
    434           }
    435         }
    436       }
    437     }
    438 
    439     public static void MutateShift(IRandom random, Encodings.PermutationEncoding.Permutation perm, double p, bool[,] subspace) {
    440       //Log("BEFOR: {0}", string.Join(", ", lle));
    441       // The goal of the mutation is to disrupt crossover when it's in an agreeing position
    442       foreach (var shift in ExhaustiveInsertionMoveGenerator.Generate(perm).Shuffle(random)) {
    443         var prev1 = shift.Index1 - 1;
    444         var next1 = (shift.Index1 + 1) % perm.Length;
    445         if (prev1 < 0) prev1 += perm.Length;
    446         var prev3 = shift.Index3 - 1;
    447         var next3 = (shift.Index3 + 1) % perm.Length;
    448         if (prev3 < 0) prev3 += perm.Length;
    449         if (subspace == null || !(subspace[perm[prev1], perm[shift.Index1]] && subspace[perm[shift.Index1], perm[next1]]
    450             && subspace[perm[prev3], perm[shift.Index3]] && subspace[perm[shift.Index3], perm[next3]])) {
    451           if (random.NextDouble() < p) {
    452             if (subspace != null) {
    453               subspace[perm[prev1], perm[shift.Index1]] = true;
    454               subspace[perm[shift.Index1], perm[next1]] = true;
    455               subspace[perm[prev3], perm[shift.Index3]] = true;
    456               subspace[perm[shift.Index3], perm[next3]] = true;
    457             }
    458             TranslocationManipulator.Apply(perm, shift.Index1, shift.Index2, shift.Index3);
    459             return;
    460           }
    461         }
    462       }
    463     }
    464 
    465     public static void MutateOpt(IRandom random, Encodings.PermutationEncoding.Permutation perm, double p, bool[,] subspace) {
    466       //Log("BEFOR: {0}", string.Join(", ", lle));
    467       // The goal of the mutation is to disrupt crossover when it's in an agreeing position
    468       foreach (var opt in ExhaustiveInversionMoveGenerator.Generate(perm).Shuffle(random)) {
    469         var prev = opt.Index1 - 1;
    470         var next = (opt.Index2 + 1) % perm.Length;
    471         if (prev < 0) prev += perm.Length;
    472         if (subspace == null || !(subspace[perm[prev], perm[opt.Index1]] && subspace[perm[opt.Index2], perm[next]])) {
    473           if (random.NextDouble() < p) {
    474             if (subspace != null) {
    475               subspace[perm[prev], perm[opt.Index1]] = true;
    476               subspace[perm[opt.Index1], perm[prev]] = true;
    477               subspace[perm[opt.Index2], perm[next]] = true;
    478               subspace[perm[next], perm[opt.Index2]] = true;
    479             }
    480             InversionManipulator.Apply(perm, opt.Index1, opt.Index2);
    481             return;
    482           }
    483         }
    484       }
    485     }
    486 
    487     protected override ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> Relink(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> a, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> b, CancellationToken token) {
     391      if (VALIDATE && !child.Solution.Validate()) throw new ArgumentException("Cross produced invalid child");
     392      return child;
     393    }
     394
     395    private ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> CrossAbsolute(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p1, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p2, CancellationToken token) {
     396      var cache = new HashSet<Encodings.PermutationEncoding.Permutation>(new PermutationEqualityComparer());
     397      var cacheHits = 0;
     398      var evaluations = 1;
     399      ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> offspring = null;
     400      for (; evaluations <= Context.LocalSearchEvaluations; evaluations++) {
     401        var c = CyclicCrossover2.Apply(Context.Random, p1.Solution, p2.Solution);
     402        if (cache.Contains(c)) {
     403          cacheHits++;
     404          if (cacheHits > 10) break;
     405          continue;
     406        }
     407        var probe = ToScope(c);
     408        Evaluate(probe, token);
     409        cache.Add(c);
     410        if (offspring == null || Context.IsBetter(probe, offspring)) {
     411          offspring = probe;
     412          if (Context.IsBetter(offspring, p1) && Context.IsBetter(offspring, p2))
     413            break;
     414        }
     415      }
     416      Context.IncrementEvaluatedSolutions(evaluations-1);
     417      return offspring;
     418    }
     419
     420    private ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> CrossRelativeDirected(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p1, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p2, CancellationToken token) {
     421      var cache = new HashSet<Encodings.PermutationEncoding.Permutation>(new PermutationEqualityComparer());
     422      var cacheHits = 0;
     423      var evaluations = 1;
     424      ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> offspring = null;
     425      for (; evaluations <= Context.LocalSearchEvaluations; evaluations++) {
     426        var c = PartiallyMatchedCrossover.Apply(Context.Random, p1.Solution, p2.Solution);
     427        if (cache.Contains(c)) {
     428          cacheHits++;
     429          if (cacheHits > 10) break;
     430          continue;
     431        }
     432        var probe = ToScope(c);
     433        Evaluate(probe, token);
     434        cache.Add(c);
     435        if (offspring == null || Context.IsBetter(probe, offspring)) {
     436          offspring = probe;
     437          if (Context.IsBetter(offspring, p1) && Context.IsBetter(offspring, p2))
     438            break;
     439        }
     440      }
     441      Context.IncrementEvaluatedSolutions(evaluations-1);
     442      return offspring;
     443    }
     444
     445    private ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> CrossRelativeUndirected(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p1, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p2, CancellationToken token) {
     446      var cache = new HashSet<Encodings.PermutationEncoding.Permutation>(new PermutationEqualityComparer());
     447      var cacheHits = 0;
     448      var evaluations = 1;
     449      ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> offspring = null;
     450      for (; evaluations <= Context.LocalSearchEvaluations; evaluations++) {
     451        var c = EdgeRecombinationCrossover.Apply(Context.Random, p1.Solution, p2.Solution);
     452        if (cache.Contains(c)) {
     453          cacheHits++;
     454          if (cacheHits > 10) break;
     455          continue;
     456        }
     457        var probe = ToScope(c);
     458        Evaluate(probe, token);
     459        cache.Add(c);
     460        if (offspring == null || Context.IsBetter(probe, offspring)) {
     461          offspring = probe;
     462          if (Context.IsBetter(offspring, p1) && Context.IsBetter(offspring, p2))
     463            break;
     464        }
     465      }
     466      Context.IncrementEvaluatedSolutions(evaluations-1);
     467      return offspring;
     468    }
     469
     470    protected override ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> Link(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> a, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> b, CancellationToken token, bool delink = false) {
    488471      if (double.IsNaN(a.Fitness)) Evaluate(a, token);
    489472      if (double.IsNaN(b.Fitness)) Evaluate(b, token);
    490473      if (Context.Random.NextDouble() < 0.5)
    491         return IsBetter(a, b) ? Relink(a, b, token, false) : Relink(b, a, token, true);
    492       else return IsBetter(a, b) ? Relink(b, a, token, true) : Relink(a, b, token, false);
    493     }
    494 
    495     protected virtual ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> Relink(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> betterScope, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> worseScope, CancellationToken token, bool fromWorseToBetter) {
     474        return Context.IsBetter(a, b) ? Relink(a, b, token) : Relink(b, a, token);
     475      else return Context.IsBetter(a, b) ? Relink(b, a, token) : Relink(a, b, token);
     476    }
     477
     478    protected virtual ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> Relink(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> betterScope, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> worseScope, CancellationToken token) {
    496479      var wrapper = new EvaluationWrapper<Encodings.PermutationEncoding.Permutation>(Problem, betterScope);
    497480      double quality;

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

    r14492 r14544  
    2626  [Plugin("HeuristicLab.Algorithms.MemPR", "Provides the MemPR (MEMetic Path Relinking) algorithm.", "3.3.14.0")]
    2727  [PluginFile("HeuristicLab.Algorithms.MemPR-3.3.dll", PluginFileType.Assembly)]
     28  [PluginDependency("HeuristicLab.Algorithms.DataAnalysis", "3.4")]
    2829  [PluginDependency("HeuristicLab.Analysis", "3.3")]
    2930  [PluginDependency("HeuristicLab.Collections", "3.3")]

  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/HeuristicLab.Encodings.LinearLinkageEncoding-3.4.csproj

    r14492 r14544  
    167167    <Compile Include="Interfaces\ILinearLinkageSwap2MoveOperator.cs" />
    168168    <Compile Include="Interfaces\ILinearLinkageCreator.cs" />
     169    <Compile Include="LinearLinkageEqualityComparer.cs" />
    169170    <Compile Include="LinearLinkage.cs" />
    170171    <Compile Include="LinearLinkageCreator.cs" />

  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/LinearLinkageEqualityComparer.cs

    r14492 r14544  
    2020#endregion
    2121
    22 using System;
    2322using System.Collections.Generic;
    24 using System.Linq;
    25 using HeuristicLab.Common;
    26 using HeuristicLab.Core;
    27 using HeuristicLab.Data;
    28 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2923
    3024namespace HeuristicLab.Encodings.LinearLinkageEncoding {
    31   [Item("LinearLinkage", "Represents an LLE grouping of items.")]
    32   [StorableClass]
    33   public sealed class LinearLinkage : IntArray {
    34 
    35     [StorableConstructor]
    36     private LinearLinkage(bool deserializing) : base(deserializing) { }
    37     private LinearLinkage(LinearLinkage original, Cloner cloner) : base(original, cloner) { }
    38     public LinearLinkage() { }
    39 
    40     private LinearLinkage(int length) : base(length) { }
    41     private LinearLinkage(int[] elements) : base(elements) { }
    42 
    43     /// <summary>
    44     /// Create a new LinearLinkage object where every element is in a seperate group.
    45     /// </summary>
    46     public static LinearLinkage SingleElementGroups(int length) {
    47       var elements = new int[length];
    48       for (var i = 0; i < length; i++) {
    49         elements[i] = i;
    50       }
    51       return new LinearLinkage(elements);
    52     }
    53 
    54     /// <summary>
    55     /// Create a new LinearLinkage object from an int[] in LLE
    56     /// </summary>
    57     /// <remarks>
    58     /// This operation checks if the argument is a well formed LLE
    59     /// and throws an ArgumentException otherwise.
    60     /// </remarks>
    61     /// <exception cref="ArgumentException">If <paramref name="lle"/> does not represent a valid LLE array.</exception>
    62     /// <param name="lle">The LLE representation</param>
    63     /// <returns>The linear linkage encoding in LLE format (with forward-links).</returns>
    64     public static LinearLinkage FromForwardLinks(int[] lle) {
    65       if (!Validate(lle))
    66         throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding.", "elements");
    67       return new LinearLinkage(lle);
    68     }
    69 
    70     /// <summary>
    71     /// Create a new LinearLinkage object by parsing a LLE-b representation
    72     /// and modifing the underlying array so that it is in LLE representation.
    73     /// </summary>
    74     /// <remarks>
    75     /// This operation runs in O(n) time, the parameter <paramref name="lleb"/> is not modified.
    76     /// </remarks>
    77     /// <exception cref="ArgumentException">If <paramref name="lleb"/> does not represent a valid LLE-b array.</exception>
    78     /// <param name="lleb">The LLE-b representation (LLE with back-links)</param>
    79     /// <returns>The linear linkage encoding in LLE format (with forward-links).</returns>
    80     public static LinearLinkage FromBackLinks(int[] lleb) {
    81       var result = new LinearLinkage(lleb.Length);
    82       for (var i = lleb.Length - 1; i > 0; i--) {
    83         if (lleb[i] == i) {
    84           if (result[i] == 0) result[i] = i;
    85           continue;
    86         }
    87         result[lleb[i]] = i;
    88         if (result[i] == 0) result[i] = i;
    89       }
    90       if (!Validate(result.array))
    91         throw new ArgumentException("Array is malformed and does not represent a valid LLE-b encoding (with back-links).", "lleb");
    92       return result;
    93     }
    94 
    95     /// <summary>
    96     /// Create a new LinearLinkage object by parsing an LLE-e representation
    97     /// and modifing the underlying array so that it is in LLE representation.
    98     /// </summary>
    99     /// <remarks>
    100     /// This operation runs in O(n) time, but requires additional memory
    101     /// in form of a int[].
    102     /// </remarks>
    103     /// <param name="llee">The LLE-e representation</param>
    104     /// <returns>The linear linkage encoding in LLE format (with forward-links).</returns>
    105     public static LinearLinkage FromEndLinks(int[] llee) {
    106       var result = new LinearLinkage(llee.Length);
    107       result.SetEndLinks(llee);
    108       return result;
    109     }
    110 
    111     /// <summary>
    112     /// Create a new LinearLinkage object by translating
    113     /// an enumeration of groups into the underlying array representation.
    114     /// </summary>
    115     /// <remarks>
    116     /// Throws an ArgumentException when there is an element assigned to
    117     /// multiple groups or elements that are not assigned to any group.
    118     /// </remarks>
    119     /// <param name="grouping">The grouping of the elements, each element must
    120     /// be part of exactly one group.</param>
    121     public static LinearLinkage FromGroups(int length, IEnumerable<IEnumerable<int>> grouping) {
    122       var result = new LinearLinkage(length);
    123       result.SetGroups(grouping);
    124       return result;
    125     }
    126 
    127     public override IDeepCloneable Clone(Cloner cloner) {
    128       return new LinearLinkage(this, cloner);
    129     }
    130 
    131     /// <summary>
    132     /// This method parses the encoded array and calculates the membership of
    133     /// each element to the groups. It starts at the lowest element.
    134     /// </summary>
    135     /// <remarks>
    136     /// Runtime complexity of this method is O(n) where n is the length of the
    137     /// array.
    138     /// </remarks>
    139     /// <exception cref="InvalidOperationException">If this object is not vaild LLE.</exception>
    140     /// <returns>An enumeration of all groups.</returns>
    141     public IEnumerable<List<int>> GetGroups() {
    142       var len = array.Length;
    143       var used = new bool[len];
    144       for (var i = 0; i < len; i++) {
    145         if (used[i]) continue;
    146         var curr = i;
    147         var next = array[curr];
    148         var group = new List<int> { curr };
    149         while (next > curr && next < len && !used[next]) {
    150           used[curr] = true;
    151           curr = next;
    152           next = array[next];
    153           group.Add(curr);
    154         }
    155         if (curr != next) throw new InvalidOperationException("Array is malformed and does not represent a valid LLE forward encoding.");
    156         used[curr] = true;
    157         yield return group;
    158       }
    159     }
    160 
    161     /// <summary>
    162     /// This method parses the encoded array and gathers all elements
    163     /// that belong to the same group as element <paramref name="index"/>.
    164     /// </summary>
    165     /// <param name="index">The element whose group should be returned.
    166     /// </param>
    167     /// <returns>The element at <paramref name="index"/> and all other
    168     /// elements in the same group.</returns>
    169     public IEnumerable<int> GetGroup(int index) {
    170       foreach (var n in GetGroupForward(index))
    171         yield return n;
    172       // the element index has already been yielded
    173       foreach (var n in GetGroupBackward(index).Skip(1))
    174         yield return n;
    175     }
    176 
    177     /// <summary>
    178     /// This method parses the encoded array and gathers the element
    179     /// <paramref name="index"/> as well as subsequent elements that
    180     /// belong to the same group.
    181     /// </summary>
    182     /// <param name="index">The element from which subsequent (having a
    183     /// larger number) elements in the group should be returned.
    184     /// </param>
    185     /// <returns>The element <paramref name="index"/> and all subsequent
    186     /// elements in the same group.</returns>
    187     public IEnumerable<int> GetGroupForward(int index) {
    188       yield return index;
    189       var next = array[index];
    190       if (next == index) yield break;
    191       int prev;
    192       do {
    193         yield return next;
    194         prev = next;
    195         next = array[next];
    196       } while (next != prev);
    197     }
    198 
    199     /// <summary>
    200     /// This method parses the encoded array and gathers the element
    201     /// given <paramref name="index"/> as well as preceeding elements that
    202     /// belong to the same group.
    203     /// </summary>
    204     /// <remarks>
    205     /// Warning, this code has performance O(index) as the array has to
    206     /// be fully traversed backwards from the given index.
    207     /// </remarks>
    208     /// <param name="index">The element from which preceeding (having a
    209     /// smaller number) elements in the group should be returned.
    210     /// </param>
    211     /// <returns>The element <paramref name="index"/> and all preceeding
    212     /// elements in the same group.</returns>
    213     public IEnumerable<int> GetGroupBackward(int index) {
    214       yield return index;
    215       var next = array[index];
    216       // return preceding elements in group
    217       for (var prev = index - 1; prev >= 0; prev--) {
    218         if (array[prev] != next) continue;
    219         next = prev;
    220         yield return next;
    221       }
    222     }
    223 
    224     /// <summary>
    225     /// This method translates an enumeration of groups into the underlying
    226     /// array representation.
    227     /// </summary>
    228     /// <remarks>
    229     /// Throws an ArgumentException when there is an element assigned to
    230     /// multiple groups or elements that are not assigned to any group.
    231     /// </remarks>
    232     /// <param name="grouping">The grouping of the elements, each element must
    233     /// be part of exactly one group.</param>
    234     /// <exception cref="ArgumentException">If <paramref name="grouping"/> cannot be converted
    235     /// to a valid LLE representation. For instance, because elements are too big or too small,
    236     /// or they're contained in multiple groups, or there are elements not assigned to any group.
    237     /// </exception>
    238     public void SetGroups(IEnumerable<IEnumerable<int>> grouping) {
    239       var len = array.Length;
    240       var used = new bool[len];
    241       foreach (var group in grouping) {
    242         var prev = -1;
    243         foreach (var g in group.OrderBy(x => x)) {
    244           if (g < prev || g >= len) throw new ArgumentException(string.Format("Element {0} is bigger than {1} or smaller than 0.", g, len - 1), "grouping");
    245           if (prev >= 0) array[prev] = g;
    246           prev = g;
    247           if (used[prev]) {
    248             throw new ArgumentException(string.Format("Element {0} is contained at least twice.", prev), "grouping");
    249           }
    250           used[prev] = true;
    251         }
    252         array[prev] = prev;
    253       }
    254       if (!used.All(x => x))
    255         throw new ArgumentException(string.Format("Elements are not assigned a group: {0}", string.Join(", ", used.Select((x, i) => new { x, i }).Where(x => !x.x).Select(x => x.i))));
    256     }
    257 
    258     /// <summary>
    259     /// Performs a check whether the array represents a valid LLE encoding.
    260     /// </summary>
    261     /// <remarks>
    262     /// The runtime complexity of this method is O(n) where n is the length of
    263     /// the array.
    264     /// </remarks>
    265     /// <returns>True if the encoding is valid.</returns>
    266     public bool Validate() {
    267       return Validate(array);
    268     }
    269 
    270     private static bool Validate(int[] array) {
    271       var len = array.Length;
    272       var used = new bool[len];
    273       for (var i = 0; i < len; i++) {
    274         if (used[i]) continue;
    275         var curr = i;
    276         var next = array[curr];
    277         while (next > curr && next < len && !used[next]) {
    278           used[curr] = true;
    279           curr = next;
    280           next = array[next];
    281         }
    282         if (curr!=next) return false;
    283         used[curr] = true;
    284       }
     25  public class LinearLinkageEqualityComparer : EqualityComparer<LinearLinkage> {
     26    public override bool Equals(LinearLinkage x, LinearLinkage y) {
     27      if (x == null && y == null) return true;
     28      if (x == null || y == null) return false;
     29      if (x.Length != y.Length) return false;
     30      for (var i = 0; i < x.Length; i++)
     31        if (x[i] != y[i]) return false;
    28532      return true;
    28633    }
    28734
    288     /// <summary>
    289     /// This method flattens tree structures that may be present in groups.
    290     /// These tree structures may be created by e.g. merging two groups by
    291     /// linking one end node to the end node of another.
    292     /// Consider following array: 5, 5, 6, 4, 4, 7, 7, 7, 8.
    293     /// This results in the following tree structure for group 7:
    294     ///      7
    295     ///    /   \
    296     ///   5     6
    297     ///  / \    |
    298     /// 0   1   2
    299     /// After this operation the array will be 1, 2, 5, 4, 4, 6, 7, 7, 8.
    300     /// Representing a tree with one branch: 0 -> 1 -> 2 -> 5 -> 6 -> 7.
    301     /// </summary>
    302     /// <remarks>
    303     /// The method first converts the array to LLE-e format and then
    304     /// linearizes the links. This requires two passes of the whole array
    305     /// as well as another copy of the underlying array.
    306     /// The runtime complexity is O(n).
    307     ///
    308     /// The method assumes that there are no back links present.
    309     /// </remarks>
    310     public void LinearizeTreeStructures() {
    311       // Step 1: Convert the array into LLE-e
    312       ToEndLinksInplace(array);
    313       // Step 2: For all groups linearize the links
    314       SetEndLinks(array);
    315     }
    316 
    317     /// <summary>
    318     /// Creates a copy of the underlying array and turns it into LLE-e.
    319     /// </summary>
    320     /// <remarks>
    321     /// LLE-e is a special format where each element points to the
    322     /// ending item of a group.
    323     /// The LLE representation 1, 2, 4, 5, 4, 6, 7, 7 would become
    324     /// 4, 4, 4, 7, 4, 7, 7, 7 in LLE-e.
    325     ///
    326     /// This operation runs in O(n) time.
    327     /// </remarks>
    328     /// <exception cref="ArgumentException">In case, this object does not
    329     /// represent a valid LLE encoding.
    330     /// </exception>
    331     /// <returns>An integer array in LLE-e representation</returns>
    332     public int[] ToEndLinks() {
    333       var result = (int[])array.Clone();
    334       ToEndLinksInplace(result);
    335       return result;
    336     }
    337 
    338     private static void ToEndLinksInplace(int[] array) {
    339       var length = array.Length;
    340       for (var i = length - 1; i >= 0; i--) {
    341         var next = array[i];
    342         if (next > i) {
    343           array[i] = array[next];
    344         } else if (next < i) {
    345           throw new ArgumentException("Array is malformed and does not represent a valid LLE encoding.", "array");
    346         }
     35    public override int GetHashCode(LinearLinkage obj) {
     36      unchecked {
     37        int hash = 17;
     38        foreach (var o in obj)
     39          hash = hash * 31 + o.GetHashCode();
     40        return hash;
    34741      }
    348     }
    349 
    350     /// <summary>
    351     /// Parses an LLE-e representation and modifies the underlying array
    352     /// so that it is in LLE representation.
    353     /// </summary>
    354     /// <remarks>
    355     /// This operation runs in O(n) time, but requires additional memory
    356     /// in form of a int[].
    357     /// </remarks>
    358     /// <param name="llee">The LLE-e representation</param>
    359     /// <exception cref="ArgumentException">
    360     /// If <paramref name="llee"/> does not contain a valid LLE-e representation or
    361     /// has a different length to the given instance.
    362     /// </exception>
    363     public void SetEndLinks(int[] llee) {
    364       var length = array.Length;
    365       if (length != llee.Length) {
    366         throw new ArgumentException(string.Format("Expected length {0} but length was {1}", length, llee.Length), "llee");
    367       }
    368       // If we are ok with mutating llee we can avoid this clone
    369       var lookup = (int[])llee.Clone();
    370       for (var i = length - 1; i >= 0; i--) {
    371         var end = llee[i];
    372         if (end == i) {
    373           array[i] = end;
    374         } else if (end > i && end < length) {
    375           array[i] = lookup[end];
    376           lookup[end] = i;
    377         } else {
    378           throw new ArgumentException("Array is malformed and does not represent a valid LLE-e end encoding.", "llee");
    379         }
    380       }
    381     }
    382 
    383     /// <summary>
    384     /// Creates a copy of the underlying array and turns it into LLE-b.
    385     /// </summary>
    386     /// <remarks>
    387     /// LLE-b is a special format where each element points to the
    388     /// predecessor instead of the successor.
    389     /// The LLE representation 1, 2, 4, 5, 4, 6, 7, 7
    390     /// would become           0, 0, 1, 3, 2, 3, 5, 6 in LLE-b.
    391     ///
    392     /// This operation runs in O(n) time.
    393     /// </remarks>
    394     /// <returns>An integer array in LLE-b representation</returns>
    395     public int[] ToBackLinks() {
    396       var result = new int[array.Length];
    397       var zeroLink = array[0];
    398       for (var i = 0; i < array.Length; i++) {
    399         if (array[i] == i) {
    400           if (result[i] == 0 && i != zeroLink) result[i] = i;
    401           continue;
    402         }
    403         result[array[i]] = i;
    404         if (result[i] == 0 && i != zeroLink) result[i] = i;
    405       }
    406       return result;
    40742    }
    40843  }

  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/Moves/Move.cs

    r14492 r14544  
    2020#endregion
    2121
    22 using HeuristicLab.Collections;
    23 
    2422namespace HeuristicLab.Encodings.LinearLinkageEncoding {
    2523  public abstract class Move {

  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/Moves/ShiftMove.cs

    r14492 r14544  
    2121
    2222using System;
    23 using HeuristicLab.Collections;
    2423
    2524namespace HeuristicLab.Encodings.LinearLinkageEncoding {

  • branches/MemPRAlgorithm/HeuristicLab.Random

    • Property svn:mergeinfo set to (toggle deleted branches)
      /branches/crossvalidation-2434/HeuristicLab.Randommergedeligible
      /stable/HeuristicLab.Randommergedeligible
      /trunk/sources/HeuristicLab.Randommergedeligible
      /branches/1721-RandomForestPersistence/HeuristicLab.Random10321-10322
      /branches/Algorithms.GradientDescent/HeuristicLab.Random5516-5520
      /branches/Benchmarking/sources/HeuristicLab.Random6917-7005
      /branches/CloningRefactoring/HeuristicLab.Random4656-4721
      /branches/CodeEditor/HeuristicLab.Random11700-11806
      /branches/DataAnalysis Refactoring/HeuristicLab.Random5471-5808
      /branches/DataAnalysis SolutionEnsembles/HeuristicLab.Random5815-6180
      /branches/DataAnalysis/HeuristicLab.Random4458-4459,​4462,​4464
      /branches/DataPreprocessing/HeuristicLab.Random10085-11101
      /branches/GP.Grammar.Editor/HeuristicLab.Random6284-6795
      /branches/GP.Symbols (TimeLag, Diff, Integral)/HeuristicLab.Random5060
      /branches/HLScript/HeuristicLab.Random10331-10358
      /branches/HeuristicLab.DatasetRefactor/sources/HeuristicLab.Random11570-12508
      /branches/HeuristicLab.Problems.DataAnalysis.Trading/HeuristicLab.Random6123-9799
      /branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Random11130-12721
      /branches/HiveStatistics/sources/HeuristicLab.Random12440-12877
      /branches/LogResidualEvaluator/HeuristicLab.Random10202-10483
      /branches/NET40/sources/HeuristicLab.Random5138-5162
      /branches/NSGA-II Changes/HeuristicLab.Random12033-12122
      /branches/ParallelEngine/HeuristicLab.Random5175-5192
      /branches/ProblemInstancesRegressionAndClassification/HeuristicLab.Random7568-7810
      /branches/QAPAlgorithms/HeuristicLab.Random6350-6627
      /branches/Restructure trunk solution/HeuristicLab.Random6828
      /branches/RuntimeOptimizer/HeuristicLab.Random8943-9078
      /branches/ScatterSearch (trunk integration)/HeuristicLab.Random7787-8333
      /branches/SlaveShutdown/HeuristicLab.Random8944-8956
      /branches/SpectralKernelForGaussianProcesses/HeuristicLab.Random10204-10479
      /branches/SuccessProgressAnalysis/HeuristicLab.Random5370-5682
      /branches/Trunk/HeuristicLab.Random6829-6865
      /branches/UnloadJobs/HeuristicLab.Random9168-9215
      /branches/VNS/HeuristicLab.Random5594-5752
      /branches/histogram/HeuristicLab.Random5959-6341

  • branches/MemPRAlgorithm/HeuristicLab.Random/3.3/RandomEnumerable.cs

    r14420 r14544  
    269269        // swapped element because we already returned it.
    270270      }
    271       yield return elements[0];
     271      if (elements.Length > 0)
     272        yield return elements[0];
    272273    }
    273274  }
Note: See TracChangeset for help on using the changeset viewer.