Free cookie consent management tool by TermsFeed Policy Generator

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

#2457: working on identification of problem instances

Location:
branches/PerformanceComparison/HeuristicLab.Algorithms.MemPR/3.3
Files:
9 edited

Legend:

Unmodified
Added
Removed

  • branches/PerformanceComparison/HeuristicLab.Algorithms.MemPR/3.3/Interfaces/Interfaces.cs

    r14563 r14690  
    2525using HeuristicLab.Algorithms.MemPR.Grouping;
    2626using HeuristicLab.Algorithms.MemPR.Permutation;
     27using HeuristicLab.Analysis.FitnessLandscape;
    2728using HeuristicLab.Core;
    2829using HeuristicLab.Encodings.BinaryVectorEncoding;
    … …  
    7677  }
    7778
     79  public interface ILocalSearchPathContext<TSolution> : IExecutionContext where TSolution : class, IItem {
     80    DirectedPath<TSolution> LocalSearchPaths { get; }
     81  }
     82
    7883  public interface IEvaluationServiceContext<TSolution> : IExecutionContext {
    7984    double Evaluate(TSolution solution, CancellationToken token);

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

    r14666 r14690  
    220220    protected virtual TPopulationContext CreateContext() {
    221221      return new TPopulationContext();
     222    }
     223
     224    public void StartSync() {
     225      using (var w = new AutoResetEvent(false)) {
     226        EventHandler handler = (sender, e) => {
     227          if (ExecutionState == ExecutionState.Paused
     228          || ExecutionState == ExecutionState.Stopped)
     229            w.Set();
     230        };
     231        ExecutionStateChanged += handler;
     232        try {
     233          Start();
     234          w.WaitOne();
     235        } finally { ExecutionStateChanged -= handler; }
     236      }
    222237    }
    223238

  • branches/PerformanceComparison/HeuristicLab.Algorithms.MemPR/3.3/MemPRContext.cs

    r14678 r14690  
    4040  [StorableClass]
    4141  public abstract class MemPRPopulationContext<TProblem, TSolution, TPopulationContext, TSolutionContext> : ParameterizedNamedItem,
    42     IPopulationBasedHeuristicAlgorithmContext<TProblem, TSolution>, ISolutionModelContext<TSolution>, IEvaluationServiceContext<TSolution>
    43       where TProblem : class, IItem, ISingleObjectiveHeuristicOptimizationProblem
     42    IPopulationBasedHeuristicAlgorithmContext<TProblem, TSolution>, ISolutionModelContext<TSolution>, IEvaluationServiceContext<TSolution>,
     43    ILocalSearchPathContext<TSolution>
     44    where TProblem : class, IItem, ISingleObjectiveHeuristicOptimizationProblem
    4445      where TSolution : class, IItem
    4546      where TPopulationContext : MemPRPopulationContext<TProblem, TSolution, TPopulationContext, TSolutionContext>
    … …  
    169170      get { return relinkedPaths.Value; }
    170171      set { relinkedPaths.Value = value; }
     172    }
     173
     174    [Storable]
     175    private IValueParameter<DirectedPath<TSolution>> localSearchPaths;
     176    public DirectedPath<TSolution> LocalSearchPaths {
     177      get { return localSearchPaths.Value; }
     178      set { localSearchPaths.Value = value; }
    171179    }
    172180
    … …  
    267275      byAdaptivewalking = cloner.Clone(original.byAdaptivewalking);
    268276      relinkedPaths = cloner.Clone(original.relinkedPaths);
     277      localSearchPaths = cloner.Clone(original.localSearchPaths);
    269278      random = cloner.Clone(original.random);
    270279      breedingStat = original.breedingStat.Select(x => Tuple.Create(x.Item1, x.Item2, x.Item3, x.Item4)).ToList();
    … …  
    296305      Parameters.Add(byAdaptivewalking = new ValueParameter<IntValue>("ByAdaptivewalking", new IntValue(0)));
    297306      Parameters.Add(relinkedPaths = new ValueParameter<DirectedPath<TSolution>>("RelinkedPaths", new DirectedPath<TSolution>()));
     307      Parameters.Add(localSearchPaths = new ValueParameter<DirectedPath<TSolution>>("LocalSearchPaths", new DirectedPath<TSolution>()));
    298308      Parameters.Add(random = new ValueParameter<IRandom>("Random", new MersenneTwister()));
    299309

  • 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.