Changeset 14550 for branches/MemPRAlgorithm
- Timestamp:
- 01/05/17 17:50:03 (8 years ago)
- Location:
- branches/MemPRAlgorithm
- Files:
-
- 1 added
- 6 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Binary/BinaryMemPR.cs
r14544 r14550 54 54 } 55 55 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; 60 58 for (var i = 0; i < len; i++) 61 if (a code[i] != bcode[i]) return false;59 if (a[i] != b[i]) return false; 62 60 return true; 63 61 } … … 105 103 var order = Enumerable.Range(0, N).Where(x => subset == null || subset[x]).Shuffle(Context.Random).ToArray(); 106 104 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 113 109 Context.IncrementEvaluatedSolutions(evaluations); 114 110 return; 115 111 } 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); 120 116 for (var iter = 0; iter < int.MaxValue; iter++) { 121 117 var moved = false; … … 131 127 if (Context.IsBetter(after, before) && (bestOfTheWalk == null || Context.IsBetter(after, bestOfTheWalk.Fitness))) { 132 128 bestOfTheWalk = (SingleObjectiveSolutionScope<BinaryVector>)currentScope.Clone(); 129 if (Context.IsBetter(bestOfTheWalk, scope)) { 130 moved = false; 131 break; 132 } 133 133 } 134 134 var diff = Problem.Maximization ? after - before : before - after; 135 135 if (diff > 0) moved = true; 136 136 else { 137 var prob = Math.Exp( temp * diff / range);137 var prob = Math.Exp(diff / temp); 138 138 if (Context.Random.NextDouble() >= prob) { 139 139 // the move is not good enough -> undo the move … … 142 142 } 143 143 } 144 temp += 100.0 / maxEvals;144 temp *= annealFactor; 145 145 if (evaluations >= maxEvals) break; 146 146 } … … 167 167 : Math.Min(p1.Fitness, p2.Fitness); 168 168 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; 170 175 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) { 175 179 for (var i = 0; i <= b; i++) 176 180 probe.Solution[i] = p1.Solution[i]; … … 178 182 probe.Solution[i] = p2.Solution[i]; 179 183 184 // only add to cache, because all solutions must be unique 185 if (cache.Contains(probe.Solution)) continue; 186 cache.Add(probe.Solution); 180 187 Evaluate(probe, token); 181 188 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 183 191 if (Context.IsBetter(probe.Fitness, better)) { 184 192 Context.IncrementEvaluatedSolutions(evaluations); … … 187 195 offspring = (ISingleObjectiveSolutionScope<BinaryVector>)probe.Clone(); 188 196 } 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)) { 192 202 probe.Solution = UniformCrossover.Apply(Context.Random, p1.Solution, p2.Solution); 203 if (cache.Contains(probe.Solution)) { 204 cacheHits++; 205 if (cacheHits > 10) break; // variability of uniform crossover is too low -> parents are too similar 206 continue; 207 } else cache.Add(probe.Solution); 193 208 Evaluate(probe, token); 194 209 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 196 212 if (Context.IsBetter(probe.Fitness, better)) { 197 213 Context.IncrementEvaluatedSolutions(evaluations); … … 202 218 } 203 219 Context.IncrementEvaluatedSolutions(evaluations); 204 return offspring; 220 // return best offspring found 221 return offspring ?? probe; 205 222 } 206 223 -
branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/LinearLinkage/LinearLinkageMemPR.cs
r14544 r14550 32 32 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; 33 33 using HeuristicLab.PluginInfrastructure; 34 using HeuristicLab.Random;35 34 36 35 namespace HeuristicLab.Algorithms.MemPR.Grouping { … … 55 54 } 56 55 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; 63 60 return true; 64 61 } … … 256 253 var evaluations = 1; 257 254 ISingleObjectiveSolutionScope<LinearLinkage> offspring = null; 258 for (; evaluations < Context.LocalSearchEvaluations; evaluations++) {255 for (; evaluations < p1Scope.Solution.Length; evaluations++) { 259 256 var code = GroupCrossover.Apply(Context.Random, p1Scope.Solution, p2Scope.Solution); 260 257 if (cache.Contains(code)) { … … 297 294 m.Apply(probe.Solution); 298 295 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 299 298 if (delink && distAfter > distBefore || !delink && distAfter < distBefore) { 300 299 var beforeQ = probe.Fitness; -
branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/MemPRAlgorithm.cs
r14544 r14550 230 230 var child = Create(token); 231 231 Context.LocalSearchEvaluations += HillClimb(child, token); 232 Context.LocalOptimaLevel += child.Fitness; 232 233 Context.AddToPopulation(child); 233 234 Context.BestQuality = child.Fitness; … … 237 238 } 238 239 Context.LocalSearchEvaluations /= 2; 240 Context.LocalOptimaLevel /= 2; 239 241 Context.Initialized = true; 240 242 } … … 254 256 if (offspring != null) { 255 257 if (Context.PopulationCount < MaximumPopulationSize) 256 HillClimb(offspring, token);258 AdaptiveClimb(offspring, Context.LocalSearchEvaluations, token); 257 259 var replNew = Replace(offspring, token); 258 260 if (replNew) { … … 265 267 if (offspring != null) { 266 268 if (Context.PopulationCount < MaximumPopulationSize) 267 HillClimb(offspring, token);269 AdaptiveClimb(offspring, Context.LocalSearchEvaluations, token); 268 270 if (Replace(offspring, token)) { 269 271 replaced = true; … … 275 277 if (offspring != null) { 276 278 if (Context.PopulationCount < MaximumPopulationSize) 277 HillClimb(offspring, token);279 AdaptiveClimb(offspring, Context.LocalSearchEvaluations, token); 278 280 if (Replace(offspring, token)) { 279 281 replaced = true; … … 285 287 if (offspring != null) { 286 288 if (Context.PopulationCount < MaximumPopulationSize) 287 HillClimb(offspring, token);289 AdaptiveClimb(offspring, Context.LocalSearchEvaluations, token); 288 290 if (Replace(offspring, token)) { 289 291 replaced = true; … … 294 296 if (!replaced && offspring != null) { 295 297 if (Context.HillclimbingSuited(offspring)) { 296 HillClimb(offspring, token);298 AdaptiveClimb(offspring, Context.LocalSearchEvaluations, token); 297 299 if (Replace(offspring, token)) { 298 300 Context.ByHillclimbing++; … … 516 518 return false;// -1; 517 519 } 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); 520 525 protected abstract double Dist(ISingleObjectiveSolutionScope<TSolution> a, ISingleObjectiveSolutionScope<TSolution> b); 521 526 protected abstract ISingleObjectiveSolutionScope<TSolution> ToScope(TSolution code, double fitness = double.NaN); … … 599 604 if (Context.Population.All(p => Context.IsBetter(offspring, p))) 600 605 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)); 602 608 603 609 Context.AddBreedingResult(p1, p2, offspring); … … 620 626 var p2 = Context.AtPopulation(i2); 621 627 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; 623 642 } 624 643 … … 630 649 var p1 = Context.AtPopulation(i1); 631 650 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; 634 666 } 635 667 … … 661 693 #region Sample 662 694 protected virtual ISingleObjectiveSolutionScope<TSolution> Sample(CancellationToken token) { 663 if (Context.PopulationCount == MaximumPopulationSize && Context.SamplingSuited()) {695 if (Context.PopulationCount == MaximumPopulationSize) { 664 696 SolutionModelTrainerParameter.Value.TrainModel(Context); 665 697 ISingleObjectiveSolutionScope<TSolution> bestSample = null; 666 698 var tries = 1; 667 for (; tries < Context.LocalSearchEvaluations; tries++) {699 for (; tries < 100; tries++) { 668 700 var sample = ToScope(Context.Model.Sample()); 669 701 Evaluate(sample, token); 670 702 if (bestSample == null || Context.IsBetter(sample, bestSample)) { 671 703 bestSample = sample; 704 if (Context.Population.Any(x => !Context.IsBetter(x, bestSample))) break; 672 705 } 673 if ( Context.Population.Any(x => !Context.IsBetter(x, bestSample))) break;706 if (!Context.SamplingSuited()) break; 674 707 } 675 708 Context.IncrementEvaluatedSolutions(tries); -
branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/MemPRContext.cs
r14544 r14550 114 114 115 115 [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] 116 123 private IValueParameter<IntValue> byBreeding; 117 124 public int ByBreeding { … … 257 264 bestSolution = cloner.Clone(original.bestSolution); 258 265 localSearchEvaluations = cloner.Clone(original.localSearchEvaluations); 266 localOptimaLevel = cloner.Clone(original.localOptimaLevel); 259 267 byBreeding = cloner.Clone(original.byBreeding); 260 268 byRelinking = cloner.Clone(original.byRelinking); … … 290 298 Parameters.Add(bestSolution = new ValueParameter<TSolution>("BestSolution")); 291 299 Parameters.Add(localSearchEvaluations = new ValueParameter<IntValue>("LocalSearchEvaluations", new IntValue(0))); 300 Parameters.Add(localOptimaLevel = new ValueParameter<DoubleValue>("LocalOptimaLevel", new DoubleValue(0))); 292 301 Parameters.Add(byBreeding = new ValueParameter<IntValue>("ByBreeding", new IntValue(0))); 293 302 Parameters.Add(byRelinking = new ValueParameter<IntValue>("ByRelinking", new IntValue(0))); … … 495 504 } 496 505 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 506 private double ProbabilityAccept2dModel(double a, IConfidenceRegressionModel model) { 503 507 var ds = new Dataset(new[] { "in", "out" }, new[] { new List<double> { a }, new List<double> { double.NaN } }); … … 509 513 return Problem.Maximization ? 1.0 - Phi(z) /* P(X >= z) */ : Phi(z); // P(X <= z) 510 514 } 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 515 552 516 private double ProbabilityAccept3dModel(double a, double b, IConfidenceRegressionModel model) { … … 558 522 var z = (goal - mean) / sdev; 559 523 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 524 } 611 525 -
branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/PermutationMemPR.cs
r14544 r14550 61 61 } 62 62 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); 65 65 } 66 66 … … 398 398 var evaluations = 1; 399 399 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 } 402 408 if (cache.Contains(c)) { 403 409 cacheHits++; … … 423 429 var evaluations = 1; 424 430 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 } 427 439 if (cache.Contains(c)) { 428 440 cacheHits++; … … 448 460 var evaluations = 1; 449 461 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 } 452 470 if (cache.Contains(c)) { 453 471 cacheHits++; … … 469 487 470 488 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)); 480 499 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) { 485 504 if (p1.PermutationType != p2.PermutationType) throw new ArgumentException(string.Format("Unequal permutation types {0} and {1}", p1.PermutationType, p2.PermutationType)); 486 505 switch (p1.PermutationType) { 487 506 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); 489 508 case PermutationTypes.RelativeDirected: 490 return RelinkShift(random, p1, p2, eval, out best);509 return RelinkShift(random, p1, p2, eval, delink, out best); 491 510 case PermutationTypes.RelativeUndirected: 492 return RelinkOpt(random, p1, p2, eval, out best);511 return RelinkOpt(random, p1, p2, eval, delink, out best); 493 512 default: throw new ArgumentException(string.Format("Unknown permutation type {0}", p1.PermutationType)); 494 513 } … … 506 525 var invChild = new int[child.Length]; 507 526 for (var i = 0; i < child.Length; i++) invChild[child[i]] = i; 508 509 //Log(string.Join(", ", child)); 527 510 528 while (options.Count > 0) { 511 529 int bestOption = -1; … … 534 552 invChild[child[idx1]] = idx1; 535 553 invChild[child[idx2]] = idx2; 536 //Log(string.Join(", ", child));537 554 if (FitnessComparer.IsBetter(maximization, bestChange, best)) { 538 555 if (Dist(child, p2) > 0) { … … 556 573 } 557 574 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) { 559 635 var maximization = Context.Problem.Maximization; 560 636 var evaluations = 0; … … 611 687 } 612 688 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) { 614 690 var maximization = Context.Problem.Maximization; 615 691 var evaluations = 0; -
branches/MemPRAlgorithm/HeuristicLab.Encodings.BinaryVectorEncoding/3.3/HeuristicLab.Encodings.BinaryVectorEncoding-3.3.csproj
r14412 r14550 120 120 <ItemGroup> 121 121 <Compile Include="BinaryVectorEncoding.cs" /> 122 <Compile Include="BinaryVectorEqualityComparer.cs" /> 122 123 <Compile Include="Creators\RandomBinaryVectorCreator.cs" /> 123 124 <Compile Include="Crossovers\MultiBinaryVectorCrossover.cs" />
Note: See TracChangeset
for help on using the changeset viewer.