Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
02/20/17 20:41:33 (8 years ago)
Author:
abeham
Message:

#2457: working on identification of problem instances

Location:
branches/PerformanceComparison/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch
Files:
6 edited

Legend:

Unmodified
Added
Removed

  • branches/PerformanceComparison/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/ExhaustiveHillClimb.cs

    r14552 r14690  
    2020#endregion
    2121
     22using System;
     23using System.Collections.Generic;
    2224using System.Threading;
    2325using HeuristicLab.Algorithms.MemPR.Interfaces;
    24 using HeuristicLab.Algorithms.MemPR.Util;
    2526using HeuristicLab.Common;
    2627using HeuristicLab.Core;
    27 using HeuristicLab.Encodings.PermutationEncoding;
    2828using HeuristicLab.Optimization;
    2929using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    … …  
    3434  public class ExhaustiveHillClimb<TContext> : NamedItem, ILocalSearch<TContext>
    3535      where TContext : ISingleSolutionHeuristicAlgorithmContext<ISingleObjectiveHeuristicOptimizationProblem, Encodings.PermutationEncoding.Permutation>,
    36                        IEvaluationServiceContext<Encodings.PermutationEncoding.Permutation> {
     36                       IEvaluationServiceContext<Encodings.PermutationEncoding.Permutation>,
     37                       ILocalSearchPathContext<Encodings.PermutationEncoding.Permutation> {
    3738
    3839    [StorableConstructor]
    … …  
    4950
    5051    public void Optimize(TContext context) {
     52      if (double.IsNaN(context.Solution.Fitness))
     53        context.Evaluate(context.Solution, CancellationToken.None);
    5154      var quality = context.Solution.Fitness;
    5255      try {
    53         var result = Exhaustive.HillClimb(context.Random, context.Solution.Solution, ref quality,
     56        var path = new List<Tuple<Encodings.PermutationEncoding.Permutation, double>>();
     57        path.Add(Tuple.Create((Encodings.PermutationEncoding.Permutation)context.Solution.Solution.Clone(), quality));
     58
     59        var result = Exhaustive.HillClimb(context.Random, context.Solution.Solution, quality,
    5460          context.Maximization, context.Evaluate, CancellationToken.None);
    55         context.IncrementEvaluatedSolutions(result.Item1);
    56         context.Iterations = result.Item2;
     61
     62        Tuple<Encodings.PermutationEncoding.Permutation, double, int> last = null;
     63        foreach (var step in result) {
     64          path.Add(Tuple.Create((Encodings.PermutationEncoding.Permutation)step.Item1.Clone(), step.Item2));
     65          last = step;
     66        }
     67        context.LocalSearchPaths.AddPath(path);
     68        context.IncrementEvaluatedSolutions(last.Item3);
     69        context.Iterations = path.Count - 2;
    5770      } finally {
    5871        context.Solution.Fitness = quality;

  • branches/PerformanceComparison/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/ExhaustiveHillClimbSubspace.cs

    r14556 r14690  
    2020#endregion
    2121
     22using System;
     23using System.Collections.Generic;
    2224using System.Threading;
    2325using HeuristicLab.Algorithms.MemPR.Interfaces;
    24 using HeuristicLab.Algorithms.MemPR.Util;
    2526using HeuristicLab.Common;
    2627using HeuristicLab.Core;
    27 using HeuristicLab.Encodings.PermutationEncoding;
    2828using HeuristicLab.Optimization;
    2929using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    … …  
    3434  public class ExhaustiveHillClimbSubspace<TContext> : NamedItem, ILocalSearch<TContext>
    3535      where TContext : ISingleSolutionHeuristicAlgorithmContext<ISingleObjectiveHeuristicOptimizationProblem, Encodings.PermutationEncoding.Permutation>,
    36                        IPermutationSubspaceContext, IEvaluationServiceContext<Encodings.PermutationEncoding.Permutation> {
     36                       IPermutationSubspaceContext, IEvaluationServiceContext<Encodings.PermutationEncoding.Permutation>,
     37                       ILocalSearchPathContext<Encodings.PermutationEncoding.Permutation> {
    3738
    3839    [StorableConstructor]
    … …  
    4950
    5051    public void Optimize(TContext context) {
     52      if (double.IsNaN(context.Solution.Fitness))
     53        context.Evaluate(context.Solution, CancellationToken.None);
    5154      var quality = context.Solution.Fitness;
    5255      try {
    53         var result = Exhaustive.HillClimb(context.Random, context.Solution.Solution, ref quality,
     56        var path = new List<Tuple<Encodings.PermutationEncoding.Permutation, double>>();
     57        path.Add(Tuple.Create((Encodings.PermutationEncoding.Permutation)context.Solution.Solution.Clone(), quality));
     58
     59        var result = Exhaustive.HillClimb(context.Random, context.Solution.Solution, quality,
    5460          context.Maximization, context.Evaluate, CancellationToken.None, context.Subspace.Subspace);
    55         context.IncrementEvaluatedSolutions(result.Item1);
    56         context.Iterations = result.Item2;
     61
     62        Tuple<Encodings.PermutationEncoding.Permutation, double, int> last = null;
     63        foreach (var step in result) {
     64          path.Add(Tuple.Create((Encodings.PermutationEncoding.Permutation)step.Item1.Clone(), step.Item2));
     65          last = step;
     66        }
     67        context.LocalSearchPaths.AddPath(path);
     68        context.IncrementEvaluatedSolutions(last.Item3);
     69        context.Iterations = path.Count - 2;
    5770      } finally {
    5871        context.Solution.Fitness = quality;

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

    r14552 r14690  
    2121
    2222using System;
     23using System.Collections.Generic;
    2324using System.Threading;
    2425using HeuristicLab.Core;
    … …  
    3334#endif
    3435
    35     public static Tuple<int, int> HillClimb(IRandom random, Encodings.PermutationEncoding.Permutation perm,
    36       ref double quality, bool maximization, Func<Encodings.PermutationEncoding.Permutation, CancellationToken, double> eval,
     36    public static IEnumerable<Tuple<Encodings.PermutationEncoding.Permutation, double, int>> HillClimb(IRandom random, Encodings.PermutationEncoding.Permutation perm,
     37      double quality, bool maximization, Func<Encodings.PermutationEncoding.Permutation, CancellationToken, double> eval,
    3738      CancellationToken token, bool[,] subspace = null) {
    3839      if (double.IsNaN(quality)) quality = eval(perm, token);
    39       Tuple<int, int> changes;
     40      IEnumerable<Tuple<Encodings.PermutationEncoding.Permutation, double, int>> localSearchPath;
    4041      switch (perm.PermutationType) {
    4142        case PermutationTypes.Absolute:
    42           changes = ExhaustiveSwap2.HillClimb(random, perm, ref quality, maximization, eval, token, subspace);
     43          localSearchPath = ExhaustiveSwap2.HillClimb(random, perm, quality, maximization, eval, token, subspace);
    4344          break;
    4445        case PermutationTypes.RelativeDirected:
    45           changes = Exhaustive1Shift.HillClimb(random, perm, ref quality, maximization, eval, token, subspace);
     46          localSearchPath = Exhaustive1Shift.HillClimb(random, perm, quality, maximization, eval, token, subspace);
    4647          break;
    4748        case PermutationTypes.RelativeUndirected:
    48           changes = Exhaustive2Opt.HillClimb(random, perm, ref quality, maximization, eval, token, subspace);
     49          localSearchPath = Exhaustive2Opt.HillClimb(random, perm, quality, maximization, eval, token, subspace);
    4950          break;
    5051        default: throw new ArgumentException(string.Format("Permutation type {0} is not known", perm.PermutationType));
    5152      }
    5253      if (VALIDATE && !perm.Validate()) throw new ArgumentException("HillClimb produced invalid child");
    53       return changes;
     54      return localSearchPath;
    5455    }
    5556  }

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

    r14552 r14690  
    2121
    2222using System;
     23using System.Collections.Generic;
    2324using System.Linq;
    2425using System.Threading;
    … …  
    3031namespace HeuristicLab.Algorithms.MemPR.Permutation.LocalSearch {
    3132  public static class Exhaustive1Shift {
    32     public static Tuple<int, int> HillClimb(IRandom random, Encodings.PermutationEncoding.Permutation perm,
    33       ref double quality, bool maximization, Func<Encodings.PermutationEncoding.Permutation, CancellationToken, double> eval,
     33    public static IEnumerable<Tuple<Encodings.PermutationEncoding.Permutation, double, int>>
     34      HillClimb(IRandom random, Encodings.PermutationEncoding.Permutation perm,
     35      double quality, bool maximization, Func<Encodings.PermutationEncoding.Permutation, CancellationToken, double> eval,
    3436      CancellationToken token, bool[,] subspace = null) {
    3537      var evaluations = 0;
    … …  
    4042      }
    4143      TranslocationMove lastSuccessMove = null;
    42       var steps = 0;
    4344      var neighborhood = ExhaustiveInsertionMoveGenerator.Generate(current).Shuffle(random).ToList();
    4445      while (true) {
    … …  
    6263          evaluations++;
    6364          if (FitnessComparer.IsBetter(maximization, q, quality)) {
    64             steps++;
     65            yield return Tuple.Create(current, q, evaluations);
    6566            quality = q;
    6667            lastSuccessMove = shift;
    … …  
    7475        if (lastSuccessMove == null) break;
    7576      }
    76       return Tuple.Create(evaluations, steps);
     77      yield return Tuple.Create(current, quality, evaluations);
    7778    }
    7879  }

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

    r14556 r14690  
    2121
    2222using System;
     23using System.Collections.Generic;
    2324using System.Linq;
    2425using System.Threading;
    … …  
    3031namespace HeuristicLab.Algorithms.MemPR.Permutation.LocalSearch {
    3132  public static class Exhaustive2Opt {
    32     public static Tuple<int, int> HillClimb(IRandom random, Encodings.PermutationEncoding.Permutation perm,
    33       ref double quality, bool maximization, Func<Encodings.PermutationEncoding.Permutation, CancellationToken, double> eval,
     33    public static IEnumerable<Tuple<Encodings.PermutationEncoding.Permutation, double, int>>
     34      HillClimb(IRandom random, Encodings.PermutationEncoding.Permutation perm,
     35      double quality, bool maximization, Func<Encodings.PermutationEncoding.Permutation, CancellationToken, double> eval,
    3436      CancellationToken token, bool[,] subspace = null) {
    3537      var evaluations = 0;
    … …  
    4042      }
    4143      InversionMove lastSuccessMove = null;
    42       var steps = 0;
    4344      var neighborhood = ExhaustiveInversionMoveGenerator.Generate(current).Shuffle(random).ToList();
    4445      while (true) {
    … …  
    5960          evaluations++;
    6061          if (FitnessComparer.IsBetter(maximization, q, quality)) {
    61             steps++;
     62            yield return Tuple.Create(current, q, evaluations);
    6263            quality = q;
    6364            lastSuccessMove = opt;
    … …  
    7172        if (lastSuccessMove == null) break;
    7273      }
    73       return Tuple.Create(evaluations, steps);
     74      yield return Tuple.Create(current, quality, evaluations);
    7475    }
    7576  }

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

    r14552 r14690  
    2121
    2222using System;
     23using System.Collections.Generic;
    2324using System.Linq;
    2425using System.Threading;
    … …  
    3031namespace HeuristicLab.Algorithms.MemPR.Permutation.LocalSearch {
    3132  public static class ExhaustiveSwap2 {
    32     public static Tuple<int, int> HillClimb(IRandom random, Encodings.PermutationEncoding.Permutation perm,
    33       ref double quality, bool maximization, Func<Encodings.PermutationEncoding.Permutation, CancellationToken, double> eval,
     33    public static IEnumerable<Tuple<Encodings.PermutationEncoding.Permutation, double, int>>
     34      HillClimb(IRandom random, Encodings.PermutationEncoding.Permutation perm,
     35      double quality, bool maximization, Func<Encodings.PermutationEncoding.Permutation, CancellationToken, double> eval,
    3436      CancellationToken token, bool[,] subspace = null) {
    3537      var evaluations = 0;
    … …  
    4042      }
    4143      Swap2Move lastSuccessMove = null;
    42       var steps = 0;
    4344      var neighborhood = ExhaustiveSwap2MoveGenerator.Generate(current).Shuffle(random).ToList();
    4445      while (true) {
    … …  
    5859          evaluations++;
    5960          if (FitnessComparer.IsBetter(maximization, q, quality)) {
    60             steps++;
     61            yield return Tuple.Create(current, q, evaluations);
    6162            quality = q;
    6263            lastSuccessMove = swap;
    … …  
    7374        if (lastSuccessMove == null) break;
    7475      }
    75       return Tuple.Create(evaluations, steps);
     76      yield return Tuple.Create(current, quality, evaluations);
    7677    }
    7778  }
Note: See TracChangeset for help on using the changeset viewer.