Changeset 14550 for branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/PermutationMemPR.cs
- Timestamp:
- 01/05/17 17:50:03 (7 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
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;
Note: See TracChangeset
for help on using the changeset viewer.