- Timestamp:
- 12/05/16 12:27:19 (8 years ago)
- Location:
- branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3
- Files:
-
- 7 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Binary/BinaryMemPR.cs
r14450 r14453 98 98 99 99 protected override void TabuWalk(ISingleObjectiveSolutionScope<BinaryVector> scope, int steps, CancellationToken token, ISolutionSubspace<BinaryVector> subspace = null) { 100 var evaluations = 0; 100 101 var subset = subspace != null ? ((BinarySolutionSubspace)subspace).Subspace : null; 101 if (double.IsNaN(scope.Fitness)) Evaluate(scope, token); 102 if (double.IsNaN(scope.Fitness)) { 103 Evaluate(scope, token); 104 evaluations++; 105 } 102 106 SingleObjectiveSolutionScope<BinaryVector> bestOfTheWalk = null; 103 107 var currentScope = (SingleObjectiveSolutionScope<BinaryVector>)scope.Clone(); … … 121 125 current[idx] = !current[idx]; 122 126 Evaluate(currentScope, token); 127 evaluations++; 123 128 var after = currentScope.Fitness; 124 129 … … 151 156 } 152 157 158 Context.IncrementEvaluatedSolutions(evaluations); 153 159 scope.Adopt(bestOfTheWalk ?? currentScope); 154 160 } … … 187 193 188 194 protected override ISingleObjectiveSolutionScope<BinaryVector> Relink(ISingleObjectiveSolutionScope<BinaryVector> a, ISingleObjectiveSolutionScope<BinaryVector> b, CancellationToken token) { 189 if (double.IsNaN(a.Fitness)) Evaluate(a, token); 190 if (double.IsNaN(b.Fitness)) Evaluate(b, token); 195 if (double.IsNaN(a.Fitness)) { 196 Evaluate(a, token); 197 Context.IncrementEvaluatedSolutions(1); 198 } 199 if (double.IsNaN(b.Fitness)) { 200 Evaluate(b, token); 201 Context.IncrementEvaluatedSolutions(1); 202 } 191 203 if (Context.Random.NextDouble() < 0.5) 192 204 return IsBetter(a, b) ? Relink(a, b, token, false) : Relink(b, a, token, true); … … 195 207 196 208 protected virtual ISingleObjectiveSolutionScope<BinaryVector> Relink(ISingleObjectiveSolutionScope<BinaryVector> betterScope, ISingleObjectiveSolutionScope<BinaryVector> worseScope, CancellationToken token, bool fromWorseToBetter) { 209 var evaluations = 0; 197 210 var childScope = (ISingleObjectiveSolutionScope<BinaryVector>)(fromWorseToBetter ? worseScope : betterScope).Clone(); 198 211 var child = childScope.Solution; … … 213 226 child[idx] = !child[idx]; // move 214 227 Evaluate(childScope, token); 228 evaluations++; 215 229 var s = childScope.Fitness; 216 230 childScope.Fitness = cF; … … 236 250 } 237 251 } 252 Context.IncrementEvaluatedSolutions(evaluations); 238 253 return best ?? childScope; 239 254 } -
branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/MemPRAlgorithm.cs
r14450 r14453 252 252 var p1 = Context.AtPopulation(i1); 253 253 var p2 = Context.AtPopulation(i2); 254 255 if (double.IsNaN(p1.Fitness)) Evaluate(p1, token);256 if (double.IsNaN(p2.Fitness)) Evaluate(p2, token);257 254 258 255 var parentDist = Dist(p1, p2); … … 361 358 362 359 protected int Replace(ISingleObjectiveSolutionScope<TSolution> child, CancellationToken token) { 363 if (double.IsNaN(child.Fitness)) Evaluate(child, token); 360 if (double.IsNaN(child.Fitness)) { 361 Evaluate(child, token); 362 Context.IncrementEvaluatedSolutions(1); 363 } 364 if (IsBetter(child.Fitness, Context.BestQuality)) { 365 Context.BestQuality = child.Fitness; 366 Context.BestSolution = (TSolution)child.Solution.Clone(); 367 } 364 368 365 369 var popSize = MaximumPopulationSize; … … 460 464 protected abstract ISolutionSubspace<TSolution> CalculateSubspace(IEnumerable<TSolution> solutions, bool inverse = false); 461 465 protected virtual void Evaluate(ISingleObjectiveSolutionScope<TSolution> scope, CancellationToken token) { 462 Context.EvaluatedSolutions++;463 466 var prob = Problem as ISingleObjectiveProblemDefinition; 464 467 if (prob != null) { … … 466 469 scope.Fitness = prob.Evaluate(ind, Context.Random); 467 470 } else RunOperator(Problem.Evaluator, scope, token); 468 if (IsBetter(scope.Fitness, Context.BestQuality))469 Context.BestQuality = scope.Fitness;470 471 } 471 472 … … 480 481 #region Improve 481 482 protected virtual int HillClimb(ISingleObjectiveSolutionScope<TSolution> scope, CancellationToken token, ISolutionSubspace<TSolution> subspace = null) { 482 if (double.IsNaN(scope.Fitness)) Evaluate(scope, token); 483 if (double.IsNaN(scope.Fitness)) { 484 Evaluate(scope, token); 485 Context.IncrementEvaluatedSolutions(1); 486 } 483 487 var before = scope.Fitness; 484 488 var lscontext = Context.CreateSingleSolutionContext(scope); … … 486 490 var after = scope.Fitness; 487 491 Context.HillclimbingStat.Add(Tuple.Create(before, after)); 492 Context.IncrementEvaluatedSolutions(lscontext.EvaluatedSolutions); 488 493 return lscontext.Iterations; 489 494 } 490 495 491 496 protected virtual void PerformTabuWalk(ISingleObjectiveSolutionScope<TSolution> scope, int steps, CancellationToken token, ISolutionSubspace<TSolution> subspace = null) { 492 if (double.IsNaN(scope.Fitness)) Evaluate(scope, token); 497 if (double.IsNaN(scope.Fitness)) { 498 Evaluate(scope, token); 499 Context.IncrementEvaluatedSolutions(1); 500 } 493 501 var before = scope.Fitness; 494 502 var newScope = (ISingleObjectiveSolutionScope<TSolution>)scope.Clone(); … … 500 508 protected abstract void TabuWalk(ISingleObjectiveSolutionScope<TSolution> scope, int steps, CancellationToken token, ISolutionSubspace<TSolution> subspace = null); 501 509 protected virtual void TabuClimb(ISingleObjectiveSolutionScope<TSolution> scope, int steps, CancellationToken token, ISolutionSubspace<TSolution> subspace = null) { 502 if (double.IsNaN(scope.Fitness)) Evaluate(scope, token); 510 if (double.IsNaN(scope.Fitness)) { 511 Evaluate(scope, token); 512 Context.IncrementEvaluatedSolutions(1); 513 } 503 514 var before = scope.Fitness; 504 515 var newScope = (ISingleObjectiveSolutionScope<TSolution>)scope.Clone(); … … 520 531 var p2 = Context.AtPopulation(i2); 521 532 522 if (double.IsNaN(p1.Fitness)) Evaluate(p1, token); 523 if (double.IsNaN(p2.Fitness)) Evaluate(p2, token); 533 if (double.IsNaN(p1.Fitness)) { 534 Evaluate(p1, token); 535 Context.IncrementEvaluatedSolutions(1); 536 } 537 if (double.IsNaN(p2.Fitness)) { 538 Evaluate(p2, token); 539 Context.IncrementEvaluatedSolutions(1); 540 } 524 541 525 542 return BreedAndImprove(p1, p2, token); … … 532 549 Mutate(offspring, token, subspace); // mutate the solutions, especially to widen the sub-space 533 550 } 534 if (double.IsNaN(offspring.Fitness)) Evaluate(offspring, token); 551 if (double.IsNaN(offspring.Fitness)) { 552 Evaluate(offspring, token); 553 Context.IncrementEvaluatedSolutions(1); 554 } 535 555 Context.BreedingStat.Add(Tuple.Create(p1.Fitness, p2.Fitness, offspring.Fitness)); 536 556 if ((IsBetter(offspring, p1) && IsBetter(offspring, p2)) … … 556 576 var p2 = Context.AtPopulation(i2); 557 577 558 if (double.IsNaN(p1.Fitness)) Evaluate(p1, token);559 if (double.IsNaN(p2.Fitness)) Evaluate(p2, token);560 561 578 return RelinkAndImprove(p1, p2, token); 562 579 } … … 584 601 SolutionModelTrainerParameter.Value.TrainModel(Context); 585 602 var sample = ToScope(Context.Model.Sample()); 603 Evaluate(sample, token); 604 Context.IncrementEvaluatedSolutions(1); 586 605 if (Context.Population.Any(p => IsBetter(sample, p) || sample.Fitness == p.Fitness)) return sample; 587 606 … … 608 627 609 628 protected double ProbabilityAccept(ISingleObjectiveSolutionScope<TSolution> scope, IList<Tuple<double, double>> data) { 610 if (double.IsNaN(scope.Fitness)) Evaluate(scope, CancellationToken.None); 629 if (double.IsNaN(scope.Fitness)) { 630 Evaluate(scope, CancellationToken.None); 631 Context.IncrementEvaluatedSolutions(1); 632 } 611 633 return ProbabilityAccept(scope.Fitness, data); 612 634 } -
branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/StaticAPI/Exhaustive1Shift.cs
r14450 r14453 67 67 if (lastSuccessMove == null) break; 68 68 } 69 return Tuple.Create( steps, evaluations);69 return Tuple.Create(evaluations, steps); 70 70 } 71 71 } -
branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/StaticAPI/Exhaustive2Opt.cs
r14450 r14453 64 64 if (lastSuccessMove == null) break; 65 65 } 66 return Tuple.Create( steps, evaluations);66 return Tuple.Create(evaluations, steps); 67 67 } 68 68 } -
branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/StaticAPI/ExhaustiveSwap2.cs
r14450 r14453 66 66 if (lastSuccessMove == null) break; 67 67 } 68 return Tuple.Create( steps, evaluations);68 return Tuple.Create(evaluations, steps); 69 69 } 70 70 } -
branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/PermutationMemPR.cs
r14450 r14453 154 154 } 155 155 156 public staticvoid TabuWalk(IRandom random, Encodings.PermutationEncoding.Permutation perm, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, ref double quality, int maxIterations = int.MaxValue, bool[,] noTouch = null) {156 public void TabuWalk(IRandom random, Encodings.PermutationEncoding.Permutation perm, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, ref double quality, int maxIterations = int.MaxValue, bool[,] noTouch = null) { 157 157 switch (perm.PermutationType) { 158 158 case PermutationTypes.Absolute: … … 170 170 } 171 171 172 public static void TabuWalkSwap(IRandom random, Encodings.PermutationEncoding.Permutation perm, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, ref double quality, int maxIterations = int.MaxValue, bool[,] noTouch = null) { 173 if (double.IsNaN(quality)) quality = eval(perm, random); 172 public void TabuWalkSwap(IRandom random, Encodings.PermutationEncoding.Permutation perm, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, ref double quality, int maxIterations = int.MaxValue, bool[,] noTouch = null) { 173 var evaluations = 0; 174 if (double.IsNaN(quality)) { 175 quality = eval(perm, random); 176 evaluations++; 177 } 174 178 Encodings.PermutationEncoding.Permutation bestOfTheWalk = null; 175 179 double bestOfTheWalkF = double.NaN; … … 177 181 var currentF = quality; 178 182 var overallImprovement = false; 179 //Console.WriteLine("Current {0}", string.Join(", ", current));180 183 var tabu = new double[current.Length, current.Length]; 181 184 for (var i = 0; i < current.Length; i++) { … … 191 194 Swap2Move bestOfTheRest = null; 192 195 var improved = false; 193 //LogAlways("TabuWalk ({0}/{2}): {1} ({3})", iter, currentF, maxIterations, string.Join(", ", current));194 196 foreach (var swap in ExhaustiveSwap2MoveGenerator.Generate(current).Shuffle(random)) { 195 197 if (noTouch != null && (noTouch[swap.Index1, 0] || noTouch[swap.Index2, 0])) … … 200 202 current[swap.Index2] = h; 201 203 var q = eval(current, random); 204 evaluations++; 202 205 if (q < quality) { 203 206 overallImprovement = true; … … 233 236 if (!allTabu && !improved) { 234 237 tabu[bestOfTheRest.Index1, current[bestOfTheRest.Index1]] = Math.Min(currentF, tabu[bestOfTheRest.Index1, current[bestOfTheRest.Index1]]); 235 //LogAlways("Making Tabu [{0},{1}] = {2}", bestOfTheRest.Index1, current[bestOfTheRest.Index1], tabu[bestOfTheRest.Index1, current[bestOfTheRest.Index1]]);236 238 tabu[bestOfTheRest.Index2, current[bestOfTheRest.Index2]] = Math.Min(currentF, tabu[bestOfTheRest.Index2, current[bestOfTheRest.Index2]]); 237 //LogAlways("Making Tabu [{0},{1}] = {2}", bestOfTheRest.Index2, current[bestOfTheRest.Index2], tabu[bestOfTheRest.Index2, current[bestOfTheRest.Index2]]);238 239 239 240 var h = current[bestOfTheRest.Index1]; … … 244 245 } else if (allTabu) break; 245 246 } 247 Context.IncrementEvaluatedSolutions(evaluations); 246 248 if (!overallImprovement && bestOfTheWalk != null) { 247 249 quality = bestOfTheWalkF; … … 250 252 } 251 253 252 public staticvoid TabuWalkShift(IRandom random, Encodings.PermutationEncoding.Permutation perm, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, ref double quality, int maxIterations = int.MaxValue, bool[,] noTouch = null) {254 public void TabuWalkShift(IRandom random, Encodings.PermutationEncoding.Permutation perm, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, ref double quality, int maxIterations = int.MaxValue, bool[,] noTouch = null) { 253 255 return; 254 256 } 255 257 256 public static void TabuWalkOpt(IRandom random, Encodings.PermutationEncoding.Permutation perm, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, ref double quality, int maxIterations = int.MaxValue, bool[,] noTouch = null) { 257 if (double.IsNaN(quality)) quality = eval(perm, random); 258 public void TabuWalkOpt(IRandom random, Encodings.PermutationEncoding.Permutation perm, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, ref double quality, int maxIterations = int.MaxValue, bool[,] noTouch = null) { 259 var evaluations = 0; 260 if (double.IsNaN(quality)) { 261 quality = eval(perm, random); 262 evaluations++; 263 } 258 264 Encodings.PermutationEncoding.Permutation bestOfTheWalk = null; 259 265 double bestOfTheWalkF = double.NaN; … … 287 293 288 294 var q = eval(current, random); 295 evaluations++; 289 296 if (q < quality) { 290 297 overallImprovement = true; … … 333 340 } else if (allTabu) break; 334 341 } 342 Context.IncrementEvaluatedSolutions(evaluations); 335 343 if (!overallImprovement && bestOfTheWalk != null) { 336 344 quality = bestOfTheWalkF; … … 456 464 } 457 465 458 public staticEncodings.PermutationEncoding.Permutation Relink(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, out double best) {466 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) { 459 467 if (p1.PermutationType != p2.PermutationType) throw new ArgumentException(string.Format("Unequal permutation types {0} and {1}", p1.PermutationType, p2.PermutationType)); 460 468 switch (p1.PermutationType) { … … 469 477 } 470 478 471 public static Encodings.PermutationEncoding.Permutation RelinkSwap(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, out double best) { 479 public Encodings.PermutationEncoding.Permutation RelinkSwap(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, out double best) { 480 var evaluations = 0; 472 481 var child = (Encodings.PermutationEncoding.Permutation)p1.Clone(); 473 482 … … 492 501 Swap(child, invChild[p2[idx]], idx); 493 502 var moveF = eval(child, random); 503 evaluations++; 494 504 if (double.IsNaN(bestChange) || moveF < bestChange) { 495 505 bestChange = moveF; … … 515 525 } 516 526 } 517 //Log(string.Join(", ", p2));527 Context.IncrementEvaluatedSolutions(evaluations); 518 528 519 529 if (VALIDATE && bestChild != null && !bestChild.Validate()) throw new ArgumentException("Relinking produced invalid child"); 520 530 if (VALIDATE && Dist(child, p2) > 0) throw new InvalidOperationException("Child is not equal to p2 after relinking"); 521 531 522 532 if (bestChild == null) best = eval(child, random); 523 533 return bestChild ?? child; 524 534 } 525 535 526 public static Encodings.PermutationEncoding.Permutation RelinkShift(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, out double best) { 536 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) { 537 var evaluations = 0; 527 538 var child = (Encodings.PermutationEncoding.Permutation)p1.Clone(); 528 539 … … 545 556 else Shift(child, from: c, to: n); 546 557 var moveF = eval(child, random); 558 evaluations++; 547 559 if (double.IsNaN(bestChange) || moveF < bestChange) { 548 560 bestChange = moveF; … … 564 576 } while (!double.IsNaN(bestChange)); 565 577 578 Context.IncrementEvaluatedSolutions(evaluations); 566 579 if (VALIDATE && !bestChild.Validate()) throw new ArgumentException("Relinking produced invalid child"); 567 580 if (VALIDATE && Dist(child, p2) > 0) throw new InvalidOperationException("Child is not equal to p2 after relinking"); … … 569 582 } 570 583 571 public static Encodings.PermutationEncoding.Permutation RelinkOpt(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, out double best) { 584 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) { 585 var evaluations = 0; 572 586 var child = (Encodings.PermutationEncoding.Permutation)p1.Clone(); 573 587 … … 646 660 } 647 661 var moveF = eval(child, random); 662 evaluations++; 648 663 if (double.IsNaN(bestChange) || moveF < bestChange) { 649 664 bestChange = moveF; … … 659 674 while (bestQueue.Count > 0) { 660 675 var m = bestQueue.Dequeue(); 661 //Log("Applying opt {0} {1}", m.Item1, m.Item2);662 //Log("{0}", string.Join(" ", child));663 676 Opt(child, m.Item1, m.Item2); 664 //Log("{0}", string.Join(" ", child));665 677 } 666 678 for (var i = 0; i < child.Length; i++) invChild[child[i]] = i; … … 672 684 } while (!double.IsNaN(bestChange)); 673 685 674 //Log("{0}", string.Join(" ", p2)); 686 Context.IncrementEvaluatedSolutions(evaluations); 687 675 688 if (VALIDATE && !bestChild.Validate()) throw new ArgumentException("Relinking produced invalid child"); 676 689 if (VALIDATE && Dist(child, p2) > 0) throw new InvalidOperationException("Child is not equal to p2 after relinking"); … … 681 694 var d = Math.Abs(invP[a] - invP[b]); 682 695 return d == 1 || d == invP.Length - 1; 683 }684 685 private static void Move(Encodings.PermutationEncoding.Permutation child, int from, int to) {686 if (child.PermutationType == PermutationTypes.Absolute) {687 // swap688 Swap(child, from, to);689 } else if (child.PermutationType == PermutationTypes.RelativeDirected) {690 // shift691 Shift(child, from, to);692 } else if (child.PermutationType == PermutationTypes.RelativeUndirected) {693 // opt694 Opt(child, from, to);695 } else throw new ArgumentException(string.Format("Unknown permutation type {0}", child.PermutationType));696 }697 698 private static void Move(PermutationTypes type, bool[] arr, int from, int to) {699 switch (type) {700 case PermutationTypes.Absolute: {701 /*var h = arr[from];702 arr[from] = arr[to];703 arr[to] = h;*/704 arr[from] = false;705 arr[to] = false;706 break;707 }708 case PermutationTypes.RelativeDirected: {709 var original = (bool[])arr.Clone();710 var number = original[from];711 int i = 0; // index in new permutation712 int j = 0; // index in old permutation713 while (i < original.Length) {714 if (j == from) {715 j++;716 }717 if (i == to) {718 arr[i] = number;719 i++;720 }721 if ((i < original.Length) && (j < original.Length)) {722 arr[i] = original[j];723 i++;724 j++;725 }726 }727 break;728 }729 case PermutationTypes.RelativeUndirected: {730 if (from > to) {731 var hu = from;732 from = to;733 to = hu;734 }735 for (int i = 0; i <= (to - from) / 2; i++) { // invert permutation between breakpoints736 var temp = arr[from + i];737 arr[from + i] = arr[to - i];738 arr[to - i] = temp;739 }740 break;741 }742 default:743 throw new ArgumentException(string.Format("Unknown permutation type {0}", type));744 }745 696 } 746 697 -
branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/SingleObjectiveSolutionScope.cs
r14450 r14453 29 29 30 30 namespace HeuristicLab.Algorithms.MemPR { 31 [Item(" MemPRScope", "Scope for a MemPR individual.")]31 [Item("Solution Scope", "Scope for an individual/solution of a single-objective single-encoded problem.")] 32 32 [StorableClass] 33 33 public sealed class SingleObjectiveSolutionScope<T> : NamedItem, ISingleObjectiveSolutionScope<T> where T : class, IItem {
Note: See TracChangeset
for help on using the changeset viewer.