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
Files:
1 added
14 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  }

  • branches/PerformanceComparison/HeuristicLab.Analysis.FitnessLandscape/3.3/CharacteristicCalculator/RandomWalkCalculator.cs

    r13920 r14690  
    5858      characteristics = cloner.Clone(original.characteristics);
    5959    }
    60     public RandomWalkCalculator() {
     60    public RandomWalkCalculator() : this(new RandomWalk()) { }
     61    public RandomWalkCalculator(RandomWalk walker) {
    6162      Name = ItemName;
    6263      Description = ItemDescription;
    63       walker = new RandomWalk();
     64      this.walker = walker;
    6465      characteristics = new CheckedItemList<StringValue>(
    6566        new[] { "AutoCorrelation1", "CorrelationLength", "InformationContent",
    66         "PartialInformationContent", "DensityBasinInformation", "InformationStability", 
     67        "PartialInformationContent", "DensityBasinInformation", "InformationStability",
    6768        "Diversity", "Regularity", "TotalEntropy", "PeakInformationContent",
    6869        "PeakDensityBasinInformation" }.Select(x => new StringValue(x)));
    … …  
    9192        };
    9293        walker.ExecutionStateChanged += evHandle;
    93         walker.Start();
    94         waitHandle.WaitOne();
    95         walker.ExecutionStateChanged -= evHandle;
     94        try {
     95          walker.Start();
     96          waitHandle.WaitOne();
     97        } finally { walker.ExecutionStateChanged -= evHandle; }
    9698      }
    9799      foreach (var p in characteristics.CheckedItems) {
    98         yield return new Result("RandomWalk." + walker.MutatorParameter.Value.Name + "." + p.Value.Value, walker.Results[p.Value.Value].Value);
     100        var resultName = "RandomWalk." + walker.MutatorParameter.Value.Name + "." + p.Value.Value;
     101        IResult result;
     102        if (walker.Results.TryGetValue(p.Value.Value, out result)) {
     103          yield return new Result(resultName, result.Value);
     104        } else yield return new Result(resultName, new DoubleValue(0));
    99105      }
    100106      walker.Prepare(true);

  • branches/PerformanceComparison/HeuristicLab.Analysis.FitnessLandscape/3.3/ProblemCharacteristicAnalysis/QAP/QAPDirectedWalk.cs

    r14678 r14690  
    3232using System.Collections.Generic;
    3333using System.Linq;
     34using System.Threading;
    3435
    3536namespace HeuristicLab.Analysis.FitnessLandscape {
    … …  
    5051    }
    5152
     53    public IFixedValueParameter<BoolValue> LocalOptimaParameter {
     54      get { return (IFixedValueParameter<BoolValue>)Parameters["LocalOptima"]; }
     55    }
     56
    5257    public int Paths {
    5358      get { return PathsParameter.Value.Value; }
    … …  
    6368      get { return SeedParameter.Value != null ? SeedParameter.Value.Value : (int?)null; }
    6469      set { SeedParameter.Value = value.HasValue ? new IntValue(value.Value) : null; }
     70    }
     71
     72    public bool LocalOptima {
     73      get { return LocalOptimaParameter.Value.Value; }
     74      set { LocalOptimaParameter.Value.Value = value; }
    6575    }
    6676
    … …  
    7484      Parameters.Add(new FixedValueParameter<BoolValue>("BestImprovement", "Whether the best of all alternatives should be chosen for each step in the path or just the first improving (least degrading) move should be made.", new BoolValue(true)));
    7585      Parameters.Add(new OptionalValueParameter<IntValue>("Seed", "The seed for the random number generator."));
     86      Parameters.Add(new FixedValueParameter<BoolValue>("LocalOptima", "Whether to perform walks between local optima.", new BoolValue(false)));
    7687    }
    7788
    … …  
    90101
    91102      var perm = new Permutation(PermutationTypes.Absolute, qap.Weights.Rows, random);
     103      if (LocalOptima) {
     104        var fit = new DoubleValue(QAPEvaluator.Apply(perm, qap.Weights, qap.Distances));
     105        QAPExhaustiveSwap2LocalImprovement.ImproveFast(perm, qap.Weights, qap.Distances, fit, new IntValue(0), new IntValue(0), qap.Maximization.Value, int.MaxValue, CancellationToken.None);
     106      }
    92107      var permutations = new List<Permutation> { perm };
    93108      while (permutations.Count < pathCount + 1) {
    94109        perm = (Permutation)permutations.Last().Clone();
    95110        BiasedShuffle(perm, random);
    96         permutations.Add(perm);
     111        if (LocalOptima) {
     112          var fit = new DoubleValue(QAPEvaluator.Apply(perm, qap.Weights, qap.Distances));
     113          QAPExhaustiveSwap2LocalImprovement.ImproveFast(perm, qap.Weights, qap.Distances, fit, new IntValue(0), new IntValue(0), qap.Maximization.Value, int.MaxValue, CancellationToken.None);
     114        }
     115        if (HammingSimilarityCalculator.CalculateSimilarity(permutations.Last(), perm) < 0.75)
     116          permutations.Add(perm);
    97117      }
    98118
    … …  
    151171
    152172      for (var p = 0; p < f2.Count; p++) {
     173        if (f2[p].Count <= 2) continue;
    153174        var bump = 0;
    154175        var flat = 0;
    … …  
    266287    }
    267288
     289    // Center-of-Mass
    268290    private static double ComBelowZero(IEnumerable<Tuple<Permutation, double>> path) {
    269291      var area = 0.0;

  • branches/PerformanceComparison/ProblemInstanceIdentifier/InstanceDescriptor.cs

    r14678 r14690  
    1 using System.Linq;
     1using System;
     2using System.Collections.Generic;
     3using System.Linq;
    24using HeuristicLab.Analysis.FitnessLandscape;
     5using HeuristicLab.Common;
    36using HeuristicLab.Data;
     7using HeuristicLab.Encodings.PermutationEncoding;
    48using HeuristicLab.Problems.QuadraticAssignment;
    59
    … …  
    913    public string Cls { get; private set; }
    1014    public int Dimension { get; set; }
    11     public double Sharpness { get; set; }
    12     public double SharpnessSdev { get; set; }
    13     public double Bumpiness { get; set; }
    14     public double BumpinessSdev { get; set; }
    15     public double Flatness { get; set; }
    16     public double FlatnessSdev { get; set; }
    17     public double Steadiness { get; set; }
    18     public double SteadinessSdev { get; set; }
     15
     16    public string[] FeatureNames { get; set; }
     17    public double[] FeatureValues { get; set; }
    1918   
    2019    private InstanceDescriptor() { }
    2120
    22     public static InstanceDescriptor FromPathRelinkingAnalysis(QuadraticAssignmentProblem qap, int paths, int? seed) {
    23       var walk = new QAPDirectedWalk {
    24         Problem = qap,
    25         BestImprovement = true,
    26         Paths = paths,
    27         Seed = seed
     21    public InstanceDescriptor(string name, string cls, int dimension, string[] names, double[] values) {
     22      Name = name;
     23      Cls = cls;
     24      Dimension = dimension;
     25      FeatureNames = names;
     26      FeatureValues = values;
     27    }
     28
     29    public InstanceDescriptor(InstanceDescriptor other) {
     30      Name = other.Name;
     31      Cls = other.Cls;
     32      Dimension = other.Dimension;
     33      FeatureNames = (string[])other.FeatureNames.Clone();
     34      FeatureValues = (double[]) other.FeatureValues.Clone();
     35    }
     36
     37    public static InstanceDescriptor FromProblemOnly(QuadraticAssignmentProblem qap) {
     38      return new InstanceDescriptor() {
     39        Name = qap.Name,
     40        Cls = GetClass(qap.Name),
     41        Dimension = qap.Weights.Rows,
     42        FeatureNames = new string[0],
     43        FeatureValues = new double[0]
    2844      };
    29       var features = walk.Calculate().ToDictionary(x => x.Name, x => x.Value);
     45    }
     46
     47    public static InstanceDescriptor FromPaths(QuadraticAssignmentProblem qap, List<List<Tuple<Permutation, double>>> trajectories) {
     48      var features = QAPDirectedWalk.Calculate(trajectories).ToDictionary(x => x.Name, x => x.Value);
    3049     
    3150      return new InstanceDescriptor() {
    … …  
    3352        Cls = GetClass(qap.Name),
    3453        Dimension = qap.Weights.Rows,
    35         Sharpness = ((DoubleValue)features["Swap2.Sharpness"]).Value,
    36         Bumpiness = ((DoubleValue)features["Swap2.Bumpiness"]).Value,
    37         Flatness = ((DoubleValue)features["Swap2.Flatness"]).Value,
    38         Steadiness = ((DoubleValue)features["Swap2.Steadiness"]).Value,
     54        FeatureNames = features.Keys.ToArray(),
     55        FeatureValues = features.Values.Select(x => ((DoubleValue)x).Value).ToArray()
    3956      };
    4057    }
    4158
    42     private static string GetClass(string name) {
     59    public static string GetClass(string name) {
    4360      var cls = name.Substring(0, 3);
    4461      var subCls = name.Last();
    … …  
    5875
    5976    public double CalculateSimilarity(InstanceDescriptor other) {
    60       var sa = (Sharpness - other.Sharpness);
    61       var bu = (Bumpiness - other.Bumpiness);
    62       var fl = (Flatness - other.Flatness);
    63       var se = (Steadiness - other.Steadiness);
    64       return sa * sa + bu * bu + fl * fl + se * se;
     77      return FeatureValues.Select((v, i) => (v - other.FeatureValues[i]) * (v - other.FeatureValues[i])).Sum();
    6578    }
    6679
    … …  
    6982    }
    7083  }
     84
     85  public class InstancesStandardizer {
     86    private double[] featureMeans;
     87    private double[] featureStdevs;
     88
     89    private InstancesStandardizer() { }
     90
     91    public static InstancesStandardizer Create(IList<InstanceDescriptor> instances) {
     92      var standardizer = new InstancesStandardizer();
     93      var featureLength = instances.First().FeatureValues.Length;
     94      standardizer.featureMeans =
     95        Enumerable.Range(0, featureLength)
     96        .Select(x => instances.Select(y => y.FeatureValues[x]).Average()).ToArray();
     97      standardizer.featureStdevs =
     98        Enumerable.Range(0, featureLength)
     99        .Select(x => instances.Select(y => y.FeatureValues[x]).StandardDeviation()).ToArray();
     100
     101      return standardizer;
     102    }
     103
     104    public void Apply(IList<InstanceDescriptor> instances) {
     105      for (var i = 0; i < instances.Count; i++) {
     106        var inst = instances[i];
     107        for (var x = 0; x < featureMeans.Length; x++)
     108          inst.FeatureValues[x] = (inst.FeatureValues[x] - featureMeans[x]) / featureStdevs[x];
     109      }
     110    }
     111  }
    71112}

  • branches/PerformanceComparison/ProblemInstanceIdentifier/ProblemInstanceIdentifier.csproj

    r14678 r14690  
    2323    <ErrorReport>prompt</ErrorReport>
    2424    <WarningLevel>4</WarningLevel>
     25    <Prefer32Bit>false</Prefer32Bit>
    2526  </PropertyGroup>
    2627  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' ">
    … …  
    3233    <ErrorReport>prompt</ErrorReport>
    3334    <WarningLevel>4</WarningLevel>
     35    <Prefer32Bit>false</Prefer32Bit>
    3436  </PropertyGroup>
    3537  <ItemGroup>
    … …  
    6769      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Random-3.3.dll</HintPath>
    6870    </Reference>
     71    <Reference Include="HeuristicLab.Selection-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     72      <SpecificVersion>False</SpecificVersion>
     73      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Selection-3.3.dll</HintPath>
     74    </Reference>
     75    <Reference Include="HeuristicLab.SequentialEngine-3.3">
     76      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.SequentialEngine-3.3.dll</HintPath>
     77    </Reference>
    6978    <Reference Include="System" />
    7079    <Reference Include="System.Core" />
    … …  
    7887  <ItemGroup>
    7988    <Compile Include="InstanceDescriptor.cs" />
     89    <Compile Include="InstanceExplorer.cs" />
    8090    <Compile Include="Program.cs" />
    8191    <Compile Include="Properties\AssemblyInfo.cs" />
    … …  
    8595  </ItemGroup>
    8696  <ItemGroup>
     97    <ProjectReference Include="..\HeuristicLab.Algorithms.MemPR\3.3\HeuristicLab.Algorithms.MemPR-3.3.csproj">
     98      <Project>{9d274421-6332-4fbc-aae4-467ace27c368}</Project>
     99      <Name>HeuristicLab.Algorithms.MemPR-3.3</Name>
     100    </ProjectReference>
    87101    <ProjectReference Include="..\HeuristicLab.Analysis.FitnessLandscape\3.3\HeuristicLab.Analysis.FitnessLandscape-3.3.csproj">
    88102      <Project>{5fbdcd4a-3c2a-4ec6-83ce-34b29f43621a}</Project>

  • branches/PerformanceComparison/ProblemInstanceIdentifier/Program.cs

    r14678 r14690  
    11using System;
    22using System.Collections.Generic;
     3using System.Globalization;
    34using System.Linq;
    45using System.Threading.Tasks;
     6using HeuristicLab.Algorithms.MemPR.Permutation;
    57using HeuristicLab.PluginInfrastructure;
    68using HeuristicLab.Problems.Instances;
    … …  
    1012namespace ProblemInstanceIdentifier {
    1113  class Program {
     14    private static HashSet<string> selectedInstances = new HashSet<string>() {
     15      "bur26a", "chr25a", "dre24", "els19", "esc32a", "had20", "kra32", "lipa30a", "lipa30b",
     16      "nug30", "rou20", "scr20", "sko42", "ste36a", "tai25a", "tai25b", "tho30", "wil50",
     17      "RAND-S-6x6-36-25-AFFY-00_rand_rand_bl", "RAND-S-6x6-36-25-AFFY-00_rand_rand_ci"
     18    };
    1219    static void Main(string[] args) {
    1320      var sync = new object();
    … …  
    1825        if (provider is TaillardQAPInstanceProvider) continue;
    1926        Parallel.ForEach(provider.GetDataDescriptors(), desc => {
    20           if (desc.Name == "esc16f") return;
     27          if (!selectedInstances.Contains(desc.Name)) return;
     28          //if (desc.Name == "esc16f") return;
    2129          var qapData = provider.LoadData(desc);
    22           if (qapData.Dimension < 15 || qapData.Dimension > 150) return;
     30          //if (qapData.Dimension < 15 || qapData.Dimension > 150) return;
    2331          var qap = new QuadraticAssignmentProblem();
    2432          qap.Load(qapData);
    … …  
    2937      }
    3038
    31       Console.WriteLine("{0}\t{1}\t{2}\t{3}\t{4}\t{5}\t{6:F2}\t{7:F2}", "Repetition", "KB-Paths", "Exp-Paths", "Cls-Hits", "Exact-Hits", "No-Hits", "Cls-Rank", "Exact-Rank");
    32       var paths = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, 40, 50 };
    33       for (var r = 0; r < 20; r++) {
    34         Parallel.ForEach(paths, kbPaths => {
    35           foreach (var expPaths in paths) {
    36             if (expPaths > kbPaths) continue;
     39      /*var classes = instances.Select(InstanceDescriptor.FromProblemOnly).GroupBy(x => x.Cls);
     40      foreach (var cls in classes.OrderBy(x => x.Key)) {
     41        Console.WriteLine("{0};{1}", cls.Key, cls.Count());
     42      }*/
     43
     44      //var kb = GenerateKnowledgeBase(instances, 200, localOptima: false);
     45
     46
     47      //var paths = new[] { 1, 2, 3, 5, 10, 20, 30, 50, 100, 200 };
     48      //var kbExplorers = paths.Select(x => new PathRelinkingExplorer() { Paths = x }).ToArray();
     49      //var expExplorers = paths.Select(x => new PathRelinkingExplorer() { Paths = x }).ToArray();
     50      //ExploreSelfIdentification(instances, kbExplorers, expExplorers);
     51
     52      var iterations = new[] { 100, 1000, 10000, 100000 };
     53      var kbExplorers = iterations.Select(x => new RandomWalkExplorer() { Iterations = x }).ToArray();
     54      var expExplorers = iterations.Select(x => new RandomWalkExplorer() { Iterations = x }).ToArray();
     55      ExploreSelfIdentification(instances, kbExplorers, expExplorers);
     56
     57      //ExploreMemPrIdentification(instances);
     58    }
     59
     60    private static List<InstanceDescriptor> GenerateKnowledgeBase(List<QuadraticAssignmentProblem> instances, InstanceExplorer explorer) {
     61      var headerPrinted = false;
     62      var sync = new object();
     63      var kb = new List<InstanceDescriptor>();
     64      Parallel.ForEach(instances.OrderBy(x => x.Weights.Rows), qap => {
     65        var instance = explorer.Explore(qap);
     66        lock (sync) {
     67          if (!headerPrinted) {
     68            headerPrinted = true;
     69            Console.WriteLine(string.Join(";",
     70              new [] { "Name", "Cls", "Dimension" }
     71              .Concat(instance.FeatureNames)));
     72          }
     73          PrintInstanceLine(instance);
     74          kb.Add(instance);
     75        }
     76      });
     77      var standardizer = InstancesStandardizer.Create(kb);
     78      var normalizedKb = kb.Select(x => new InstanceDescriptor(x)).ToList();
     79      standardizer.Apply(normalizedKb);
     80      Console.WriteLine();
     81      foreach (var instance in kb) {
     82        PrintInstanceLine(instance);
     83      }
     84      //return normalizedKb;
     85      return kb;
     86    }
     87
     88    private static void PrintInstanceLine(InstanceDescriptor instance) {
     89      Console.WriteLine(string.Join(";",
     90        new[] {instance.Name, instance.Cls, instance.Dimension.ToString(CultureInfo.CurrentCulture)}
     91          .Concat(instance.FeatureValues.Select(x => x.ToString(CultureInfo.CurrentCulture)))));
     92    }
     93
     94    private static void ExploreSelfIdentification(List<QuadraticAssignmentProblem> instances, InstanceExplorer[] kbExplorer, InstanceExplorer[] expExporer) {
     95      var sync = new object();
     96      Console.WriteLine("{0}\t{1}\t{2}\t{3}\t{4}\t{5}", "Repetition", "KB-Effort", "Exp-Effort",
     97        "Exact-Hits", "No-Hits", "Exact-Rank");
     98      var kbSeeds = Enumerable.Range(0, 20).ToList();
     99      var expSeeds = Enumerable.Range(20, 20).ToList();
     100      for (var r = 0; r < 10; r++) {
     101        var rlokal = r;
     102        Parallel.ForEach(kbExplorer, kbPaths => {
     103        //foreach (var kbPaths in kbExplorer) {
     104          foreach (var expPaths in expExporer) {
     105            //if (expPaths > kbPaths) continue;
    37106            var kb = new List<InstanceDescriptor>();
    38107            var exp = new List<InstanceDescriptor>();
    39108            foreach (var qap in instances) {
    40               kb.Add(InstanceDescriptor.FromPathRelinkingAnalysis(qap, kbPaths, null));
    41               exp.Add(InstanceDescriptor.FromPathRelinkingAnalysis(qap, expPaths, null));
     109              kb.Add(kbPaths.Explore(qap, kbSeeds[rlokal]));
     110              exp.Add(expPaths.Explore(qap, expSeeds[rlokal]));
    42111            }
     112            var standardizer = InstancesStandardizer.Create(kb);
     113            standardizer.Apply(kb);
     114            standardizer.Apply(exp);
     115            int exactCount = 0, clsCount = 0, missedCount = 0;
     116            int exactRank = 0, clsRank = 0;
     117            foreach (var e in exp) {
     118              var ordered = kb.OrderBy(x => x.CalculateSimilarity(e)).ToList();
     119              var bestMatch = ordered.First();
     120              if (bestMatch.Cls == e.Cls) {
     121                clsCount++;
     122                if (bestMatch.Name == e.Name) exactCount++;
     123              }
     124              else missedCount++;
     125              clsRank += ordered.FindIndex((id) => id.Cls == e.Cls) + 1;
     126              exactRank += ordered.FindIndex((id) => id.Name == e.Name) + 1;
     127            }
     128            lock (sync) {
     129              Console.WriteLine("{0}\t{1}\t{2}\t{3}\t{4}\t{5:F2}", rlokal, kbPaths.Effort, expPaths.Effort, exactCount,
     130                missedCount, exactRank / (double) exp.Count);
     131            }
     132          }
     133        });
     134        //}
     135      }
     136    }
     137   
     138    private static void ExploreMemPrIdentification(List<QuadraticAssignmentProblem> instances) {
     139      var sync = new object();
     140      Console.WriteLine("{0}\t{1}\t{2}\t{3}\t{4}\t{5}", "Repetition", "KB-Runtime", "Exp-Runtime",
     141        "Exact-Hits", "No-Hits", "Average-Rank");
     142      var paths = new[] { 10 };
     143      var repetitions = 10;
     144      var kbSeeds = Enumerable.Range(0, repetitions).ToList();
     145      var expSeeds = Enumerable.Range(repetitions, repetitions).ToList();
     146      for (var r = 0; r < repetitions; r++) {
     147        var rlokal = r;
     148        Parallel.ForEach(paths, kbPaths => {
     149          var memPr = new PermutationMemPR();
     150          foreach (var expPaths in paths) {
     151            //if (expPaths > kbPaths) continue;
     152            var kb = new List<InstanceDescriptor>();
     153            var exp = new List<InstanceDescriptor>();
     154            foreach (var qap in instances.Select(x => (QuadraticAssignmentProblem)x.Clone())) {
     155              memPr.Problem = qap;
     156              memPr.Prepare(true);
     157              memPr.Seed = kbSeeds[rlokal];
     158              memPr.MaximumExecutionTime = TimeSpan.FromSeconds(kbPaths);
     159              memPr.StartSync();
     160              if (memPr.Context.RelinkedPaths.IsEmpty) continue;
     161              kb.Add(InstanceDescriptor.FromPaths(qap, memPr.Context.RelinkedPaths.Paths.ToList()));
     162              memPr.Prepare(true);
     163              memPr.Seed = expSeeds[rlokal];
     164              memPr.MaximumExecutionTime = TimeSpan.FromSeconds(expPaths);
     165              memPr.StartSync();
     166              if (memPr.Context.RelinkedPaths.IsEmpty) continue;
     167              exp.Add(InstanceDescriptor.FromPaths(qap, memPr.Context.RelinkedPaths.Paths.ToList()));
     168            }
     169            var standardizer = InstancesStandardizer.Create(kb);
     170            standardizer.Apply(kb);
     171            standardizer.Apply(exp);
    43172            int exactCount = 0, clsCount = 0, missedCount = 0;
    44173            int exactRank = 0, clsRank = 0;
    … …  
    54183            }
    55184            lock (sync) {
    56               Console.WriteLine("{0}\t{1}\t{2}\t{3}\t{4}\t{5}\t{6:F2}\t{7:F2}", r, kbPaths, expPaths, clsCount, exactCount, missedCount, clsRank / (double)exp.Count, exactRank / (double)exp.Count);
     185              Console.WriteLine("{0}\t{1}\t{2}\t{3}\t{4}\t{5:F2}", rlokal, kbPaths, expPaths, exactCount,
     186                missedCount, exactRank / (double)exp.Count);
    57187            }
    58188          }
Note: See TracChangeset for help on using the changeset viewer.