- Timestamp:
- 01/05/17 00:32:43 (8 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/PermutationMemPR.cs
r14477 r14544 39 39 [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms, Priority = 999)] 40 40 public class PermutationMemPR : MemPRAlgorithm<SingleObjectiveBasicProblem<PermutationEncoding>, Encodings.PermutationEncoding.Permutation, PermutationMemPRPopulationContext, PermutationMemPRSolutionContext> { 41 private const double UncommonBitSubsetMutationProbabilityMagicConst = 0.05;42 43 41 #if DEBUG 44 42 private const bool VALIDATE = true; … … 144 142 } 145 143 146 protected override int TabuWalk(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> scope, int maxEvals, CancellationToken token, ISolutionSubspace<Encodings.PermutationEncoding.Permutation> subspace = null) {144 protected override void AdaptiveWalk(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> scope, int maxEvals, CancellationToken token, ISolutionSubspace<Encodings.PermutationEncoding.Permutation> subspace = null) { 147 145 var wrapper = new EvaluationWrapper<Encodings.PermutationEncoding.Permutation>(Context.Problem, scope); 148 146 var quality = scope.Fitness; 149 147 try { 150 returnTabuWalk(Context.Random, scope.Solution, wrapper.Evaluate, ref quality, maxEvals, subspace != null ? ((PermutationSolutionSubspace)subspace).Subspace : null);148 TabuWalk(Context.Random, scope.Solution, wrapper.Evaluate, ref quality, maxEvals, subspace != null ? ((PermutationSolutionSubspace)subspace).Subspace : null); 151 149 } finally { 152 150 scope.Fitness = quality; … … 154 152 } 155 153 156 public int TabuWalk(IRandom random, Encodings.PermutationEncoding.Permutation perm, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, ref double quality, int maxEvals = int.MaxValue, bool[,] subspace = null) { 157 int newSteps = 0; 154 public void TabuWalk(IRandom random, Encodings.PermutationEncoding.Permutation perm, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, ref double quality, int maxEvals = int.MaxValue, bool[,] subspace = null) { 158 155 switch (perm.PermutationType) { 159 156 case PermutationTypes.Absolute: 160 newSteps =TabuWalkSwap(random, perm, eval, ref quality, maxEvals, subspace);157 TabuWalkSwap(random, perm, eval, ref quality, maxEvals, subspace); 161 158 break; 162 159 case PermutationTypes.RelativeDirected: 163 newSteps =TabuWalkShift(random, perm, eval, ref quality, maxEvals, subspace);160 TabuWalkShift(random, perm, eval, ref quality, maxEvals, subspace); 164 161 break; 165 162 case PermutationTypes.RelativeUndirected: 166 newSteps =TabuWalkOpt(random, perm, eval, ref quality, maxEvals, subspace);163 TabuWalkOpt(random, perm, eval, ref quality, maxEvals, subspace); 167 164 break; 168 165 default: throw new ArgumentException(string.Format("Permutation type {0} is not known", perm.PermutationType)); 169 166 } 170 167 if (VALIDATE && !perm.Validate()) throw new ArgumentException("TabuWalk produced invalid child"); 171 return newSteps;172 168 } 173 169 … … 382 378 } 383 379 384 protected override ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> Cross(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p1, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p2, CancellationToken token) {385 Encodings.PermutationEncoding.Permutationchild = null;380 protected override ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> Breed(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p1, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p2, CancellationToken token) { 381 ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> child = null; 386 382 387 383 if (p1.Solution.PermutationType == PermutationTypes.Absolute) { 388 child = C yclicCrossover.Apply(Context.Random, p1.Solution, p2.Solution);384 child = CrossAbsolute(p1, p2, token); 389 385 } else if (p1.Solution.PermutationType == PermutationTypes.RelativeDirected) { 390 child = PartiallyMatchedCrossover.Apply(Context.Random, p1.Solution, p2.Solution);386 child = CrossRelativeDirected(p1, p2, token); 391 387 } else if (p1.Solution.PermutationType == PermutationTypes.RelativeUndirected) { 392 child = EdgeRecombinationCrossover.Apply(Context.Random, p1.Solution, p2.Solution);388 child = CrossRelativeUndirected(p1, p2, token); 393 389 } else throw new ArgumentException(string.Format("Unknown permutation type {0}", p1.Solution.PermutationType)); 394 390 395 if (VALIDATE && !child.Validate()) throw new ArgumentException("Cross produced invalid child"); 396 return ToScope(child); 397 } 398 399 protected override void Mutate(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> offspring, CancellationToken token, ISolutionSubspace<Encodings.PermutationEncoding.Permutation> subspace = null) { 400 Mutate(Context.Random, offspring.Solution, UncommonBitSubsetMutationProbabilityMagicConst, subspace != null ? ((PermutationSolutionSubspace)subspace).Subspace : null); 401 } 402 403 public static void Mutate(IRandom random, Encodings.PermutationEncoding.Permutation perm, double p, bool[,] subspace) { 404 switch (perm.PermutationType) { 405 case PermutationTypes.Absolute: 406 MutateSwap(random, perm, p, subspace); 407 break; 408 case PermutationTypes.RelativeDirected: 409 MutateShift(random, perm, p, subspace); 410 break; 411 case PermutationTypes.RelativeUndirected: 412 MutateOpt(random, perm, p, subspace); 413 break; 414 default: throw new ArgumentException(string.Format("Permutation type {0} is not known", perm.PermutationType)); 415 } 416 if (VALIDATE && !perm.Validate()) throw new ArgumentException("Mutate produced invalid child"); 417 } 418 419 public static void MutateSwap(IRandom random, Encodings.PermutationEncoding.Permutation perm, double p, bool[,] subspace) { 420 //Log("BEFOR: {0}", string.Join(", ", lle)); 421 // The goal of the mutation is to disrupt crossover when it's in an agreeing position 422 var options = new List<int>(Enumerable.Range(0, perm.Length).Where(x => subspace == null || !subspace[x, 0])); 423 if (options.Count < 1) return; 424 425 for (var i = options.Count - 1; i > 0; i--) { 426 if (random.NextDouble() < p) { 427 var j = random.Next(0, i); 428 var h = perm[options[i]]; 429 perm[options[i]] = perm[options[j]]; 430 perm[options[j]] = h; 431 if (subspace != null) { 432 subspace[options[i], 0] = true; 433 subspace[options[j], 0] = true; 434 } 435 } 436 } 437 } 438 439 public static void MutateShift(IRandom random, Encodings.PermutationEncoding.Permutation perm, double p, bool[,] subspace) { 440 //Log("BEFOR: {0}", string.Join(", ", lle)); 441 // The goal of the mutation is to disrupt crossover when it's in an agreeing position 442 foreach (var shift in ExhaustiveInsertionMoveGenerator.Generate(perm).Shuffle(random)) { 443 var prev1 = shift.Index1 - 1; 444 var next1 = (shift.Index1 + 1) % perm.Length; 445 if (prev1 < 0) prev1 += perm.Length; 446 var prev3 = shift.Index3 - 1; 447 var next3 = (shift.Index3 + 1) % perm.Length; 448 if (prev3 < 0) prev3 += perm.Length; 449 if (subspace == null || !(subspace[perm[prev1], perm[shift.Index1]] && subspace[perm[shift.Index1], perm[next1]] 450 && subspace[perm[prev3], perm[shift.Index3]] && subspace[perm[shift.Index3], perm[next3]])) { 451 if (random.NextDouble() < p) { 452 if (subspace != null) { 453 subspace[perm[prev1], perm[shift.Index1]] = true; 454 subspace[perm[shift.Index1], perm[next1]] = true; 455 subspace[perm[prev3], perm[shift.Index3]] = true; 456 subspace[perm[shift.Index3], perm[next3]] = true; 457 } 458 TranslocationManipulator.Apply(perm, shift.Index1, shift.Index2, shift.Index3); 459 return; 460 } 461 } 462 } 463 } 464 465 public static void MutateOpt(IRandom random, Encodings.PermutationEncoding.Permutation perm, double p, bool[,] subspace) { 466 //Log("BEFOR: {0}", string.Join(", ", lle)); 467 // The goal of the mutation is to disrupt crossover when it's in an agreeing position 468 foreach (var opt in ExhaustiveInversionMoveGenerator.Generate(perm).Shuffle(random)) { 469 var prev = opt.Index1 - 1; 470 var next = (opt.Index2 + 1) % perm.Length; 471 if (prev < 0) prev += perm.Length; 472 if (subspace == null || !(subspace[perm[prev], perm[opt.Index1]] && subspace[perm[opt.Index2], perm[next]])) { 473 if (random.NextDouble() < p) { 474 if (subspace != null) { 475 subspace[perm[prev], perm[opt.Index1]] = true; 476 subspace[perm[opt.Index1], perm[prev]] = true; 477 subspace[perm[opt.Index2], perm[next]] = true; 478 subspace[perm[next], perm[opt.Index2]] = true; 479 } 480 InversionManipulator.Apply(perm, opt.Index1, opt.Index2); 481 return; 482 } 483 } 484 } 485 } 486 487 protected override ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> Relink(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> a, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> b, CancellationToken token) { 391 if (VALIDATE && !child.Solution.Validate()) throw new ArgumentException("Cross produced invalid child"); 392 return child; 393 } 394 395 private ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> CrossAbsolute(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p1, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p2, CancellationToken token) { 396 var cache = new HashSet<Encodings.PermutationEncoding.Permutation>(new PermutationEqualityComparer()); 397 var cacheHits = 0; 398 var evaluations = 1; 399 ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> offspring = null; 400 for (; evaluations <= Context.LocalSearchEvaluations; evaluations++) { 401 var c = CyclicCrossover2.Apply(Context.Random, p1.Solution, p2.Solution); 402 if (cache.Contains(c)) { 403 cacheHits++; 404 if (cacheHits > 10) break; 405 continue; 406 } 407 var probe = ToScope(c); 408 Evaluate(probe, token); 409 cache.Add(c); 410 if (offspring == null || Context.IsBetter(probe, offspring)) { 411 offspring = probe; 412 if (Context.IsBetter(offspring, p1) && Context.IsBetter(offspring, p2)) 413 break; 414 } 415 } 416 Context.IncrementEvaluatedSolutions(evaluations-1); 417 return offspring; 418 } 419 420 private ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> CrossRelativeDirected(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p1, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p2, CancellationToken token) { 421 var cache = new HashSet<Encodings.PermutationEncoding.Permutation>(new PermutationEqualityComparer()); 422 var cacheHits = 0; 423 var evaluations = 1; 424 ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> offspring = null; 425 for (; evaluations <= Context.LocalSearchEvaluations; evaluations++) { 426 var c = PartiallyMatchedCrossover.Apply(Context.Random, p1.Solution, p2.Solution); 427 if (cache.Contains(c)) { 428 cacheHits++; 429 if (cacheHits > 10) break; 430 continue; 431 } 432 var probe = ToScope(c); 433 Evaluate(probe, token); 434 cache.Add(c); 435 if (offspring == null || Context.IsBetter(probe, offspring)) { 436 offspring = probe; 437 if (Context.IsBetter(offspring, p1) && Context.IsBetter(offspring, p2)) 438 break; 439 } 440 } 441 Context.IncrementEvaluatedSolutions(evaluations-1); 442 return offspring; 443 } 444 445 private ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> CrossRelativeUndirected(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p1, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p2, CancellationToken token) { 446 var cache = new HashSet<Encodings.PermutationEncoding.Permutation>(new PermutationEqualityComparer()); 447 var cacheHits = 0; 448 var evaluations = 1; 449 ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> offspring = null; 450 for (; evaluations <= Context.LocalSearchEvaluations; evaluations++) { 451 var c = EdgeRecombinationCrossover.Apply(Context.Random, p1.Solution, p2.Solution); 452 if (cache.Contains(c)) { 453 cacheHits++; 454 if (cacheHits > 10) break; 455 continue; 456 } 457 var probe = ToScope(c); 458 Evaluate(probe, token); 459 cache.Add(c); 460 if (offspring == null || Context.IsBetter(probe, offspring)) { 461 offspring = probe; 462 if (Context.IsBetter(offspring, p1) && Context.IsBetter(offspring, p2)) 463 break; 464 } 465 } 466 Context.IncrementEvaluatedSolutions(evaluations-1); 467 return offspring; 468 } 469 470 protected override ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> Link(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> a, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> b, CancellationToken token, bool delink = false) { 488 471 if (double.IsNaN(a.Fitness)) Evaluate(a, token); 489 472 if (double.IsNaN(b.Fitness)) Evaluate(b, token); 490 473 if (Context.Random.NextDouble() < 0.5) 491 return IsBetter(a, b) ? Relink(a, b, token, false) : Relink(b, a, token, true);492 else return IsBetter(a, b) ? Relink(b, a, token, true) : Relink(a, b, token, false);493 } 494 495 protected virtual ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> Relink(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> betterScope, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> worseScope, CancellationToken token , bool fromWorseToBetter) {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) { 496 479 var wrapper = new EvaluationWrapper<Encodings.PermutationEncoding.Permutation>(Problem, betterScope); 497 480 double quality;
Note: See TracChangeset
for help on using the changeset viewer.