Free cookie consent management tool by TermsFeed Policy Generator

Changeset 14550


Ignore:
Timestamp:
01/05/17 17:50:03 (8 years ago)
Author:
abeham
Message:

#2701:

  • Added BinaryVectorEqualityComparer (identical to the one in the P3 plugin) to binaryvector plugin
  • Added delinking for absolute coded permutations
  • Some tweaks
Location:
branches/MemPRAlgorithm
Files:
1 added
6 edited

Legend:

Unmodified
Added
Removed

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

    r14544 r14550  
    5454    }
    5555
    56     protected override bool Eq(ISingleObjectiveSolutionScope<BinaryVector> a, ISingleObjectiveSolutionScope<BinaryVector> b) {
    57       var len = a.Solution.Length;
    58       var acode = a.Solution;
    59       var bcode = b.Solution;
     56    protected override bool Eq(BinaryVector a, BinaryVector b) {
     57      var len = a.Length;
    6058      for (var i = 0; i < len; i++)
    61         if (acode[i] != bcode[i]) return false;
     59        if (a[i] != b[i]) return false;
    6260      return true;
    6361    }
    … …  
    105103      var order = Enumerable.Range(0, N).Where(x => subset == null || subset[x]).Shuffle(Context.Random).ToArray();
    106104
    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
     105      var bound = Problem.Maximization ? Context.Population.Max(x => x.Fitness) : Context.Population.Min(x => x.Fitness);
     106      var range = Math.Abs(bound - Context.LocalOptimaLevel);
     107      if (range.IsAlmost(0)) range = Math.Abs(bound * 0.05);
     108      if (range.IsAlmost(0)) { // because bound = localoptimalevel = 0
    113109        Context.IncrementEvaluatedSolutions(evaluations);
    114110        return;
    115111      }
    116 
    117       //var upperBound = Problem.Maximization ? min - range : max + range;
    118       //var lowerBound = Problem.Maximization ? max : min;
    119       var temp = 1.0;
     112     
     113      var temp = -range / Math.Log(1.0 / maxEvals);
     114      var endtemp = -range / Math.Log(0.1 / maxEvals);
     115      var annealFactor = Math.Pow(endtemp / temp, 1.0 / maxEvals);
    120116      for (var iter = 0; iter < int.MaxValue; iter++) {
    121117        var moved = false;
    … …  
    131127          if (Context.IsBetter(after, before) && (bestOfTheWalk == null || Context.IsBetter(after, bestOfTheWalk.Fitness))) {
    132128            bestOfTheWalk = (SingleObjectiveSolutionScope<BinaryVector>)currentScope.Clone();
     129            if (Context.IsBetter(bestOfTheWalk, scope)) {
     130              moved = false;
     131              break;
     132            }
    133133          }
    134134          var diff = Problem.Maximization ? after - before : before - after;
    135135          if (diff > 0) moved = true;
    136136          else {
    137             var prob = Math.Exp(temp * diff / range);
     137            var prob = Math.Exp(diff / temp);
    138138            if (Context.Random.NextDouble() >= prob) {
    139139              // the move is not good enough -> undo the move
    … …  
    142142            }
    143143          }
    144           temp += 100.0 / maxEvals;
     144          temp *= annealFactor;
    145145          if (evaluations >= maxEvals) break;
    146146        }
    … …  
    167167                                        : Math.Min(p1.Fitness, p2.Fitness);
    168168
    169       var offspring = ToScope(null);
     169
     170      var cache = new HashSet<BinaryVector>(new BinaryVectorEqualityComparer());
     171      cache.Add(p1.Solution);
     172      cache.Add(p2.Solution);
     173
     174      ISingleObjectiveSolutionScope<BinaryVector> offspring = null;
    170175      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;
     176      // first try all possible combinations of 1-point crossover
     177      /*var order = Enumerable.Range(1, N - 2).Where(x => p1.Solution[x] != p2.Solution[x]).Shuffle(Context.Random).ToList();
     178      foreach (var b in order) {
    175179        for (var i = 0; i <= b; i++)
    176180          probe.Solution[i] = p1.Solution[i];
    … …  
    178182          probe.Solution[i] = p2.Solution[i];
    179183
     184        // only add to cache, because all solutions must be unique
     185        if (cache.Contains(probe.Solution)) continue;
     186        cache.Add(probe.Solution);
    180187        Evaluate(probe, token);
    181188        evaluations++;
    182         if (Context.IsBetter(probe, offspring)) {
     189        if (offspring == null || Context.IsBetter(probe, offspring)) {
     190          // immediately return upon finding a better offspring than better parent
    183191          if (Context.IsBetter(probe.Fitness, better)) {
    184192            Context.IncrementEvaluatedSolutions(evaluations);
    … …  
    187195          offspring = (ISingleObjectiveSolutionScope<BinaryVector>)probe.Clone();
    188196        }
    189       }
    190 
    191       while (evaluations < Context.LocalSearchEvaluations) {
     197      }*/
     198
     199      var cacheHits = 0;
     200      // if we got some evaluations left, try uniform crossover
     201      while (evaluations < Math.Min(Context.LocalSearchEvaluations, N)) {
    192202        probe.Solution = UniformCrossover.Apply(Context.Random, p1.Solution, p2.Solution);
     203        if (cache.Contains(probe.Solution)) {
     204          cacheHits++;
     205          if (cacheHits > 10) break; // variability of uniform crossover is too low -> parents are too similar
     206          continue;
     207        } else cache.Add(probe.Solution);
    193208        Evaluate(probe, token);
    194209        evaluations++;
    195         if (Context.IsBetter(probe, offspring)) {
     210        if (offspring == null || Context.IsBetter(probe, offspring)) {
     211          // immediately return upon finding a better offspring than better parent
    196212          if (Context.IsBetter(probe.Fitness, better)) {
    197213            Context.IncrementEvaluatedSolutions(evaluations);
    … …  
    202218      }
    203219      Context.IncrementEvaluatedSolutions(evaluations);
    204       return offspring;
     220      // return best offspring found
     221      return offspring ?? probe;
    205222    }
    206223

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

    r14544 r14550  
    3232using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    3333using HeuristicLab.PluginInfrastructure;
    34 using HeuristicLab.Random;
    3534
    3635namespace HeuristicLab.Algorithms.MemPR.Grouping {
    … …  
    5554    }
    5655
    57     protected override bool Eq(ISingleObjectiveSolutionScope<LinearLinkage> a, ISingleObjectiveSolutionScope<LinearLinkage> b) {
    58       var s1 = a.Solution;
    59       var s2 = b.Solution;
    60       if (s1.Length != s2.Length) return false;
    61       for (var i = 0; i < s1.Length; i++)
    62         if (s1[i] != s2[i]) return false;
     56    protected override bool Eq(LinearLinkage a, LinearLinkage b) {
     57      if (a.Length != b.Length) return false;
     58      for (var i = 0; i < a.Length; i++)
     59        if (a[i] != b[i]) return false;
    6360      return true;
    6461    }
    … …  
    256253      var evaluations = 1;
    257254      ISingleObjectiveSolutionScope<LinearLinkage> offspring = null;
    258       for (; evaluations < Context.LocalSearchEvaluations; evaluations++) {
     255      for (; evaluations < p1Scope.Solution.Length; evaluations++) {
    259256        var code = GroupCrossover.Apply(Context.Random, p1Scope.Solution, p2Scope.Solution);
    260257        if (cache.Contains(code)) {
    … …  
    297294          m.Apply(probe.Solution);
    298295          var distAfter = Dist(probe, b);
     296          // consider all moves that would increase the distance between probe and b
     297          // or decrease it depending on whether we do delinking or relinking
    299298          if (delink && distAfter > distBefore || !delink && distAfter < distBefore) {
    300299            var beforeQ = probe.Fitness;

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

    r14544 r14550  
    230230          var child = Create(token);
    231231          Context.LocalSearchEvaluations += HillClimb(child, token);
     232          Context.LocalOptimaLevel += child.Fitness;
    232233          Context.AddToPopulation(child);
    233234          Context.BestQuality = child.Fitness;
    … …  
    237238        }
    238239        Context.LocalSearchEvaluations /= 2;
     240        Context.LocalOptimaLevel /= 2;
    239241        Context.Initialized = true;
    240242      }
    … …  
    254256      if (offspring != null) {
    255257        if (Context.PopulationCount < MaximumPopulationSize)
    256           HillClimb(offspring, token);
     258          AdaptiveClimb(offspring, Context.LocalSearchEvaluations, token);
    257259        var replNew = Replace(offspring, token);
    258260        if (replNew) {
    … …  
    265267      if (offspring != null) {
    266268        if (Context.PopulationCount < MaximumPopulationSize)
    267           HillClimb(offspring, token);
     269          AdaptiveClimb(offspring, Context.LocalSearchEvaluations, token);
    268270        if (Replace(offspring, token)) {
    269271          replaced = true;
    … …  
    275277      if (offspring != null) {
    276278        if (Context.PopulationCount < MaximumPopulationSize)
    277           HillClimb(offspring, token);
     279          AdaptiveClimb(offspring, Context.LocalSearchEvaluations, token);
    278280        if (Replace(offspring, token)) {
    279281          replaced = true;
    … …  
    285287      if (offspring != null) {
    286288        if (Context.PopulationCount < MaximumPopulationSize)
    287           HillClimb(offspring, token);
     289          AdaptiveClimb(offspring, Context.LocalSearchEvaluations, token);
    288290        if (Replace(offspring, token)) {
    289291          replaced = true;
    … …  
    294296      if (!replaced && offspring != null) {
    295297        if (Context.HillclimbingSuited(offspring)) {
    296           HillClimb(offspring, token);
     298          AdaptiveClimb(offspring, Context.LocalSearchEvaluations, token);
    297299          if (Replace(offspring, token)) {
    298300            Context.ByHillclimbing++;
    … …  
    516518      return false;// -1;
    517519    }
    518    
    519     protected abstract bool Eq(ISingleObjectiveSolutionScope<TSolution> a, ISingleObjectiveSolutionScope<TSolution> b);
     520
     521    protected bool Eq(ISingleObjectiveSolutionScope<TSolution> a, ISingleObjectiveSolutionScope<TSolution> b) {
     522      return Eq(a.Solution, b.Solution);
     523    }
     524    protected abstract bool Eq(TSolution a, TSolution b);
    520525    protected abstract double Dist(ISingleObjectiveSolutionScope<TSolution> a, ISingleObjectiveSolutionScope<TSolution> b);
    521526    protected abstract ISingleObjectiveSolutionScope<TSolution> ToScope(TSolution code, double fitness = double.NaN);
    … …  
    599604        if (Context.Population.All(p => Context.IsBetter(offspring, p)))
    600605          HillClimb(offspring, token);
    601         else HillClimb(offspring, token, CalculateSubspace(new[] { p1.Solution, p2.Solution }));
     606        else if (!Eq(offspring, p1) && !Eq(offspring, p2) && Context.HillclimbingSuited(offspring.Fitness))
     607          HillClimb(offspring, token, CalculateSubspace(new[] { p1.Solution, p2.Solution }, inverse: false));
    602608
    603609        Context.AddBreedingResult(p1, p2, offspring);
    … …  
    620626      var p2 = Context.AtPopulation(i2);
    621627
    622       return Context.RelinkSuited(p1, p2) ? PerformRelinking(p1, p2, token, delink: false) : null;
     628      if (!Context.RelinkSuited(p1, p2)) return null;
     629
     630      var link = PerformRelinking(p1, p2, token, delink: false);
     631      if (double.IsNaN(link.Fitness)) {
     632        Evaluate(link, token);
     633        Context.IncrementEvaluatedSolutions(1);
     634      }
     635      // new best solutions are improved using hill climbing in full solution space
     636      if (Context.Population.All(p => Context.IsBetter(link, p)))
     637        HillClimb(link, token);
     638      else if (!Eq(link, p1) && !Eq(link, p2) && Context.HillclimbingSuited(link.Fitness))
     639        HillClimb(link, token, CalculateSubspace(new[] { p1.Solution, p2.Solution }, inverse: true));
     640
     641      return link;
    623642    }
    624643
    … …  
    630649      var p1 = Context.AtPopulation(i1);
    631650      var p2 = Context.AtPopulation(i2);
    632 
    633       return Context.DelinkSuited(p1, p2) ? PerformRelinking(p1, p2, token, delink: true) : null;
     651     
     652      if (!Context.DelinkSuited(p1, p2)) return null;
     653
     654      var link = PerformRelinking(p1, p2, token, delink: true);
     655      if (double.IsNaN(link.Fitness)) {
     656        Evaluate(link, token);
     657        Context.IncrementEvaluatedSolutions(1);
     658      }
     659      // new best solutions are improved using hill climbing in full solution space
     660      if (Context.Population.All(p => Context.IsBetter(link, p)))
     661        HillClimb(link, token);
     662      /*else if (!Eq(link, p1) && !Eq(link, p2) && Context.HillclimbingSuited(link.Fitness))
     663        HillClimb(link, token, CalculateSubspace(new[] { p1.Solution, p2.Solution }, inverse: false));*/
     664
     665      return link;
    634666    }
    635667
    … …  
    661693    #region Sample
    662694    protected virtual ISingleObjectiveSolutionScope<TSolution> Sample(CancellationToken token) {
    663       if (Context.PopulationCount == MaximumPopulationSize && Context.SamplingSuited()) {
     695      if (Context.PopulationCount == MaximumPopulationSize) {
    664696        SolutionModelTrainerParameter.Value.TrainModel(Context);
    665697        ISingleObjectiveSolutionScope<TSolution> bestSample = null;
    666698        var tries = 1;
    667         for (; tries < Context.LocalSearchEvaluations; tries++) {
     699        for (; tries < 100; tries++) {
    668700          var sample = ToScope(Context.Model.Sample());
    669701          Evaluate(sample, token);
    670702          if (bestSample == null || Context.IsBetter(sample, bestSample)) {
    671703            bestSample = sample;
     704            if (Context.Population.Any(x => !Context.IsBetter(x, bestSample))) break;
    672705          }
    673           if (Context.Population.Any(x => !Context.IsBetter(x, bestSample))) break;
     706          if (!Context.SamplingSuited()) break;
    674707        }
    675708        Context.IncrementEvaluatedSolutions(tries);

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

    r14544 r14550  
    114114
    115115    [Storable]
     116    private IValueParameter<DoubleValue> localOptimaLevel;
     117    public double LocalOptimaLevel {
     118      get { return localOptimaLevel.Value.Value; }
     119      set { localOptimaLevel.Value.Value = value; }
     120    }
     121
     122    [Storable]
    116123    private IValueParameter<IntValue> byBreeding;
    117124    public int ByBreeding {
    … …  
    257264      bestSolution = cloner.Clone(original.bestSolution);
    258265      localSearchEvaluations = cloner.Clone(original.localSearchEvaluations);
     266      localOptimaLevel = cloner.Clone(original.localOptimaLevel);
    259267      byBreeding = cloner.Clone(original.byBreeding);
    260268      byRelinking = cloner.Clone(original.byRelinking);
    … …  
    290298      Parameters.Add(bestSolution = new ValueParameter<TSolution>("BestSolution"));
    291299      Parameters.Add(localSearchEvaluations = new ValueParameter<IntValue>("LocalSearchEvaluations", new IntValue(0)));
     300      Parameters.Add(localOptimaLevel = new ValueParameter<DoubleValue>("LocalOptimaLevel", new DoubleValue(0)));
    292301      Parameters.Add(byBreeding = new ValueParameter<IntValue>("ByBreeding", new IntValue(0)));
    293302      Parameters.Add(byRelinking = new ValueParameter<IntValue>("ByRelinking", new IntValue(0)));
    … …  
    495504    }
    496505
    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 
    502506    private double ProbabilityAccept2dModel(double a, IConfidenceRegressionModel model) {
    503507      var ds = new Dataset(new[] { "in", "out" }, new[] { new List<double> { a }, new List<double> { double.NaN } });
    … …  
    509513      return Problem.Maximization ? 1.0 - Phi(z) /* P(X >= z) */ : Phi(z); // P(X <= z)
    510514    }
    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     }
    551515
    552516    private double ProbabilityAccept3dModel(double a, double b, IConfidenceRegressionModel model) {
    … …  
    558522      var z = (goal - mean) / sdev;
    559523      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       }
    610524    }
    611525

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

    r14544 r14550  
    6161    }
    6262
    63     protected override bool Eq(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> a, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> b) {
    64       return new PermutationEqualityComparer().Equals(a.Solution, b.Solution);
     63    protected override bool Eq(Encodings.PermutationEncoding.Permutation a, Encodings.PermutationEncoding.Permutation b) {
     64      return new PermutationEqualityComparer().Equals(a, b);
    6565    }
    6666
    … …  
    398398      var evaluations = 1;
    399399      ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> offspring = null;
    400       for (; evaluations <= Context.LocalSearchEvaluations; evaluations++) {
    401         var c = CyclicCrossover2.Apply(Context.Random, p1.Solution, p2.Solution);
     400      for (; evaluations <= p1.Solution.Length; evaluations++) {
     401        Encodings.PermutationEncoding.Permutation c = null;
     402        var xochoice = Context.Random.Next(3);
     403        switch (xochoice) {
     404          case 0: c = CyclicCrossover2.Apply(Context.Random, p1.Solution, p2.Solution); break;
     405          case 1: c = PartiallyMatchedCrossover.Apply(Context.Random, p1.Solution, p2.Solution); break;
     406          case 2: c = UniformLikeCrossover.Apply(Context.Random, p1.Solution, p2.Solution); break;
     407        }
    402408        if (cache.Contains(c)) {
    403409          cacheHits++;
    … …  
    423429      var evaluations = 1;
    424430      ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> offspring = null;
    425       for (; evaluations <= Context.LocalSearchEvaluations; evaluations++) {
    426         var c = PartiallyMatchedCrossover.Apply(Context.Random, p1.Solution, p2.Solution);
     431      for (; evaluations <= p1.Solution.Length; evaluations++) {
     432        Encodings.PermutationEncoding.Permutation c = null;
     433        var xochoice = Context.Random.Next(3);
     434        switch (xochoice) {
     435          case 0: c = OrderCrossover2.Apply(Context.Random, p1.Solution, p2.Solution); break;
     436          case 1: c = PartiallyMatchedCrossover.Apply(Context.Random, p1.Solution, p2.Solution); break;
     437          case 2: c = MaximalPreservativeCrossover.Apply(Context.Random, p1.Solution, p2.Solution); break;
     438        }
    427439        if (cache.Contains(c)) {
    428440          cacheHits++;
    … …  
    448460      var evaluations = 1;
    449461      ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> offspring = null;
    450       for (; evaluations <= Context.LocalSearchEvaluations; evaluations++) {
    451         var c = EdgeRecombinationCrossover.Apply(Context.Random, p1.Solution, p2.Solution);
     462      for (; evaluations <= p1.Solution.Length; evaluations++) {
     463        Encodings.PermutationEncoding.Permutation c = null;
     464        var xochoice = Context.Random.Next(3);
     465        switch (xochoice) {
     466          case 0: c = OrderCrossover2.Apply(Context.Random, p1.Solution, p2.Solution); break;
     467          case 1: c = EdgeRecombinationCrossover.Apply(Context.Random, p1.Solution, p2.Solution); break;
     468          case 2: c = MaximalPreservativeCrossover.Apply(Context.Random, p1.Solution, p2.Solution); break;
     469        }
    452470        if (cache.Contains(c)) {
    453471          cacheHits++;
    … …  
    469487
    470488    protected override ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> Link(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> a, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> b, CancellationToken token, bool delink = false) {
    471       if (double.IsNaN(a.Fitness)) Evaluate(a, token);
    472       if (double.IsNaN(b.Fitness)) Evaluate(b, token);
    473       if (Context.Random.NextDouble() < 0.5)
    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) {
    479       var wrapper = new EvaluationWrapper<Encodings.PermutationEncoding.Permutation>(Problem, betterScope);
     489      if (double.IsNaN(a.Fitness)) {
     490        Evaluate(a, token);
     491        Context.IncrementEvaluatedSolutions(1);
     492      }
     493      if (double.IsNaN(b.Fitness)) {
     494        Evaluate(b, token);
     495        Context.IncrementEvaluatedSolutions(1);
     496      }
     497
     498      var wrapper = new EvaluationWrapper<Encodings.PermutationEncoding.Permutation>(Problem, ToScope(null));
    480499      double quality;
    481       return ToScope(Relink(Context.Random, betterScope.Solution, worseScope.Solution, wrapper.Evaluate, out quality));
    482     }
    483 
    484     public Encodings.PermutationEncoding.Permutation Relink(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, out double best) {
     500      return ToScope(Relink(Context.Random, a.Solution, b.Solution, wrapper.Evaluate, delink, out quality));
     501    }
     502
     503    public Encodings.PermutationEncoding.Permutation Relink(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, bool delink, out double best) {
    485504      if (p1.PermutationType != p2.PermutationType) throw new ArgumentException(string.Format("Unequal permutation types {0} and {1}", p1.PermutationType, p2.PermutationType));
    486505      switch (p1.PermutationType) {
    487506        case PermutationTypes.Absolute:
    488           return RelinkSwap(random, p1, p2, eval, out best);
     507          return delink ? DelinkSwap(random, p1, p2, eval, out best) : RelinkSwap(random, p1, p2, eval, out best);
    489508        case PermutationTypes.RelativeDirected:
    490           return RelinkShift(random, p1, p2, eval, out best);
     509          return RelinkShift(random, p1, p2, eval, delink, out best);
    491510        case PermutationTypes.RelativeUndirected:
    492           return RelinkOpt(random, p1, p2, eval, out best);
     511          return RelinkOpt(random, p1, p2, eval, delink, out best);
    493512        default: throw new ArgumentException(string.Format("Unknown permutation type {0}", p1.PermutationType));
    494513      }
    … …  
    506525      var invChild = new int[child.Length];
    507526      for (var i = 0; i < child.Length; i++) invChild[child[i]] = i;
    508 
    509       //Log(string.Join(", ", child));
     527     
    510528      while (options.Count > 0) {
    511529        int bestOption = -1;
    … …  
    534552          invChild[child[idx1]] = idx1;
    535553          invChild[child[idx2]] = idx2;
    536           //Log(string.Join(", ", child));
    537554          if (FitnessComparer.IsBetter(maximization, bestChange, best)) {
    538555            if (Dist(child, p2) > 0) {
    … …  
    556573    }
    557574
    558     public Encodings.PermutationEncoding.Permutation RelinkShift(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, out double best) {
     575    public Encodings.PermutationEncoding.Permutation DelinkSwap(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, out double best) {
     576      var maximization = Context.Problem.Maximization;
     577      var evaluations = 0;
     578      var child = (Encodings.PermutationEncoding.Permutation)p1.Clone();
     579
     580      best = double.NaN;
     581      Encodings.PermutationEncoding.Permutation bestChild = null;
     582
     583      var options = Enumerable.Range(0, child.Length).Where(x => child[x] == p2[x]).ToList();
     584     
     585      while (options.Count > 0) {
     586        int bestOption = -1;
     587        int bestCompanion = -1;
     588        var bestChange = double.NaN;
     589        for (var j = 0; j < options.Count; j++) {
     590          var idx = options[j];
     591          if (child[idx] != p2[idx]) {
     592            options.RemoveAt(j);
     593            j--;
     594            continue;
     595          }
     596          for (var k = 0; k < child.Length; k++) {
     597            if (k == idx) continue;
     598            Swap(child, k, idx);
     599            var moveF = eval(child, random);
     600            evaluations++;
     601            if (FitnessComparer.IsBetter(maximization, moveF, bestChange)) {
     602              bestChange = moveF;
     603              bestOption = j;
     604              bestCompanion = k;
     605            }
     606            // undo
     607            Swap(child, k, idx);
     608          }
     609        }
     610        if (!double.IsNaN(bestChange)) {
     611          var idx1 = options[bestOption];
     612          Swap(child, idx1, bestCompanion);
     613          if (FitnessComparer.IsBetter(maximization, bestChange, best)) {
     614            if (!Eq(child, p2)) {
     615              best = bestChange;
     616              bestChild = (Encodings.PermutationEncoding.Permutation)child.Clone();
     617            }
     618          }
     619          options.RemoveAt(bestOption);
     620        }
     621      }
     622      if (bestChild == null) {
     623        best = eval(child, random);
     624        evaluations++;
     625      }
     626      Context.IncrementEvaluatedSolutions(evaluations);
     627
     628      if (VALIDATE && bestChild != null && !bestChild.Validate()) throw new ArgumentException("Relinking produced invalid child");
     629      if (VALIDATE && Dist(child, p2) > 0) throw new InvalidOperationException("Child is not equal to p2 after relinking");
     630
     631      return bestChild ?? child;
     632    }
     633
     634    public Encodings.PermutationEncoding.Permutation RelinkShift(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, bool delink, out double best) {
    559635      var maximization = Context.Problem.Maximization;
    560636      var evaluations = 0;
    … …  
    611687    }
    612688
    613     public Encodings.PermutationEncoding.Permutation RelinkOpt(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, out double best) {
     689    public Encodings.PermutationEncoding.Permutation RelinkOpt(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, bool delink, out double best) {
    614690      var maximization = Context.Problem.Maximization;
    615691      var evaluations = 0;

  • branches/MemPRAlgorithm/HeuristicLab.Encodings.BinaryVectorEncoding/3.3/HeuristicLab.Encodings.BinaryVectorEncoding-3.3.csproj

    r14412 r14550  
    120120  <ItemGroup>
    121121    <Compile Include="BinaryVectorEncoding.cs" />
     122    <Compile Include="BinaryVectorEqualityComparer.cs" />
    122123    <Compile Include="Creators\RandomBinaryVectorCreator.cs" />
    123124    <Compile Include="Crossovers\MultiBinaryVectorCrossover.cs" />
Note: See TracChangeset for help on using the changeset viewer.