Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
12/06/16 15:07:45 (8 years ago)
Author:
abeham
Message:

#2701:

  • Using evaluated solutions from HC as max evaluations for tabu walking in MemPR
  • Fixed some bugs in MemPR (permutation) regarding subspace calculation (true means okay, false means no)
  • Fixed bug in TSP
Location:
branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3
Files:
8 edited

Legend:

Unmodified
Added
Removed

  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Binary/BinaryMemPR.cs

    r14453 r14456  
    9797    }
    9898
    99     protected override void TabuWalk(ISingleObjectiveSolutionScope<BinaryVector> scope, int steps, CancellationToken token, ISolutionSubspace<BinaryVector> subspace = null) {
     99    protected override int TabuWalk(ISingleObjectiveSolutionScope<BinaryVector> scope, int maxEvals, CancellationToken token, ISolutionSubspace<BinaryVector> subspace = null) {
    100100      var evaluations = 0;
    101101      var subset = subspace != null ? ((BinarySolutionSubspace)subspace).Subspace : null;
    … …  
    111111      for (var i = 0; i < N; i++) tabu[i] = Tuple.Create(current[i] ? double.NaN : currentScope.Fitness, !current[i] ? double.NaN : currentScope.Fitness);
    112112      var subN = subset != null ? subset.Count(x => x) : N;
    113       if (subN == 0) return;
     113      if (subN == 0) return 0;
    114114      var order = Enumerable.Range(0, N).Where(x => subset == null || subset[x]).Shuffle(Context.Random).ToArray();
    115115
    116       for (var iter = 0; iter < steps; iter++) {
     116      var steps = 0;
     117      var stepsUntilBestOfWalk = 0;
     118      for (var iter = 0; iter < int.MaxValue; iter++) {
    117119        var allTabu = true;
    118120        var bestOfTheRestF = double.NaN;
    … …  
    130132          if (IsBetter(after, before) && (bestOfTheWalk == null || IsBetter(after, bestOfTheWalk.Fitness))) {
    131133            bestOfTheWalk = (SingleObjectiveSolutionScope<BinaryVector>)currentScope.Clone();
     134            stepsUntilBestOfWalk = steps;
    132135          }
    133136
    … …  
    138141          if (IsBetter(after, before) && !isTabu) {
    139142            improved = true;
     143            steps++;
    140144            tabu[idx] = current[idx] ? Tuple.Create(after, tabu[idx].Item2) : Tuple.Create(tabu[idx].Item1, after);
    141145          } else { // undo the move
    … …  
    147151            currentScope.Fitness = before;
    148152          }
     153          if (evaluations >= maxEvals) break;
    149154        }
    150155        if (!allTabu && !improved) {
    … …  
    153158          tabu[bestOfTheRest] = current[bestOfTheRest] ? Tuple.Create(better, tabu[bestOfTheRest].Item2) : Tuple.Create(tabu[bestOfTheRest].Item1, better);
    154159          currentScope.Fitness = bestOfTheRestF;
     160          steps++;
    155161        } else if (allTabu) break;
     162        if (evaluations >= maxEvals) break;
    156163      }
    157164
    158165      Context.IncrementEvaluatedSolutions(evaluations);
    159166      scope.Adopt(bestOfTheWalk ?? currentScope);
     167      return stepsUntilBestOfWalk;
    160168    }
    161169

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

    r14454 r14456  
    231231          Analyze(token);
    232232          token.ThrowIfCancellationRequested();
     233          if (Terminate()) return;
    233234        }
    234235        Context.HcSteps /= 2;
    … …  
    314315        Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
    315316      else ((IntValue)res.Value).Value = Context.Iterations;
     317      if (!Results.TryGetValue("HcSteps", out res))
     318        Results.Add(new Result("HcSteps", new IntValue(Context.HcSteps)));
     319      else ((IntValue)res.Value).Value = Context.HcSteps;
    316320      if (!Results.TryGetValue("ByBreeding", out res))
    317321        Results.Add(new Result("ByBreeding", new IntValue(Context.ByBreeding)));
    … …  
    491495      Context.HillclimbingStat.Add(Tuple.Create(before, after));
    492496      Context.IncrementEvaluatedSolutions(lscontext.EvaluatedSolutions);
    493       return lscontext.Iterations;
     497      return lscontext.EvaluatedSolutions;
    494498    }
    495499
    … …  
    501505      var before = scope.Fitness;
    502506      var newScope = (ISingleObjectiveSolutionScope<TSolution>)scope.Clone();
    503       TabuWalk(newScope, steps, token, subspace);
     507      var newSteps = TabuWalk(newScope, steps, token, subspace);
    504508      Context.TabuwalkingStat.Add(Tuple.Create(before, newScope.Fitness));
     509      //Context.HcSteps = (int)Math.Ceiling(Context.HcSteps * (1.0 + Context.TabuwalkingStat.Count) / (2.0 + Context.TabuwalkingStat.Count) + newSteps / (2.0 + Context.TabuwalkingStat.Count));
    505510      if (IsBetter(newScope, scope) || (newScope.Fitness == scope.Fitness && Dist(newScope, scope) > 0))
    506511        scope.Adopt(newScope);
    507512    }
    508     protected abstract void TabuWalk(ISingleObjectiveSolutionScope<TSolution> scope, int steps, CancellationToken token, ISolutionSubspace<TSolution> subspace = null);
     513    protected abstract int TabuWalk(ISingleObjectiveSolutionScope<TSolution> scope, int maxEvals, CancellationToken token, ISolutionSubspace<TSolution> subspace = null);
    509514    protected virtual void TabuClimb(ISingleObjectiveSolutionScope<TSolution> scope, int steps, CancellationToken token, ISolutionSubspace<TSolution> subspace = null) {
    510515      if (double.IsNaN(scope.Fitness)) {
    … …  
    514519      var before = scope.Fitness;
    515520      var newScope = (ISingleObjectiveSolutionScope<TSolution>)scope.Clone();
    516       TabuWalk(newScope, steps, token, subspace);
     521      var newSteps = TabuWalk(newScope, steps, token, subspace);
    517522      Context.TabuwalkingStat.Add(Tuple.Create(before, newScope.Fitness));
     523      //Context.HcSteps = (int)Math.Ceiling(Context.HcSteps * (1.0 + Context.TabuwalkingStat.Count) / (2.0 + Context.TabuwalkingStat.Count) + newSteps / (2.0 + Context.TabuwalkingStat.Count));
    518524      if (IsBetter(newScope, scope) || (newScope.Fitness == scope.Fitness && Dist(newScope, scope) > 0))
    519525        scope.Adopt(newScope);
    … …  
    557563        || Context.Population.Any(p => IsBetter(offspring, p))) return offspring;
    558564
    559       if (IsBetter(offspring.Fitness, Context.BestQuality))
    560         HillClimb(offspring, token); // perform hillclimb in full solution space
    561       else if (HillclimbingSuited(offspring))
     565      if (HillclimbingSuited(offspring))
    562566        HillClimb(offspring, token, subspace); // perform hillclimb in the solution sub-space
    563567      return offspring;
    … …  
    589593      if (dist1 > 0 && dist2 > 0) {
    590594        var subspace = CalculateSubspace(new[] { a.Solution, b.Solution }, inverse: true);
    591         if (IsBetter(child.Fitness, Context.BestQuality))
    592           HillClimb(child, token); // perform hillclimb in full solution space
    593         else if (HillclimbingSuited(child)) {
     595        if (HillclimbingSuited(child)) {
    594596          HillClimb(child, token, subspace); // perform hillclimb in solution sub-space
    595597        }

  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/StaticAPI/Exhaustive.cs

    r14450 r14456  
    3535    public static Tuple<int, int> HillClimb(IRandom random, Encodings.PermutationEncoding.Permutation perm,
    3636      ref double quality, bool maximization, Func<Encodings.PermutationEncoding.Permutation, double> eval,
    37       CancellationToken token, bool[,] noTouch = null) {
     37      CancellationToken token, bool[,] subspace = null) {
    3838      if (double.IsNaN(quality)) quality = eval(perm);
    3939      Tuple<int, int> changes;
    4040      switch (perm.PermutationType) {
    4141        case PermutationTypes.Absolute:
    42           changes = ExhaustiveSwap2.HillClimb(random, perm, ref quality, maximization, eval, token, noTouch);
     42          changes = ExhaustiveSwap2.HillClimb(random, perm, ref quality, maximization, eval, token, subspace);
    4343          break;
    4444        case PermutationTypes.RelativeDirected:
    45           changes = Exhaustive1Shift.HillClimb(random, perm, ref quality, maximization, eval, token, noTouch);
     45          changes = Exhaustive1Shift.HillClimb(random, perm, ref quality, maximization, eval, token, subspace);
    4646          break;
    4747        case PermutationTypes.RelativeUndirected:
    48           changes = Exhaustive2Opt.HillClimb(random, perm, ref quality, maximization, eval, token, noTouch);
     48          changes = Exhaustive2Opt.HillClimb(random, perm, ref quality, maximization, eval, token, subspace);
    4949          break;
    5050        default: throw new ArgumentException(string.Format("Permutation type {0} is not known", perm.PermutationType));

  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/StaticAPI/Exhaustive1Shift.cs

    r14453 r14456  
    2121
    2222using System;
     23using System.Linq;
    2324using System.Threading;
    2425using HeuristicLab.Algorithms.MemPR.Util;
    2526using HeuristicLab.Core;
    2627using HeuristicLab.Encodings.PermutationEncoding;
     28using HeuristicLab.Random;
    2729
    2830namespace HeuristicLab.Algorithms.MemPR.Permutation.LocalSearch {
    … …  
    3032    public static Tuple<int, int> HillClimb(IRandom random, Encodings.PermutationEncoding.Permutation perm,
    3133      ref double quality, bool maximization, Func<Encodings.PermutationEncoding.Permutation, double> eval,
    32       CancellationToken token, bool[,] noTouch = null) {
     34      CancellationToken token, bool[,] subspace = null) {
     35      var evaluations = 0;
    3336      var current = perm;
    34       if (double.IsNaN(quality)) quality = eval(current);
     37      if (double.IsNaN(quality)) {
     38        quality = eval(current);
     39        evaluations++;
     40      }
    3541      TranslocationMove lastSuccessMove = null;
    36       int steps = 0, evaluations = 0;
     42      var steps = 0;
     43      var neighborhood = ExhaustiveInsertionMoveGenerator.Generate(current).Shuffle(random).ToList();
    3744      while (true) {
    38         foreach (var shift in ExhaustiveInsertionMoveGenerator.Generate(current)) {
     45        foreach (var shift in neighborhood) {
    3946          if (lastSuccessMove != null && shift.Index1 == lastSuccessMove.Index1 && shift.Index2 == lastSuccessMove.Index2 && shift.Index3 == lastSuccessMove.Index3) {
    4047            // been there, done that
    … …  
    4855          var next3 = (shift.Index3 + 1) % current.Length;
    4956          if (prev3 < 0) prev3 += current.Length;
    50           if (noTouch != null && ((noTouch[current[prev1], current[shift.Index1]] || noTouch[current[shift.Index1], current[next1]]
    51                                 || noTouch[current[prev3], current[shift.Index3]] || noTouch[current[shift.Index3], current[next3]])))
     57          if (subspace != null && !(subspace[current[prev1], current[shift.Index1]] && subspace[current[shift.Index1], current[next1]]
     58                                && subspace[current[prev3], current[shift.Index3]] && subspace[current[shift.Index3], current[next3]]))
    5259            continue;
    5360          TranslocationManipulator.Apply(current, shift.Index1, shift.Index2, shift.Index3);

  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/StaticAPI/Exhaustive2Opt.cs

    r14453 r14456  
    2121
    2222using System;
     23using System.Linq;
    2324using System.Threading;
    2425using HeuristicLab.Algorithms.MemPR.Util;
    2526using HeuristicLab.Core;
    2627using HeuristicLab.Encodings.PermutationEncoding;
     28using HeuristicLab.Random;
    2729
    2830namespace HeuristicLab.Algorithms.MemPR.Permutation.LocalSearch {
    … …  
    3032    public static Tuple<int, int> HillClimb(IRandom random, Encodings.PermutationEncoding.Permutation perm,
    3133      ref double quality, bool maximization, Func<Encodings.PermutationEncoding.Permutation, double> eval,
    32       CancellationToken token, bool[,] noTouch = null) {
     34      CancellationToken token, bool[,] subspace = null) {
     35      var evaluations = 0;
    3336      var current = perm;
    34       if (double.IsNaN(quality)) quality = eval(current);
     37      if (double.IsNaN(quality)) {
     38        quality = eval(current);
     39        evaluations++;
     40      }
    3541      InversionMove lastSuccessMove = null;
    36       int steps = 0, evaluations = 0;
     42      var steps = 0;
     43      var neighborhood = ExhaustiveInversionMoveGenerator.Generate(current).Shuffle(random).ToList();
    3744      while (true) {
    38         foreach (var opt in ExhaustiveInversionMoveGenerator.Generate(current)) {
     45        foreach (var opt in neighborhood) {
    3946          if (lastSuccessMove != null && opt.Index1 == lastSuccessMove.Index1 && opt.Index2 == lastSuccessMove.Index2) {
    4047            // been there, done that
    … …  
    4552          var next = (opt.Index2 + 1) % current.Length;
    4653          if (prev < 0) prev += current.Length;
    47           if (noTouch != null && ((noTouch[current[prev], current[opt.Index1]]) || (noTouch[current[opt.Index2], current[next]])))
     54          if (subspace != null && !(subspace[current[prev], current[opt.Index1]] && subspace[current[opt.Index2], current[next]]))
    4855            continue;
    4956

  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/StaticAPI/ExhaustiveSwap2.cs

    r14453 r14456  
    2121
    2222using System;
     23using System.Linq;
    2324using System.Threading;
    2425using HeuristicLab.Algorithms.MemPR.Util;
    2526using HeuristicLab.Core;
    2627using HeuristicLab.Encodings.PermutationEncoding;
     28using HeuristicLab.Random;
    2729
    2830namespace HeuristicLab.Algorithms.MemPR.Permutation.LocalSearch {
    … …  
    3032    public static Tuple<int, int> HillClimb(IRandom random, Encodings.PermutationEncoding.Permutation perm,
    3133      ref double quality, bool maximization, Func<Encodings.PermutationEncoding.Permutation, double> eval,
    32       CancellationToken token, bool[,] noTouch = null) {
     34      CancellationToken token, bool[,] subspace = null) {
     35      var evaluations = 0;
    3336      var current = perm;
    34       if (double.IsNaN(quality)) quality = eval(current);
     37      if (double.IsNaN(quality)) {
     38        quality = eval(current);
     39        evaluations++;
     40      }
    3541      Swap2Move lastSuccessMove = null;
    36       int steps = 0, evaluations = 0;
     42      var steps = 0;
     43      var neighborhood = ExhaustiveSwap2MoveGenerator.Generate(current).Shuffle(random).ToList();
    3744      while (true) {
    38         foreach (var swap in ExhaustiveSwap2MoveGenerator.Generate(current)) {
     45        foreach (var swap in neighborhood) {
    3946          if (lastSuccessMove != null && swap.Index1 == lastSuccessMove.Index1 && swap.Index2 == lastSuccessMove.Index2) {
    4047            // been there, done that
    … …  
    4249            break;
    4350          }
    44           if (noTouch != null && (noTouch[swap.Index1, 0] || noTouch[swap.Index2, 0]))
     51          if (subspace != null && !(subspace[swap.Index1, 0] && subspace[swap.Index2, 0]))
    4552            continue;
    4653

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

    r14453 r14456  
    144144    }
    145145
    146     protected override void TabuWalk(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> scope, int steps, CancellationToken token, ISolutionSubspace<Encodings.PermutationEncoding.Permutation> subspace = null) {
     146    protected override int TabuWalk(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> scope, int maxEvals, CancellationToken token, ISolutionSubspace<Encodings.PermutationEncoding.Permutation> subspace = null) {
    147147      var wrapper = new EvaluationWrapper<Encodings.PermutationEncoding.Permutation>(Context.Problem, scope);
    148148      var quality = scope.Fitness;
    149149      try {
    150         TabuWalk(Context.Random, scope.Solution, wrapper.Evaluate, ref quality, Context.HcSteps, subspace != null ? ((PermutationSolutionSubspace)subspace).Subspace : null);
     150        return TabuWalk(Context.Random, scope.Solution, wrapper.Evaluate, ref quality, maxEvals, subspace != null ? ((PermutationSolutionSubspace)subspace).Subspace : null);
    151151      } finally {
    152152        scope.Fitness = quality;
    … …  
    154154    }
    155155
    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) {
     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;
    157158      switch (perm.PermutationType) {
    158159        case PermutationTypes.Absolute:
    159           TabuWalkSwap(random, perm, eval, ref quality, maxIterations, noTouch);
     160          newSteps = TabuWalkSwap(random, perm, eval, ref quality, maxEvals, subspace);
    160161          break;
    161162        case PermutationTypes.RelativeDirected:
    162           TabuWalkShift(random, perm, eval, ref quality, maxIterations, noTouch);
     163          newSteps = TabuWalkShift(random, perm, eval, ref quality, maxEvals, subspace);
    163164          break;
    164165        case PermutationTypes.RelativeUndirected:
    165           TabuWalkOpt(random, perm, eval, ref quality, maxIterations, noTouch);
     166          newSteps = TabuWalkOpt(random, perm, eval, ref quality, maxEvals, subspace);
    166167          break;
    167168        default: throw new ArgumentException(string.Format("Permutation type {0} is not known", perm.PermutationType));
    168169      }
    169170      if (VALIDATE && !perm.Validate()) throw new ArgumentException("TabuWalk produced invalid child");
    170     }
    171 
    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) {
     171      return newSteps;
     172    }
     173
     174    public int TabuWalkSwap(IRandom random, Encodings.PermutationEncoding.Permutation perm, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, ref double quality, int maxEvals = int.MaxValue, bool[,] subspace = null) {
    173175      var evaluations = 0;
     176      var maximization = Context.Problem.Maximization;
    174177      if (double.IsNaN(quality)) {
    175178        quality = eval(perm, random);
    … …  
    189192      }
    190193
    191       for (var iter = 0; iter < maxIterations; iter++) {
     194      var steps = 0;
     195      var stepsUntilBestOfWalk = 0;
     196      for (var iter = 0; iter < int.MaxValue; iter++) {
    192197        var allTabu = true;
    193198        var bestOfTheRestF = double.NaN;
    … …  
    195200        var improved = false;
    196201        foreach (var swap in ExhaustiveSwap2MoveGenerator.Generate(current).Shuffle(random)) {
    197           if (noTouch != null && (noTouch[swap.Index1, 0] || noTouch[swap.Index2, 0]))
     202          if (subspace != null && !(subspace[swap.Index1, 0] && subspace[swap.Index2, 0]))
    198203            continue;
    199204
    … …  
    203208          var q = eval(current, random);
    204209          evaluations++;
    205           if (q < quality) {
     210          if (FitnessComparer.IsBetter(maximization, q, quality)) {
    206211            overallImprovement = true;
    207212            quality = q;
    … …  
    209214          }
    210215          // check if it would not be an improvement to swap these into their positions
    211           var isTabu = q >= tabu[swap.Index1, current[swap.Index1]] && q >= tabu[swap.Index2, current[swap.Index2]];
     216          var isTabu = !FitnessComparer.IsBetter(maximization, q, tabu[swap.Index1, current[swap.Index1]])
     217                    && !FitnessComparer.IsBetter(maximization, q, tabu[swap.Index2, current[swap.Index2]]);
    212218          if (!isTabu) allTabu = false;
    213           if (q < currentF && !isTabu) {
    214             if (double.IsNaN(bestOfTheWalkF) || bestOfTheWalkF > q) {
     219          if (FitnessComparer.IsBetter(maximization, q, currentF) && !isTabu) {
     220            if (FitnessComparer.IsBetter(maximization, q, bestOfTheWalkF)) {
    215221              bestOfTheWalk = (Encodings.PermutationEncoding.Permutation)current.Clone();
    216222              bestOfTheWalkF = q;
    217             }
    218 
     223              stepsUntilBestOfWalk = steps;
     224            }
     225            steps++;
    219226            improved = true;
    220227            // perform the move
    221228            currentF = q;
    222229            // mark that to move them to their previous position requires to make an improvement
    223             tabu[swap.Index1, current[swap.Index2]] = Math.Min(q, tabu[swap.Index1, current[swap.Index2]]);
    224             //LogAlways("Making Tabu [{0},{1}] = {2}", swap.Index1, current[swap.Index2], tabu[swap.Index1, current[swap.Index2]]);
    225             tabu[swap.Index2, current[swap.Index1]] = Math.Min(q, tabu[swap.Index2, current[swap.Index1]]);
    226             //LogAlways("Making Tabu [{0},{1}] = {2}", swap.Index2, current[swap.Index1], tabu[swap.Index2, current[swap.Index1]]);
     230            tabu[swap.Index1, current[swap.Index2]] = maximization ? Math.Max(q, tabu[swap.Index1, current[swap.Index2]])
     231                                                                   : Math.Min(q, tabu[swap.Index1, current[swap.Index2]]);
     232            tabu[swap.Index2, current[swap.Index1]] = maximization ? Math.Max(q, tabu[swap.Index2, current[swap.Index1]])
     233                                                                   : Math.Min(q, tabu[swap.Index2, current[swap.Index1]]);
    227234          } else { // undo the move
    228             if (!isTabu && (double.IsNaN(bestOfTheRestF) || q < bestOfTheRestF)) {
     235            if (!isTabu && FitnessComparer.IsBetter(maximization, q, bestOfTheRestF)) {
    229236              bestOfTheRest = swap;
    230237              bestOfTheRestF = q;
    … …  
    233240            current[swap.Index1] = h;
    234241          }
    235         }
    236         if (!allTabu && !improved) {
    237           tabu[bestOfTheRest.Index1, current[bestOfTheRest.Index1]] = Math.Min(currentF, tabu[bestOfTheRest.Index1, current[bestOfTheRest.Index1]]);
    238           tabu[bestOfTheRest.Index2, current[bestOfTheRest.Index2]] = Math.Min(currentF, tabu[bestOfTheRest.Index2, current[bestOfTheRest.Index2]]);
     242          if (evaluations >= maxEvals) break;
     243        }
     244        if (!allTabu && !improved && bestOfTheRest != null) {
     245          tabu[bestOfTheRest.Index1, current[bestOfTheRest.Index1]] = maximization ? Math.Max(currentF, tabu[bestOfTheRest.Index1, current[bestOfTheRest.Index1]])
     246                                                                                   : Math.Min(currentF, tabu[bestOfTheRest.Index1, current[bestOfTheRest.Index1]]);
     247          tabu[bestOfTheRest.Index2, current[bestOfTheRest.Index2]] = maximization ? Math.Max(currentF, tabu[bestOfTheRest.Index2, current[bestOfTheRest.Index2]])
     248                                                                                   : Math.Min(currentF, tabu[bestOfTheRest.Index2, current[bestOfTheRest.Index2]]);
    239249
    240250          var h = current[bestOfTheRest.Index1];
    … …  
    243253
    244254          currentF = bestOfTheRestF;
     255          steps++;
    245256        } else if (allTabu) break;
     257        if (evaluations >= maxEvals) break;
    246258      }
    247259      Context.IncrementEvaluatedSolutions(evaluations);
    … …  
    250262        for (var i = 0; i < current.Length; i++) perm[i] = bestOfTheWalk[i];
    251263      }
    252     }
    253 
    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) {
    255       return;
    256     }
    257 
    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) {
     264      return stepsUntilBestOfWalk;
     265    }
     266
     267    public int TabuWalkShift(IRandom random, Encodings.PermutationEncoding.Permutation perm, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, ref double quality, int maxEvals = int.MaxValue, bool[,] subspace = null) {
     268      return 0;
     269    }
     270
     271    public int TabuWalkOpt(IRandom random, Encodings.PermutationEncoding.Permutation perm, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, ref double quality, int maxEvals = int.MaxValue, bool[,] subspace = null) {
     272      var maximization = Context.Problem.Maximization;
    259273      var evaluations = 0;
    260274      if (double.IsNaN(quality)) {
    … …  
    263277      }
    264278      Encodings.PermutationEncoding.Permutation bestOfTheWalk = null;
    265       double bestOfTheWalkF = double.NaN;
     279      var bestOfTheWalkF = double.NaN;
    266280      var current = (Encodings.PermutationEncoding.Permutation)perm.Clone();
    267281      var currentF = quality;
    268282      var overallImprovement = false;
    269       //Console.WriteLine("Current    {0}", string.Join(", ", current));
    270283      var tabu = new double[current.Length, current.Length];
    271284      for (var i = 0; i < current.Length; i++) {
    … …  
    277290      }
    278291
    279       for (var iter = 0; iter < maxIterations; iter++) {
     292      var steps = 0;
     293      var stepsUntilBestOfWalk = 0;
     294      for (var iter = 0; iter < int.MaxValue; iter++) {
    280295        var allTabu = true;
    281296        var bestOfTheRestF = double.NaN;
    … …  
    287302          var next = (opt.Index2 + 1) % current.Length;
    288303          if (prev < 0) prev += current.Length;
    289           if (noTouch != null && ((noTouch[current[prev], current[opt.Index1]]) || (noTouch[current[opt.Index2], current[next]])))
     304          if (subspace != null && !(subspace[current[prev], current[opt.Index1]] && subspace[current[opt.Index2], current[next]]))
    290305            continue;
    291306
    … …  
    294309          var q = eval(current, random);
    295310          evaluations++;
    296           if (q < quality) {
     311          if (FitnessComparer.IsBetter(maximization, q, quality)) {
    297312            overallImprovement = true;
    298313            quality = q;
    … …  
    300315          }
    301316          // check if it would not be an improvement to opt these into their positions
    302           var isTabu = q >= tabu[current[prev], current[opt.Index1]] && q >= tabu[current[opt.Index2], current[next]];
     317          var isTabu = !FitnessComparer.IsBetter(maximization, q, tabu[current[prev], current[opt.Index1]])
     318                    && !FitnessComparer.IsBetter(maximization, q, tabu[current[opt.Index2], current[next]]);
    303319          if (!isTabu) allTabu = false;
    304           if (q < currentF && !isTabu) {
    305             if (double.IsNaN(bestOfTheWalkF) || bestOfTheWalkF > q) {
     320          if (!isTabu && FitnessComparer.IsBetter(maximization, q, currentF)) {
     321            if (FitnessComparer.IsBetter(maximization, q, bestOfTheWalkF)) {
    306322              bestOfTheWalk = (Encodings.PermutationEncoding.Permutation)current.Clone();
    307323              bestOfTheWalkF = q;
    308             }
    309 
     324              stepsUntilBestOfWalk = steps;
     325            }
     326
     327            steps++;
    310328            improved = true;
    311329            // perform the move
    312330            currentF = q;
    313331            // mark that to move them to their previous position requires to make an improvement
    314             tabu[current[prev], current[opt.Index2]] = Math.Min(q, tabu[current[prev], current[opt.Index2]]);
    315             tabu[current[opt.Index2], current[prev]] = Math.Min(q, tabu[current[opt.Index2], current[prev]]);
    316             tabu[current[opt.Index1], current[next]] = Math.Min(q, tabu[current[opt.Index1], current[next]]);
    317             tabu[current[next], current[opt.Index1]] = Math.Min(q, tabu[current[next], current[opt.Index1]]);
     332            if (maximization) {
     333              tabu[current[prev], current[opt.Index2]] = Math.Max(q, tabu[current[prev], current[opt.Index2]]);
     334              tabu[current[opt.Index2], current[prev]] = Math.Max(q, tabu[current[opt.Index2], current[prev]]);
     335              tabu[current[opt.Index1], current[next]] = Math.Max(q, tabu[current[opt.Index1], current[next]]);
     336              tabu[current[next], current[opt.Index1]] = Math.Max(q, tabu[current[next], current[opt.Index1]]);
     337            } else {
     338              tabu[current[prev], current[opt.Index2]] = Math.Min(q, tabu[current[prev], current[opt.Index2]]);
     339              tabu[current[opt.Index2], current[prev]] = Math.Min(q, tabu[current[opt.Index2], current[prev]]);
     340              tabu[current[opt.Index1], current[next]] = Math.Min(q, tabu[current[opt.Index1], current[next]]);
     341              tabu[current[next], current[opt.Index1]] = Math.Min(q, tabu[current[next], current[opt.Index1]]);
     342            }
    318343          } else { // undo the move
    319             if (!isTabu && (double.IsNaN(bestOfTheRestF) || q < bestOfTheRestF)) {
     344            if (!isTabu && FitnessComparer.IsBetter(maximization, q, bestOfTheRestF)) {
    320345              bestOfTheRest = opt;
    321346              bestOfTheRestF = q;
    … …  
    324349            InversionManipulator.Apply(current, opt.Index1, opt.Index2);
    325350          }
    326         }
    327         if (!allTabu && !improved) {
     351          if (evaluations >= maxEvals) break;
     352        }
     353        if (!allTabu && !improved && bestOfTheRest != null) {
    328354          var prev = bestOfTheRest.Index1 - 1;
    329355          var next = (bestOfTheRest.Index2 + 1) % current.Length;
    330356          if (prev < 0) prev += current.Length;
    331357
    332           tabu[current[prev], current[bestOfTheRest.Index1]] = Math.Min(currentF, tabu[current[prev], current[bestOfTheRest.Index1]]);
    333           tabu[current[bestOfTheRest.Index1], current[prev]] = Math.Min(currentF, tabu[current[bestOfTheRest.Index1], current[prev]]);
    334           tabu[current[bestOfTheRest.Index2], current[next]] = Math.Min(currentF, tabu[current[bestOfTheRest.Index2], current[next]]);
    335           tabu[current[next], current[bestOfTheRest.Index2]] = Math.Min(currentF, tabu[current[next], current[bestOfTheRest.Index2]]);
    336 
     358          if (maximization) {
     359            tabu[current[prev], current[bestOfTheRest.Index1]] = Math.Max(currentF, tabu[current[prev], current[bestOfTheRest.Index1]]);
     360            tabu[current[bestOfTheRest.Index1], current[prev]] = Math.Max(currentF, tabu[current[bestOfTheRest.Index1], current[prev]]);
     361            tabu[current[bestOfTheRest.Index2], current[next]] = Math.Max(currentF, tabu[current[bestOfTheRest.Index2], current[next]]);
     362            tabu[current[next], current[bestOfTheRest.Index2]] = Math.Max(currentF, tabu[current[next], current[bestOfTheRest.Index2]]);
     363          } else {
     364            tabu[current[prev], current[bestOfTheRest.Index1]] = Math.Min(currentF, tabu[current[prev], current[bestOfTheRest.Index1]]);
     365            tabu[current[bestOfTheRest.Index1], current[prev]] = Math.Min(currentF, tabu[current[bestOfTheRest.Index1], current[prev]]);
     366            tabu[current[bestOfTheRest.Index2], current[next]] = Math.Min(currentF, tabu[current[bestOfTheRest.Index2], current[next]]);
     367            tabu[current[next], current[bestOfTheRest.Index2]] = Math.Min(currentF, tabu[current[next], current[bestOfTheRest.Index2]]);
     368          }
    337369          InversionManipulator.Apply(current, bestOfTheRest.Index1, bestOfTheRest.Index2);
    338370
    339371          currentF = bestOfTheRestF;
     372          steps++;
    340373        } else if (allTabu) break;
     374        if (evaluations >= maxEvals) break;
    341375      }
    342376      Context.IncrementEvaluatedSolutions(evaluations);
    … …  
    345379        for (var i = 0; i < current.Length; i++) perm[i] = bestOfTheWalk[i];
    346380      }
     381      return stepsUntilBestOfWalk;
    347382    }
    348383
    … …  
    478513
    479514    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) {
     515      var maximization = Context.Problem.Maximization;
    480516      var evaluations = 0;
    481517      var child = (Encodings.PermutationEncoding.Permutation)p1.Clone();
    … …  
    502538          var moveF = eval(child, random);
    503539          evaluations++;
    504           if (double.IsNaN(bestChange) || moveF < bestChange) {
     540          if (FitnessComparer.IsBetter(maximization, moveF, bestChange)) {
    505541            bestChange = moveF;
    506542            bestOption = j;
    … …  
    516552          invChild[child[idx2]] = idx2;
    517553          //Log(string.Join(", ", child));
    518           if (double.IsNaN(best) || bestChange < best) {
     554          if (FitnessComparer.IsBetter(maximization, bestChange, best)) {
    519555            if (Dist(child, p2) > 0) {
    520556              best = bestChange;
    … …  
    525561        }
    526562      }
     563      if (bestChild == null) {
     564        best = eval(child, random);
     565        evaluations++;
     566      }
    527567      Context.IncrementEvaluatedSolutions(evaluations);
    528568
    529569      if (VALIDATE && bestChild != null && !bestChild.Validate()) throw new ArgumentException("Relinking produced invalid child");
    530570      if (VALIDATE && Dist(child, p2) > 0) throw new InvalidOperationException("Child is not equal to p2 after relinking");
    531      
    532       if (bestChild == null) best = eval(child, random);
     571
    533572      return bestChild ?? child;
    534573    }
    535574
    536575    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) {
     576      var maximization = Context.Problem.Maximization;
    537577      var evaluations = 0;
    538578      var child = (Encodings.PermutationEncoding.Permutation)p1.Clone();
    … …  
    557597          var moveF = eval(child, random);
    558598          evaluations++;
    559           if (double.IsNaN(bestChange) || moveF < bestChange) {
     599          if (FitnessComparer.IsBetter(maximization, moveF, bestChange)) {
    560600            bestChange = moveF;
    561601            bestFrom = c < n ? n : c;
    … …  
    569609          Shift(child, bestFrom, bestTo);
    570610          for (var i = Math.Min(bestFrom, bestTo); i < Math.Max(bestFrom, bestTo); i++) invChild[child[i]] = i;
    571           if (double.IsNaN(best) || bestChange < best) {
     611          if (FitnessComparer.IsBetter(maximization, bestChange, best)) {
    572612            best = bestChange;
    573613            bestChild = (Encodings.PermutationEncoding.Permutation)child.Clone();
    … …  
    576616      } while (!double.IsNaN(bestChange));
    577617
     618      if (bestChild == null) {
     619        best = eval(child, random);
     620        evaluations++;
     621      }
    578622      Context.IncrementEvaluatedSolutions(evaluations);
    579       if (VALIDATE && !bestChild.Validate()) throw new ArgumentException("Relinking produced invalid child");
     623
     624      if (VALIDATE && bestChild != null && !bestChild.Validate()) throw new ArgumentException("Relinking produced invalid child");
    580625      if (VALIDATE && Dist(child, p2) > 0) throw new InvalidOperationException("Child is not equal to p2 after relinking");
    581       return bestChild;
     626
     627      return bestChild ?? child;
    582628    }
    583629
    584630    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) {
     631      var maximization = Context.Problem.Maximization;
    585632      var evaluations = 0;
    586633      var child = (Encodings.PermutationEncoding.Permutation)p1.Clone();
    … …  
    602649        Queue<Tuple<int, int>> bestQueue = null;
    603650        bestChange = double.NaN;
    604         //Log("{0}", string.Join(" ", child));
    605651        for (var j = 0; j < p2.Length; j++) {
    606652          if (IsUndirectedEdge(invChild, p2[j], p2.GetCircular(j + 1))) continue;
    … …  
    661707          var moveF = eval(child, random);
    662708          evaluations++;
    663           if (double.IsNaN(bestChange) || moveF < bestChange) {
     709          if (FitnessComparer.IsBetter(maximization, moveF, bestChange)) {
    664710            bestChange = moveF;
    665711            bestQueue = new Queue<Tuple<int, int>>(undoStack.Reverse());
    … …  
    677723          }
    678724          for (var i = 0; i < child.Length; i++) invChild[child[i]] = i;
    679           if (double.IsNaN(best) || bestChange < best) {
     725          if (FitnessComparer.IsBetter(maximization, bestChange, best)) {
    680726            best = bestChange;
    681727            bestChild = (Encodings.PermutationEncoding.Permutation)child.Clone();
    … …  
    684730      } while (!double.IsNaN(bestChange));
    685731
     732      if (bestChild == null) {
     733        best = eval(child, random);
     734        evaluations++;
     735      }
    686736      Context.IncrementEvaluatedSolutions(evaluations);
    687737     
    688       if (VALIDATE && !bestChild.Validate()) throw new ArgumentException("Relinking produced invalid child");
     738      if (VALIDATE && bestChild != null && !bestChild.Validate()) throw new ArgumentException("Relinking produced invalid child");
    689739      if (VALIDATE && Dist(child, p2) > 0) throw new InvalidOperationException("Child is not equal to p2 after relinking");
    690       return bestChild;
     740      return bestChild ?? child;
    691741    }
    692742

  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Util/FitnessComparer.cs

    r14450 r14456  
    2323  public static class FitnessComparer {
    2424    public static bool IsBetter(bool maximization, double a, double b) {
    25       return maximization && a > b
    26              || !maximization && a < b;
     25      return double.IsNaN(b) && !double.IsNaN(a)
     26        || maximization && a > b
     27        || !maximization && a < b;
    2728    }
    2829  }
Note: See TracChangeset for help on using the changeset viewer.