Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
01/05/17 17:50:03 (7 years ago)
Author:
abeham
Message:

#2701:

  • Added BinaryVectorEqualityComparer (identical to the one in the P3 plugin) to binaryvector plugin
  • Added delinking for absolute coded permutations
  • Some tweaks
File:
1 edited

Legend:

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

    r14544 r14550  
    6161    }
    6262
    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);
    6565    }
    6666
     
    398398      var evaluations = 1;
    399399      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        }
    402408        if (cache.Contains(c)) {
    403409          cacheHits++;
     
    423429      var evaluations = 1;
    424430      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        }
    427439        if (cache.Contains(c)) {
    428440          cacheHits++;
     
    448460      var evaluations = 1;
    449461      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        }
    452470        if (cache.Contains(c)) {
    453471          cacheHits++;
     
    469487
    470488    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));
    480499      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) {
    485504      if (p1.PermutationType != p2.PermutationType) throw new ArgumentException(string.Format("Unequal permutation types {0} and {1}", p1.PermutationType, p2.PermutationType));
    486505      switch (p1.PermutationType) {
    487506        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);
    489508        case PermutationTypes.RelativeDirected:
    490           return RelinkShift(random, p1, p2, eval, out best);
     509          return RelinkShift(random, p1, p2, eval, delink, out best);
    491510        case PermutationTypes.RelativeUndirected:
    492           return RelinkOpt(random, p1, p2, eval, out best);
     511          return RelinkOpt(random, p1, p2, eval, delink, out best);
    493512        default: throw new ArgumentException(string.Format("Unknown permutation type {0}", p1.PermutationType));
    494513      }
     
    506525      var invChild = new int[child.Length];
    507526      for (var i = 0; i < child.Length; i++) invChild[child[i]] = i;
    508 
    509       //Log(string.Join(", ", child));
     527     
    510528      while (options.Count > 0) {
    511529        int bestOption = -1;
     
    534552          invChild[child[idx1]] = idx1;
    535553          invChild[child[idx2]] = idx2;
    536           //Log(string.Join(", ", child));
    537554          if (FitnessComparer.IsBetter(maximization, bestChange, best)) {
    538555            if (Dist(child, p2) > 0) {
     
    556573    }
    557574
    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) {
    559635      var maximization = Context.Problem.Maximization;
    560636      var evaluations = 0;
     
    611687    }
    612688
    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) {
    614690      var maximization = Context.Problem.Maximization;
    615691      var evaluations = 0;
Note: See TracChangeset for help on using the changeset viewer.