Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
01/05/17 00:32:43 (8 years ago)
Author:
abeham
Message:

#2701:

  • LLE: Added equality comparer
  • MemPR:
    • Added GPR to learn about heuristic performance
    • Changed Breeding to do more exhaustive search on crossover
    • Added Delinking separately to Relinking
    • Rewrote d/relinking for LLE
    • Reduce usage of local search
    • Renamed TabuWalk to AdaptiveWalk
    • Rewrote adaptive walk for binary problems
    • Renamed LLE namespace to Grouping to avoid namespace clashes
File:
1 edited

Legend:

Unmodified
Added
Removed

  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/PermutationMemPR.cs

    r14477 r14544  
    3939  [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms, Priority = 999)]
    4040  public class PermutationMemPR : MemPRAlgorithm<SingleObjectiveBasicProblem<PermutationEncoding>, Encodings.PermutationEncoding.Permutation, PermutationMemPRPopulationContext, PermutationMemPRSolutionContext> {
    41     private const double UncommonBitSubsetMutationProbabilityMagicConst = 0.05;
    42 
    4341#if DEBUG
    4442    private const bool VALIDATE = true;
    … …  
    144142    }
    145143
    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) {
    147145      var wrapper = new EvaluationWrapper<Encodings.PermutationEncoding.Permutation>(Context.Problem, scope);
    148146      var quality = scope.Fitness;
    149147      try {
    150         return TabuWalk(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);
    151149      } finally {
    152150        scope.Fitness = quality;
    … …  
    154152    }
    155153
    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) {
    158155      switch (perm.PermutationType) {
    159156        case PermutationTypes.Absolute:
    160           newSteps = TabuWalkSwap(random, perm, eval, ref quality, maxEvals, subspace);
     157          TabuWalkSwap(random, perm, eval, ref quality, maxEvals, subspace);
    161158          break;
    162159        case PermutationTypes.RelativeDirected:
    163           newSteps = TabuWalkShift(random, perm, eval, ref quality, maxEvals, subspace);
     160          TabuWalkShift(random, perm, eval, ref quality, maxEvals, subspace);
    164161          break;
    165162        case PermutationTypes.RelativeUndirected:
    166           newSteps = TabuWalkOpt(random, perm, eval, ref quality, maxEvals, subspace);
     163          TabuWalkOpt(random, perm, eval, ref quality, maxEvals, subspace);
    167164          break;
    168165        default: throw new ArgumentException(string.Format("Permutation type {0} is not known", perm.PermutationType));
    169166      }
    170167      if (VALIDATE && !perm.Validate()) throw new ArgumentException("TabuWalk produced invalid child");
    171       return newSteps;
    172168    }
    173169
    … …  
    382378    }
    383379
    384     protected override ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> Cross(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p1, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p2, CancellationToken token) {
    385       Encodings.PermutationEncoding.Permutation child = 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;
    386382
    387383      if (p1.Solution.PermutationType == PermutationTypes.Absolute) {
    388         child = CyclicCrossover.Apply(Context.Random, p1.Solution, p2.Solution);
     384        child = CrossAbsolute(p1, p2, token);
    389385      } else if (p1.Solution.PermutationType == PermutationTypes.RelativeDirected) {
    390         child = PartiallyMatchedCrossover.Apply(Context.Random, p1.Solution, p2.Solution);
     386        child = CrossRelativeDirected(p1, p2, token);
    391387      } else if (p1.Solution.PermutationType == PermutationTypes.RelativeUndirected) {
    392         child = EdgeRecombinationCrossover.Apply(Context.Random, p1.Solution, p2.Solution);
     388        child = CrossRelativeUndirected(p1, p2, token);
    393389      } else throw new ArgumentException(string.Format("Unknown permutation type {0}", p1.Solution.PermutationType));
    394390
    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) {
    488471      if (double.IsNaN(a.Fitness)) Evaluate(a, token);
    489472      if (double.IsNaN(b.Fitness)) Evaluate(b, token);
    490473      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) {
    496479      var wrapper = new EvaluationWrapper<Encodings.PermutationEncoding.Permutation>(Problem, betterScope);
    497480      double quality;
Note: See TracChangeset for help on using the changeset viewer.