Changeset 14453 for branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/PermutationMemPR.cs
- Timestamp:
- 12/05/16 12:27:19 (8 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
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
Note: See TracChangeset
for help on using the changeset viewer.